数据结构排序综合设计报告(含代码).docx

《数据结构排序综合设计报告(含代码).docx》由会员分享，可在线阅读，更多相关《数据结构排序综合设计报告(含代码).docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构排序综合设计报告(含代码) 数据结构 课程设计报告 题目：排序综合 专业：计算机科学与技术 班级：嵌入式1102班 组员：11160501 丁雷 11160522 高明尧 目录 1需求分析 (3) 2概要设计 (3) 3 详细设计 (5) 4调试结果 (8) 5课程设计总结 (11) 参考书目 (11) 1需求分析 1.1 任务与分析 任务： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 要求： 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起 泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的

2、文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中 两种较快的方法。 分析： 本系统实现了几种常用的排序方法，包括：插入排序、起泡排序、快速排序（递归、非递归）、堆排序。 1.2 功能模块的划分 1.2.1 输入模块 利用随机函数产生N个随机整数（20000以上），个数由用户自己输入。 1.2.2输出模块 输出排序前或排序后的数据元素到屏幕显示，并且输出按照选择的算法排序后的数据元素到文件中保存。 1.2.3输出结论 比较不同排序时间长短，输出两种最快的排序方法。 1.2.4排序模块 插入排序 思路:设有一组关键字K1,K2,.,Kn,排序开始变认为K1

3、是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列. 冒泡排序 如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较 简单选择排序 通过n-I次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之 2概要设计 2.1程序结构框图 2.2程序流程图插 入 排 序 气 泡 排 序 简 单 选 择 排 序 寻 找 最 快 排 序 开始产 生 随

4、 机 函 数 综合排序系统 开始 选择选取数 产 生 随 机 函 数 插 入 排 序 起 泡 排 序 简 单 选 择 排 序 寻 找 最 快 排 序 退 出 输出 2.3头文件 #include #include #include #include 2.5各种操作函数： （1）创建一个数组函数： （2）输出数组函数： ( 3 ) 简单选择排序 （4）插入排序函数： （5）起泡排序函数： （6）时间函数：start = clock();end = clock(); 2.6主函数 V oid main() 接受命令（选择要执行的操作）； 处理命令； 输出结果； 3 详细设计 #include #i

5、nclude #include #define N 30001 void main() int i,j,n,k; int n1,t; int aN,bN,c3,d3; clock_t start,finish; int time1,time2,time3; printf(*数据结构排序综合*n); printf(n输入要产生的随机数个数：); scanf(%d,&n); srand(unsigned)time(NULL); for(i=0;it & j=0) bj+1=bj; j-; if(j!=(i-1) /第i个数字比前面的都大，不需要重新插入 bj+1=t; for(i=n-1;i=0;

6、i-) printf(%d ,bi); finish=clock(); c0=finish-start; printf(n插入排序耗时%d毫秒！nnn,c0); /起泡排序 for(i=0;i0) j=0; for(i=0;ibi+1) t=bi; bi=bi+1; bi+1=t; j=i; n1=j; printf(%d ,t); finish=clock(); c1=finish-start; printf(n起泡排序耗时%d毫秒！nnn,c1); /简单选择排序 for(i=0;ii-1;j-) if(bj=0;i-) printf(%d ,bi); finish=clock(); c2

7、=finish-start; printf(n简单选择排序耗时%d毫秒！nnn,c2); /寻找两种最快方法 for(i=0;idj) t=di; di=dj; dj=t; / printf(%d,c0); printf(排序这组数据最快的两组排序法是：n); if(d0=c0) printf(插入排序：%d毫秒n,d0); if(d0=c1) printf(起泡排序：%d毫秒n,d0); if(d0=c2) printf(简单选择排序：%d毫秒n,d0); if(d0!=d1) if(d1=c0) printf(插入排序：%d毫秒n,d1); if(d1=c1) printf(起泡排序：%d

8、毫秒n,d1); if(d1=c2) printf(简单选择排序：%d毫秒n,d1); 4调试结果 数据由系统随机产生，不需要输入测试数据，产生数据元素的个数由用户输入。 4.1欢迎界面 4.2产生随机函数 4.3 排序 输入50个随机数个排序方法的结果 排序时间结果 6课程设计总结 通过这次课程设计的学习让我学会了许多，加深了对数据结构排序算法的认识。在这次课程设计中，独立完成了每种排序算法。排序算法选了三个，包括：插入排序、气泡排序、简单选择排序。同时也实现了随机数的生成。虽然在算法完成的过程中从网上参考了一些资料，但对这次课程设计的成果还是非常满意的。 这次的课程设计还有很多不足之处。有

9、些排序方法没有些，像堆排序了，快序排序了。还有就是最后寻找两种最坏的方法时花了很多时间，想了几种方法，开始用结构体，但发现太麻烦了，所以改用了上述方法。由于时间限制，只在课程设计快结束时完成了产生随机文件这部分，我想以后有时间再来完成它。 同时在完成这个课程设计后，我也学到了很多知识，并能训练的掌握他们了。首先学会了随机数的产生。熟练的撑握了C语言的文件读写操作。撑握了每种排序算法的基本思想，并从同学那里学会了编写程序的一般步骤：思考问题，写出解决方案，写出伪代码，完成代码，调试程序。不像以前那样开始就直接写代码。当然，还包括如何写出操作简便，感觉友好的界面。但我还是认为自己还有很多不足，希望以后能弥补。 参考书目 1 数据结构（C语言版）。严蔚敏，清华大学出版社 2 数据结构习题集（C语言版）。严蔚敏，清华大学出版社 3 C语言课程设计案例精编。郭翠英，中国水利出版社