完整的课程设计

1、目 录摘 要 .2前 言.3正 文.4一、采用类 C语言定义相关的数据类型.4二、程序操作过程图.6三、程序流程图.7四、程序调试分析和结果.9五、源程序（带注释）.11六、各种排序算法的性能分析.20总 结.21心 得 体 会.23参 考 文 献.24致 谢.26附件 I 部分源程序代码.27摘 要排序（sorting）是计算机程序设计的一种重要操作，他的功能是将一个数据元素（或记录）的任意序列，重新排列一个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的储存器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机储存器中进行的排序过程；另一类是外部

2、排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。内部排序又分为：插入排序、快速排序、选择排序、归并排序和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序；基数排序又分为：多关键字的排序和链式基数排序。本次课程设计就是内部排序中的几个排序方法。关键字： 内部排序关键字重新排列前 言“天之道，损有余而补不足”，自然万物发展的规律， 都是倾向于消除差异。无独有偶，热力学第二定律也指出：任意封闭的系统，都会朝着熵增加的方向发展。从信息论的角度来看，也就是倾向于更加无序。然而，“

3、 人之道，则不然，损不足以奉有余”，人总是偏好有序。就数据处理而言，有序性的确十分有用。所谓排序， 就是按照某种次序，重新排列某一序列中的所有元素。为此，任意一对元素之间 都应该能比较大小，即在所有元素之间可以定义一个全序关系。排序不仅可以作为查找等操作的预处理计算，而且也是实际应用中需要反复进行的一项基本操作。前言很多涉及计算器程序的算法都是以栈的相关操作为基础，通过对计算器算法的设计，有利于在学习中更好的理解栈及其相关的操作。但是，这款计算器主要是通过数组进行的。没有直接使用栈，但用到栈的思想。我们在写程序时，大框架已成的情况下，仍然发现有些错误很难找到，对于这样的问题，可以利用计算机纠错

4、功能，先运行，再根据题提示修改和完善程序。在计算器用到的算法中，c 语言算法可读性很强，一方面，是因为 c 语言是高级语言，是面向程序员的语言，二是 c 语言的功能是很完备的，可以达到事半功倍的效果，和其他语言相比量是比较少。正 文一、采用类 C 语言定义相关的数据类型（11、输入2、选择3、输出（21、输入模块的功能：利用随机函数产生N 个数（超过20000确，所以在本程序中只随机产生100个数。create(a,b,&n) 是一个随机函数，它可以随机产生 100个随机数 。2、选择模块的功能：选择数字则进行对应的排序；选择字母则进行重新产生随机数和退出的操作。1插入排序insertsort

5、(a,n)2希尔排序xiersort(a,n)3快速排序quicksort(a,1,n)4堆排序duisort(a,n)C(c)重新产生20个随机数create(a,b,&n)N(n)退出程序3、输出模块的功能：把利用各种排序方法排好顺序的数输出到一个文件夹中。writefile1(a,n)向指定的文件中写入排序前的数writefile2(a,n)向指定的文件中写入用各种排序方法排好序的数二、程序操作过程图开始123456插 入排 序希 尔排 序冒 泡排序快 速排序简单排序堆排序把利用排序方法排好序的数输出到指定的文件夹N(n)C（c）重新产生随机数三、程序流程图开始N(n)退插 入排 序希

6、尔排 序冒 泡排序快 速排序简单排序堆（c）重 新产 生随 机排序把用各种排序方法排好的数的顺序输出到指定的文件夹中四、程序调试分析和结果（1 100 个数，选择“1序；在选择“2（3）选择“34下：（45五、源程序（带注释）#include#include#include#include#define SIZE 20000struct elementint key;listSIZE;/创建一个数组/int creat()int i,n;int num;n=0;printf(请输入元素个数:);scanf(%d,&num);for( i = 0;i num; i+ )listn.key = r

7、and() % 10000;n+;return(n);/输出数组/void print(struct element aSIZE,int n)int i;for(i=0;in;i+)printf(%5d,ai .key);printf(n);/保存到文件/void save(struct element aSIZE,int n, char fileName )int m_wr=0; / 写入 TXT文件变量FILE *fp;if ( ( fp = fopen ( fileName, w ) ) = NULL )printf(File writer errorn);for (int m=0; m

8、n; m+ )m_wr = am.key;fprintf ( fp, %d , m_wr );/ 写入 TXT中fclose ( fp );/ 直接插入排序/void insert_sort(element a, int n)int i, j;element next;for(i=1; i=0 & next.key =1;i-)ai.key=ai-1.key;k=n/2;while(k=1)for(i=k+1;ia0.key)&(j=0)aj+k.key=aj.key;j=j-k;aj+k=a0;k=k/2;for(i=0;in;i+)ai.key=ai+1.key;printf(输出希尔排序

9、的结果:n);/快速排序/int hoare(struct element aSIZE,int l,int h)/分区处理函数int i,j;struct element x;i=l;j=h;x.key=ai.key;dowhile(i=x.key)j-;if(ij)ai.key=aj.key;i+;while(ij)&(ai.key=x.key)i+;if(ij)aj.key=ai.key;j-;while(ij);ai.key=x.key;return(i);/堆排序函数/调整堆的函数void heap(struct element aSIZE,int i,int m)/*i是根结点编号,

10、m是以 i为根的子树的最后一个结点编号*/struct element x;int j;x.key=ai.key;j=2*i;/保存记录内容/j 为左孩子编号while(j=m)if(jaj+1.key) /当结点 i有左,右两个孩子时,j取关键较小的孩子编号j+;if(aj.keym,以便结束循环ai.key=x.key;/堆排序的主体函数void heapsort(struct element aSIZE,int n)int i,v;struct element x;for(i=n;i0;i-)ai.key=ai-1.key;for(i=n/2;i=1;i-)heap(a,i,n);for

11、(v=n;v=2;v-)x.key=a1.key;a1.key=av.key;av.key=x.key;heap(a,1,v-1);/堆顶堆尾元素交换/这次比上次少处理一个记录for(i=0;in;i+)ai.key=ai+1.key;for(i=0;in/2;i+)int k;k=ai.key;ai.key=an-i-1.key;an-i-1.key=k;void main()int num,l,h,c;clock_t start, end;c=1;char file150 = 直接插入排序.txt;char file250 = 希尔排序.txt;char file350 = 非递归的快速排

12、序.txt;char file450 = 堆排序.txt;printf(*欢迎使用本系统学习各种排序*n);printf(*温馨提示：首先请生成用于排序的元素，以便进行排序*n);printf(*主菜单*n);printf(*1生成随机排序元素*n);printf(*printf(*printf(*printf(*printf(*23450直接插入排序希尔排序*n);*n);*n);*n);*n);非递归的快速排序堆排序退出printf(*n);while(c!=0)printf(*请输入0-5进行操作n);scanf(%d,&c);switch(c)case 1:num=creat();pr

13、int(list,num);break;case 2:start = clock();insert_sort(list,num);end = clock();print(list,num);save(list,num, file1) ;printf(The time : %d msn, end - start );break;case 3:start = clock();shell(list,num);end = clock();print(list,num);save(list,num,file2) ;printf(The time : %d msn, end - start );break

14、;case 4:l=0;h=num-1;start = clock();end = clock();printf(输出递归快速排序结果:n);print(list,num);save(list,num,file3);printf(The time : %d msn, end - start );break;case 5:start = clock();heapsort(list,num);end = clock();print(list,num);save(list,num,file4);printf(The time : %d msn, end - start );break;/main e

15、nd六、各种排序算法的性能分析由于程序不能统计出运行各种算法所需要的时间，所以在本程序中以各种算法的时间复杂度来分析各种算法的性能。2. 希尔排序：算法的时间复杂度为 n的 1.2次幂3. 冒泡排序 ：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡。算法的时间复杂度为：O(n*n)。当数据为正序，将不会有交换，复杂度为 O(0)。4. 快速排序：算法的平均时间复杂度为：log2(n)*n，所有内部排。5.简单排序：算法的时间复杂度为：O(n*n)。6.堆排序：算法的时间复杂度为：log2(n)*n综上：由各种算法的时间复杂度比较可知，堆排序和快速排序是渐进最优的

16、排序算法。总 结1、插入排序（InsertSort）插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快 2 倍。一般不用在数据大于 1000的场合下使用插入排序，或者重复排序超过 200数据项的序列。2、 Shell排序（ShellSort）Shell 排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素 进行一 次插入排序 ，以减 少数据 交换和 移动的次数 。平均 效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用 D.E.Knuth的分组方法。Shell排序比冒泡排序快 5倍，比插入排序大致

17、快 2倍。Shell排序比起QuickSort，MergeSort，HeapSort 慢很多。但是它相对比较简单，它适合于数据量在 5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。3、快速排序（QuickSort）快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。（1） 如果不多于 1个数据，直接返回。（2） 一般选择序列最左边的值作为支点数据。（3） 将序列分成 2 部分，一部分都大于支点数据，另外一部分都小于支点数据。（4） 对两边利用递归排序数列。快速排序比大部分排序算法都要快。尽管我

18、们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。4、堆排序（HeapSort）或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。心 得 体 会说实话，本次做数据结构课程设计，时间非常紧，在课间我做的少，基本上都是在课后把本次课程

19、设计做出来的。我们的课程设计安排在 17、18、19 周去做。但是在 16 周的星期 1、2 的上午和星期 4 的下午我都有考试，因此在星期 1 的上午的考试结束后，在下午的课程设计的课上我都在复习第二天要考试的内容；而在星期2 上午考试结束后，星期 2 下午和星期三我都在复习星期 4 要考试的内容。所以，我从星期 1 到星期 4 的课程设计课我基本上什么也没有做。我真正开始做课程设计是从星期 5 上午在寝室开始的。做了星期 5 一天，我才把方案设计、程序操作过程、程序流程图和很少一部分程序源代码做好，然后在寝室花了整整一周才把所有内容都写完。然后星期 2 花了一整天的时间才整理出来这个课程设

20、计的论文。写完后，我心里有两个感受：第一是：累！我差不多花了整整 20 天时间来写这个课程设计，在这其间，我只有在吃饭的时候看会儿电影，其余的时候我基本上都在做课程设计（睡觉的时间除外）。第二是：满足！这个课程设计是我从搜集资料、整理资料、到写好这份课程设计都是我一个人完成的，绝没有抄袭别人的。通过这次课程设计，我收获颇多。原来上课时没有听懂的地方，通过这次课程设计，我自己翻书，查资料，我基本上都理解了；原来疑惑的地方现在也明白了！自从拿到题目到完成整个编程，从理论到实践，在两周多的时间里，通过查资料，向老师和同学请教，让我学到很多很多的东西，同时巩固了以前所学过的知识。在测试阶段中发现了几处

21、错误导致程序运行不正确，去上网查找相关的资料,向老师请教，又同学一起讨论。通过耐心的分析源代码终于编好了一个完整无误的程序。在这次的算法与数据结构程序设计中遇到了现实编程中必然见到的问题，通过对这些问题分析和解决积累了编程的实践经验。在实际的编程操作中发现自己对计算机编程语言知识的不足。总之，通过这次课程设计，我拓宽了知识面，锻炼了能力。尤其是观察、分析和解决问题的实际工作能力。从课堂走向实践。通过课程设计，让我们找出自身状况与实际需要的差距，并在以后的学习期间及时补充相关知识。参 考 文 献【1】严蔚敏，吴伟民.数据结构（C .清华大学出版社【2】邓均辉. 数据结构与算法.清华大学出版社【3】朱站立，张选平，韩家新.数据结构-使用 c 语言.西安交通大学出版社【4】谭浩强.c 语言程序设计. 清华大学出版社.【5】 严蔚敏