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

-.z.1．实验要求实验目的:通过编程，学习、实现、比照各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。理解算法的主要思想及流程。实验内容：使用链表实现下面各种排序算法，并进展比拟。排序算法：1、插入排序2、冒泡排序〔改良型冒泡排序〕3、快速排序4、简单项选择择排序5、堆排序〔小根堆〕要求： 1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比拟上述排序算法中关键字的比拟次数和移动次数〔其中关键字交换计为3次移动〕。3、对于这三类数据，比拟上述排序算法中不同算法的执行时间，准确到微秒〔选作〕4、对2和3的结果进展分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性代码要求：1、必须要有异常处理，比方删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2.程序分析通过排序算法将单链表中的数据进展由小至大〔正向排序〕2.1存储构造……单链表存储数据：……structnode{intdata;node*ne*t;};单链表定义如下：classLinkList{private:node*front;public: LinkList(inta[],intn); //构造 ~LinkList();voidinsert(node*p,node*s); //插入voidturn(node*p,node*s); //交换数据voidprint(); //输出voidInsertSort(); //插入排序voidBubbleSort(); //pos冒泡voidQSort(); //快速排序voidSelectSort(); //简单项选择择排序node*Get(inti);//查找位置为i的结点voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的递归主体voidheapsort(intn);//堆排序算法};关键算法分析：1.直接插入排序：首先将待排序数据建立一个带头结点的单链表。将单链表划分为有序区和无序区，有序区只包含一个元素节点，依次取无序区中的每一个结点，在有序区中查找待插入结点的插入位置，然后把该结点从单链表中删除，再插入到相应位置。分析上述排序过程，需设一个工作指针p->ne*t在无序区中指向待插入的结点，在找到插入位置后，将结点p->ne*t插在结点s和p之间。voidLinkList::InsertSort() //将第一个元素定为初始有序区元素，由第二个元素开场依次比拟{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->ne*t; //要插入的节点的前驱while(p->ne*t) {node*s=front;//充分利用带头结点的单链表while(1) { paref++;if(p->ne*t->data<s->ne*t->data) //[P后继]比[S后继]小则插入 { insert(p,s);break; } s=s->ne*t;if(s==p) //假设一趟比拟完毕，且不需要插入 { p=p->ne*t;break; } } } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}2.快速排序：主要通过轴值将数据从两端向中间进展比拟，交换以实现排序。通过递归的调用来实现整个链表数据的排序。代码中选用了第一个元素作为轴值。一趟排序的代码：voidLinkList::QSZ(node*b,node*e){if(b->ne*t==e||b==e) //排序完成return;node*qianqu=b; //轴点前驱node*p=qianqu->ne*t;while(p!=e&&p!=e->ne*t) { paref++;if(qianqu->ne*t->data>p->ne*t->data) //元素值小于轴点值，则将该元素插在轴点之前 {if(p->ne*t==e) //假设该元素为e，则将其前驱设为ee=p; insert(p,qianqu); qianqu=qianqu->ne*t; }elsep=p->ne*t; } QSZ(b,qianqu); //继续处理轴点左侧链表 QSZ(qianqu->ne*t,e); //继续处理轴点右侧链表}整个快速排序的实现:voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*e=front;while(e->ne*t) { e=e->ne*t; } QSZ(front,e); QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}3.改良版的冒泡排序：通过设置pos来记录无序边界的位置以减少比拟次数。将数据从前向后两两比拟，遇到顺序不对是直接交换两数据的值。每交换一次movef+3；voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->ne*t;while(p->ne*t) //排序查找无序边界 { paref++;if(p->data>p->ne*t->data) turn(p,p->ne*t); p=p->ne*t; }node*pos=p;p=front->ne*t;while(pos!=front->ne*t) {node*bound=pos; pos=front->ne*t;while(p->ne*t!=bound) { paref++;if(p->data>p->ne*t->data) { turn(p,p->ne*t);pos=p->ne*t; } p=p->ne*t; } p=front->ne*t; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}4.选择排序：每趟排序再待排序的序列中选择关键码最小的元素，顺序添加至已排好的有序序列最后，知道全部记录排序完毕。voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*s=front;while(s->ne*t->ne*t) {node*p=s;node*inde*=p;while(p->ne*t) { paref++;if(p->ne*t->data<inde*->ne*t->data)inde*=p; p=p->ne*t; } insert(inde*,s); s=s->ne*t; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}5.堆排序：利用前一趟比拟的结果来减少比拟次数，提高整体的效率。其中通过链表储存了一棵树。选择使用小根堆进展排序。voidLinkList::sift(intk,intm){inti=k,j=2*i;while(j<=m) { paref++;if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; } }}voidLinkList::heapsort(intn){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数for(inti=n/2;i>=1;i--) sift(i,n);for(inti=1;i<n;i++) { turn(Get(1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}其中堆排序中需要知道孩子节点和父亲节点处的值，故设置了函数获取i出的指针。node*LinkList::Get(inti){node*p=front->ne*t;intj=1;while(j!=i&&p) { p=p->ne*t; j++; }if(!p)throw"查找位置非法";elsereturnp;};6.输出结果的函数：voidtell(LinkList&a,LinkList&b,LinkList&c,LinkList&d,LinkList&e){a.print(); paref=0;movef=0;a.InsertSort(); cout<<"排序结果：";a.print(); cout<<"1.插入排序法：pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;b.BubbleSort(); cout<<"2.改良型冒泡排序法：pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;c.QSort(); cout<<"3.快速排序法：pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;d.SelectSort(); cout<<"4.简单项选择择排序法pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl; paref=0;movef=0;e.heapsort(10); cout<<"5.堆排序算法pare："<<setw(3)<<paref<<";Move："<<setw(3)<<movef<<endl;}7.统计时间的函数：#include<windows.h>{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->ne*t; //要插入的节点的前驱QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((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.流程图开场：开场初始化正序链表，调用各类排序，并输出运行结果初始化正序链表，调用各类排序，并输出运行结果初始化逆序链表，调用各类排序，并输出运行结果初始化逆序链表，调用各类排序，并输出运行结果初始化顺序随机的链表，调用各类排序，并输出运行结果初始化顺序随机的链表，调用各类排序，并输出运行结果结束结束2.测试条件：如果需要对不同的正序，逆序随机序列进展排序，则需要在main函数中进展初始化设置。3.测试结论：4.总结通过这次实验我再次复习了链表的建立及相应的操作，对各类排序算法的实现也有了新的理解，在调试过程中出现了许多问题也花费了很多时间和精力去逐步解决，最后程序运行成功的瞬间真的很开心。问题一：直接插入排序中假设是使用从后向前比拟插入的话〔即书上的方法〕难以找到该节点的前驱节点，不方便进展操作，所以最后采用了从前向后进展比拟。voidLinkList::InsertSort() //将第一个元素定为初始有序区元素，由第二个元素开场依次比拟{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->ne*t; //要插入的节点的前驱while(p->ne*t) {node*s=front; //充分利用带头结点的单链表while(1) { paref++;if(p->ne*t->data<s->ne*t->data) //[P后继]比[S后继]小则插入 { insert(p,s);break; } s=s->ne*t;if(s==p) //假设一趟比拟完毕，且不需要插入 { p=p->ne*t;break; } } }问题二：如何将书上以数组方式储存的树转化为链表储存并进展操作？原本打算建立一颗完全二叉树储存相应数据再进展排序，但是那样的话需要新设置结点存左孩子右孩子，比拟麻烦容易出错，所以选择了利用Get(inti)函数将筛选结点的位置获得。与书上代码相比修改如下：if(j<m&&(Get(j)->data>Get(j+1)->data))j++;if(Get(i)->data<Get(j)->data)break;else { turn(Get(i),Get(j)); i=j; j=2*i; }问题三：时间如何准确至微秒？需要调用函数，这个问题是上网查找解决的。总结：解决了以上的问题后代码就比拟完整了，可是还是希望通过日后的学习能将算法编写得更完善，灵活，简捷。附录：完整代码如下：#include"lianbiaopai*u.h"#include<windows.h>usingnamespacestd;voidmain(){inta[10]={1,2,3,4,5,6,7,8,9,10};LinkListzheng*u1(a,10),zheng*u2(a,10),zheng*u3(a,10),zheng*u4(a,10),zheng*u5(a,10); cout<<"正序数列："; tell(zheng*u1,zheng*u2,zheng*u3,zheng*u4,zheng*u5);intb[10]={10,9,8,7,6,5,4,3,2,1};LinkListni*u1(b,10),ni*u2(b,10),ni*u3(b,10),ni*u4(b,10),ni*u5(b,10); cout<<"\n逆序数列："; tell(ni*u1,ni*u2,ni*u3,ni*u4,ni*u5);intc[10]={2,6,10,5,8,3,9,1,4,7};LinkListsuiji1(c,10),suiji2(c,10),suiji3(c,10),suiji4(c,10),suiji5(c,10); cout<<"\n随机数列："; tell(suiji1,suiji2,suiji3,suiji4,suiji5);}#include<iostream>#include<stdio.h>#include<stdlib.h>#include<time.h>#include<iomanip>#include<windows.h>usingnamespacestd;intparef;intmovef;structnode{intdata;node*ne*t;};classLinkList{private:node*front;public: LinkList(inta[],intn); //构造 ~LinkList();voidinsert(node*p,node*s); //插入voidturn(node*p,node*s); //交换数据voidprint(); //输出voidInsertSort(); //插入排序voidBubbleSort(); //pos冒泡voidQSort(); //快速排序voidSelectSort(); //简单项选择择排序node*Get(inti);//查找位置为i的结点voidsift(intk,intm);//一趟堆排序voidLinkList::QSZ(node*b,node*e);//快速排序的递归主体voidheapsort(intn);//堆排序算法};LinkList::LinkList(inta[],intn){ front=newnode; front->ne*t=NULL;for(inti=n-1;i>=0;i--) {node*p=newnode;//新节点 p->data=a[i]; p->ne*t=front->ne*t; front->ne*t=p;//头插法建立单链表，最先参加的被不断后移 }}LinkList::~LinkList(){node*q=front;while(q) { front=q; q=q->ne*t;deletefront; }}voidLinkList::insert(node*p,node*s)//将p->ne*t插入s和s->ne*t之间{node*q=p->ne*t;p->ne*t=p->ne*t->ne*t; q->ne*t=s->ne*t;s->ne*t=q; movef++;}voidLinkList::turn(node*p,node*s) //交换数据{inttemp=p->data;p->data=s->data;s->data=temp; movef+=3;}voidLinkList::print() //输出需要显示的内容{node*p=front->ne*t;while(p) { cout<<p->data<<''; p=p->ne*t; } cout<<endl;}voidLinkList::InsertSort() //将第一个元素定为初始有序区元素，由第二个元素开场依次比拟{LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->ne*t; //要插入的节点的前驱while(p->ne*t) {node*s=front; //充分利用带头结点的单链表while(1) { paref++;if(p->ne*t->data<s->ne*t->data) //[P后继]比[S后继]小则插入 { insert(p,s);break; } s=s->ne*t;if(s==p) //假设一趟比拟完毕，且不需要插入 { p=p->ne*t;break; } } } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidLinkList::QSZ(node*b,node*e){if(b->ne*t==e||b==e) //排序完成return;node*qianqu=b; //轴点前驱node*p=qianqu->ne*t;while(p!=e&&p!=e->ne*t) { paref++;if(qianqu->ne*t->data>p->ne*t->data) //元素值小于轴点值，则将该元素插在轴点之前 {if(p->ne*t==e) //假设该元素为e，则将其前驱设为ee=p; insert(p,qianqu); qianqu=qianqu->ne*t; }elsep=p->ne*t; } QSZ(b,qianqu); //继续处理轴点左侧链表 QSZ(qianqu->ne*t,e); //继续处理轴点右侧链表}voidLinkList::QSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*e=front;while(e->ne*t) { e=e->ne*t; } QSZ(front,e); QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidLinkList::BubbleSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*p=front->ne*t;while(p->ne*t) //排序查找无序边界 { paref++;if(p->data>p->ne*t->data) turn(p,p->ne*t); p=p->ne*t; }node*pos=p;p=front->ne*t;while(pos!=front->ne*t) {node*bound=pos; pos=front->ne*t;while(p->ne*t!=bound) { paref++;if(p->data>p->ne*t->data) { turn(p,p->ne*t);pos=p->ne*t; } p=p->ne*t; } p=front->ne*t; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}voidLinkList::SelectSort(){LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数node*s=front;while(s->ne*t->ne*t) {node*p=s;node*inde*=p;while(p->ne*t) { paref++;if(p->ne*t->data<inde*->ne*t->data) inde*=p; p=p->ne*t; } insert(inde*,s); s=s->ne*t; } QueryPerformanceCounter(&t2);//测后跳动次数doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为："<<d<<endl;}node*LinkList::Get(inti){node*p=front->ne*t;intj=1;while(j!=i&&p) { p=p->ne*t; j++; }if(!p)throw"查找位置非法";elsereturnp;}voidLinkList::sift(intk,intm){inti=k,j=