c++数据结构实验链表排序

1、1实验要求i.实验目的 : 通过编程，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。ii.实验内容：使用链表实现下面各种排序算法，并进行比较。排序算法：1、插入排序2、冒泡排序（改进型冒泡排序）3、快速排序4、简单选择排序5、堆排序（小根堆）要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3 次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对 2 和 3 的结果进行分析，验证上述各种算法的时间复杂度编写测试mai

2、n()函数测试线性表的正确性iii.代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2. 程序分析通过排序算法将单链表中的数据进行由小至大（正向排序）2.1 存储结构单链表存储数据：struct node int data; node*next; ; 单链表定义如下：classlinklist private: node * front; public: linklist( int a, int n)

3、; /构造linklist(); 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); /快速排序的递归主

4、体void heapsort(int n); /堆排序算法; 2.2关键算法分析：1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区， 有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p-next 在无序区中指向待插入的结点，在找到插入位置后，将结点p-next 插在结点s 和 p 之间。void linklist :insertsort() /将第一个元素定为初始有序区元素，由第二个元素开始依次比较 large_integer t1,

5、 t2, feq; queryperformancefrequency(&feq); /每秒跳动次数queryperformancecounter(&t1); /测前跳动次数node * p = front-next; /要插入的节点的前驱while (p-next) node * s = front; /充分利用带头结点的单链表while (1) comparef+; if (p-next-data next-data) / p后继 比s后继 小则插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比较结束，且不需要插入 p

6、= p-next; break; queryperformancecounter(&t2); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： d next = e | b = e) /排序完成return; node * qianqu = b; /轴点前驱node * p = qianqu-next; while (p != e & p != e-next) comparef+; if (qianqu-next-data p

7、-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); /每秒跳动次数que

8、ryperformancecounter(&t1); /测前跳动次数node * e = front; while (e-next) e = e-next; qsz(front, e); queryperformancecounter(&t2); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： d next; while (p-next) / 排序查找无序边界 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); /测后跳动次数double d = (d

10、ouble)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： 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); /测后跳动次数doubled = (double)t2.quad

11、part - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： d endl; 5.堆排序：利用前一趟比较的结果来减少比较次数，提高整体的效率。其中通过链表储存了一棵树。选择使用小根堆进行排序。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); /每秒跳动次数queryperformancecounter(&t1); /测前跳动次数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); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： d next; int j = 1; while (j != i&p) p = p-next; j+; if (!p) throw查找位置非法; elsereturn p; ; 6.输出结果的函数：void tell( linklist & a, linklist & b, linklist &c, linklist &d, lin

14、klist & e) a.print(); comparef = 0; movef = 0; a.insertsort(); cout 排序结果： ; a.print(); cout 1.插入排序法：compare： setw(3) comparef ; move： setw(3) movef endl; comparef = 0; movef = 0; b.bubblesort(); cout 2.改进型冒泡排序法：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.简单选择排序法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.统计时间的函数：

16、#include large_integer t1, t2, feq; queryperformancefrequency(&feq); /每秒跳动次数queryperformancecounter(&t1); /测前跳动次数node * p = front-next; /要插入的节点的前驱queryperformancecounter(&t2); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： d next; /要

17、插入的节点的前驱while (p-next) node * s = front; /充分利用带头结点的单链表while (1) comparef+; if (p-next-data next-data) / p后继 比s后继 小则插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比较结束，且不需要插入 p = p-next; break; 问题二：如何将书上以数组方式储存的树转化为链表储存并进行操作？原本打算建立一颗完全二叉树储存相应数据再进行排序，但是那样的话需要新设置结点存左孩子右孩子，比较麻烦容易出错，所以选择了利用get(int i)

18、函数将筛选结点的位置获得。与书上代码相比修改如下：if (jdataget(j + 1)-data) j+; if (get(i)-data data) break; else turn(get(i), get(j); i = j; j = 2 * i; 问题三：时间如何精确至微秒？需要调用函数，这个问题是上网查找解决的。总结： 解决了以上的问题后代码就比较完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。附录：完整代码如下：#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 正序数列： ; 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逆序数列： ; 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 #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); /构造linklist(); void insert(node*p, node*s); /插入void turn(node*p, node*s); /交换数据void print(); /输出void insertsort(); /插入排序void bubblesort();

22、/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( int a, int n) front = new node; front-next = null ; for (int i = n - 1; i = 0; i-) node *

23、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(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) /交换数据 int temp = p-data; p-data = s-data; s-data = temp; movef += 3; voidlinklist :print() /输出需要显示的内容 node * p = front-next; while (p) cout data next; cout next; /要插入的节点的前驱while (p-next) node * s = front; /充分利用带头结点的单链表while (1) comparef+; if (p-next-d

25、ata next-data) / p后继 比s后继 小则插入 insert(p, s); break; s = s-next; if (s = p) /若一趟比较结束，且不需要插入 p = p-next; break; queryperformancecounter(&t2); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： d next = e | b = e) /排序完成return; node * qianqu = b; /轴

26、点前驱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); qianqu = qianqu-next; else p = p-next; qsz(b, qianqu); /继续处理轴点左侧链表qsz(qianqu-next, e); /继续处理轴点右侧链表 void linklist :

27、qsort() large_integer t1, t2, feq; queryperformancefrequency(&feq); /每秒跳动次数queryperformancecounter(&t1); /测前跳动次数node * e = front; while (e-next) e = e-next; qsz(front, e); queryperformancecounter(&t2); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/

28、时间差秒cout 操作时间为： d 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 != 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); /测后跳动次数double d = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： 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); /测后跳动次数doubled = (double)t2.quadpart - (double)t1.quadpart) / ( double)feq.quadpart);/时间差秒cout 操作时间为： 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