《数据结构实验9：排序子系统.docx》由会员分享，可在线阅读，更多相关《数据结构实验9：排序子系统.docx（26页珍藏版）》请在三一办公上搜索。
1、实验9 :排序子系统1. 实验目的（1）掌握常用排序方法的基本思想。（2）通过实验加深理解各种排序算法。（3）通过实验掌握各种排序方法的时间复杂度分析。（4）了解各种排序方法的优缺点及适用范围。2. 实验内容（1）编写直接插入排序程序。（2）编写希尔排序程序。（3）编写冒泡排序程序。（4）编写快速排序程序。（5）编写选择排序程序。（6）编写归并排序程序。（7）编写堆排序程序。（8）程序执行时，要求能显示每一趟的排序结果。（9）设计一个选择式菜单，以菜单方式选择上述排序程序。排序子系统“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个*1更
2、新排序数据*2直接插入排序*3-希尔排序*4冒泡排序*5快 速 排 序*6选 择 排 序*7归 并 排 序*8堆 排 序*0返回* 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请选择菜单号（0-8）：3. 实验程序#include#include#include#define L 8#define FALSE 0#define TURE 1typedef structint key;char otherinfo;RecType;typedef RecType SeqlistL+1;int num;Seqlist R;void Inser
3、tsort();void Bubblesort();void QuickSort(int low,int high);void Shellsort();void Selectsort();void Mergesort();int Partition(int i,int j);void Heap();void main()Seqlist S;int i,k;char ch1,ch2,q;printf(nt请输A%d个待排序数据(按【Enter】键分隔)：nt,L);for(i=1;i=L;i+)scanf(%d”,&Si.key);getchar();printf(t)；printf(nt排序数
4、据已经输入完毕！)；ch1=y;while(ch1=，y，|ch1=，Y，)printf(n)；printf(ntt排序子系统);printf(ntt*);printf(ntt*1更新排序数据*);printf(ntt*2直接插入排序*);printf(ntt*3希 尔 排序*);printf(ntt*4冒泡 排序*);printf(ntt*5快 速 排序*);printf(ntt*)；printf(ntt*7printf(ntt*)；printf(ntt*)；6-选择排序归并排序*）；8-堆排序0返 回printf(ntt*);printf(ntt请选择菜单号(0-8)：);scanf(%c
5、”,&ch2);getchar();for(i=1;i=L;i+)Ri.key=Si.key;switch(ch2)case 1:printf(nt请输A%d个待排序数据(按【Enter】键分隔)：nt,L);for(i=1;i=L;i+)scanf(%d”,&Si.key);getchar();printf(t)；printf(nt排序数据已经输入完毕！)； break;case 2:Insertsort();break;case 3:Shellsort();break;case 4:Bubblesort();break;case 5:printf(nt原始数据为(按【Enter】键开始排序
6、)：)； for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；num=0;QuickSort(1,L);printf(nt排序的最终结果是：)；for(k=1;k=L;k+)printf(%5d”,Rk.key);printf(n);break;case 6:Selectsort();break;case 7:Mergesort();break;case 8:Heap();break;case 0:ch1=n;break;default:printf(nt 输入出错！);if(ch2!=0)if(ch2=,2,|ch2=，3，|ch2=
7、,4,|ch2=，5，|ch2=，6，|ch2=，7，|ch2=，8，)printf(nt排序输出完毕！)；printf(nnt按回车键返回。)；q=getchar();if(q!=，xA，)getchar();ch1=，n，;void Insertsort()int i,j,k,m=0;printf(nt原始数据为(按【Enter】键开始排序)：)；for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；for(i=2;i=L;i+)if(Ri.keyRi-1.key)R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1
8、=Rj;j-;Rj+1=R0;m+;printf(t第d趟排序结果为(按【Enter】键继续)：”,m);for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；printf(nt排序的最终结果是：)；for(i=1;i=L;i+)printf(%5d”,Ri.key);printf(n)；void Shellsort()int i,j,gap,x,m=0,k;printf(nt原始数据为(按【Enter】键开始排序)：)；for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+gap.key)x=Rj.key;Rj.k
9、ey=Rj+gap.key;Rj+gap.key=x;j=j-gap;elsej=0;gap=gap/2;m+;printf(t第d趟排序结果为(按【Enter】键继续)：”,m);for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；printf(nt排序的最终结果是：)；for(i=1;i=L;i+)printf(%5d”,Ri.key);printf(n)；void Bubblesort()int i,j,k;int exchange;printf(nt原始数据为(按【Enter】键开始排序)：)；for(k=1;k=L;k+)pr
10、intf(%5d”,Rk.key);getchar();printf(n)；for(i=1;i=i+1;j-)if(Rj.keyRj-1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TURE;if(exchange)printf(t第d趟排序结果为(按【Enter】键继续)：，i);for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；printf(nt排序的最终结果是：)；for(i=1;i=L;i+)printf(%5d”,Ri.key);printf(n)；i
11、nt Partition(int i,int j)RecType pirot=Ri;while(ij)while(i=pirot.key)j-;if(ij)Ri+=Rj;while(ij&Rj.key=pirot.key)i+；if(ij)Rj-=Ri;Ri=pirot;return i;void QuickSort(int low,int high)int pirotpos,k;if(lowhigh)pirotpos=Partition(low,high);num+;printf(t第%d趟排序结果为(按【Enter】键继续)：”,num);for(k=1;k=L;k+)printf(%5d
12、”,Rk.key);getchar();printf(n)；QuickSort(low,pirotpos-1);QuickSort(pirotpos+1,high);void Selectsort()int i,j,k,h;printf(nt原始数据为(按【Enter】键开始排序)：)；for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；for(i=1;i=L;i+)h=i;for(j=i+1;j=L;j+)if(Rj.keyRh.key)h=j;if(h!=j)R0=Ri;Ri=Rh;Rh=R0;printf(t第d趟排序结果为(按【
13、Enter】键继续)：，i);for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；printf(nt排序的最终结果是：)；for(i=1;i=L;i+)printf(%5d”,Ri.key);printf(n)；void Merge(int low,int mm,int high)int i=low,j=mm+1,p=0;RecType *R1;R1=(RecType *)malloc(high-low+1)*sizeof(RecType);if(!R1)printf(nt内存容量不够！);while(i=mm&j=high)R1p+
14、= (Ri.key=Rj.key)?Ri+:Rj+;while(i=mm)R1p+=Ri+;while(i=high)R1p+=Rj+;for(p=0,i=low;i=high;p+,i+)Ri=R1p;void MergePass(int length)int i;for(i=1;i+2*length-1=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1);if(i+length-1L)Merge(i,i+length-1,L);void Mergesort()int length,k,m=0;printf(nt原始数据为(按【Enter】键开始排
15、序)：);for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；for(length=1;lengthL;length*=2)MergePass(length);m+;printf(t第d趟排序结果为(按【Enter】键继续)：”,m);for(k=1;k=L;k+)printf(%5d”,Rk.key);getchar();printf(n)；printf(nt排序的最终结果是：)；for(k=1;k=L;k+)printf(%5d”,Rk.key);printf(n)；void CreateHeap(int root,int inde
16、x)int j,temp,finish;j=2*root;temp=Rroot.key;finish=0;while(j=index&finish=0)if(jindex)if(Rj.key=Rj.key)finish=1;elseRj/2.key=Rj.key;j=j*2;Rj/2.key=temp;void HeapSort()int i,j,temp,k;for(i=(L/2);i=1;i-)CreateHeap(i,L);for(i=L-1,k=1;i=1;i-,k+)temp=Ri+1.key;Ri+1.key=R1.key;R1.key=temp;CreateHeap(1,i);p
17、rintf(t 第%d趟排序结果为(按【Enter】键继续)：,k);for(j=1;j=L;j+)printf(%5d,Rj.key);getchar();printf(n)；void Heap()int i;printf(nt原始数据为(按【Enter】键开始排序)：);for(i=1;i=L;i+)printf(%5d,Ri.key);printf(nt)；getchar();HeapSort();printf(nt排序的最终结果是：)；for(i=1;i、l 74J- - 7 更直希真选归堆返 _请选择菜单号（0-8）, 42原始数据为（按”局心】键开始排序），8679216第1趟排序
18、结果为（按Enter】键继续）:186?16第2趟排序结果为（按Enter键继续）:128616第3趟排序结果为（按EnterJ键继续）:12?16第4趟排序结果为（按Enter键继续）:12?92弟5趟排序结果为（按【Enter】键继续）:12?92第6趟排序结果为（按Enter键继续）:12?排序的最终结果是：127 141516865552611415922147921486149214861514158614151692排序输出完毕!按回车键返回。排序子系统，D:皿律文档教育学习据结魅证性实赫DeHug,实触10 :排序子秦貌归妃ff.ff.lJTJ?.lJT回清讹择菜单号(LJ-B)
19、: UPress mnv 1蛀察 Izn cunt:inue。咬帷文档教育学习据结构睑证性史科Debug、实腕10 :排序子索毓孙b排序子系统1224567N-0,h.f _TJ1-I速择开日更直希日属选也逝请选择英单号(w-) : aany key to continue5.突验小结这次试验，我也和以前一样把代码打完运行之后运行找错，结果又有错误了，两个地方 漏了“；”，一运行就提示我错误信息，在我改正之后才能够顺利运行程序代码。这次试验，我也遇到了很奇怪的问题，菜单中的第七个选项无法运行，以选择“7”就 会弹出一个框框，让我“调试程序”活着“退出程序”的错误提示。所以就直接关了后重新 运行了一次，重新运行后就没有去选择7,其他的试过，能很好地给出我要的结果。我想， 会不会是因为我的系统是Win7的关系，才会出现这种提示嘛！？就算不是也无所谓了，归 并排序也不是我们要考试的，我们主要掌握直接插入排序、希尔排序和冒泡排序就行了老师 说，我也就没多想什么。这章主要讲的是排序，排序是将数据的任意序列，重新排列成一个按关键字有序排列的 序列，整过过程全部在内存进行的排序称为内排序。
