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

1、1實(shí)驗(yàn)要求i.實(shí)驗(yàn)?zāi)康?: 通過(guò)編程，學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。理解算法的主要思想及流程。ii.實(shí)驗(yàn)內(nèi)容：使用鏈表實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、冒泡排序（改進(jìn)型冒泡排序）3、快速排序4、簡(jiǎn)單選擇排序5、堆排序（小根堆）要求：1、測(cè)試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)2、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（其中關(guān)鍵字交換計(jì)為3 次移動(dòng)）。3、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）4、對(duì) 2 和 3 的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度編寫(xiě)測(cè)試mai

2、n()函數(shù)測(cè)試線性表的正確性iii.代碼要求：1、必須要有異常處理，比如刪除空鏈表時(shí)需要拋出異常；2、保持良好的編程的風(fēng)格：代碼段與段之間要有空行和縮近標(biāo)識(shí)符名稱應(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ǔ)結(jié)構(gòu)單鏈表存儲(chǔ)數(shù)據(jù)：struct node int data; node*next; ; 單鏈表定義如下：classlinklist private: node * front; public: linklist( int a, int n)

3、; /構(gòu)造linklist(); void insert(node*p, node*s); /插入void turn(node*p, node*s); /交換數(shù)據(jù)void print(); /輸出void insertsort(); /插入排序void bubblesort(); /pos冒泡void qsort(); /快速排序void selectsort(); /簡(jiǎn)單選擇排序node* get(int i); /查找位置為 i的結(jié)點(diǎn)void sift(int k, int m); /一趟堆排序void linklist :qsz(node * b, node *e); /快速排序的遞歸主

4、體void heapsort(int n); /堆排序算法; 2.2關(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-next 在無(wú)序區(qū)中指向待插入的結(jié)點(diǎn)，在找到插入位置后，將結(jié)點(diǎn)p-next 插在結(jié)點(diǎn)s 和 p 之間。void linklist :insertsort() /將第一個(gè)元素定為初始有序區(qū)元素，由第二個(gè)元素開(kāi)始依次比較 large_integer t1,

5、 t2, feq; queryperformancefrequency(&feq); /每秒跳動(dòng)次數(shù)queryperformancecounter(&t1); /測(cè)前跳動(dòng)次數(shù)node * p = front-next; /要插入的節(jié)點(diǎn)的前驅(qū)while (p-next) node * s = front; /充分利用帶頭結(jié)點(diǎn)的單鏈表while (1) comparef+; if (p-next-data next-data) / p后繼 比s后繼 小則插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比較結(jié)束，且不需要插入 p

6、= p-next; break; queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next = e | b = e) /排序完成return; node * qianqu = b; /軸點(diǎn)前驅(qū)node * p = qianqu-next; while (p != e & p != e-next) comparef+; if (qianqu-next-data p

7、-next-data) /元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 if (p-next = e) /若該元素為 e，則將其前驅(qū)設(shè)為ee = p; insert(p, qianqu); qianqu = qianqu-next; else p = p-next; qsz(b, qianqu); /繼續(xù)處理軸點(diǎn)左側(cè)鏈表qsz(qianqu-next, e); /繼續(xù)處理軸點(diǎn)右側(cè)鏈表 整個(gè)快速排序的實(shí)現(xiàn): void linklist :qsort() large_integer t1, t2, feq; queryperformancefrequency(&feq); /每秒跳動(dòng)次數(shù)que

8、ryperformancecounter(&t1); /測(cè)前跳動(dòng)次數(shù)node * e = front; while (e-next) e = e-next; qsz(front, e); queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next; while (p-next) / 排序查找無(wú)序邊界 comparef+; if (p-data p-next-dat

9、a) turn(p, p-next); p = p-next; node * pos = p; p = front-next; while (pos != front-next) node * bound = pos; pos = front-next; while (p-next != bound) comparef+; if (p-data p-next-data) turn(p, p-next); pos = p-next; p = p-next; p = front-next; queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)double d = (d

10、ouble)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next-next) node * p = s; node * index = p; while (p-next) comparef+; if (p-next-data next-data) index = p; p = p-next; insert(index, s); s = s-next; queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quad

11、part - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d endl; 5.堆排序：利用前一趟比較的結(jié)果來(lái)減少比較次數(shù)，提高整體的效率。其中通過(guò)鏈表儲(chǔ)存了一棵樹(shù)。選擇使用小根堆進(jìn)行排序。void linklist :sift( int k, int m) int i = k, j = 2 * i; while (j = m) comparef+; if (jdataget(j + 1)-data) j+; if (get(i)-data data) break; else turn(get(i), get(j)

12、; i = j; j = 2 * i; void linklist :heapsort(int n) large_integer t1, t2, feq; queryperformancefrequency(&feq); /每秒跳動(dòng)次數(shù)queryperformancecounter(&t1); /測(cè)前跳動(dòng)次數(shù)for (int i = n / 2; i = 1; i-) sift(i, n); for (int i = 1; i n; i+) turn(get(1), get( n - i + 1); sift(1, n - i); queryperformancecounter

13、(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next; int j = 1; while (j != i&p) p = p-next; j+; if (!p) throw查找位置非法; elsereturn p; ; 6.輸出結(jié)果的函數(shù)：void tell( linklist & a, linklist & b, linklist &c, linklist &d, lin

14、klist & e) a.print(); comparef = 0; movef = 0; a.insertsort(); cout 排序結(jié)果： ; a.print(); cout 1.插入排序法：compare： setw(3) comparef ; move： setw(3) movef endl; comparef = 0; movef = 0; b.bubblesort(); cout 2.改進(jìn)型冒泡排序法：compare： setw(3) comparef ; move ： setw(3) movef endl; comparef = 0; movef = 0; c.qso

15、rt(); cout 3.快速排序法：compare： setw(3) comparef ; move： setw(3) movef endl; comparef = 0; movef = 0; d.selectsort(); cout 4.簡(jiǎn)單選擇排序法compare： setw(3) comparef ; move： setw(3) movef endl; comparef = 0; movef = 0; e.heapsort(10); cout 5.堆排序算法compare： setw(3) comparef ; move ： setw(3) movef endl; 7.統(tǒng)計(jì)時(shí)間的函數(shù)：

16、#include large_integer t1, t2, feq; queryperformancefrequency(&feq); /每秒跳動(dòng)次數(shù)queryperformancecounter(&t1); /測(cè)前跳動(dòng)次數(shù)node * p = front-next; /要插入的節(jié)點(diǎn)的前驅(qū)queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next; /要

17、插入的節(jié)點(diǎn)的前驅(qū)while (p-next) node * s = front; /充分利用帶頭結(jié)點(diǎn)的單鏈表while (1) comparef+; if (p-next-data next-data) / p后繼 比s后繼 小則插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比較結(jié)束，且不需要插入 p = p-next; 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(int i)

18、函數(shù)將篩選結(jié)點(diǎn)的位置獲得。與書(shū)上代碼相比修改如下：if (jdataget(j + 1)-data) j+; if (get(i)-data data) break; else turn(get(i), get(j); i = j; j = 2 * i; 問(wèn)題三：時(shí)間如何精確至微秒？需要調(diào)用函數(shù)，這個(gè)問(wèn)題是上網(wǎng)查找解決的?？偨Y(jié)： 解決了以上的問(wèn)題后代碼就比較完整了，可是還是希望通過(guò)日后的學(xué)習(xí)能將算法編寫(xiě)得更完善，靈活，簡(jiǎn)捷。附錄：完整代碼如下：#include lianbiaopaixu.h#include using namespace std; void main() int a10 =

19、1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ; linklist zhengxu1(a, 10), zhengxu2(a, 10), zhengxu3(a, 10), zhengxu4(a, 10), zhengxu5(a, 10); cout 正序數(shù)列： ; tell(zhengxu1, zhengxu2, zhengxu3, zhengxu4, zhengxu5); int b10 = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 ; linklist nixu1(b, 10), nixu2(b, 10), nixu3(b, 10), nixu4(b, 10)

20、, nixu5(b, 10); cout n逆序數(shù)列： ; tell(nixu1, nixu2, nixu3, nixu4, nixu5); int c10 = 2, 6, 10, 5, 8, 3, 9, 1, 4, 7 ; linklist suiji1(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 #include#include #include #include

21、 #include using namespace std; int comparef; int movef; struct node int data; node*next; ; classlinklist private: node * front; public: linklist( int a, int n); /構(gòu)造linklist(); void insert(node*p, node*s); /插入void turn(node*p, node*s); /交換數(shù)據(jù)void print(); /輸出void insertsort(); /插入排序void bubblesort();

22、/pos冒泡void qsort(); /快速排序void selectsort(); /簡(jiǎn)單選擇排序node* get(int i); /查找位置為 i的結(jié)點(diǎn)void sift(int k, int m); /一趟堆排序void linklist :qsz(node * b, node *e); /快速排序的遞歸主體void heapsort(int n); /堆排序算法; linklist :linklist( int a, int n) front = new node; front-next = null ; for (int i = n - 1; i = 0; i-) node *

23、p = new node; /新節(jié)點(diǎn)p-data = ai; p-next = front-next; front-next = p; /頭插法建立單鏈表，最先加入的被不斷后移 linklist :linklist() node * q = front; while (q) front = q; q = q-next; delete front; void linklist :insert(node*p, node*s) /將p-next插入 s和s-next之間 node * q = p-next; p-next = p-next-next; q-next = s-next; s-next

24、= q; movef+; void linklist :turn(node*p, node*s) /交換數(shù)據(jù) int temp = p-data; p-data = s-data; s-data = temp; movef += 3; voidlinklist :print() /輸出需要顯示的內(nèi)容 node * p = front-next; while (p) cout data next; cout next; /要插入的節(jié)點(diǎn)的前驅(qū)while (p-next) node * s = front; /充分利用帶頭結(jié)點(diǎn)的單鏈表while (1) comparef+; if (p-next-d

25、ata next-data) / p后繼 比s后繼 小則插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比較結(jié)束，且不需要插入 p = p-next; break; queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next = e | b = e) /排序完成return; node * qianqu = b; /軸

26、點(diǎn)前驅(qū)node * p = qianqu-next; while (p != e & p != e-next) comparef+; if (qianqu-next-data p-next-data) /元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 if (p-next = e) /若該元素為 e，則將其前驅(qū)設(shè)為ee = p; insert(p, qianqu); qianqu = qianqu-next; else p = p-next; qsz(b, qianqu); /繼續(xù)處理軸點(diǎn)左側(cè)鏈表qsz(qianqu-next, e); /繼續(xù)處理軸點(diǎn)右側(cè)鏈表 void linklist :

27、qsort() large_integer t1, t2, feq; queryperformancefrequency(&feq); /每秒跳動(dòng)次數(shù)queryperformancecounter(&t1); /測(cè)前跳動(dòng)次數(shù)node * e = front; while (e-next) e = e-next; qsz(front, e); queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/

28、時(shí)間差秒cout 操作時(shí)間為： d next; while (p-next) / 排序查找無(wú)序邊界 comparef+; if (p-data p-next-data) turn(p, p-next); p = p-next; node * pos = p; p = front-next; while (pos != front-next) node * bound = pos; pos = front-next; while (p-next != bound) comparef+; if (p-data p-next-data) turn(p, p-next); pos = p-next;

29、p = p-next; p = front-next; queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)double d = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next-next) node * p = s; node * index = p; while (p-next) comparef+; if (p-next-data next-data) index = p; p = p-next; insert(index,

30、s); s = s-next; queryperformancecounter(&t2); /測(cè)后跳動(dòng)次數(shù)doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/時(shí)間差秒cout 操作時(shí)間為： d next; int j = 1; while (j != i&p) p = p-next; j+; if (!p) throw查找位置非法; elsereturn p; void linklist :sift( int k, int m) int i = k, j = 2 * i; while (j = m) comparef+; if (jdataget(j + 1)-data) j+; if (get(i)-data data) break; else turn(get(i), get(j); i = j; j = 2 * i; void linklist :heapsort(int n) large_integer t1, t2, fe