c++数据结构实验链表排序.docx
- 文档编号:11163983
- 上传时间:2023-05-29
- 格式:DOCX
- 页数:28
- 大小:119.85KB
c++数据结构实验链表排序.docx
《c++数据结构实验链表排序.docx》由会员分享,可在线阅读,更多相关《c++数据结构实验链表排序.docx(28页珍藏版)》请在冰点文库上搜索。
c++数据结构实验链表排序
1.实验要求
i.实验目的:
通过编程,学习、实现、对比各种排序算法,掌握各种排序算法的优劣,以及各种算法使用的情况。
理解算法的主要思想及流程。
ii.实验内容:
使用链表实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、冒泡排序(改进型冒泡排序)
3、快速排序
4、简单选择排序
5、堆排序(小根堆)
要求:
1、测试数据分成三类:
正序、逆序、随机数据
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性
iii.代码要求:
1、必须要有异常处理,比如删除空链表时需要抛出异常;
2、保持良好的编程的风格:
代码段与段之间要有空行和缩近
标识符名称应该与其代表的意义一致
函数名之前应该添加注释说明该函数的功能
关键代码应说明其功能
3、递归程序注意调用的过程,防止栈溢出
2.程序分析
通过排序算法将单链表中的数据进行由小至大(正向排序)
2.1存储结构
单链表存储数据:
structnode
{
intdata;
node*next;
};
单链表定义如下:
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);//堆排序算法
};
2.2关键算法分析:
1.直接插入排序:
首先将待排序数据建立一个带头结点的单链表。
将单链表划分为有序区和无序区,有序区只包含一个元素节点,依次取无序区中的每一个结点,在有序区中查找待插入结点的插入位置,然后把该结点从单链表中删除,再插入到相应位置。
分析上述排序过程,需设一个工作指针p->next在无序区中指向待插入的结点,在找到插入位置后,将结点p->next插在结点s和p之间。
voidLinkList:
:
InsertSort()//将第一个元素定为初始有序区元素,由第二个元素开始依次比较
{
LARGE_INTEGERt1,t2,feq;
QueryPerformanceFrequency(&feq);//每秒跳动次数
QueryPerformanceCounter(&t1);//测前跳动次数
node*p=front->next;//要插入的节点的前驱
while(p->next)
{
node*s=front;//充分利用带头结点的单链表
while
(1)
{
paref++;
if(p->next->data
{
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<<"操作时间为:
"< } 2.快速排序: 主要通过轴值将数据从两端向中间进行比较,交换以实现排序。 通过递归的调用来实现整个链表数据的排序。 代码中选用了第一个元素作为轴值。 一趟排序的代码: voidLinkList: : 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) { paref++; if(qianqu->next->data>p->next->data)//元素值小于轴点值,则将该元素插在轴点之前 { if(p->next==e)//若该元素为e,则将其前驱设为e e=p; insert(p,qianqu); qianqu=qianqu->next; } elsep=p->next; } QSZ(b,qianqu);//继续处理轴点左侧链表 QSZ(qianqu->next,e);//继续处理轴点右侧链表 } 整个快速排序的实现: voidLinkList: : QSort() { LARGE_INTEGERt1,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);//时间差秒 cout<<"操作时间为: "< } 3.改进版的冒泡排序: 通过设置pos来记录无序边界的位置以减少比较次数。 将数据从前向后两两比较,遇到顺序不对是直接交换两数据的值。 每交换一次movef+3; voidLinkList: : BubbleSort() { LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数 node*p=front->next; while(p->next)//排序查找无序边界 { paref++; 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) { paref++; if(p->data>p->next->data) { turn(p,p->next);pos=p->next; } p=p->next; } p=front->next; } QueryPerformanceCounter(&t2);//测后跳动次数 doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为: "< } 4.选择排序: 每趟排序再待排序的序列中选择关键码最小的元素,顺序添加至已排好的有序序列最后,知道全部记录排序完毕。 voidLinkList: : SelectSort() { LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数 node*s=front; while(s->next->next) { node*p=s; node*index=p; while(p->next) { paref++; if(p->next->data index=p; p=p->next; } insert(index,s); s=s->next; } QueryPerformanceCounter(&t2);//测后跳动次数 doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为: "< } 5.堆排序: 利用前一趟比较的结果来减少比较次数,提高整体的效率。 其中通过链表储存了一棵树。 选择使用小根堆进行排序。 voidLinkList: : sift(intk,intm) { inti=k,j=2*i; while(j<=m) { paref++; if(j if(Get(i)->data 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 { turn(Get (1),Get(n-i+1)); sift(1,n-i); } QueryPerformanceCounter(&t2);//测后跳动次数 doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为: "< } 其中堆排序中需要知道孩子节点和父亲节点处的值,故设置了函数获取i出的指针。 node*LinkList: : Get(inti) { node*p=front->next; intj=1; while(j! =i&&p) { p=p->next; 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: "< "< paref=0;movef=0; b.BubbleSort(); cout<<"2.改进型冒泡排序法: pare: "< "< paref=0;movef=0; c.QSort(); cout<<"3.快速排序法: pare: "< "< paref=0;movef=0; d.SelectSort(); cout<<"4.简单选择排序法pare: "< "< paref=0;movef=0; e.heapsort(10); cout<<"5.堆排序算法pare: "< "< } 7.统计时间的函数: #include { LARGE_INTEGERt1,t2,feq; QueryPerformanceFrequency(&feq);//每秒跳动次数 QueryPerformanceCounter(&t1);//测前跳动次数 node*p=front->next;//要插入的节点的前驱 QueryPerformanceCounter(&t2);//测后跳动次数 doubled=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart);//时间差秒 cout<<"操作时间为: "< }; 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->next;//要插入的节点的前驱 while(p->next) { node*s=front;//充分利用带头结点的单链表 while (1) { paref++; if(p->next->data { insert(p,s);break; } s=s->next; if(s==p)//若一趟比较结束,且不需要插入 { p=p->next;break; } } } 问题二: 如何将书上以数组方式储存的树转化为链表储存并进行操作? 原本打算建立一颗完全二叉树储存相应数据再进行排序,但是那样的话需要新设置结点存左孩子右孩子,比较麻烦容易出错,所以选择了利用Get(inti)函数将筛选结点的位置获得。 与书上代码相比修改如下: if(j if(Get(i)->data else { turn(Get(i),Get(j)); i=j; j=2*i; } 问题三: 时间如何精确至微秒? 需要调用函数,这个问题是上网查找解决的。 总结: 解决了以上的问题后代码就比较完整了,可是还是希望通过日后的学习能将算法编写得更完善,灵活,简捷。 附录: 完整代码如下: #include"lianbiaopaixu.h" #include usingnamespacestd; voidmain() { inta[10]={1,2,3,4,5,6,7,8,9,10}; LinkListzhengxu1(a,10),zhengxu2(a,10),zhengxu3(a,10),zhengxu4(a,10),zhengxu5(a,10); cout<<"正序数列: "; tell(zhengxu1,zhengxu2,zhengxu3,zhengxu4,zhengxu5); intb[10]={10,9,8,7,6,5,4,3,2,1}; LinkListnixu1(b,10),nixu2(b,10),nixu3(b,10),nixu4(b,10),nixu5(b,10); cout<<"\n逆序数列: "; tell(nixu1,nixu2,nixu3,nixu4,nixu5); 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 #include #include #include #include #include usingnamespacestd; intparef; intmovef; structnode { intdata; node*next; }; 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->next=NULL; for(inti=n-1;i>=0;i--) { node*p=newnode;//新节点 p->data=a[i]; p->next=front->next; front->next=p;//头插法建立单链表,最先加入的被不断后移 } } LinkList: : ~LinkList() { node*q=front; while(q) { front=q; q=q->next; deletefront; } } voidLinkList: : 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=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->next; while(p) { cout< p=p->next; } cout< } voidLinkList: : InsertS
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- c+ 数据结构 实验 排序