C语言排列组合课程设计

1、程设计课程设计名称：排序综合专业班级：学生姓名：学 号:指导教师：课程设计时间：计算机应用技术专业课程设计任务书学生姓名专业班级学号JS目排序综合课题性质A课題来源D指导教师同组姓名无主要内容运用c语言的知识对程序进行模块化设计；运用数据结构的知识分别对七种排序方法进行设计；采用菜单式对排序结果进行输出；任务要求综合运用这一年来所学的C语言知识与数据结构的知识对所选的课题进行 详细的设计，任务分为9个模块进行设计分别为：插入排序函数、冒泡排序函 数、快速排序函数、选择排序函数、希尔排序函数、归并排序函数、堆排序函 数以及选择函数与主函数。参考文献数据结构（C语言版）严蔚敏 清华大学出版社C语言

2、程序设计（第三版）谭浩强清华大学出版社数据结构教程（C语言版）西安电子科技大学数据结构教程上机实验指导清华大学出版社审査意见指导教师签字：教研室主任签字：2014年6月15日 TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 1、需求分析：4 HYPERLINK l bookmark6 o Current Document 2、概要设计4 HYPERLINK l bookmark8 o Current Document 3、运行环境51）、软件环境52）、硬件环境5 HYPERLINK l bookmark10 o Current D

3、ocument 4开发工具和编程语言5 HYPERLINK l bookmark12 o Current Document 5详细设计5 HYPERLINK l bookmark14 o Current Document 6调试分析12 HYPERLINK l bookmark16 o Current Document 7测试结果12一、泗!试方法:12二、测试结果：12 HYPERLINK l bookmark18 o Current Document 参考文献15 HYPERLINK l bookmark20 o Current Document 心得体会161 X需求分析：排序综合问题，

4、用数据结构的思想对一些数字进行排序，实现以下排序功能:1、插入排序2、冒泡排序3、快速排序4、选择排序5、希尔排序6、归并排序7、堆排序2、概要设计1、程序总体框架图如下：2、程序中各函数简单说明见如表1函数说明所示:返回值函数名参数表函数说明iiitmamvoid主函数voidDJnseilRecoidTvpe R插入排序voidBubbleSoitRecoidTvpe R冒泡排序iiitPartitionRecoidTvpe R划分算法voidQuicksortRecoidTvpe R快速排序voidSelectSoilRecoidTvpe R选择排序voidShellSoitRecoid

5、Tvpe R希尔排序voidMeigeSortRecoidTvpe R归并排序voidHeapAdjustRecoidTvpe R堆排序voidDisplay显不表1函数3、运行环境、软件环境操作系统：windows7windows8、硬件环境处理器：Intel Pentium 166MX或更高内存:64MB硬盘空间：1T显卡：SVGA显示适配4开发工具和编程语言编程珂:境：Dev-C+ 5.0 beta 9.2 (4.9.9.2)编程语言：C语言，ANSI C895详细设计/*排序综合*/# iiiclude#define MAXSIZE 300tvpedef stmctint key；ch

6、ar data;RecoidType；/*插入排序*/void D_Insen(RecoidT?pe R,mt n)M 11个记录序列Rl-Rn进行直接插入排序intij;for(i=2;iR0 .key)/*将关键字值人于Ri.kevQ即此时的R0.key的所有l,i-2,)顺序后移一个记录位置*/RU+l=Rj；J-；Rj+1=RO;/*冒泡排序*/void BubbleSon(RecoidTvpe R.mt n)/对RlRn这n个记录进行冒泡排序int i,j,swap;fbr(i=l;in;i-H-)swap=0;for(j=ljRj+l.key)如果Rj.key大于Rj+l.key则

7、交换它俩RO=R|J；Rj=Rj+l；Rj+1=RO;swap=l;if(swap=0)break;严快速排序*/mt Panition(RecoidTvpe R.iiit Lmt j)划分算法/对Ri卜Rj,以Ri为基准记录进行划分，并返回RKi在划分后的正确位置RO=Ri；wlule(ij)while(i=RO.key)从左向右扫描查找第一个关键字小于RO.key的记录R卜；if(ij)/当i小于j时则R|j.key小于RO.key将Rj交换到表的左端 R】=R|；i+；while(ij &Ri .kev=RO .key)从左当右打描查找第一个关键字大于RO.key的记录Ri i+；Rj=

8、Ri；j-；Ri=RO;retuin i;void QuickSoit(RecordType Rjnt s,int t)/进行快速排序int i;if(st)i=Partition(R,s,t);/l为基准记录的位置并由此将表分为RsRi-l和Ri+1卜Rt两部分QuickSoit(R.sj-l);QuickSort(Rj+1 ,t);/*选择排序*/void SelectSort(RecordType Rjnt n)对于RlbRn这n个记录进行选择排序int i,j,k;fbi(i=l;in;i-H-)k=i;for(j=i+l;j=nj+)if(R|j .keyRk .key)k=J；if

9、(i!=k)R0=Rk;Rk=Ri;R】=R0;/*希尔排序*/void ShellIiisen(RecoidType R,iiit n.mt d)对R1卜Rn这n个记录进行希尔排序，d为增长因子(步长)intij;for(i=d+1 ;i0&R0 .key-Rlj -key J=j -d)Rj+d=Rj;Rj+d=RO;void ShellSoit(RecordType R.iiit n)/进行希尔排序int d10,t,k;pnntf(n输入增量因子的个数n”)；pnntfC*由人到小输入每个增量因子:n);for(k=0;kt;k+) scanf(”d“,&dk);for(k=0;kt;

10、k+)ShellInsert(R,n,dk);/*归并排序*/void Merge(RecordTvpe R,RecordType R!,int k,int n)一趟二路归并 int ijjl,ul,12,u2,m;11=0;m=0:wlule(ll+kn)12=11+k;ul=12-l;if(12+k-ln)u2=12+k-l;elseu2=n-l;for(i=ll J=12 ;i=u 1 &j=u2 ;m+)if(Ri .key=Rj.key)Rlm=Ri+;elseRlm=Rj +;while(i=ul)Rlm+=Ri-H-;while(j=u2)Rlm+=Rj-H-;ll=u2+l;f

11、br(i=ll ;in;i+4ii+)Rli=Ri；void MergeSort(RecordType R,iiit n)非递归方法进行归并排序mt nk;RecordTvpe R1 MAXSIZE;k=l;wlule(kn)Merge(R,Rhk4i);fbr(i=O;in;i+)Ri=Rli；k=2*k;/*堆排序*/void HeapAdjust(RecordType R,int sjnt t)基于人根堆得堆排序 intij;RO=Rs;i=s;for(j=2*ij=t;j=2*j)/关键字较人的孩子向卞调整，先假定为左孩子 &Rj.keyRj .key)break;Ri=Rj；l=j;

12、Ri=RO;void HeapSort(RecordType R,int n)/进行堆排序mt i;HeapAdjust(R.iai); fbr(i=n;il;i)fR0=Rl;Rl=Ri;R】=R0；HeapAdjust(R 1 j-1);严显示*7void Display()pnntfC*插入排序按 l*iiM); pnntf(* * * * 冒泡排序按 2* * * *n”); pnntff*快速排序按 3*n”); printf(*选择排序按 4*n); pnntfC*希尔排序按尹*ir); pnntf(* * * * 归并排序按 6* * * * *n”); pnntfC*堆排序按

13、7*ir);int i=l,j、x;int Key;RecordTvpe RMAXSIZE; pnntf(Mn*欢迎登陆排序系统*:ir); pnntfCn*以-1作为结束标志*:n”)； pnntf(”n请写出你要排序的数:n”)； scanff%dt&x);while(x!=-l)Ri.key=x;scanf(”d”、&x);i+;pnntf(”输出有效数字:n”)； for(j=ljij+)pimtf(%4d,R|j.key);pnntfViiSort*ir)+pnntf(”n请输入你要选择的排序类型:n”);DisplayO； piintf(MEnter Key:”)； scanff%

14、cT：&Key);if(Ke 尸=1)pnntf(插入排序如下:”)； D_Insert(Rj-l);else if(Key=:2)pnntf(“冒泡排序如下:”)；BubbleSort(Rj-l);else ifK.cy=rt)pnmf(快速排序如下:”)；QuickSort(R, 1else if(Key=4)prmtfC选择排序如下:”); SelectSon(Rj-l);else ifKcy=5)希尔排序如卜:”)；ShellSoit(R4-l);else if(Key=6)pnmf(“归并排序如卞:”)； MebgeSort(Rj-l);else ifKcy=l)printfC堆排序

15、如下:J;HeapSoit(Rj-l);elsepnntf(”请输入17间的数字”)；for(j=lJij+)pimtf(n%4d,RIj.key);6调试分析1、测试中的问题举例：在进行快速排序时输入一行数字当运行时无论怎样也不出现排序后的 结果，经过多次检查后发现在进行划分算法时ij的值取法不当，最后经重新修 改后运行。2、算法改进设想举例在程序中有很多不如意的地方，在进行归并排序时用的是非递归的排序算 法，算法略显冗杂。在进行归并排序时可以采用递归排序，釆用递归排序的思想 对此进行快速的排序算法，另外还可以设计一个计算程序运行时间的函数并计算 每个排序算法所耗费的时间，选出较为优秀的排序

16、算法。7测试结果一、测试方法如下：1、输入你想要测试的一组数字，并以T作为结束标志2、选择你想要进行的测试类型3、调用你想要测试类型的函数4、输出测试结果二、测试结果如下：1、插入排序结果2、选择排序结果:3、希尔排序结果:4、归并排序结果:5、堆排序结果:参考文献严蔚敏，数据结构（C语言版）清华大学出版社谭浩强.C语言程序设计（第三版） 清华大学出版社胡元义数据结构教程（C语言版） 西安电子科技大学李春葆数据结构教程上机实验指导 清华大学出版社心得体会通过这次的数据结构课程设计我深深地体会到数据结构思想在c语言编程中 的巨大用途，在进行排序综合这个课程设计题目的过程中，我多处都运用了数据 结构的思想，例如：在我进行快速排序时其中的划分算法快速排序中起着桥梁的 作用，正是数据结构的这种思想才能简便而乂快捷的完成快速排序这项功能，另 外堆排序中也运用了二叉树的思想。完成这次课程设计的过程中还发现了自己的 诸多不足之处，这次课程设计确确实实提高了自己的编程能力。信息科学与工程彥It镐裡截针嵐债评价来课程名称：数据结构课程设计设计题目：排序综合专业：班级：姓名：学号:序号评审项目分数满分标准说明1内容思路清晰：语言表达准确