C语言排列组合课程设计.doc

课 程 设 计课程设计名称： 排序综合 专 业 班 级 ： 学 生 姓 名 ： 学 号 ： 指 导 教 师 ： 课程设计时间： 计算机应用技术 专业课程设计任务书学生姓名专业班级学号 题 目排序综合课题性质A课题来源D指导教师同组姓名无主要内容运用C语言的知识对程序进行模块化设计；运用数据结构的知识分别对七种排序方法进行设计；采用菜单式对排序结果进行输出；任务要求 综合运用这一年来所学的C语言知识与数据结构的知识对所选的课题进行详细的设计，任务分为9个模块进行设计分别为：插入排序函数、冒泡排序函数、快速排序函数、选择排序函数、希尔排序函数、归并排序函数、堆排序函数以及选择函数与主函数。参考文献数据结构（C语言版）严蔚敏 清华大学出版社C语言程序设计（第三版）谭浩强 清华大学出版社数据结构教程 （C语言版）西安电子科技大学数据结构教程上机实验指导 清华大学出版社审查意见指导教师签字：教研室主任签字： 2014 年 6 月 15 日 目录1、需求分析：42、概要设计43 、运行环境51）、软件环境52）、硬件环境54 开发工具和编程语言55 详细设计56 调试分析127 测试结果12一、测试方法：12二、测试结果：12参考文献15心得体会161、需求分析：排序综合问题，用数据结构的思想对一些数字进行排序，实现以下排序功能：1、插入排序2、冒泡排序3、快速排序4、选择排序5、希尔排序6、归并排序7、堆排序2、概要设计 1、程序总体框架图如下： 排序综合 快 速 排 序 堆 排 序 归 并 排 序 希 尔 排 序 选 择 排 序 冒 泡 排 序 插 入 排 序2、程序中各函数简单说明见如表1函数说明所示：返回值函数名参数表函数说明intmainvoid主函数voidD_InsertRecordType R插入排序voidBubbleSortRecordType R冒泡排序intPartitionRecordType R划分算法voidQuickSortRecordType R 快速排序voidSelectSortRecordType R选择排序voidShellSortRecordType R希尔排序voidMergeSortRecordType R归并排序voidHeapAdjustRecordType R堆排序voidDisplay显示 表1函数3 、运行环境 1）、软件环境操作系统：windows7、windows8 2）、硬件环境 处理器：Intel Pentium 166MX 或更高内存：64MB硬盘空间：1T显卡：SVGA 显示适配4 开发工具和编程语言编程环境：Dev-C+ 5.0 beta 9.2 (4.9.9.2)编程语言：C语言，ANSI C895 详细设计/*排序综合*/#include#define MAXSIZE 300typedef structint key;char data;RecordType; /*插入排序*/void D_Insert(RecordType R,int n)/对n个记录序列R1Rn进行直接插入排序int i,j;for(i=2;iR0.key)/*将关键字值大于Ri.key()即此时的R0.key的所有Rj(j=i-1,i-2,)顺序后移一个记录位置*/Rj+1=Rj;j-;Rj+1=R0; /*冒泡排序*/void BubbleSort(RecordType R,int n)/对R1Rn这n个记录进行冒泡排序int i,j,swap;for(i=1;in;i+)swap=0;for(j=1;jRj+1.key)/如果Rj.key大于Rj+1.key则交换它俩R0=Rj;Rj=Rj+1;Rj+1=R0;swap=1;if(swap=0)break; /*快速排序*/int Partition(RecordType R,int i,int j)/划分算法/对RiRj,以Ri为基准记录进行划分，并返回RKi在划分后的正确位置R0=Ri;while(ij)while(i=R0.key)/从左向右扫描查找第一个关键字小于R0.key的记录Rjj-;if(ij)/当i小于j时则Rj.key小于R0.key将Rj交换到表的左端Ri=Rj;i+;while(ij&Ri.key=R0.key)/从左当右扫描查找第一个关键字大于R0.key的记录Rii+;if(ij)Rj=Ri;j-;Ri=R0;return i;void QuickSort(RecordType R,int s,int t)/进行快速排序int i;if(st)i=Partition(R,s,t);/i为基准记录的位置并由此将表分为RsRi-1和Ri+1Rt两部分QuickSort(R,s,i-1);QuickSort(R,i+1,t); /*选择排序*/void SelectSort(RecordType R,int n) /对于R1Rn这n个记录进行选择排序int i,j,k;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)if(Rj.keyRk.key)k=j;if(i!=k)R0=Rk;Rk=Ri;Ri=R0; /*希尔排序*/void ShellInsert(RecordType R,int n,int d) /对R1Rn这n个记录进行希尔排序，d为增长因子（步长）int i,j;for(i=d+1;i0&R0.keyRj.key;j=j-d)Rj+d=Rj;Rj+d=R0;void ShellSort(RecordType R,int n)/进行希尔排序int d10,t,k;printf(n输入增量因子的个数n);scanf(%d,&t);printf(由大到小输入每个增量因子:n);for(k=0;kt;k+)scanf(%d,&dk);for(k=0;kt;k+)ShellInsert(R,n,dk); /*归并排序*/void Merge(RecordType R,RecordType R!,int k,int n)/一趟二路归并int i,j,l1,u1,l2,u2,m;l1=0;m=0;while(l1+kn)l2=l1+k;u1=l2-1;if(l2+k-1n)u2=l2+k-1;elseu2=n-1;for(i=l1,j=l2;i=u1&j=u2;m+)if(Ri.key=Rj.key)R1m=Ri+;elseR1m=Rj+;while(i=u1)R1m+=Ri+;while(j=u2)R1m+=Rj+;l1=u2+1;for(i=l1;in;i+,m+)R1i=Ri;void MergeSort(RecordType R,int n)/非递归方法进行归并排序int i,k;RecordType R1MAXSIZE;k=1;while(kn)Merge(R,R1,k,n);for(i=0;in;i+)Ri=R1i;k=2*k; /*堆排序*/void HeapAdjust(RecordType R,int s,int t)/基于大根堆得堆排序int i,j;R0=Rs;i=s;for(j=2*i;j=t;j=2*j)/沿关键字较大的孩子向下调整，先假定为左孩子if(jt&Rj.keyRj.key)break;Ri=Rj;i=j;Ri=R0;void HeapSort(RecordType R,int n)/进行堆排序int i;for(i=n/2;i0;i-)HeapAdjust(R,i,n);for(i=n;i1;i-)R0=R1;R1=Ri;Ri=R0;HeapAdjust(R,1,i-1); /*显示*/void Display()printf(*插入排序按1*n);printf(*冒泡排序按2*n);printf(*快速排序按3*n);printf(*选择排序按4*n);printf(*希尔排序按5*n);printf(*归并排序按6*n);printf(*堆排序按7*n);void main()/主函数int i=1,j,x;int Key;RecordType RMAXSIZE;printf(n*欢迎登陆排序系统*:n);printf(n*以-1作为结束标志*:n);printf(n请写出你要排序的数:n);scanf(%d,&x);while(x!=-1)Ri.key=x;scanf(%d,&x);i+;printf(输出有效数字:n);for(j=1;ji;j+)printf(%4d,Rj.key);/printf(nSort*n)+printf(n请输入你要选择的排序类型:n);Display();printf(Enter Key:);scanf(%d,&Key);if(Key=1)printf(插入排序如下:);D_Insert(R,i-1);else if(Key=2)printf(冒泡排序如下:);BubbleSort(R,i-1);else if(Key=#)printf(快速排序如下:);QuickSort(R,1,i-1);else if(Key=4)printf(选择排序如下:);SelectSort(R,i-1);else if(Key=5)printf(希尔排序如下:);ShellSort(R,i-1);else if(Key=6)printf(归并排序如下:);MebgeSort(R,i-1);else if(Key=7)printf(堆排序如下:);HeapSort(R,i-1);elseprintf(请输入17间的数字); for(j=1;ji;j+)printf(%4d,Rj.key);printf(n);6 调试分析1、测试中的问题举例： 在进行快速排序时输入一行数字当运行时无论怎样也不出现排序后的结果，经过多次检查后发现在进行划分算法时i,j的值取法不当，最后经重新修改后运行。2、算法改进设想举例 在程序中有很多不如意的地方，在进行归并排序时用的是非递归的排序算法，算法略显冗杂。在进行归并排序时可以采用递归排序，采用递归排序的思想对此进行快速的排序算法，另外还可以设计一个计算程序运行时间的函数并计算每个排序算法所耗费的时间，选出较为优秀的排序算法。7 测试结果一、测试方法如下： 1、输入你想要测试的一组数字，并以-1作为结束标志 2、选择你想要进行的测试类型 3、调用你想要测试类型的函数 4、输出测试结果二、测试结果如下： 1、插入排序结果 2、选择排序结果： 3、希尔排序结果： 4、归并排序结果： 5、堆排序结果： 参考文献1严蔚敏,数据结构（C语言版） 清华大学出版社2谭浩强.C语言程序设计（第三版） 清华大学出版社3胡元义数据结构教程 （C语言版） 西安电子科技大学4李春葆数据结构教程上机实验指导 清华大学出版社 心得体会 通过这次的数据结构课程设计我深深地体会到数据结构思想在C语言编程中的巨大用途，在进行排序综合这个课程设计题目的过程中，我多处都运用了数据结构的思想，例如：在我进行快速排序时其中的划分算法快速排序中起着桥梁的作用，正是数据结构的这种思想才能简便而又快捷的完成快速排序这项功能，另外堆排序中也运用了二叉树的思想。完成这次课程设计的过程中还发现了自己的诸多不足之处，这次课程设计确确实实提高了自己的编程能力。信息科学与工程 学院课程设计成绩评价表课程名称：数据结构课程设计设计题目：排序综合专业： 班级： 姓名： 学号：序号评审项目分 数满分标准说明1内 容思路清晰；语言表达准确，概念清楚，论点正确；实验方法