西北工业大学-程序设计大作业.docx

《西北工业大学-程序设计大作业.docx》由会员分享，可在线阅读，更多相关《西北工业大学-程序设计大作业.docx（17页珍藏版）》请在课桌文档上搜索。

1、学院x学院班级xx学号x姓名目录1摘要1.1设计题目1.2设计内容1.3开发工具1.4应用平台2详细设计2.1程序结构2.2主要功能42.3函数实现42.4开发日志63程序调试及运行73.1程序运行结果73.2程序使用说明113.3程序开发总结124附件（源程序）121摘要1.1设计题目算法型大作业眶目：编写七种排序算法的演示程序。1.2设计内容编写快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序函数，通过主函数调用以实现七种排序算法的演示。1,3开发工具VisualC+6.01.4应用平台Windows2000/XP/Vista32位2详细设计2.1程序结构程序的整体结构与

2、流程见下图所示。程序运行时在主菜单中输入序号选择排序方法或选择结束程序，当进行某种排序方法后，在主函数中输入待排数据个数和待排数据，通过调用对应的排序函数实现排序并输出。该排序结束后再次进入主函数，通过循环重复上述操作。其中，主函数中将数组地址和待排序数据个数传递给排序函数，在排序函数中实现排序功能。退出系统2.2主要功能函数的功能为对快速排序、插入排序、选择排序、冒泡排序、堆排序、归并排序、基数排序算法的演示。主函数：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。最后输出 最后输出 最后输出 最后输出快速排序函数：根据快速排序的算法,插入排序函数：根据插入排序的

3、算法,选择排序函数：根据选择排序的算法,冒泡排序函数：根据冒泡排序的算法,堆排序函数：根据堆排序的算法，最后输出归并排序函数：根据归并排序的算法，最后输出基数排序函数：根据基数排序的算法，最后输出2.3函数实现主色鼓：在主函数中对菜单输出，通过switch语句中的case分支选择所需要的排序方法：通过while循环使演示程序在运行时能够持续进行快速推:快速排序（kuaisu）又被称做分区交换排序，这是一种平均性能非常好的排序方法。其算法基本思想是：任取排序表中的某个数据元素（例如取第一个数据元素）作为基准，按照该数据元素的关键字大小，将整个排序表划分为左右两个子表：左侧子表中所有数据元素的关犍

4、字都小于基准数据元素的关健字。右侧子表中所有数据元素的关键字都大于或等于基准数据元素的关键字，基准数据元素则排在这两个子表中间（这也是该数据元素最终应安放的位置），然后分别对这两个子表重复施行上述方法的快速排序，直到所有的子表长度为I,则排序结束。插入拚序:插入排序（CharU）的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到己排序的部分排序表的适当位置。当插入第i（li=n）个数据元素时，前面的i-1个数据元素已经排好序，这时，用第i个数据元素的关键字与前面的M个数据元素的关键字顺序进行比较，找到插入位置后就将第i个数据元素插入。

5、如此进行n-l次插入，就完成了排序.以下是在顺序表上实现的直接插入排序在顺序表上进行直接插入排序时，当插入第i（li=n）个数据元素时，前面的A01、Afi、Ai-2已经排好序，这时，用Ai-1的关键字依次与Ai-2,Ai-31,的关键字顺序进行比较，如果这些数据元素的关键字大于Ai-ll的关键字，则将数据元素向后移一个位置，当找到插入位置后就将Ai-1插入，就完成了A01,AIH,An-1的排序。选择排序选择排序（x三ze）的算法基本思想是：a）开始时设i的初始值为0。b）如果i=n,因此在则趟归并中while循环不执行，只做把temptable.arr中的数据元素复制至hable.arr的

6、工作。基数林序：基数排序法(radixsort)则是属于分配式排序(distributionsort),基数排序法又称桶子法(bucketsort)或binsort,顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些桶中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m),其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。具体可以参看后面的代码进行理解。其它t使用了Stdlib头文件里包含的系统函数，包括清屏函数和运行时的暂停，增强了程序运行时的效果。2.4开发日志在老师布置了大作业的题目后，我就把题目卜.载f来并

7、进行分析已选择合适的题目。经过我的慎重考虑，选择了算法型大作业题目中的编写七种排序算法的演示程序，觉得自己有能力把这道题目很好完成。在认真分析连题目后，基本确定了整体的思路，但是其中有堆排序，归并排序，基数排序我没有在教材中接触过，于是借助了图书馆和网络上的资源，重点对这三的函数进行编写.在编写大作业过程中大的困难我没有遇到，只是有些小的疏忽常常导致程序无法运行，如形参和实参的不一致等。我也在其中意识到对知识掌握的不够熟练，在解决了这些问题后，我觉得自己Xj程序的编写更加熟练了，对问题的分析也更加严谨了。在C程序设计的实验和理论考试之前代码己基本完成。在考试结束后，我又对程序稍微进行了修改，使

8、之运行时效果更好。接着开始写实验报告，整理自己的大作业。我对我的作业是很满意的。3程序调试及运行3.1程序运行结果七种排序算法的演示程序1 .进入程序运行后所显示的菜单:情输入序号进行选择:6 7 8-1 PjEis归基退2.快速排序:E*A*X共*fff二二二-74l-=dc王%选用归基退5678*x*JY输入序号进行选择：,输入待排序数的个数:储输入待排序数据：54792:第1趟：24795第2趟：24795戛趟：24597第4冠：24579排序结果:245793.插入排序:XEc ； *E: ft#chngyunh 1 DebuXchengyunhe 1. *a速入杯!予 br Ukr

9、Ublthp- -UL wt he 才 篇选闻归基退12345678F输入序号进行选择：辰输入待排序数的个数:,输入待排序数据：631第1趟:4661便2趟:34663三3446MF序结果：1346h按任芭键继续.4.选择排序:5.冒泡排序:E七种排序算法的演示程序清输入待排序数据:562712学趟：275612第2趟：271256第3趟：122756请输入序号进行选择：3输入待排序数的个数:123456786.堆排序:7.归并排序:8.基数排序:9结束:3.2程序使用说明1.打开源程序，调试完毕后开始运行，开始进行七种算法的演示：2.按照说明进行输入,选择数字1-7即可进入相应的排序算法演示

10、程序，选择8结束程序:3.选择排序的方法后，按要求输入待排数据的个数，然后输入待排序数据即可（数据排序结束后，会自动清屏，进入菜单进行接下来的选择）；4.应当注意，本演示程序对数据进行的是升序；3.3程序开发总结在选择这个题日时，我觉得难度系数10对我有挑战性，并且我对排序有相对比较熟悉，所以就选了这个题目。但是在编写过程中却遇到很多问题。我和我的同学进行了讨论，查阅了图书馆和网络上的资料，结合力我个人对本题Fl的理解对各种问题进行了处理，学到了很多教材上没有的知识。从这次实践中，我意识到自己还有很多不足之处。能力也得到了提高。我在进行编程时还需要翻书看找，对于这一点，只能说对知识的学习还不够

11、扎实，所以有空时还应该继续熟悉这门课程。另外，就是对于错误的处理，不能得心应手，不能正确处理一些简单的错误。对于逻辑上的借误，不能够立即找到出错点，往往需要向同学请教才能找出佛误，并且改正。我觉得这是自己独自思考能力不高的问题，遇事需要自己仔细想想，若还不能改正，再请教别人也不迟。从总体上说，最终结果我很满意，我觉得我所设计的程序操作方便，功能良好。我在上面花费了很多时间和精力，对作业不断进行修改和完善，我很有成就感。我的能力在这之中得到了提高。4附件（源程序）#include#include/*快速排序*/voidkuaisu(intA,intn)inti,j,k,t,p;for(i=0jn

12、-1;i+)k=i;for(j=i+1;jn;j+)if(A0Ak)k=j;t=Ak;Ak=Ai;Agt;Printf(第d趟:,i+1);for(p=0;pn;p+)printf(,%d,Ap);PrintfCn);printt(,rn排序结果:)；for(i=0;in;i+)printf(%dAi);printfCn);Printter);system(rpause);system(,CLS);Iiiiiiiiiiiiiiiiiiir*插入排序*/voidcharu(intA,intn)inti,klt,j,h=1;for(i=1;in;i+)t=Ai;k=i-1;while(tAk)Ak

13、+1=Ak;k-；if(k=-1)break;Printf(第d趟:,h+);for(j=0;jn;j+)printf(%d,Aj);printf(,rn);Ak1=t;Printf(,rn排序结果:)；for(i=0;in;i+)printf(,%d,Ai);PrintfCr);PrintfCn”)；system(pause);SyStem(CLS);/*选择排序*/voidxuanze(intAQJntn)intiJKUh=1;for(i=0jin-1;i+)k=i;for(j=i+1;jn;j+)f(AOAk)k=j;if(H=k)t=Ai;Ai=Ak;Ak=t;Printf(第d趟:,

14、h+);for(l=0;ln;l+)printf(,%d,AI);printf(n);Printfcn排序结果:)；for(i=0;ivn;i+)printf(%d,Ai);printf(n);printf(n);system(,pause);system(,CLS);/*冒泡排序Iiiiiiiiiiiiiiiiiiiiiivoidmaopao(intA,intn)intij,t,h=1,p;for(j=0;jn-1;j+)for(i=0;iAi+1)t=Ai,Ai=Ai+1,Ai+1=t,p+;Printf(第d趟:,h+);for(p=0;Peri;p+)printf(,%d,Ap);pr

15、intf(n);PrintfCn排序结果:)；for(i=0;ivn;i+)printf(%d,Ai);printf(n);printf();system(pause);system(CLS);/*堆扑F序*/voidshift(intA,inti,itm)intk,t;t=Ai;k=2#i+1;while(km)if(km-1)&(AkAk+1)k+;if(t=O;i-)shift(A,i,n);for(i=n-1;i=1;i-)k=A0;A0=Ai;Ai=k;shift(A,0,i);Printf(第d趟:,h+);for(j=0;jn;j+)printf(%d,1,Aj);PrintfC

16、r);printf(,rn排序结果:)；for(i=0;ivn;i+)printf(%d,Ai);Printfer);Printf(rr);system(pause);system(,CLS);/*归并排序*/voidmerge(intnumber111intfirst,intlast,intmid)intnumberjemp10=0;inti=first,j=mid15k;for(k=0;k=last-first;k+)if(i=mid+1)number_tempk=numberj+;continue;if(j=last+1)numberjempk=numberi+;continue;if(

17、numberinumberj)numberjempk=numberi;elsenumberjempk=numberj+;for(i=first,j=O;i=last;i+,j+)numberi=numberjempj;voidmerge_sort(intnumber,intfirst,intlast)intmid=0;if(firstlast)mid=(firstlast)2;merge_sort(number,first,mid);merge_sort(number,mid+1,last);merge(number,first,last,mid);voidguibing(inta。,intn

18、)inti;merge_sort(a,0,n-1);Printf(,rn排序结果:)；for(i=0;in;i+)printf(%d,ai);PrintfCr);printf(,rnM);system(pause);system(CLS);Illlllllllllllllllir1基数排序*i/voidjishu(intdatasintn)inttemp1010=0;intorder10=0;inti,j,k,qllsd;k=0;q=1；while(q=n)for(i=0;ivn;i+)lsd=(dataiq)%n);templsdorderlsd=datai;orderlsd+;for(i=

19、0;ivn;i+)if(orderiI=0)for(j=0;jorderi;j+)datak=tempij;k+;orderi=0;q*=n;k=0;Printfen排序结果:”)；for(i=0;in;i+)Printf(%ddatai);Printfen);printf(,rn);system(,pause,);system(,CLS);/*主函数*/intmain()intA100,p,n,i;while(1)printf(,rnt*七种排序算法的演示程序*n);Printf(Hr*n);printf(t*1-快速排序*n”)；printf(t*2-插入排序*n);Printfct*3-

20、选择排序*n);Printf(*4-冒泡排序*n);printf(t*5-堆排序*n);printf(t*6-一归并排序*n);PrintfCt*7-基数排序*n);Printfet*8-退出程序*n);printf(t*n);pritf(,t*w)Printf(”请输入序号进行选择:n);scanf(%dM,&p);if(p=8)break;Printf(”请输入待排序数的个数:n);scanf(%dH,&n);Printf(”请输入待排序数据:rr);for(i=0;in;i+)SCanf(%d”,&Ai);Switch(P)case1:kuaisu(A,n);break;case2:charu(A,n);break;case3:xuanze(A,n);break;case4:maopao(A,n);break;case5:duipai(A,n);break;case6:guibing(A,n);break;case7:jishu(A,n);break;printf(rnntttt谢谢您的使用nr);return0;