数据结构课程设计-排序算法演示系统.doc
《数据结构课程设计-排序算法演示系统.doc》由会员分享,可在线阅读,更多相关《数据结构课程设计-排序算法演示系统.doc(34页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、各专业全套优秀毕业设计图纸计算机学院数据结构课程设计题 目:数据结构排序算法演示系统 班 级: 姓 名: 学 号: 同组人姓名: 起 迄 日 期: 课程设计地点: 指导教师: 评阅意见:成绩评定:评阅人: 日期:完成日期:2014年12月目录一、课程设计的目的1二、设计内容和要求1三、数据采取的结构1四、功能模块详细设计14.1 详细设计思想24.1.1 冒泡排序54.1.2 快速排序74.1.3 直接插入排序94.1.4 希尔排序104.1.5 直接选择排序12 4.1.6 堆排序14 4.1.7归并排序17五、总结或心得体会19六、参考文献20七、附录20一. 设计目的随着计算机技术的发展
2、,各种排序算法不断的被提出。排序算法在计算机科学中有非常重要的意义,且应用很广泛。在以后的发展中排序对我们的学习和生活的影响会逐渐增大,很有必要学习排序知识。此次课程设计一方面使自己掌握排序的知识,另一方面锻炼一下团队合作开发系统的能力。二. 设计内容和要求功能要求:(1)界面友好,易与操作。可采用菜单或其它人机对话方式进行选择。(2)实现各种内部排序。包括直接插入排序,冒泡排序,直接选择排序,希尔排序,快速排序,堆排序,归并排序。(3)待排序的元素的关键字为整数或(字符)。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。(1)
3、 演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表,以便比较各种排序的优劣。三. 本设计所采用的数据结构typedef struct int key;RecType;希尔排序排序算法演示系统冒泡排序归并排序快速排序 直接插入排序直接选择排序堆排序四. 功能模块详细设计4.1 详细设计思想主函数:#include#include#include #define L 8 /排序元素个数#define FALSE 0#define TRUE 1typedef structint key;RecType;RecType RL;int num; int sum;int sun; /定义
4、排序趟数的全局变量 /系统主界面/主函数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);printf(ntt*n);printf(ntt * 1-更新排序数据* 2-直接插入排序 n);printf(ntt * 3-希 尔 排 序* 4-冒 泡 排 序 n);
5、printf(ntt * 5-快 速 排 序* 6-直接选择排序 n);printf(ntt * 7-堆 排 序 * 8-归 并 排 序 n);printf(ntt *0-退 出* n); printf(ntt*n);printf(ntt请选择:);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数据输入完毕!);br
6、eak;case 2:Insertsort();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(k=1;k=L;k+)printf(%5d,Rk.key);printf(ntt比较次数是:%dntt,sum);printf(ntt
7、交换次数是:%dntt,sun);break;case 6:Selectsort();break;case 7:Heap();break;case 8:Mergesort();break;case 0:ch1=n;break;default:system(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)getchar();ch1=n;r
8、eturn 1;图一 主界面4.1.1 冒泡排序核心思想 依次比较相邻的两个数,将小数放在前面,大数放在后面,第一轮比较后,最大的数便被放到了最后;第二轮操作前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;int exchange=TRUE;/标志位exchange初始化为TRUE 1prin
9、tf(ntt原始数据为(按回车键开始排序):ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);for(i=1;iL&exchange=TRUE;i+)/外层对总的循环次数执行次数exchange=FALSE;for(j=1;j=L+1-i;j+) /内层相邻记录的交换与比较 m+;/比较次数+if(Rj.keyRj-1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;y+;/移动次数+m-;/比较次数if(exchange) /输出语句printf
10、(tt第%d趟冒泡排序的结果为:ntt,i);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);for(i=1;i=L;i+) printf(%5d,Ri.key);图二 直接插入排序4.1.2 快速排序核心思想 首先检查数据列表中的数据数,如果小于两个,则直接退出程序。如果有超过两个以上的数据,就选择一个分割点将数据分成两个部分,小于分割点的数据放在一组,其
11、余的放在另一组,然后分别对两组数据排序。 通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过,你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多核心代码/递归算法实现void Quicksort(int low,int high) int i=low,j=high,k;R0.key=Rlow.key;while(ij)while(ij&R0.key=Rj.key) /右侧扫描j-;sum+;if(ij) Ri.key=Rj.key;/交换 i+;sun+;while(ij&Ri.keyR0.key)/左侧扫描 i+;sum+;if(ij)Rj.key=Ri.key;
12、/交换j-;sun+;Ri.key=R0.key;num+;/输出语句包括排序的结果及次数 printf(tt第%d趟快速排序的结果为:ntt,num);for(k=1;k=L;k+) printf(%5d,Rk.key);getchar();printf(n);if(lowi-1) Quicksort(low,i-1);/递归部分(左侧)if(j+1high) Quicksort(j+1,high);/递归部分(右侧)图三 快速排序4.1.3 直接插入排序核心思想经过i-1遍处理后,L1.i-1己排好序。第i遍处理仅将Li插入L1.i-1的适当位置,使得L1.i又是排好序的序列。要达到这个目
13、的,我们可以用顺序比较的方法。首先比较Li和Li-1,如果Li-1 Li,则L1.i已排好序,第i遍处理就结束了;否则交换Li与Li-1的位置,继续比较Li-1和Li-2,直到找到某一个位置j(1ji-1),使得Lj Lj+1时为止核心代码void Insertsort()int i,j,k,m=0,x=0; /初始化比较次数变量m,移动次数变量xprintf(ntt原始数据为:(按回车键开始排序)ntt);for(k=1;k=L;k+)printf(%5d,Rk.key);getchar();printf(n);/主要运行部分for(i=2;i=L;i+)if(Ri.keyRi-1.key)
14、R0=Ri;j=i-1;while(R0.keyRj.key)Rj+1=Rj;j-;Rj+1=R0;x+;m+;/输出语句包括排序的结果及次数 printf(tt第%d趟直接插入排序的结果为:ntt,m);for(k=1;k=L;k+) printf(%5d,Rk.key);getchar();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);图四 直接插入排
15、序4.1.4 希尔排序核心思想 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2d1重复上述的分组和排序,直至所取的增量dt=1(dtdt-ld2d1),即所有记录放在同一组中进行直接插入排序为止。核心代码void Shellsort()int i,j,gap,x,k,y=0,m=0; /初始化比较次数变量m,移动次数变量yprintf(ntt原始数据为:(按回车键开始排序)ntt);for(k=1;k0)for(i=gap+1;i0)if(Rj.keyRj+gap.key)x=R
16、j.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=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);for(i=1;i=L;i+)printf(%5d,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 排序 算法 演示 系统
限制150内