c++數據結構實驗鏈表排序參考模板

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

2、數測試線性表的正確性iii. 代碼要求：1、必須要有異常處理，比如刪除空鏈表時需要拋出異常；2、保持良好的編程的風格：代碼段與段之間要有空行和縮近標識符名稱應該與其代表的意義一致函數名之前應該添加注釋說明該函數的功能關鍵代碼應說明其功能 3、遞歸程序注意調用的過程，防止棧溢出2. 程序分析通過排序算法將單鏈表中的數據進行由小至大（正向排序）2.1 存儲結構單鏈表存儲數據：struct node1 / 18int data;node*next;單鏈表定義如下：class LinkListprivate:node * front;public:LinkList(int a, int n);/構造L

3、inkList();void insert(node*p, node*s);/插入void turn(node*p, node*s);/交換數據void print();/輸出void InsertSort();/插入排序void BubbleSort();/pos冒泡void QSort();/快速排序void SelectSort();/簡單選擇排序node* Get(int i); /查找位置為i的結點void sift(int k, int m); /一趟堆排序void LinkList:QSZ(node * b, node *e); /快速排序的遞歸主體void heapsort(i

4、nt n); /堆排序算法;2.2 關鍵算法分析：1.直接插入排序：首先將待排序數據建立一個帶頭結點的單鏈表。將單鏈表劃分為有序區(qū)和無序區(qū)，有序區(qū)只包含一個元素節(jié)點，依次取無序區(qū)中的每一個結點，在有序區(qū)中查找待插入結點的插入位置，然后把該結點從單鏈表中刪除，再插入到相應位置。分析上述排序過程，需設一個工作指針p->next在無序區(qū)中指向待插入的結點，在找到插入位置后，將結點p->next插在結點s和p之間。void LinkList:InsertSort()/將第一個元素定為初始有序區(qū)元素，由第二個元素開始依次比較LARGE_INTEGER t1, t2, feq;QueryPer

5、formanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * p = front->next;/要插入的節(jié)點的前驅while (p->next)node * s = front;/充分利用帶頭結點的單鏈表while (1)comparef+;if (p->next->data <s->next->data)/ P后繼比S后繼小則插入insert(p, s); break;s = s->next;if (s = p)/若一趟比較結束，且不需

6、要插入p = p->next; break;QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;2.快速排序：主要通過軸值將數據從兩端向中間進行比較，交換以實現排序。通過遞歸的調用來實現整個鏈表數據的排序。代碼中選用了第一個元素作為軸值。一趟排序的代碼：void LinkLis

7、t:QSZ(node * b, node *e)if (b->next = e | b = e)/排序完成return;node * qianqu = b; /軸點前驅node * p = qianqu->next;while (p != e && p != e->next)comparef+;if (qianqu->next->data > p->next->data)/元素值小于軸點值，則將該元素插在軸點之前if (p->next = e)/若該元素為e，則將其前驅設為ee = p;insert(p, qianqu);q

8、ianqu = qianqu->next;else p = p->next;QSZ(b, qianqu);/繼續(xù)處理軸點左側鏈表QSZ(qianqu->next, e);/繼續(xù)處理軸點右側鏈表整個快速排序的實現:void LinkList:QSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * e = front;while (e->next)e = e->next;Q

9、SZ(front, e);QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;3.改進版的冒泡排序：通過設置pos來記錄無序邊界的位置以減少比較次數。將數據從前向后兩兩比較，遇到順序不對是直接交換兩數據的值。每交換一次movef+3；void LinkList:BubbleSort(

10、)LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * p = front->next;while (p->next) / 排序查找無序邊界comparef+;if (p->data > p->next->data)turn(p, p->next);p = p->next;node * pos = p; p = front->next;while (pos

11、!= 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); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPar

12、t) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;4.選擇排序：每趟排序再待排序的序列中選擇關鍵碼最小的元素，順序添加至已排好的有序序列最后，知道全部記錄排序完畢。void LinkList:SelectSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * s = fr

13、ont;while (s->next->next)node * p = s;node * index = p;while (p->next)comparef+;if (p->next->data < index->next->data)index = p;p = p->next;insert(index, s);s = s->next;QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (do

14、uble)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;5.堆排序： 利用前一趟比較的結果來減少比較次數，提高整體的效率。 其中通過鏈表儲存了一棵樹。 選擇使用小根堆進行排序。void LinkList:sift(int k, int m)int i = k, j = 2 * i;while (j <= m)comparef+;if (j<m && (Get(j)->data>Get(j + 1)->data) j+;if (Get(i)-

15、>data < Get(j)->data) break;elseturn(Get(i), Get(j);i = j;j = 2 * i;void LinkList:heapsort(int n)LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 for (int i = n / 2; i >= 1; i-)sift(i, n);for (int i = 1; i < n; i+)turn(Ge

16、t(1), Get(n - i + 1);sift(1, n - i);QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;其中堆排序中需要知道孩子節(jié)點和父親節(jié)點處的值，故設置了函數獲取i出的指針。node*LinkList:Get(int i)node*p = front->

17、next;int j = 1;while (j != i&&p)p = p->next;j+;if (!p) throw "查找位置非法"else return p;6.輸出結果的函數：void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e)a.print();comparef = 0; movef = 0;a.InsertSort();cout << "排序結果：" a.print();c

18、out << "1.插入排序法： Compare：" << setw(3) << comparef << " Move：" << setw(3) << movef << endl;comparef = 0; movef = 0;b.BubbleSort();cout << "2.改進型冒泡排序法： Compare：" << setw(3) << comparef << " Move："

19、 << setw(3) << movef << endl;comparef = 0; movef = 0;c.QSort();cout << "3.快速排序法： Compare：" << setw(3) << comparef << " Move：" << setw(3) << movef << endl;comparef = 0; movef = 0;d.SelectSort();cout << "4.簡單選擇排

20、序法 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) << mo

21、vef << endl;7.統(tǒng)計時間的函數：#include<windows.h>LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * p = front->next;/要插入的節(jié)點的前驅QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) /

22、(double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;2.3 其他算法的時間復雜度：排序方法隨機序列的平均情況最好情況最壞情況輔助空間直接插入排序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. 程序運行結果1.流程圖開始：初始化正序鏈表，調

23、用各類排序，并輸出運行結果初始化逆序鏈表，調用各類排序，并輸出運行結果初始化順序隨機的鏈表，調用各類排序，并輸出運行結果結 束2.測試條件：如果需要對不同的正序，逆序隨機序列進行排序，則需要在main函數中進行初始化設置。3.測試結論：4. 總結 通過這次實驗我再次復習了鏈表的建立及相應的操作，對各類排序算法的實現也有了新的理解，在調試過程中出現了許多問題也花費了很多時間和精力去逐步解決，最后程序運行成功的瞬間真的很開心。 問題一：直接插入排序中若是使用從后向前比較插入的話（即書上的辦法）難以找到該節(jié)點的前驅節(jié)點，不方便進行操作，所以最后采用了從前向后進行比較。void LinkList:In

24、sertSort()/將第一個元素定為初始有序區(qū)元素，由第二個元素開始依次比較LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * p = front->next;/要插入的節(jié)點的前驅while (p->next)node * s = front;/充分利用帶頭結點的單鏈表while (1)comparef+;if (p->next->data <s->next->da

25、ta)/ P后繼比S后繼小則插入insert(p, s); break;s = s->next;if (s = p)/若一趟比較結束，且不需要插入p = p->next; break;問題二：如何將書上以數組方式儲存的樹轉化為鏈表儲存并進行操作？原本打算建立一顆完全二叉樹儲存相應數據再進行排序，但是那樣的話需要新設置結點存左孩子右孩子，比較麻煩容易出錯，所以選擇了利用Get(int i)函數將篩選結點的位置獲得。與書上代碼相比修改如下：if (j<m && (Get(j)->data>Get(j + 1)->data) j+;if (Get(

26、i)->data < Get(j)->data) break;elseturn(Get(i), Get(j);i = j;j = 2 * i;問題三：時間如何精確至微秒？需要調用函數，這個問題是上網查找解決的?？偨Y：解決了以上的問題后代碼就比較完整了，可是還是希望通過日后的學習能將算法編寫得更完善，靈活，簡捷。附錄：完整代碼如下：#include "lianbiaopaixu.h"#include <windows.h>using namespace std;void main()int a10 = 1, 2, 3, 4, 5, 6, 7, 8

27、, 9, 10 ;LinkList zhengxu1(a, 10), zhengxu2(a, 10), zhengxu3(a, 10), zhengxu4(a, 10), zhengxu5(a, 10);cout << "正序數列："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), nixu5(

28、b, 10);cout << "n逆序數列："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隨機數列："tell(suiji1, suiji2, suiji3, suiji4, suiji5);#include <iostrea

29、m>#include<stdio.h>#include <stdlib.h>#include <time.h>#include <iomanip>#include <windows.h>using namespace std;int comparef;int movef;struct nodeint data;node*next;class LinkListprivate:node * front;public:LinkList(int a, int n);/構造LinkList();void insert(node*p, no

30、de*s);/插入void turn(node*p, node*s);/交換數據void print();/輸出void InsertSort();/插入排序void BubbleSort();/pos冒泡void QSort();/快速排序void SelectSort();/簡單選擇排序node* Get(int i); /查找位置為i的結點void sift(int k, int m); /一趟堆排序void LinkList:QSZ(node * b, node *e); /快速排序的遞歸主體void heapsort(int n); /堆排序算法;LinkList:LinkList(

31、int a, int n)front = new node;front->next = NULL;for (int i = n - 1; i >= 0; i-)node * p = new node; /新節(jié)點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(n

32、ode*p, node*s) /將p->next插入s和s->next之間node * q = p->next;p->next = p->next->next;q->next = s->next;s->next = q;movef+;void LinkList:turn(node*p, node*s)/交換數據int temp = p->data;p->data = s->data;s->data = temp;movef += 3;void LinkList:print()/輸出需要顯示的內容node * p =

33、front->next;while (p)cout << p->data << ' 'p = p->next;cout << endl;void LinkList:InsertSort()/將第一個元素定為初始有序區(qū)元素，由第二個元素開始依次比較LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * p = front->next;/要插

34、入的節(jié)點的前驅while (p->next)node * s = front;/充分利用帶頭結點的單鏈表while (1)comparef+;if (p->next->data <s->next->data)/ P后繼比S后繼小則插入insert(p, s); break;s = s->next;if (s = p)/若一趟比較結束，且不需要插入p = p->next; break;QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)

35、t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;void LinkList:QSZ(node * b, node *e)if (b->next = e | b = e)/排序完成return;node * qianqu = b; /軸點前驅node * p = qianqu->next;while (p != e && p != e->next)comparef+;if (qianqu->next-&g

36、t;data > p->next->data)/元素值小于軸點值，則將該元素插在軸點之前if (p->next = e)/若該元素為e，則將其前驅設為ee = p;insert(p, qianqu);qianqu = qianqu->next;else p = p->next;QSZ(b, qianqu);/繼續(xù)處理軸點左側鏈表QSZ(qianqu->next, e);/繼續(xù)處理軸點右側鏈表void LinkList:QSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq)

37、; /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * e = front;while (e->next)e = e->next;QSZ(front, e);QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;

38、void LinkList:BubbleSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * p = front->next;while (p->next) / 排序查找無序邊界comparef+;if (p->data > p->next->data)turn(p, p->next);p = p->next;node * pos = p; p = f

39、ront->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); /測后跳動次數 double d = (double)t2.Quad

40、Part - (double)t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout << "操作時間為：" << d << endl;void LinkList:SelectSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCounter(&t1); /測前跳動次數 node * s = front;while (s->next->next)n

41、ode * p = s;node * index = p;while (p->next)comparef+;if (p->next->data < index->next->data)index = p;p = p->next;insert(index, s);s = s->next;QueryPerformanceCounter(&t2); /測后跳動次數 double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時間差秒 cout &l

42、t;< "操作時間為：" << d << endl;node*LinkList:Get(int i)node*p = front->next;int j = 1;while (j != i&&p)p = p->next;j+;if (!p) throw "查找位置非法"else return p;void LinkList:sift(int k, int m)int i = k, j = 2 * i;while (j <= m)comparef+;if (j<m && (Get(j)->data>Get(j + 1)->data) j+;if (Get(i)->data < Get(j)->data) break;elseturn(Get(i), Get(j);i = j;j = 2 * i;void LinkList:heapsort(int n)LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動次數 QueryPerformanceCoun