数据结构课程设计排序算法演示系统

1、各专业全套优秀毕业设计图纸计算机学院数据结构课程设计题 目：数据结构排序算法演示系统班 级：姓 名：学 号：同组人姓名：起迄日期:课程设计地点 :指导教师：评阅意见：成绩评定：评阅人：日期：完成日期： 2014 年 12 月目录一、课程设计的目的1二、设计内容和要求1三、数据采取的结构1四、功能模块详细设计14.1详细设计思想2冒泡排序5快速排序7直接插入排序9希尔排序10直接选择排序12堆排序14归并排序17五、总结或心得体会19六、参考文献 .20七、附录 .20一.设计目的随着计算机技术的发展， 各种排序算法不断的被提出。 排序算法在计算机科学中有非常重要的意义， 且应用很广泛。 在以后

2、的发展中排序对我们的学习和生活的影响会逐渐增大， 很有必要学习排序知识。 此次课程设计一方面使自己掌握排序的知识，另一方面锻炼一下团队合作开发系统的能力。二.设计内容和要求功能要求：(1) 界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。(2) 实现各种内部排序。包括直接插入排序，冒泡排序，直接选择排序，希尔排序，快速排序，堆排序，归并排序。(3) 待排序的元素的关键字为整数或（字符）。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数 ( 关键字交换以 3 次计) 。（ 1） 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表

3、，以便比较各种排序的优劣。三.本设计所采用的数据结构typedef structint key;RecType;四. 功能模块详细设计排序算法演示系统冒快直希直堆归泡速接尔接排并排排插排选序排序序入序择序排排序序- 1 -4.1 详细设计思想主函数：#include<stdio.h>#include<stdlib.h>#include <math.h>#define L 8/排序元素个数#define FALSE 0#define TRUE 1typedef structint key;RecType;RecType RL;int num;int sum;i

4、nt sun;/定义排序趟数的全局变量/系统主界面/主函数int main()RecType S100;int i,k;char ch1,ch2,q;printf("ntt*排序 算法 演示 系统 *nntt请输入 %d 个待排序的数据： n",L);for(i=1;i<=L;i+)printf("tt 请输入第 %dth 数据 :",i);scanf("%d",&Si.key);getchar();ch1='y'while(ch1='y')printf("ntt菜单n"

5、;);printf("ntt*n");printf("ntt * 1-更新排序数据 * 2- 直接插入排序n");printf("ntt * 3-希 尔排序*4- 冒 泡排 序n");printf("ntt * 5-快 速排序*6- 直接选择排序n");printf("ntt * 7-堆 排序 * 8- 归 并排 序n");printf("ntt *0-退出*n");printf("ntt*n");- 2 -printf("ntt 请选择 :&q

6、uot;);scanf("%c",&ch2);getchar();for(i=1;i<=L;i+)Ri.key=Si.key;switch(ch2)case '1':printf("ntt 请输入 %d 个待排序数据 ntt",L);for(i=1;i<=L;i+)scanf("%d",&Si.key);getchar();printf("tt");printf("ntt 数据输入完毕！ ");break;case '2':Insert

7、sort();break;case '3':Shellsort();break;case '4':Bubblesort();break;case '5':printf("ntt 原始数据为（按回车键开始排序）：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");num=0;sun=0;sum=0;Quicksort(1,L);printf("ntt 排序最终结果是： ntt");for

8、(k=1;k<=L;k+)printf("%5d",Rk.key);printf("ntt 比较次数是： %dntt",sum);- 3 -printf("ntt 交换次数是： %dntt",sun);break;case '6':Selectsort();break;case '7':Heap();break;case '8':Mergesort();break;case '0':ch1='n'break;default:system("

9、cls");/清屏printf("ntt 对不起，您输入有误，请重新输入！ n"); break;if(ch2!='0')if(ch2='2'|ch2='3'|ch2='4'|ch2='5'|ch2='6'|ch2='7'|ch2='8')printf("nntt 排序完毕！ ");printf("ntt 按回车键继续！ ");q=getchar();if(q!='n')getcha

10、r();ch1='n'return 1;- 4 -图一 主界面冒泡排序核心思想依次比较相邻的两个数，将小数放在前面，大数放在后面，第一轮比较后，最大的数便被放到了最后；第二轮操作前 n-1 个数据（假设有 n 个数据），依然是依次比较相邻的两个数， 将小数放在前面， 大数放在后面， 倒数第二个数便是第二大的数；同理第 i 轮操作前 n-i+1 的数据（假设 i 取值是从 1 开始的），则 n-i+i 位置上的数据为第 i 大的数据。一共有 n-1 轮，第 i 轮比较中共比较 n-i 次比较。核心代码void Bubblesort()int i,j,k,x=0,y=0,m=0;i

11、nt exchange=TRUE;/标志位 exchange初始化为 TRUE 1printf("ntt 原始数据为（按回车键开始排序）：ntt");for(k=1;k<=L;k+)- 5 -printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<L&&exchange=TRUE;i+)/外层对总的循环次数执行次数exchange=FALSE;for(j=1;j<=L+1-i;j+) / 内层相邻记录的交换与比较 m+;/ 比较次数 + if(Rj.k

12、ey<Rj-1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/ 移动次数 +m-;/ 比较次数if(exchange)/输出语句printf("tt 第%d 趟冒泡排序的结果为：ntt",i);for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");printf("ntt 比较次数是： tt");printf("%d",m);pri

13、ntf("ntt 移动次数是： tt");printf("%d",y);printf("ntt 排序最终结果是： ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);- 6 -图二 直接插入排序快速排序核心思想首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据， 就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。通常分割点的数据是随机选取的。 这样无论你的数据是否已被排列过，你所分割成的两

14、个字列表的大小是差不多的。而只要两个子列表的大小差不多核心代码/递归算法实现void Quicksort(int low,int high)int i=low,j=high,k;R0.key=Rlow.key;while(i<j)while(i<j&&R0.key<=Rj.key)/右侧扫描j-;sum+;- 7 -if(i<j) Ri.key=Rj.key;/ 交换i+;sun+;while(i<j&&Ri.key<R0.key)/左侧扫描i+;sum+;if(i<j)Rj.key=Ri.key;/ 交换j-;sun+

15、;Ri.key=R0.key;num+;/输出语句包括排序的结果及次数printf("tt 第 %d 趟快速排序的结果为： ntt",num); for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");if(low<i-1) Quicksort(low,i-1);/ 递归部分 (左侧 ) if(j+1<high) Quicksort(j+1,high);/ 递归部分 (右侧 )图三 快速排序- 8 -直接插入排序核心思想经过 i-1遍处理后 ,L1.i-

16、1己排好序。第i 遍处理仅将Li插入 L1.i-1的适当位置，使得L1.i又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较 Li和 Li-1，如果 Li-1 Li，则 L1.i已排好序，第 i 遍处理就结束了；否则交换 Li与 Li-1的位置，继续比较 Li-1和 Li-2，直到找到某一个位置 j(1 j i-1) ，使得 LjLj+1时为止核心代码void Insertsort()int i,j,k,m=0,x=0; /初始化比较次数变量 m，移动次数变量 x printf("ntt 原始数据为：（按回车键开始排序） ntt"); for(k=1;k&

17、lt;=L;k+)printf("%5d",Rk.key);getchar();printf("n");/主要运行部分for(i=2;i<=L;i+)if(Ri.key<Ri-1.key)R0=Ri;j=i-1;while(R0.key<Rj.key)Rj+1=Rj;j-;Rj+1=R0;x+;m+;/输出语句包括排序的结果及次数- 9 -printf("tt 第%d 趟直接插入排序的结果为： ntt",m); for(k=1;k<=L;k+) printf("%5d",Rk.key);ge

18、tchar();printf("n");printf("n");printf("ntt 比较次数是： tt");printf("%d",m);printf("ntt 移动次数是： tt");printf("%d",x);printf("ntt 排序最终结果是： ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);图四 直接插入排序希尔排序核心思想先取一个小于 n 的整数 d1 作为第一个增量，把

19、文件的全部记录分成 d1 个组。所有距离为 dl 的倍数的记录放在同一个组中。先在各组内进-10-行直接插入排序；然后，取第二个增量d2<d1 重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l< <d2< d1) ，即所有记录放在同一组中进行直接插入排序为止。核心代码void Shellsort()int i,j,gap,x,k,y=0,m=0;/ 初始化比较次数变量m，移动次数变量yprintf("ntt原始数据为：（按回车键开始排序）ntt");for(k=1;k<=L;k+)printf("%5d",

20、Rk.key);getchar();printf("n");/函数主要部分gap=L/2;while(gap>0)for(i=gap+1;i<=L;i+)j=i-gap;while(j>0)if(Rj.key>Rj+gap.key)x=Rj.key;/ 交换语句Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;y+;/ 移动次数 +elsej=0;gap=gap/2;m+;/ 比较次数 +/ 输出语句包括排序的结果及次数printf("tt 第 %d 趟希尔排序的结果为： ntt",m); for(k=

21、1;k<=L;k+)-11-printf("%5d",Rk.key);getchar();printf("n");printf("ntt比较次数是：tt");printf("%d",m);printf("ntt移动次数是：tt");printf("%d",y);printf("ntt排序最终结果是：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n")

22、;图五希尔排序直接选择排序核心思想第一次从 R0Rn-1 中选取最小值，与 R0 交换，第二次从 R1Rn-1 中选取最小值， 与 R2 交换， . ， 第 i 次从 Ri-1Rn-1中选取最小值，与Ri-1交换， .，第 n-1 次从 Rn-2Rn-1中选取-12-最小值，与Rn-2 交换 , 总共通过n-1 次 , 得到一个按排序码从小到大排列的有序序列 .核心代码void Selectsort()int i,j,k,h,x=0,y=0;printf("ntt 原始数据为（按回车键开始排序）：ntt");for(k=1;k<=L;k+)printf("%

23、5d",Rk.key);getchar();printf("n");for(i=1;i<L;i+)h=i;for(j=i+1;j<=L;j+)x+;/比较次数if(Rj.key<Rh.key)h=j;/确定最小值if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=R0.key;y+;/ 移动次数printf("tt 第%d 趟选择排序的结果为：ntt",i);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf(&

24、quot;n");/输出语句包括排序的结果及次数printf("ntt 比较次数： %d",x);printf("ntt 移动次数： %d",y);printf("ntt 排序最终结果是： ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");-13-图六 选择排序堆排序核心思想堆排序是一树形选择排序，在排序过程中，将 R1.N 看成是一颗完全二叉树的顺序存储结构， 利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小

25、的元素。将原始记录序列建成一个堆，成为初始堆，并输出堆顶元素；调整剩余的记录序列，使之成为一个新堆，再输出堆顶元素；如此反复进行，当堆中只有一个元素时， 整个序列的排序结束， 输出的序列便是原始序列的非递减有序序列。在堆排序的过程中， 主要负责两方面的工作： 一是如何将原始记录序列构造成一个堆， 即建立初始堆； 二是输出堆顶元素后， 如何将剩余记录整理成一个新堆。核心代码void CreateHeap(int root,int index,int *x,int *y)int j,temp,finish;j=2*root; /j 指向左孩子 temp=Rroot.key;finish=0;whi

26、le(j<=index&&finish=0)if(j<index)if(Rj.key<Rj+1.key)-14-j+;/ 指向较大的孩子if(temp>=Rj.key)finish=1;elseRj/2.key=Rj.key;(*y)+;j=j*2;*x = *x+2;Rj/2.key=temp;(*y)+;/ 堆排序void Heapsort()int i,j,temp,k,x=0,y=0;for(i=(L/2);i>=1;i-)/ 建立初始堆CreateHeap(i,L,&x,&y);x=0;y=0;for(i=L-1,k=1;

27、i>=1;i-,k+)/ 将堆中根节点和最后一个节点交换temp=Ri+1.key;Ri+1.key=R1.key;R1.key=temp;CreateHeap(1,i,&x,&y);printf("tt第 %d 趟堆排序的结果为：ntt",k);for(j=1;j<=L;j+)printf("%5d",Rj.key);getchar();printf("n");printf("ntt比较次数是：%dtt",x);-15-printf("ntt移动次数是：%dtt",

28、y);void Heap()int i;printf("ntt原始数据为（按回车键开始排序）：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);getchar();printf("n");Heapsort();printf("ntt排序最终结果是：ntt");for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");void Merge(int low,int mm,int high,in

29、t *x,int *y)/两个有序序列的合并int i=low,j=mm+1,p=0;RecType *R1;/i 对第一个开始到结尾，j 从第二个开始到结尾R1=new RecTypehigh-low+1;if(!R1)printf(" 内存不足！ ");while(i<=mm&&j<=high)/两序列从起始位置开始将小的元素放入到R1中R1p+=(Ri.key<=Rj.key)?Ri+:Rj+;(*x)+;(*y)+;while(i<=mm)/第二段结束，剩余放入R1 中R1p+=Ri+;(*y)+;while(j<=hi

30、gh)/第二段剩余，剩余放入R1 中R1p+=Rj+;-16-(*y)+;for(p=0,i=low;i<=high;p+,i+)/剩余元素放入R1 中 ,赋予 RRi=R1p;(*y)+;图七堆排序归并排序核心思想将有 n 个记录的原始序列看作n 个有序子序列， 每个子序列的长度为1，然后从第一个子序列开始，把相邻的子序列两两合并，得到n/2个长度为2 或 1 的子序列（当子序列个数为奇数时，最后一组合并得到的序列长度为1），把这一过程称为一次归并排序，对第一次归并排序后的n/2个子序列采用上述方法继续顺序成对归并，如此重复，当最后得到的长度为n 的一个子序列时，该子序列便是原始序列归

31、并排序后的有序序列。核心代码void MergePass(int length,int *x,int *y)/一次二路归并排序 int i;-17-for(i=1;i+2*length-1<=L;i=i+2*length)Merge(i,i+length-1,i+2*length-1,x,y); /函数调用if(i+length-1<L)Merge(i,i+length-1,L,x,y);/ 函数调用/ 归并排序void Mergesort() / 二路归并排序 int length,k,m=0,i,x=0,y=0;printf("ntt 原始数据为（按回车键开始排序）：

32、 ntt"); for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");for(length=1;length<L;length*=2) MergePass(length,&x,&y);m+; / 输出语句包括排序的结果及次数printf("tt 第 %d 趟归并排序的结果为： ntt",m); for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf(&q

33、uot;n");printf("ntt 排序最终结果是： ntt"); for(i=1;i<=L;i+) printf("%5d",Ri.key);-18-printf("n");printf("tt比较次数： %dn",x);printf("tt移动次数： %dn",y);图八归并排序五. 总结或心得回顾这个设计过程 , 我学到了许多书本上没有学到的知识。通过这次小组制作的程序 , 丰富了自己的实践技能 , 扩展了本专业的知识面 , 使我受益非浅 , 同时也体验到了搞软件开发的

34、困难度。在这次设计的同时我又从中学到了许多东西。但由于我对这样的排序系统还只是一个开始， 了解的不多，这其中或许还有很多的不足 , 在这里也恳请各位老师能够对我们的作品指明不足并加以改正。总之，在这一次的课程设计过程中， 我们查阅了大量的资料， 对数据结构有了一点初步的认识，对于网络工程这些辅助性的教材也巩固了不少， 为我们这次的课设提供了很大的帮助，锻炼了我们的能力 , 让我更加熟练了这门程序设计语言： C/C+ 语言，系统地学习了数据结构方面的知识，并更进一步提高了我们在程序设计、调试方面的技巧。更重要的是，它还让我们认识到了自己的不足，在编程方面，我仅仅是刚刚入门而已， 以后的道路任重道

35、远， 需要我不断的丰富自己、 充实自-19-己，这样才能在程序设计方面有所收获。在最后也感谢我们的小组成员, 我在他的帮忙下顺利的做好自己负责的部分.六参考文献严蔚敏 , 吴伟明 , 数据结构 (C 语言版 ) , 清华大学出版社 ,2007 年:P263-P288 。七附录#include<stdio.h>#include<stdlib.h>#include <math.h>#define L 8/排序元素个数#define FALSE 0#define TRUE 1typedef structint key;RecType;RecType RL;int

36、num;int sum;int sun;/定义排序趟数的全局变量/系统主界面void Bubblesort()int i,j,k,x=0,y=0,m=0;int exchange=TRUE;/标志位 exchange初始化为 TRUE 1 printf("ntt 原始数据为（按回车键开始排序）： ntt"); for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<L&&exchange=TRUE;i+)/外层对总的循环次数执

37、行次数exchange=FALSE;for(j=1;j<=L+1-i;j+) / 内层相邻记录的交换与比较 m+;/ 比较次数 + if(Rj.key<Rj-1.key)-20-R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/ 移动次数 +m-;/ 比较次数if(exchange)/输出语句printf("tt 第%d 趟冒泡排序的结果为：ntt",i);for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();prin

38、tf("n");printf("ntt 比较次数是： tt");printf("%d",m);printf("ntt 移动次数是： tt");printf("%d",y);printf("ntt 排序最终结果是： ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);/递归算法实现void Quicksort(int low,int high)int i=low,j=high,k;R0.key=Rlow.key;wh

39、ile(i<j)while(i<j&&R0.key<=Rj.key)/右侧扫描j-;sum+;if(i<j) Ri.key=Rj.key;/ 交换 i+;sun+;-21-while(i<j&&Ri.key<R0.key)/左侧扫描i+;sum+;if(i<j)Rj.key=Ri.key;/ 交换j-;sun+;Ri.key=R0.key;num+;/输出语句包括排序的结果及次数printf("tt 第 %d 趟快速排序的结果为： ntt",num); for(k=1;k<=L;k+) prin

40、tf("%5d",Rk.key);getchar();printf("n");if(low<i-1) Quicksort(low,i-1);/ 递归部分 (左侧 ) if(j+1<high) Quicksort(j+1,high);/ 递归部分 (右侧 )void Insertsort()int i,j,k,m=0,x=0; /初始化比较次数变量 m，移动次数变量 x printf("ntt 原始数据为：（按回车键开始排序） ntt"); for(k=1;k<=L;k+)printf("%5d",

41、Rk.key);getchar();printf("n");/主要运行部分for(i=2;i<=L;i+)if(Ri.key<Ri-1.key)R0=Ri;j=i-1;while(R0.key<Rj.key)Rj+1=Rj;-22-j-;Rj+1=R0;x+;m+;/输出语句包括排序的结果及次数printf("tt 第%d 趟直接插入排序的结果为： ntt",m); for(k=1;k<=L;k+) printf("%5d",Rk.key);getchar();printf("n");pri

42、ntf("n");printf("ntt 比较次数是： tt");printf("%d",m);printf("ntt 移动次数是： tt");printf("%d",x);printf("ntt 排序最终结果是： ntt");for(i=1;i<=L;i+) printf("%5d",Ri.key);void Shellsort()int i,j,gap,x,k,y=0,m=0; /初始化比较次数变量 m，移动次数变量 y printf("

43、;ntt 原始数据为：（按回车键开始排序） ntt"); for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/函数主要部分gap=L/2;while(gap>0)for(i=gap+1;i<=L;i+)j=i-gap;while(j>0)if(Rj.key>Rj+gap.key)-23-x=Rj.key;/ 交换语句Rj.key=Rj+gap.key;Rj+gap.key=x;j=j-gap;y+;/ 移动次数 +elsej=0;gap=gap/2

44、;m+;/比较次数 +/输出语句包括排序的结果及次数printf("tt 第%d 趟希尔排序的结果为： ntt",m);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");printf("ntt 比较次数是： tt");printf("%d",m);printf("ntt 移动次数是： tt");printf("%d",y);printf("ntt 排序最终结果是： ntt&

45、quot;);for(i=1;i<=L;i+)printf("%5d",Ri.key);printf("n");void Selectsort()int i,j,k,h,x=0,y=0;printf("ntt 原始数据为（按回车键开始排序）： ntt"); for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();-24-printf("n");for(i=1;i<L;i+)h=i;for(j=i+1;j<=L;j+)x+;/比较次数if(Rj.key<Rh.key)h=j;/确定最小值if(h!=i)R0.key=Ri.key;Ri.key=Rh.key;Rh.key=R0.key;y+;/ 移动次数printf("tt 第%d 趟选择排序的结果为： ntt",i);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");/输出语句包括