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è)試main()函

2、數(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 node1 / 18int data;node*next;單鏈表定義如下：class LinkListprivate:node * front;public:LinkList(int a, int n);/構(gòu)造L

3、inkList();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); /快速排序的遞歸主體void heapsort(i

4、nt 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, t2, feq;QueryPer

5、formanceFrequency(&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 <s->next->data)/ P后繼比S后繼小則插入insert(p, s); break;s = s->next;if (s = p)/若一趟比較結(jié)束，且不需

6、要插入p = p->next; break;QueryPerformanceCounter(&t2); /測(cè)后跳動(dòng)次數(shù) double d = (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è)元素作為軸值。一趟排序的代碼：void LinkLis

7、t:QSZ(node * b, node *e)if (b->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->next->data)/元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前if (p->next = e)/若該元素為e，則將其前驅(qū)設(shè)為ee = p;insert(p, qianqu);q

8、ianqu = 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ù) QueryPerformanceCounter(&t1); /測(cè)前跳動(dòng)次數(shù) node * e = front;while (e->next)e = e->next;Q

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

10、)LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1); /測(cè)前跳動(dòng)次數(shù) node * p = front->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

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); /測(cè)后跳動(dòng)次數(shù) double d = (double)t2.QuadPart - (double)t1.QuadPar

12、t) / (double)feq.QuadPart);/時(shí)間差秒 cout << "操作時(shí)間為：" << d << endl;4.選擇排序：每趟排序再待排序的序列中選擇關(guān)鍵碼最小的元素，順序添加至已排好的有序序列最后，知道全部記錄排序完畢。void LinkList:SelectSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1); /測(cè)前跳動(dòng)次數(shù) 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); /測(cè)后跳動(dòng)次數(shù) double d = (double)t2.QuadPart - (double)t1.QuadPart) / (do

14、uble)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 (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); /每秒跳動(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(Ge

16、t(1), Get(n - i + 1);sift(1, n - i);QueryPerformanceCounter(&t2); /測(cè)后跳動(dòng)次數(shù) double d = (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(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.輸出結(jié)果的函數(shù)：void tell(LinkList &a, LinkList &b, LinkList &c, LinkList &d, LinkList &e)a.print();comparef = 0; movef = 0;a.InsertSort();cout << "排序結(jié)果：" a.print();c

18、out << "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："

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.簡(jiǎn)單選擇排

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)計(jì)時(shí)間的函數(shù)：#include<windows.h>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ù) double d = (double)t2.QuadPart - (double)t1.QuadPart) /

22、(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)改進(jì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)始：初始化正序鏈表，調(diào)

23、用各類排序，并輸出運(yùn)行結(jié)果初始化逆序鏈表，調(diào)用各類排序，并輸出運(yùn)行結(jié)果初始化順序隨機(jī)的鏈表，調(diào)用各類排序，并輸出運(yùn)行結(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ì)各類排序算法的實(shí)現(xiàn)也有了新的理解，在調(diào)試過(guò)程中出現(xiàn)了許多問(wèn)題也花費(fèi)了很多時(shí)間和精力去逐步解決，最后程序運(yùn)行成功的瞬間真的很開(kāi)心。 問(wèn)題一：直接插入排序中若是使用從后向前比較插入的話（即書(shū)上的辦法）難以找到該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，不方便進(jìn)行操作，所以最后采用了從前向后進(jìn)行比較。void LinkList:In

24、sertSort()/將第一個(gè)元素定為初始有序區(qū)元素，由第二個(gè)元素開(kāi)始依次比較LARGE_INTEGER t1, 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 <s->next->da

25、ta)/ 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)函數(shù)將篩選結(jié)點(diǎn)的位置獲得。與書(shū)上代碼相比修改如下：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;問(wèn)題三：時(shí)間如何精確至微秒？需要調(diào)用函數(shù)，這個(gè)問(wèn)題是上網(wǎng)查找解決的。總結(jié)：解決了以上的問(wèn)題后代碼就比較完整了，可是還是希望通過(guò)日后的學(xué)習(xí)能將算法編寫(xiě)得更完善，靈活，簡(jiǎn)捷。附錄：完整代碼如下：#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 << "正序數(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), nixu5(

28、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 <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);/構(gòu)造LinkList();void insert(node*p, no

30、de*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); /快速排序的遞歸主體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é)點(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(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)/交換數(shù)據(jù)int temp = p->data;p->data = s->data;s->data = temp;movef += 3;void LinkList:print()/輸出需要顯示的內(nèi)容node * p =

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

34、入的節(jié)點(diǎn)的前驅(qū)while (p->next)node * s = front;/充分利用帶頭結(jié)點(diǎn)的單鏈表while (1)comparef+;if (p->next->data <s->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ù) double d = (double)t2.QuadPart - (double)

35、t1.QuadPart) / (double)feq.QuadPart);/時(shí)間差秒 cout << "操作時(shí)間為：" << d << endl;void LinkList:QSZ(node * b, node *e)if (b->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-&g

36、t;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:QSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq)

37、; /每秒跳動(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ù) double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時(shí)間差秒 cout << "操作時(shí)間為：" << d << endl;

38、void LinkList:BubbleSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1); /測(cè)前跳動(dòng)次數(shù) node * p = front->next;while (p->next) / 排序查找無(wú)序邊界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); /測(cè)后跳動(dòng)次數(shù) double d = (double)t2.Quad

40、Part - (double)t1.QuadPart) / (double)feq.QuadPart);/時(shí)間差秒 cout << "操作時(shí)間為：" << d << endl;void LinkList:SelectSort()LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳動(dòng)次數(shù) QueryPerformanceCounter(&t1); /測(cè)前跳動(dòng)次數(shù) 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); /測(cè)后跳動(dòng)次數(shù) double d = (double)t2.QuadPart - (double)t1.QuadPart) / (double)feq.QuadPart);/時(shí)間差秒 cout &l

42、t;< "操作時(shí)間為：" << 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); /每秒跳動(dòng)次數(shù) QueryPerformanceCoun