数据结构课程设计-排序综合报告.doc

《数据结构课程设计-排序综合报告.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-排序综合报告.doc（29页珍藏版）》请在三一文库上搜索。

1、数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构-课程设计 课 程 代 码: 8404181 题 目: 排序综合 年级/专业/班: 2009 级软件工程四班 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 06 月 20 日 完 成 时 间: 2011 年 07 月 03 日 课程设计成绩： 学习态度及平 时成绩（30） 技术水平与实际 能力（20） 创新（5）说明书撰写质量（45） 总 分 （100） 指导教师签名： 年 月 摘摘 要要 排序（sorting）是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据 元素（记录），根据某一个（或几个）关键字按一定的

2、顺序重新排列成为有序的序列。由于 待排序的记录数量不同，使得排序过程中涉及的存储器的不同，可将排序方法分为两大 类：一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程； 另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录， 在排序过程中尚需要对外存进行访问的排序过程。 内部排序又分为：插入排序、快速排序、选择排序、归并排序和基数排序。其中插入 排序又分为：直接插入排序、其他插入排序和希尔排序；选择排序分为：简单选择排序、 树形选择排序和堆排序；基数排序分为：多关键字排序和链式基数排序。 本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质

3、，排序的应 用，排序的分类，利用 C 语言采用数组存储结构编程实现了本排序综合系统，该系统包 含了几种常见的排序方法，有直接插入排序、希尔排序、冒泡排序、非递归的快速排序、 递归的快速排序、简单排序、堆排序。 关键字关键字：内部排序，外部排序，排序，重新排列，关键字 目目 录录 1 需求分析需求分析1 1.1 任务与分析任务与分析 .1 1.2 功能模块的划分功能模块的划分 .1 1.2.1 输入模块1 1.2.2 选择排序方法模块1 1.2.3 输出模块1 1.3 排序模块分析排序模块分析 .2 1.3.1 直接插入排序2 1.3.2 希尔排序2 1.3.3 冒泡排序2 1.3.4 快速排序

4、（递归和非递归）2 1.3.5 简单排序3 1.3.6 堆排序3 1.4 系统需求分析规格说明书系统需求分析规格说明书 .3 2 开发及运行平台开发及运行平台4 2.1 WINDOWS操作系统操作系统.4 2.2 VC+6.0.4 3 概要设计概要设计.4 3.1 程序结构框图程序结构框图 .4 3.2 程序流程图程序流程图 .5 3.3 抽象数据类型定义抽象数据类型定义 .5 3.4 各种操作函数：各种操作函数： .6 3.5 主函数主函数 .6 4 详细设计详细设计.7 4.1 数据类型定义数据类型定义 .7 4.2 主要模块内部设计主要模块内部设计 .7 4.2.1 模块 1 直接插入排

5、序模块设计7 4.2.2 模块 2 希尔排序模块设计7 4.2.3 模块 3 冒泡排序模块设计8 4.2.4 模块 4 非递归快排模块设计9 4.2.5 模块 5 递归快排模块设计10 4.2.6 模块 6 简单排序模块设计10 4.2.7 模块 7 堆排序模块设计10 5 调试分析调试分析.12 5.1 调试过程调试过程 .12 5.2 性能分析性能分析 .12 6 测试分析测试分析.13 6.1 测试用例测试用例 .13 6.2 测试结果测试结果 .13 7 结论结论.15 参考文献参考文献.16 附附 录录.17 1 1 1 需需求求分分析析 1.11.1 任务与分析任务与分析 任务：

6、机函数产生 N 个随机整数（20000 以上） ，对这些数进行多种方法进行排序。 要求： 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、 希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序） 。并把排序后的 结果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比） ， 找出其中两种较快的方法。 分析： 前面分析了排序的种类以及过程，因此，本系统实现了几种常用的排序方法， 包括：直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排 序、简单排序、堆排序。 1.21.2 功能模块的划分功能模块的划分 1.2.11.2.

7、1 输入模块输入模块 利用随机函数产生 N 个数（20000 以上） ，产生的数据个数有用户自己输入。 1.2.21.2.2 选择排序方法模块选择排序方法模块 在菜单中通过键入相应的选项编号来选择采用何种算法排序，包括的排序算法有： 直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排 序、堆排序。 1.2.31.2.3 输出模块输出模块 输出排序前的，或者排序后的数据元素到屏幕上显示，并且输出一某一种算法排 序后的数据元素到文件中保存。 2 1.31.3 排序模块分析排序模块分析 1.3.11.3.1 直接插入排序直接插入排序 思路：设有一组关键字K1,K2,.,Kn,

8、排序开始变认为 K1 是一个有序的序列, 让 K2 插入到表长为 1 的有序序列,使之成为一个表长为 2 的有序序列, 让 K3 插入到表 长为 2 的有序序列,使之成为一个表长为 3 的有序序列,依次类推,最后让 Kn 插入上述表 长为 n-1 的有序序列,得到一个表长为 n 的有序序列. 1.3.21.3.2 希尔排序希尔排序 思路：先取一个正整数 d1(d1=1),即所有记录成为一个组为此.一般选 d1 约为 n/2,d2 为 d1/2,.,di=1 1.3.31.3.3 冒泡排序冒泡排序 思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟： 首先比较第 1 个和第 2

9、 个数，将小数放前，大数放后。然后比较第 2 个数和第 3 个数， 将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。 至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为 可能由于第 2 个数和第 3 个数的交换，使得第 1 个数不再小于第 2 个数） ，将小数放前， 大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的） ，第二趟结束， 在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数） 。如此下 去，重复以上过程，直至最终完成排序。用二重循环实现，外循环变量设为 i，内循环 变量设为 j。外循环重复 9 次，内循环

10、依次重复 9，8，.，1 次。每次进行比较的两个 元素都是与内循环 j 有关的，它们可以分别用 aj和 aj+1标识，i 的值依次为 1,2,.,9，对于每一个 i, j 的值依次为 1,2,.10-i。 1.3.41.3.4 快速排序（递归和非递归）快速排序（递归和非递归） 思路:以第一个关键字 K1 为控制字，将K1、K2、.Kn分成两个子区，使左区的 有关键字小于等于 K1，右区所有关键字大于等于 K1，最后控制居两个子区中间的适 当位置。在子区内数据尚处于无序状态。 将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的 3 左子区和右子区，控制字区中。 重复第（1）

11、 、 （2）步，直到左区处理完毕。然后退栈对一个个子区进行相类似的 处理，直到栈空 分区处理函数 hoare( ) 思路：首先用两个指针 i、j 分别指向首、尾两个关键字，i=1，j=8。如对 (46、56、14、43、95、10、19、72)。第一个关键字 46 作为控制字，该关键字所属的 记录另存储在一个 x 变量中。从文件右端元素 rj.key 开始与控制字 x.key 相比较，当 rj.key 大于等于 x.key 时，rj不移动，修改指针 j，j-，直到 rj.key=0 i-) / 元素后移一个位置 ,0 号位置作为监视哨 ai=ai-1; k=n/2; / 步长 while(k=

12、1) 8 for(i=k+1;ia0.key) j=j-k; aj+k=a0; k=k/2; / 更新步长 for(i=0;i aj+1.key) / 满足条件交换元素 ai aj; flag=1; if(flag=0) break; printf(“ 冒泡排序完成!n“); 9 4.2.44.2.4 模块模块 4 4 非递归快排模块设计非递归快排模块设计 模块算法： int hoare(struct element a,int l,int h)/分区处理函数 i=l;j=h;x=ai; /初始化 do while(i=x.key) /从后向前搜索第一个小于 x 的元素 j-; if(i aj

13、.key) /满足条件，交换元素 ai aj; printf(“ 简单排序完成!n“); 4.2.74.2.7 模块模块 7 7 堆排序模块设计堆排序模块设计 模块算法 /调整堆的函数 void heap(struct element a,int i,int m) 11 /*i 是根结点编号,m 是以 i 为根的子树的最后一个结点编号*/ x=ai; /保存记录内容 j=2*i; /j 为左孩子编号 while(jaj+1.key) /当结点 i 有左,右两个孩子时,j 取关键较小 的孩子编号 j+; if(aj.keym,以便结束循环 ai=x; /堆排序的主体函数 void heapsor

14、t(struct element a,int n) for(i=n;i0;i-) /全部元素后移一位 ai=ai-1; for(i=n/2;i=1;i-) heap(a,i,n); /堆调整 for(v=n;v=2;v-) a1 av; /堆顶堆尾元素交换 heap(a,1,v-1); /这次比上次少处理一个记录 for(i=0;i #include #include #define SIZE 1000000 / 定义数据类型结构体 / /关键字定义在结构体中，方便以后的代码重用 struct element int key; listSIZE; /创建一个数组/ int creat() in

15、t i; / i- 循环控制 int num; / num- 记录元素的个数 printf(“ 请输入元素个数:“); scanf(“%d“, if(num999999) printf(“输入超界!n“); return 0; for( i = 0;i =0 i-) / 元素后移一个位置 ,0 号位置作为监视哨 ai=ai-1; k=n/2; / 步长 while(k=1) for(i=k+1;ia0.key) j=j-k; aj+k=a0; k=k/2; for(i=0;i aj+1.key) / 满足条件交换元素 19 temp=aj; aj=aj+1; aj+1=temp; flag=1

16、; if(flag=0) break; printf(“ 冒泡排序完成!n“); /快速排序/ int hoare(struct element a,int l,int h)/分区处理函数 int i,j; struct element x; i=l; j=h; x=ai; do while(i=x.key) /从后向前搜索第一个小于 x 的元素 j-; if(i aj.key) /满足条件，交换元素 temp=ai; ai=aj; aj=temp; printf(“ 简单排序完成!n“); /堆排序函数/ /调整堆的函数 void heap(struct element a,int i,in

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

18、=n/2;i=1;i-) heap(a,i,n); /堆调整 for(v=n;v=2;v-) x=a1; /堆顶堆尾元素交换 a1=av; av=x; heap(a,1,v-1); /这次比上次少处理一个记录 for(i=0;in;i+) /元素前移一位 ai=ai+1; for(i=0;in/2;i+) /交换元素 x=ai; ai=an-i-1; an-i-1=x; printf(“ 堆排序完成!n“); / 欢迎界面函数 / void startface() system(“color 0A“); /设置屏幕显示的前景色、背景色 system(“cls“); /清屏 printf(“nn

19、nnn“); printf(“ * 22 n“); printf(“ * * n“); printf(“ * 欢迎使用综合排序系统 * n“); printf(“ * * n“); printf(“ * n“); printf(“nnnnnnnnnn“); system(“pause“); /暂停 / 菜单函数 / void menu() system(“cls“); /清屏 printf(“ntt* 主菜单 *n“); printf(“tt| |n“); printf(“tt| 1-生成随机排序元素 |n“); printf(“tt| 2-直接插入排序 |n“); printf(“tt| 3

20、-希尔排序 |n“); printf(“tt| 4-冒泡排序 |n“); printf(“tt| 5-非递归的快速排序 |n“); printf(“tt| 6-递归的快速排序 |n“); printf(“tt| 7-简单排序 |n“); printf(“tt| 8-堆排序 |n“); printf(“tt| 0-退出 |n“); printf(“tt| |n“); printf(“n“); void main() int num,c; / num- 记录个数， c- 操作选项 int flag=0; /标志 clock_t start, end; / 计时变量 / 文件名数组 / char f

21、ile130 = “直接插入排序.txt“; char file230 = “希尔排序.txt“; char file330 = “冒泡排序.txt“; char file430 = “非递归的快速排序.txt“; char file530 = “递归的快速排序.txt“; char file630 = “简单排序.txt“; char file730 = “堆排序.txt“; startface(); menu(); 23 while(1) printf(“*请输入操作项：“); scanf(“%d“, if(c!=1 else switch(c) case 1:num=creat(); p

22、rint(list,num); printf(“n“); flag=1; break; case 2:start = clock(); insert_sort(list,num); end = clock(); printf(“ 直接插入排序后的结果：n“); print(list,num); save(list,num, file1) ; printf(“ The time : %d msn“, end - start ); printf(“n“); break; case 3:start = clock(); shell_sort(list,num); end = clock(); pri

23、ntf(“ 希尔排序后的结果：n“); print(list,num); save(list,num,file2) ; printf(“ The time : %d msn“, end - start ); printf(“n“); break; case 4:start = clock(); bubble_sort(list,num); end = clock(); printf(“ 冒泡排序后的结果：n“); print(list,num); save(list,num,file3) ; printf(“ The time : %d msn“, end - start ); printf(

24、“n“); break; case 5:start = clock(); quick_sort_1(list,num); end = clock(); printf(“ 非递归快排后的结果：n“); print(list,num); 24 save(list,num,file4) ; printf(“ The time : %d msn“, end - start ); printf(“n“); break; case 6: start = clock(); quick_sort_2(list,0,num-1); end = clock(); printf(“ 递归快排完成!n“); prin

25、tf(“ 递归快排后的结果：n“); print(list,num); save(list,num,file5); printf(“ The time : %d msn“, end - start ); printf(“n“); break; case 7:start = clock(); jiandan_sort(list,num); end = clock(); printf(“ 简单排序后的结果：n“); print(list,num); save(list,num,file6); printf(“ The time : %d msn“, end - start ); printf(“n“); break; case 8:start = clock(); heapsort(list,num); end = clock(); printf(“ 堆排序后的结果：n“); print(list,num); save(list,num,file7); printf(“ The time : %d msn“, end - start ); printf(“n“); break; case 0:exit(1); default:printf(“输入错误!请重新输入.n“);