c语言设计大作业.pdf

学院班级学号姓名航空学院01011001 班2010300145郭汉青摘要摘要/先建立具有输入、输出和循环选择子程序功能的主函数，在主函数中声明每个子函数，接着再用一个 switch 分支选择对各个子函数进行引用。再为每一种排序算法建立一个或几个子函数。参数基本都是传递排序数组的个数和数组的头指针，没有返回值。由于时间有限，且目前的编程能力有限，程序仅仅是把基本内容表达出来了，许多细节任有很多修改余地。目录1 摘要.31.1 设计题目.31.2 设计内容.31.3 开发工具.31.4 应用平台.32 详细设计.32.1 程序结构.32.2 主要功能.42.3 函数实现.42.4 开发日志.53 程序调试及运行.63.1 程序运行结果.63.2 程序使用说明.103.3 程序开发总结.104 附件（源程序）.11Email:.cn21 1 摘要摘要1.1 设计题目编写七种排序算法的演示程序/快速排序；插入排序；选择排序；冒泡排序；堆排序；归并排序；基数排序。1.2 设计内容先建立具有输入、输出和循环选择子程序功能的主函数，并在主函数中声明每个子函数，再为每一种排序算法建立一个或几个子函数。这个程序就基本完成了。子函数中直接定义了数组原型，通过七种算法，利用循环语句和自定义函数调用把数组a10按升序重新排列。1.3 开发工具/*Visual C+6.0和 Win32。*/1.4 应用平台WindowsXP/732 位2 2 详细设计详细设计2.1 程序结构先建立具有输入、输出和循环选择子程序功能的主函数，并在主函数中声明每个子函数，接着再用一个 switch 分支选择对各个子函数进行引用。再为每一种排序算法建立一个或几个子函数。Email:*.cn3参数基本都是传递排序数组的个数和数组的头指针，没有返回值。主函数快速排序插入排序选择排序冒泡排序堆排序归并排序基数排序2.2 主要功能/*这七道程序的作用是把数组中的数从小到大排序。他们分别使用了不同的算法，对数组a 进行排列。这七个程序能实现对一些常见的排序算法的演示，使我们对这些排序算法的原理和算法的实现过程更加熟悉，对 C 语言的语法结构和数据结构更加清晰。*/2.3 函数实现1.快速排序：就是你从数组中 任取一个元素 p(可随机取,现在以取第一个为例)，以 P 作为主元,对数组进行划分,前一部分小于 P,后一部分 大于 p，划分处理存储 p，然后分别对划分后的前一部分和后一部分使用递归调用。最后将数组划分为小数组,通过局部的有序合并,解决问题。2.选择法：这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中 选择最小的与第二个交换，这样往复下去。3.插入法：插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张。这种算法其实不是简单算法中最好的，因为其循环次数虽然并不固定，我们仍可以使用O 方法。从上面的结果可以看出，循环的次数 f(n)=1/2*n*(n-1)=1/2*n*n。所以其复杂度仍为 O(n*n)（这里说明一下，其实如果不是为了展示这些简单 排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是 O(n)（推导类似 选择法），但我们每次要进行与内层循环相同次数的=操作。正常的一次交换我们需要三次=而这里显然多了一些，所以我们浪费了时间。4.冒泡排序：书上有。Email:*.cn45.堆排序：用二叉树的结构来表示数组,及用数组来表示二叉树的结构,比如i为父节点其子节点为2i和2i+1。其中,大顶堆中 父节点大于其两个子节点。6.归并排序：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。7.基数排序：先从数据的低位开始,进行分配,分成 10 个空间,分别存储位为 0，1，2，39，重复的对次地位操作,知道预定的高位,排序完成。2.4 开发日志/*请在详细描述你设计、调试程序的过程，这里的描述类似日记*/这七个算法在我们 C 语言课堂上只学过两种即冒泡法和选择法。于是我先把这两种算法编辑出来了。然后其他五种算法我只有通过查阅其它C 语言的教材和上网学习来弄懂。最后又和其他同学讨论终于把七个零散的程序编写出来了。本以为这样就万事大吉了，不过看到其它同学都是用了switch 语句进行选择，我才知道最难的还没到，我只有一边看书并请教老师用switch 语句，把七道程序组合到一个程序里，这样就完成了编程。接着是报告这个也挺难弄的。主要是有些项目不知道写啥东西，通过与同学讨论和自己琢磨，终于完成了报告，也不知道对不对。总之，这个大作业的确是消耗了很多时间和脑力，不过感觉收获挺大的。Email:*.cn53 3 程序调试及运行程序调试及运行3.1 程序运行结果Email:.cn6Email:.cn7Email:.cn8Email:.cn93.2 程序使用说明/*请在这里详细描述如何使用你的程序，就好比是一个小型说明书*/。打开程序后，运行程序，先进行switch 选择,可以选择七种不同算法即快速排序；插入排序；选择排序；冒泡排序；堆排序；归并排序；基数排序.程序会自动演示排序结果。3.3 程序开发总结/*请在这里简要描述你对编写大作业的收获与思考*/搞了一个星期总算完成了这个大作业，尽管可能编的并不是很好，程序显得有些乱，但毕竟是大功告成。这次大作业有几个类型，其中算法型最难，当然分值也最高，因此我果断选了这个。刚拿到题目，顿时傻了眼。前面几个题闻所未闻完全不知如何下手，总算找到一个见到过的题目，可是这七种算法我才会两种即冒泡法和选择法。其他的也是闻所未闻。于是只有找C 语言的其他教材，上网搜才搞清楚其他的五算法是啥意思。终于把七道程序弄出来了，然而这项工作还只是冰山一角，这个报告才是最难搞的。因为不知道应该写啥，没有模板可以借鉴，最后只有与同学探讨，试探这弄出来了买也不知道和不合格。不过在这复习备考的黄金时刻，拿大把时间做这个大作业确实太过奢侈，不免与同学有些相互借鉴。不管怎样大作业是写了，本学期的 C 语言上机也就结束了，不过说实话我们的 C 语言技术还差得很，很多问题没有搞懂，还有许多知识点没有涉及。不过通过的大作业我对排序法应该是有了不小突破七把利剑在手还怕不会排序Email:*.cn10么，哈哈。排序的确很重要，而且很实用，希望借此机会我的排序能力有很大进步。4 4 附件（源程序）附件（源程序）/*请在附上你的程序源代码，如果是多个请标出文件名称以及工程管理名称及设置*/#include#include void main()int QuickSort();int charu();int xuanze();int maopao();int dui();int guibing();void jishu();int c;printf(*n);printf(*1.快速排序*n);printf(*2.插入排序*n);printf(*3.选择排序*n);printf(*4.冒泡排序*n);printf(*5.堆排序*n);printf(*6.归并排序*n);printf(*7.基数排序*n);printf(*0.退出*n);printf(*nn);printf(请您输入您选择的演示:n);scanf(%d,&c);switch(c)case 1:printf(快速排序:n);QuickSort();break;case 2:printf(插入排序:n);charu();break;case 3:printf(选择排序:n);xuanze();break;case 4:printf(冒泡排序:n);maopao();break;Email:*.cn11case 5:printf(堆排序:n);dui();break;case 6:printf(归并排序:n);guibing();break;case 7:printf(基数排序:n);jishu();break;default:printf(输入错误，请重新选择!n);break;void quickSort(int a,int left,int right)int i,j,temp;i=left;j=right;temp=aleft;if(leftright)return;while(i!=j)while(aj=temp&ji)j-;if(ji)ai+=aj;while(aii)i+;if(ji)aj-=ai;ai=temp;quickSort(a,left,i-1);quickSort(a,i+1,right);int QuickSort()int a10=2,5,3,6,8,7,1,4,9,10;int i;quickSort(a,0,9);for(i=0;i10;i+)printf(%d,ai);return 0;Email:.cn12int charu()int a10=2,5,3,6,8,7,1,4,9,10;int i,j,t;for(i=1;i=0&taj;j-)aj+1=aj;aj+1=t;for(i=9;i=0;i-)printf(%d,ai);return 0;int xuanze()void sort(int array,int n);int a10=2,5,3,6,8,7,1,4,9,10;int i;sort(a,10);for(i=0;i10;i+)printf(%d,ai);printf(n);return 0;void sort(int array,int n)int i,j,k,t;for(i=0;in-1;i+)k=i;for(j=i+1;jn;j+)if(arrayjarrayk)k=j;t=arrayk;arrayk=arrayi;arrayi=t;int maopao()int a10=2,5,3,6,8,7,1,4,9,10;Email:.cn13int i,j,k;for(i=0;i9;i+)for(j=0;jaj+1)k=aj+1;aj+1=aj;aj=k;for(i=0;i10;i+)printf(%d,ai);return 0;void sift(int*x,int n,int s)int t,k,j;t=*(x+s);/*暂存开始元素*/k=s;/*开始元素下标*/j=2*k+1;/*右子树元素下标*/while(jn)if(jn-1&*(x+j)*(x+j+1)j+;if(t=0;i-)sift(x,n,i);/*初始建堆*/for(k=n-1;k=1;k-)t=*(x+0);/*堆顶放到最后*/*(x+0)=*(x+k);*(x+k)=t;sift(x,k,0);/*剩下的数再建堆*/int dui()void heap_sort(int*x,int n);int a10=2,5,3,6,8,7,1,4,9,10;int i;heap_sort(a,10);for(i=0;i10;i+)printf(%d,ai);return 0;int guibing()Email:*.cn15int a10=2,5,3,6,8,7,1,4,9,10;int temp1010=0;int order10=0;int i,j,k,n,lsd;k=0;n=1;while(n=10)for(i=0;i10;i+)lsd=(ai/n)%10);templsdorderlsd=ai;orderlsd+;printf(n 重新排列:);for(i=0;i10;i+)if(orderi!=0)for(j=0;jorderi;j+)ak=tempij;printf(%d,ak);k+;orderi=0;n*=10;k=0;printf(n 排序后:);for(i=0;i10;i+)printf(%d,ai);printf(n);return 0;#define MAX_NUM 2/*定义数组值中最大位数*/#define COUNT 10/*定义数组元素个数*/void jishu(void)int numCOUNT=2,5,3,6,8,7,1,4,9,10;/*要排序的数组*/Email:*.cn16int temp10COUNT=0;/*定义临时数据交换数组*/int i,j,k=0,p=0,n=1,m=1,lsd;for(i=0;iCOUNT;i+)/*测试排序前结果*/printf(%d,numi);printf(n);while(n=MAX_NUM)/*开始 LSD*/for(i=0;i numi)/*若位数值大于此数组值，则放置首位元素*/temp0k=numi;else/*否则放置对应的位数值元素中*/lsd=(numi/m)%10;templsdk=numi;k+;for(i=0;i10;i+)/*将处理后的数组放置要排序的数组*/for(j=0;jCOUNT;j+)if(tempij!=0&pCOUNT)nump=tempij;tempij=0;p+;k=0;p=0;n+;m*=10;for(i=0;iCOUNT;i+)/*测试排序后结果*/printf(%d,numi);printf(n);Email:*.cn17Email:.cn18