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

1、 目录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函数说明所示：返回值函数名参数表函

2、数说明intmainvoid主函数voidD_InsertRecordType R插入排序voidBubbleSortRecordType R冒泡排序intPartitionRecordType R划分算法voidQuickSortRecordType R 快速排序voidSelectSortRecordType R选择排序voidShellSortRecordType R希尔排序voidMergeSortRecordType R归并排序voidHeapAdjustRecordType R堆排序voidDisplay显示 表1函数3 、运行环境 1）、软件环境操作系统：windows7、win

3、dows8 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)/

4、*将关键字值大于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,in

5、t 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=Par

6、tition(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个

7、记录进行希尔排序，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,i

8、nt 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;Record

9、Type 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-)HeapAdju

10、st(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作为结

11、束标志*: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-

12、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);print

13、f(n);6 调试分析1、测试中的问题举例： 在进行快速排序时输入一行数字当运行时无论怎样也不出现排序后的结果，经过多次检查后发现在进行划分算法时i,j的值取法不当，最后经重新修改后运行。2、算法改进设想举例 在程序中有很多不如意的地方，在进行归并排序时用的是非递归的排序算法，算法略显冗杂。在进行归并排序时可以采用递归排序，采用递归排序的思想对此进行快速的排序算法，另外还可以设计一个计算程序运行时间的函数并计算每个排序算法所耗费的时间，选出较为优秀的排序算法。7 测试结果一、测试方法如下： 1、输入你想要测试的一组数字，并以-1作为结束标志 2、选择你想要进行的测试类型 3、调用你想要测试类型

14、的函数 4、输出测试结果二、测试结果如下： 1、插入排序结果 2、选择排序结果： 3、希尔排序结果： 4、归并排序结果： 5、堆排序结果： 参考文献1严蔚敏,数据结构（C语言版） 清华大学出版社2谭浩强.C语言程序设计（第三版） 清华大学出版社3胡元义数据结构教程 （C语言版） 西安电子科技大学4李春葆数据结构教程上机实验指导 清华大学出版社 心得体会 通过这次的数据结构课程设计我深深地体会到数据结构思想在C语言编程中的巨大用途，在进行排序综合这个课程设计题目的过程中，我多处都运用了数据结构的思想，例如：在我进行快速排序时其中的划分算法快速排序中起着桥梁的作用，正是数据结构的这种思想才能简便而

15、又快捷的完成快速排序这项功能，另外堆排序中也运用了二叉树的思想。完成这次课程设计的过程中还发现了自己的诸多不足之处，这次课程设计确确实实提高了自己的编程能力。信息科学与工程 学院课程设计成绩评价表课程名称：数据结构课程设计设计题目：排序综合专业： 班级： 姓名： 学号：序号评审项目分 数满分标准说明1内 容思路清晰；语言表达准确，概念清楚，论点正确；实验方法科学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，做了大量的工作。2创 新内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解3完整性、实用性整体构思合理，理论依据充分，设计完整，实用性强4数据准确、可靠数据准确，公式推导正确5规 范 性设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定6纪 律 性能很好的遵守各项纪律，设计过程认真；7答 辩准备工作充分，回答问题有理论依据，基本概念清楚。主要问题回答简明准确。在规定的时间内作完报告。总 分综合意见 指导教师 年 月 日.忽略此处.