课 程 设 计
课程设计名称： 排序综合 专 业 班 级 ： 00 学 生 姓 名 ： 00 学 号 ： 000 指 导 教 师 ： 000 课程设计时间： 2010.6.21-2010.6.25
1 / 22
计算机科学与技术 专业课程设计任务书
学生姓名 题 目 课题性质 指导教师 A．工程设计 专业班级 排序综合 课题来源 同组姓名 D．自拟课题 无 学号 主要内容 综合应用所学知识，设计完成一个排序综合系统。本系统拟实现以下功能： 1.直接插入排序 2.希尔排序 3.快速排序 4.堆排序 5.结果保存 6.计算排序时间 系统要求采用VC6.0工具进行开发实现。 综合运用和融化所学理论知识，提高分析和解决实际问题的能力，使用c语任务要求 言设计一个排序综合系统。 完成课程设计报告，报告中对关键部分给出图表说明。要求格式规范，工作量饱满。 [1] 数据结构. 严蔚敏，吴伟民 编著. 清华大学出版社. 2007年03月 [2] 数据结构、算法与应用：C++语言描术. （美）萨尼（Sahni,S.） 著，汪诗林 等译. 机械工业出版社.2005年03月 指导教师签字： 审查意见 教研室主任签字： 2010 年 6 月24 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页
参考文献
2 / 22
信息科学与工程 学院课程设计成绩评价表
课程名称：数据结构课程设计
设计题目：排序 序号 评审项目 分 数 满分标准说明 思路清晰；语言表达准确，概念清楚，论点正确；实验方法科学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，做了大量的工作。 内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解 整体构思合理，理论依据充分，设计完整，实用性强 1 内 容 2 创 新 3 完整性、实用性 4 数据准确、可靠 数据准确，公式推导正确 设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定 能很好的遵守各项纪律，设计过程认真； 准备工作充分，回答问题有理论依据，基本概念清楚。主要问题回答简明准确。在规定的时间内作完报告。 5 规 范 性 6 纪 律 性 7 答 辩 总 分 综 合 意 见 指导教师 年 月 日
3 / 22
1、 需求分析
1.1、直接插入排序
思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.
1.2、希尔排序
思路：先取一个正整数d1(d1 1.3、快速排序:（递归和非递归） 思路:以第一个关键字K1为控制字，将[K1、K2、….Kn]分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。 将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。 重复第（1）、（2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的处理，直到栈空 分区处理函数hoare 思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。如对(46、56、14、43、95、10、19、72)。第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。从文件右端元素r[j].key开始与控制字x.key相比较，当r[j].key大于等于x.key时，r[j]不移动，修改指针j，j--，直到r[j].key r[i].key与x.key相比较，当r[i].key小于等于x.key时，r[i]不移动，修改指针i，i--，直到r[i].key 思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理： 初建堆，从堆的定义出发，当i=1、2、。。。。、[2/n]时应满足ki<=k2i和ki<=k2i+1.所以先取i=[n/2](它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。 堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。 2、 概要设计 2.1、头文件 #include 2.2 、ADT struct element { int key; }list[20]; struct rnode { int key; int point; 5 / 22 }; 2.3、各种操作函数： （1）创建一个数组函数：int creat()； （2）输出数组函数：void print(struct element a[20],int n)； （3）保存函数：void save(struct element a[SIZE],int n, char [] ) （4）直接插入排序函数：void insert_sort(element a[], int n) （5）希尔排序函数：void shell(struct element a[20],int n)； （6）快速排序函数（分区处理函数）：int hoare(struct element a[20],int l,int h)； （7）非递归的快速排序函数：void quick1(struct element a[20],int n)； （8）递归的快速排序函数：void quick2(struct element a[20],int l,int h)； （9）堆排序（调整堆的函数）：void heap(struct element a[20],int i,int m)； （10）堆排序（主体函数）：void heapsort(struct element a[20],int n)； （11）时间函数：start = clock();end = clock(); 2.4、主函数 Void main() { 接受命令（选择要执行的操作）； 处理命令； 输出结果； } 3、 详细设计 3.1、程序源代码： #include #define SIZE 1000000 6 / 22 struct element { int key; }list[SIZE]; ///////创建一个数组//////// int creat() { int i,n; int num; } /////////////输出数组///////////// void print(struct element a[SIZE],int n) { int i; 7 / 22 n=0; printf(\"请输入元素个数:\"); scanf(\"%d\for( i = 0;i < num; i++ ) { } return(n); list[n].key = rand() % 10000; n++; for(i=0;i /////////////保存到文件///////////// void save(struct element a[SIZE],int n, char [] ) { int m_wr=0; // 写入TXT文件变量 FILE *fp; if ( ( fp = fopen ( , \"w\" ) ) == NULL ) printf(\" error\\n\"); for (int m=0; m void insert_sort(element a[], int n) { int i, j; element next; for(i=1; i { } m_wr = a[m].key; fprintf ( fp, \"%d \ // 写入TXT中 fclose ( fp ); } } next = a[i]; for(j=i-1;j>=0 && next.key < a[j].key;j--) a[j+1].key=a[j].key; a[j+1]=next; printf(\"输出直接插入排序的结果:\\n\"); /////////////////希尔排序////////////////////// void shell(struct element a[SIZE],int n) { int i,j,k; for(i=n;i>=1;i--) a[i].key=a[i-1].key; k=n/2; while(k>=1) { for(i=k+1;i<=n;i++) { } 9 / 22 a[0].key=a[i].key; j=i-k; while((a[j].key>a[0].key)&&(j>=0)) { } a[j+k]=a[0]; a[j+k].key=a[j].key; j=j-k; } } k=k/2; for(i=0;i ////////////////////快速排序/////////////////////////// int hoare(struct element a[SIZE],int l,int h)//分区处理函数 { int i,j; struct element x; i=l; j=h; x.key=a[i].key; do { while((i j--; if(i a[i].key=a[j].key; i++; if(i } } a[j].key=a[i].key; j--; }while(i int i,l,h,tag,top; int s[20][2]; l=0;h=n-1;tag=1;top=0; do { while(l else { l=s[top][0]; h=s[top][1]; 11 / 22 } } top--; }while(tag==1); void quick2(struct element a[SIZE],int l,int h)//递归的快速排序 { } ////////////////////堆排序函数////////////////////////// //调整堆的函数 void heap(struct element a[SIZE],int i,int m) /*i是根结点编号,m是以i为根的子树的最后一个结点编号*/ { struct element x; int j; x.key=a[i].key; //保存记录内容 j=2*i; //j 为左孩子编号 while(j<=m) { if(j int i; if(l if(a[j].key>a[j+1].key) //当结点i有左,右两个孩子时,j取关键较小 的孩子编号 j++; if(a[j].key 结束循环 } //堆排序的主体函数 void heapsort(struct element a[SIZE],int n) { int i,v; struct element x; for(i=n;i>0;i--) a[i].key=a[i-1].key; } a[i].key=x.key; for(i=n/2;i>=1;i--) heap(a,i,n); for(v=n;v>=2;v--) { x.key=a[1].key; //堆顶堆尾元素交换 a[1].key=a[v].key; 13 / 22 } } a[v].key=x.key; heap(a,1,v-1); //这次比上次少处理一个记录 for(i=0;i for(i=0;i a[i].key=a[n-i-1].key; a[n-i-1].key=k; void main() { int num,l,h,c; clock_t start, end; c=1; char file1[50] = \"直接插入排序.txt\"; char file2[50] = \"希尔排序.txt\"; char file3[50] = \"非递归的快速排序.txt\"; char file4[50] = \"递归的快速排序.txt\"; char file5[50] = \"堆排序.txt\"; printf(\"***********欢迎使用本系统学习各种排序*************\\n\"); printf(\"*温馨提示：首先请生成用于排序的元素，以便进行排序*\\n\"); printf(\"********************主菜单************************\\n\"); 14 / 22 printf(\"* 1 生成随机排序元素 *\\n\"); printf(\"* 2 直接插入排序 *\\n\"); printf(\"* 3 希尔排序 *\\n\"); printf(\"* 4 非递归的快速排序 *\\n\"); printf(\"* 5 递归的快速排序 *\\n\"); printf(\"* 6 堆排序 *\\n\"); printf(\"* 0 退出 *\\n\"); printf(\"**************************************************\\n\"); while(c!=0) { printf(\"*请输入0-6进行操作 \\n\"); scanf(\"%d\switch(c) { case 1:num=creat(); print(list,num); break; case 2:start = clock(); insert_sort(list,num); end = clock(); print(list,num); save(list,num, file1) ; printf(\"The time : %d ms\\n\break; case 3:start = clock(); shell(list,num); end = clock(); print(list,num); save(list,num,file2) ; 15 / 22 printf(\"The time : %d ms\\n\break; case 4:start = clock(); quick1(list,num); end = clock(); print(list,num); save(list,num,file3) ; printf(\"The time : %d ms\\n\break; case 5:l=0;h=num-1; start = clock(); quick2(list,l,h); end = clock(); printf(\"输出递归快速排序结果:\\n\"); print(list,num); save(list,num,file4); printf(\"The time : %d ms\\n\break; case 6:start = clock(); heapsort(list,num); end = clock(); print(list,num); save(list,num,file5); } } printf(\"The time : %d ms\\n\break; }//main end 16 / 22 4、 调试分析 4.1、insertion_sort排序算法分析： 该算法的时间复杂度为O(n*n).直接插入排序是稳定的排序方法。当n值较 小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 4.2、shell排序算法分析： Shell排序算法的时间复杂度分析比较复杂，实际所需的时间取决于各次排 序时增量的个数和增量的取值。当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。由于Shell排序算法是按增量分组进行的排序，所以Shell排序算法是一种不稳定的排序算法。 4.3、quick排序算法分析： 快速排序主体算法时间运算约为O(log2n),划分子区函数运算量约为O(n)， 所总时复杂度为O(nlog2n). 因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。 4.4、heapsort排序算法分析： 堆排序中heap算法的时间复杂度与堆所对应的完全二叉树的深度[log2n]+1 相关，而heapsort中对heap的调用数量级为n，所以整个堆排序的时间复杂度为O(nlog2n)。 堆排序是不稳定的。 17 / 22 5、 调试结果 5.1系统操作 5.1.1、主菜单界面 5.1.2、生成排序元素 5.1.3直接插入排序 18 / 22 5.1.4、希尔排序 5.1.5非递归的快速排序 5.1.6递归的快速排序 5.1.7堆排序 19 / 22 5.2、测试数据 5.2.1、 100个数据元素 5.2.2、 1000个数据元素 20 / 22 5.2.3、10000个数据元素 5.2.4、100000个数据元素 21 / 22 课程设计总结 通过这次课程设计的学习让我学会了许多。让我对我们的专业知识有了很大 理解！我对专业的课程有了初步的认识。 在这次课程设计中，独立完成了在两种存储结构下的每种排序算法。排序算法共有七个：插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序。同时也实现了随机数的生成。并把排序后的结果保存在不同的文件中。虽然在算法完成的过程中也在网上查阅了一些资料，但对这次课程设计的成果还是非常满意的。 这次的课程设计还有很多不足之处，如链表存储结构中的堆排序算法，当排序个数过多时，就会等待很长时间。可能时调用的函数过多的原因造成的，但排序是正确的。用指针代替函数的调用。还有就是随机数不能随时更改，只能设定一次。链表归并算法不是对链表直接操作，而是将链表中的元素放入数组中进行排序，我想了很多方法都没有想出对链表的直接操作的算法。由于时间限制，只在课程设计快结束时完成了产生随机文件这部分，我想以后有时间再来完成它。 同时在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的文件读写操作。撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。 但我还是认为自己有些不足，希望以后能弥补这些不足。 所以，这次的课程设计我学会了很多，不光让我认识了本专业知识，还让我学了一定的心境！那就是做事情的时候即使不会做也不能慌张，要慢慢放下心来，不要光想自己怎么、怎么不会了！不要去想不会，而是冷下心来慢慢思考、思考。这样你就会有了思虑的。 22 / 22 因篇幅问题不能全部显示，请点此查看更多更全内容