c++數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)鏈表排序

-.z.1．實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康?通過(guò)編程，學(xué)習(xí)、實(shí)現(xiàn)、比照各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。理解算法的主要思想及流程。實(shí)驗(yàn)內(nèi)容：使用鏈表實(shí)現(xiàn)下面各種排序算法，并進(jìn)展比擬。排序算法：1、插入排序2、冒泡排序〔改良型冒泡排序〕3、快速排序4、簡(jiǎn)單項(xiàng)選擇擇排序5、堆排序〔小根堆〕要求： 1、測(cè)試數(shù)據(jù)分成三類(lèi)：正序、逆序、隨機(jī)數(shù)據(jù)2、對(duì)于這三類(lèi)數(shù)據(jù)，比擬上述排序算法中關(guān)鍵字的比擬次數(shù)和移動(dòng)次數(shù)〔其中關(guān)鍵字交換計(jì)為3次移動(dòng)〕。3、對(duì)于這三類(lèi)數(shù)據(jù)，比擬上述排序算法中不同算法的執(zhí)行時(shí)間，準(zhǔn)確到微秒〔選作〕4、對(duì)2和3的結(jié)果進(jìn)展分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度編寫(xiě)測(cè)試main()函數(shù)測(cè)試線性表的正確性代碼要求：1、必須要有異常處理，比方刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識(shí)符名稱(chēng)應(yīng)該與其代表的意義一致函數(shù)名之前應(yīng)該添加注釋說(shuō)明該函數(shù)的功能關(guān)鍵代碼應(yīng)說(shuō)明其功能3、遞歸程序注意調(diào)用的過(guò)程，防止棧溢出2.程序分析通過(guò)排序算法將單鏈表中的數(shù)據(jù)進(jìn)展由小至大〔正向排序〕2.1存儲(chǔ)構(gòu)造……單鏈表存儲(chǔ)數(shù)據(jù)：……structnode{intdata;node*ne*t;};單鏈表定義如下：classLinkList{private:node*front;public: LinkList(inta[],intn); //構(gòu)造 ~LinkList();voidinsert(node*p,node*s); //插入voidturn(node*p,node*s); //交換數(shù)據(jù)voidprint(); //輸出voidInsertSort(); //插入排序voidBubbleSort(); //pos冒泡voidQSort(); //快速排序voidSelectSort(); //簡(jiǎn)單項(xiàng)選擇擇排序node*Get(inti);//查找位置為i的結(jié)點(diǎn)voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的遞歸主體voidheapsort(intn);//堆排序算法};關(guān)鍵算法分析：1.直接插入排序：首先將待排序數(shù)據(jù)建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表。將單鏈表劃分為有序區(qū)和無(wú)序區(qū)，有序區(qū)只包含一個(gè)元素節(jié)點(diǎn)，依次取無(wú)序區(qū)中的每一個(gè)結(jié)點(diǎn)，在有序區(qū)中查找待插入結(jié)點(diǎn)的插入位置，然后把該結(jié)點(diǎn)從單鏈表中刪除，再插入到相應(yīng)位置。分析上述排序過(guò)程，需設(shè)一個(gè)工作指針p->ne*t在無(wú)序區(qū)中指向待插入的結(jié)點(diǎn)，在找到插入位置后，將結(jié)點(diǎn)p->ne*t插在結(jié)點(diǎn)s和p之間。voidLinkList::InsertSort() //將第一個(gè)元素定為初始有序區(qū)元素，由第二個(gè)元素開(kāi)場(chǎng)依次比擬{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*p=front->ne*t; //要插入的節(jié)點(diǎn)的前驅(qū)while(p->ne*t) {node*s=front;//充分利用帶頭結(jié)點(diǎn)的單鏈表while(1) { paref++;if(p->ne*t->data<s->ne*t->data) //[P后繼]比[S后繼]小則插入 { insert(p,s);break; } s=s->ne*t;if(s==p) //假設(shè)一趟比擬完畢，且不需要插入 { p=p->ne*t;break; } } } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}2.快速排序：主要通過(guò)軸值將數(shù)據(jù)從兩端向中間進(jìn)展比擬，交換以實(shí)現(xiàn)排序。通過(guò)遞歸的調(diào)用來(lái)實(shí)現(xiàn)整個(gè)鏈表數(shù)據(jù)的排序。代碼中選用了第一個(gè)元素作為軸值。一趟排序的代碼：voidLinkList::QSZ(node*b,node*e){if(b->ne*t==e||b==e) //排序完成return;node*qianqu=b; //軸點(diǎn)前驅(qū)node*p=qianqu->ne*t;while(p!=e&&p!=e->ne*t) { paref++;if(qianqu->ne*t->data>p->ne*t->data) //元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 {if(p->ne*t==e) //假設(shè)該元素為e，則將其前驅(qū)設(shè)為ee=p; insert(p,qianqu); qianqu=qianqu->ne*t; }elsep=p->ne*t; } QSZ(b,qianqu); //繼續(xù)處理軸點(diǎn)左側(cè)鏈表 QSZ(qianqu->ne*t,e); //繼續(xù)處理軸點(diǎn)右側(cè)鏈表}整個(gè)快速排序的實(shí)現(xiàn):voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*e=front;while(e->ne*t) { e=e->ne*t; } QSZ(front,e); QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}3.改良版的冒泡排序：通過(guò)設(shè)置pos來(lái)記錄無(wú)序邊界的位置以減少比擬次數(shù)。將數(shù)據(jù)從前向后兩兩比擬，遇到順序不對(duì)是直接交換兩數(shù)據(jù)的值。每交換一次movef+3；voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*p=front->ne*t;while(p->ne*t) //排序查找無(wú)序邊界 { paref++;if(p->data>p->ne*t->data) turn(p,p->ne*t); p=p->ne*t; }node*pos=p;p=front->ne*t;while(pos!=front->ne*t) {node*bound=pos; pos=front->ne*t;while(p->ne*t!=bound) { paref++;if(p->data>p->ne*t->data) { turn(p,p->ne*t);pos=p->ne*t; } p=p->ne*t; } p=front->ne*t; } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}4.選擇排序：每趟排序再待排序的序列中選擇關(guān)鍵碼最小的元素，順序添加至已排好的有序序列最后，知道全部記錄排序完畢。voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*s=front;while(s->ne*t->ne*t) {node*p=s;node*inde*=p;while(p->ne*t) { paref++;if(p->ne*t->data<inde*->ne*t->data)inde*=p; p=p->ne*t; } insert(inde*,s); s=s->ne*t; } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}5.堆排序：利用前一趟比擬的結(jié)果來(lái)減少比擬次數(shù)，提高整體的效率。其中通過(guò)鏈表儲(chǔ)存了一棵樹(shù)。選擇使用小根堆進(jìn)展排序。voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m) { paref++;if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; } }}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)for(inti=n/2;i>=1;i--) sift(i,n);for(inti=1;i<n;i++) { turn(Get(1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}其中堆排序中需要知道孩子節(jié)點(diǎn)和父親節(jié)點(diǎn)處的值，故設(shè)置了函數(shù)獲取i出的指針。node*LinkList::Get(inti){node*p=front->ne*t;intj=1;while(j!=i&&p) { p=p->ne*t; j++; }if(!p)throw"查找位置非法";elsereturnp;};6.輸出結(jié)果的函數(shù)：voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){a.print(); paref=0;movef=0;a.InsertSort(); cout<<"排序結(jié)果：";a.print(); cout<<"1.插入排序法：pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;b.BubbleSort(); cout<<"2.改良型冒泡排序法：pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;c.QSort(); cout<<"3.快速排序法：pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;d.SelectSort(); cout<<"4.簡(jiǎn)單項(xiàng)選擇擇排序法pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;e.heapsort(10); cout<<"5.堆排序算法pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl;}7.統(tǒng)計(jì)時(shí)間的函數(shù)：#include<windows.h>{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*p=front->ne*t; //要插入的節(jié)點(diǎn)的前驅(qū)QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;};2.3其他算法的時(shí)間復(fù)雜度：排序方法隨機(jī)序列的平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)~O(n)改良版冒泡排序O(n2)O(n)O(n2)O(1)選擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)3.程序運(yùn)行結(jié)果1.流程圖開(kāi)場(chǎng)：開(kāi)場(chǎng)初始化正序鏈表，調(diào)用各類(lèi)排序，并輸出運(yùn)行結(jié)果初始化正序鏈表，調(diào)用各類(lèi)排序，并輸出運(yùn)行結(jié)果初始化逆序鏈表，調(diào)用各類(lèi)排序，并輸出運(yùn)行結(jié)果初始化逆序鏈表，調(diào)用各類(lèi)排序，并輸出運(yùn)行結(jié)果初始化順序隨機(jī)的鏈表，調(diào)用各類(lèi)排序，并輸出運(yùn)行結(jié)果初始化順序隨機(jī)的鏈表，調(diào)用各類(lèi)排序，并輸出運(yùn)行結(jié)果結(jié)束結(jié)束2.測(cè)試條件：如果需要對(duì)不同的正序，逆序隨機(jī)序列進(jìn)展排序，則需要在main函數(shù)中進(jìn)展初始化設(shè)置。3.測(cè)試結(jié)論：4.總結(jié)通過(guò)這次實(shí)驗(yàn)我再次復(fù)習(xí)了鏈表的建立及相應(yīng)的操作，對(duì)各類(lèi)排序算法的實(shí)現(xiàn)也有了新的理解，在調(diào)試過(guò)程中出現(xiàn)了許多問(wèn)題也花費(fèi)了很多時(shí)間和精力去逐步解決，最后程序運(yùn)行成功的瞬間真的很開(kāi)心。問(wèn)題一：直接插入排序中假設(shè)是使用從后向前比擬插入的話〔即書(shū)上的方法〕難以找到該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，不方便進(jìn)展操作，所以最后采用了從前向后進(jìn)展比擬。voidLinkList::InsertSort() //將第一個(gè)元素定為初始有序區(qū)元素，由第二個(gè)元素開(kāi)場(chǎng)依次比擬{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*p=front->ne*t; //要插入的節(jié)點(diǎn)的前驅(qū)while(p->ne*t) {node*s=front; //充分利用帶頭結(jié)點(diǎn)的單鏈表while(1) { paref++;if(p->ne*t->data<s->ne*t->data) //[P后繼]比[S后繼]小則插入 { insert(p,s);break; } s=s->ne*t;if(s==p) //假設(shè)一趟比擬完畢，且不需要插入 { p=p->ne*t;break; } } }問(wèn)題二：如何將書(shū)上以數(shù)組方式儲(chǔ)存的樹(shù)轉(zhuǎn)化為鏈表儲(chǔ)存并進(jìn)展操作？原本打算建立一顆完全二叉樹(shù)儲(chǔ)存相應(yīng)數(shù)據(jù)再進(jìn)展排序，但是那樣的話需要新設(shè)置結(jié)點(diǎn)存左孩子右孩子，比擬麻煩容易出錯(cuò)，所以選擇了利用Get(inti)函數(shù)將篩選結(jié)點(diǎn)的位置獲得。與書(shū)上代碼相比修改如下：if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; }問(wèn)題三：時(shí)間如何準(zhǔn)確至微秒？需要調(diào)用函數(shù)，這個(gè)問(wèn)題是上網(wǎng)查找解決的?？偨Y(jié)：解決了以上的問(wèn)題后代碼就比擬完整了，可是還是希望通過(guò)日后的學(xué)習(xí)能將算法編寫(xiě)得更完善，靈活，簡(jiǎn)捷。附錄：完整代碼如下：#include"lianbiaopai*u.h"#include<windows.h>usingnamespacestd;voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,10};LinkListzheng*u1(a,10),zheng*u2(a,10),zheng*u3(a,10),zheng*u4(a,10),zheng*u5(a,10); cout<<"正序數(shù)列："; tell(zheng*u1,zheng*u2,zheng*u3,zheng*u4,zheng*u5);intb[10]={10,9,8,7,6,5,4,3,2,1};LinkListni*u1(b,10),ni*u2(b,10),ni*u3(b,10),ni*u4(b,10),ni*u5(b,10); cout<<"\n逆序數(shù)列："; tell(ni*u1,ni*u2,ni*u3,ni*u4,ni*u5);intc[10]={2,6,10,5,8,3,9,1,4,7};LinkListsuiji1(c,10),suiji2(c,10),suiji3(c,10),suiji4(c,10),suiji5(c,10); cout<<"\n隨機(jī)數(shù)列："; tell(suiji1,suiji2,suiji3,suiji4,suiji5);}#include<iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<iomanip>#include<windows.h>usingnamespacestd;intparef;intmovef;structnode{intdata;node*ne*t;};classLinkList{private:node*front;public: LinkList(inta[],intn); //構(gòu)造 ~LinkList();voidinsert(node*p,node*s); //插入voidturn(node*p,node*s); //交換數(shù)據(jù)voidprint(); //輸出voidInsertSort(); //插入排序voidBubbleSort(); //pos冒泡voidQSort(); //快速排序voidSelectSort(); //簡(jiǎn)單項(xiàng)選擇擇排序node*Get(inti);//查找位置為i的結(jié)點(diǎn)voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的遞歸主體voidheapsort(intn);//堆排序算法};LinkList::LinkList(inta[],intn){ front=newnode; front->ne*t=NULL;for(inti=n-1;i>=0;i--) {node*p=newnode;//新節(jié)點(diǎn) p->data=a[i]; p->ne*t=front->ne*t; front->ne*t=p;//頭插法建立單鏈表，最先參加的被不斷后移 }}LinkList::~LinkList(){node*q=front;while(q) { front=q; q=q->ne*t;deletefront; }}voidLinkList::insert(node*p,node*s)//將p->ne*t插入s和s->ne*t之間{node*q=p->ne*t;p->ne*t=p->ne*t->ne*t; q->ne*t=s->ne*t;s->ne*t=q; movef++;}voidLinkList::turn(node*p,node*s) //交換數(shù)據(jù){inttemp=p->data;p->data=s->data;s->data=temp; movef+=3;}voidLinkList::print() //輸出需要顯示的內(nèi)容{node*p=front->ne*t;while(p) { cout<<p->data<<''; p=p->ne*t; } cout<<endl;}voidLinkList::InsertSort() //將第一個(gè)元素定為初始有序區(qū)元素，由第二個(gè)元素開(kāi)場(chǎng)依次比擬{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*p=front->ne*t; //要插入的節(jié)點(diǎn)的前驅(qū)while(p->ne*t) {node*s=front; //充分利用帶頭結(jié)點(diǎn)的單鏈表while(1) { paref++;if(p->ne*t->data<s->ne*t->data) //[P后繼]比[S后繼]小則插入 { insert(p,s);break; } s=s->ne*t;if(s==p) //假設(shè)一趟比擬完畢，且不需要插入 { p=p->ne*t;break; } } } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}voidLinkList::QSZ(node*b,node*e){if(b->ne*t==e||b==e) //排序完成return;node*qianqu=b; //軸點(diǎn)前驅(qū)node*p=qianqu->ne*t;while(p!=e&&p!=e->ne*t) { paref++;if(qianqu->ne*t->data>p->ne*t->data) //元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 {if(p->ne*t==e) //假設(shè)該元素為e，則將其前驅(qū)設(shè)為ee=p; insert(p,qianqu); qianqu=qianqu->ne*t; }elsep=p->ne*t; } QSZ(b,qianqu); //繼續(xù)處理軸點(diǎn)左側(cè)鏈表 QSZ(qianqu->ne*t,e); //繼續(xù)處理軸點(diǎn)右側(cè)鏈表}voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*e=front;while(e->ne*t) { e=e->ne*t; } QSZ(front,e); QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*p=front->ne*t;while(p->ne*t) //排序查找無(wú)序邊界 { paref++;if(p->data>p->ne*t->data) turn(p,p->ne*t); p=p->ne*t; }node*pos=p;p=front->ne*t;while(pos!=front->ne*t) {node*bound=pos; pos=front->ne*t;while(p->ne*t!=bound) { paref++;if(p->data>p->ne*t->data) { turn(p,p->ne*t);pos=p->ne*t; } p=p->ne*t; } p=front->ne*t; } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1);//測(cè)前跳動(dòng)次數(shù)node*s=front;while(s->ne*t->ne*t) {node*p=s;node*inde*=p;while(p->ne*t) { paref++;if(p->ne*t->data<inde*->ne*t->data) inde*=p; p=p->ne*t; } insert(inde*,s); s=s->ne*t; } QueryPerformanceCounter(&t2);//測(cè)后跳動(dòng)次數(shù)doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//時(shí)間差秒 cout<<"操作時(shí)間為："<<d<<endl;}node*LinkList::Get(inti){node*p=front->ne*t;intj=1;while(j!=i&&p) { p=p->ne*t; j++; }if(!p)throw"查找位置非法";elsereturnp;}voidLinkList::sift(intk,intm){inti=k,j=