c++数据结构实验链表排序参考模板

1、1实验要求i. 实验目的:通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。ii. 实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）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.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p->next在无序区中指向待插入的结点，在找到插入位置后，将结点p->next插在结点s和p之间。void LinkList:InsertSort()/将第一个元素定为初始有序区元素，由第二个元素开始依次比较LARGE_INTEGER t1, t2, feq;QueryPer

5、formanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front->next;/要插入的节点的前驱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);/继续处理轴点左侧链表QSZ(qianqu->next, e);/继续处理轴点右侧链表整个快速排序的实现: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;其中堆排序中需要知道孩子节点和父亲节点处的值，故设置了函数获取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.统计时间的函数：#include<windows.h>LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front->next;/要插入的节点的前驱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. 总结 通过这次实验我再次复习了链表的建立及相应的操作，对各类排序算法的实现也有了新的理解，在调试过程中出现了许多问题也花费了很多时间和精力去逐步解决，最后程序运行成功的瞬间真的很开心。 问题一：直接插入排序中若是使用从后向前比较插入的话（即书上的办法）难以找到该节点的前驱节点，不方便进行操作，所以最后采用了从前向后进行比较。void LinkList:In

24、sertSort()/将第一个元素定为初始有序区元素，由第二个元素开始依次比较LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front->next;/要插入的节点的前驱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;问题三：时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。总结：解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。附录：完整代码如下：#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; /新节点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()/将第一个元素定为初始有序区元素，由第二个元素开始依次比较LARGE_INTEGER t1, t2, feq;QueryPerformanceFrequency(&feq); /每秒跳动次数 QueryPerformanceCounter(&t1); /测前跳动次数 node * p = front->next;/要插

34、入的节点的前驱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);/继续处理轴点左侧链表QSZ(qianqu->next, e);/继续处理轴点右侧链表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