《数据结构课程设计排序综合报告》由会员分享，可在线阅读，更多相关《数据结构课程设计排序综合报告（27页珍藏版）》请在金锄头文库上搜索。
1、数学与计算机学院课程设计说明书课 程 名 称: 数据结构-课程设计 课 程 代 码: 8404181 题 目: 排序综合 年级/专业/班: 2009级软件工程四班 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 06 月 20 日完 成 时 间: 2011 年 07 月 03 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 摘 要 排序（sorting）是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。由于
2、待排序的记录数量不同，使得排序过程中涉及的存储器的不同，可将排序方法分为两大类：一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需要对外存进行访问的排序过程。内部排序又分为：插入排序、快速排序、选择排序、归并排序和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序；基数排序分为：多关键字排序和链式基数排序。本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质，排序的应用，排序的分类，利用C语言采用数组存储
3、结构编程实现了本排序综合系统，该系统包含了几种常见的排序方法，有直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。关键字：内部排序，外部排序，排序，重新排列，关键字目 录 1需求分析11.1 任务与分析11.2 功能模块的划分11.2.1 输入模块11.2.2 选择排序方法模块11.2.3 输出模块11.3 排序模块分析21.3.1 直接插入排序21.3.2 希尔排序21.3.3 冒泡排序21.3.4 快速排序（递归和非递归）21.3.5 简单排序31.3.6 堆排序31.4 系统需求分析规格说明书32开发及运行平台42.1 windows操作系统42.2
4、VC+6.043 概要设计43.1 程序结构框图43.2 程序流程图53.3 抽象数据类型定义53.4 各种操作函数：63.5 主函数64 详细设计74.1 数据类型定义74.2 主要模块内部设计74.2.1 模块1 直接插入排序模块设计74.2.2 模块2 希尔排序模块设计74.2.3 模块3 冒泡排序模块设计84.2.4 模块4 非递归快排模块设计94.2.5 模块5 递归快排模块设计104.2.6 模块6 简单排序模块设计104.2.7 模块7 堆排序模块设计105 调试分析125.1 调试过程125.2 性能分析126 测试分析136.1 测试用例136.2 测试结果137 结论15参
5、考文献16附 录171需求分析1.1 任务与分析任务：机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。分析：前面分析了排序的种类以及过程，因此，本系统实现了几种常用的排序方法，包括：直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。1.2 功能模块的划分1.2.1 输入模块
6、利用随机函数产生N个数（20000以上），产生的数据个数有用户自己输入。1.2.2 选择排序方法模块在菜单中通过键入相应的选项编号来选择采用何种算法排序，包括的排序算法有：直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。1.2.3 输出模块输出排序前的，或者排序后的数据元素到屏幕上显示，并且输出一某一种算法排序后的数据元素到文件中保存。1.3 排序模块分析1.3.1 直接插入排序思路：设有一组关键字K1,K2,.,Kn,排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之
7、成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.3.2 希尔排序思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,.,di=11.3.3 冒泡排序思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一
8、趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，.，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用aj和aj+1标识，i的值依次为1,2,.,9，对于每一个i, j的值依次为1,2,.10-i。1.3.4
9、快速排序（递归和非递归）思路:以第一个关键字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作为控制字，该关键字所属的记录另
10、存储在一个x变量中。从文件右端元素rj.key开始与控制字x.key相比较，当rj.key大于等于x.key时，rj不移动，修改指针j，j-，直到rj.keyx.key，把记录rj移动到文件左边i所指向的位置;然后在文件左边修改i指针,i+，让ri.key与x.key相比较，当ri.key小于等于x.key时，ri不移动，修改指针i，i-，直到ri.keyx.key, 把记录ri移动到文件右边j所指向的位置;然后在文件右边修改j指针j-。重复上面的步骤.1.3.5 简单排序思路：在n个记录中，用两重循环，外层循环i从第一个元素a0开始至最后一个元素an-1，内层循环j从外层循环所值元素ai的下
11、一个元素aj=ai+1开始至最后一个元素an-1搜索，只要找到比ai小的元素，便与ai交换，如此重复执行操作，当外层循环完毕后，全部记录就排序完成了。1.3.6 堆排序思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。、2/n时应满足ki=k2i和ki=k2i+1.所以先取i=n/2(它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中
12、最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。1.4 系统需求分析规格说明书这是一个关于排序的综合系统，该系统包含就平时记录操作中比较常见的几种排序方法；其中包括：直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。应用该系统可以完成数据记录的排序操作。对不同的数据量、不同的数据结构可以采用不同的排序方法。2开发及运行平台2.1 windows操作系统2.2 VC+6.0本系统在上述环境中设计实现，并且编译通过，能正常运行。3 概要设计3.1 程序
13、结构框图图1 程序结构框图3.2 程序流程图图 2 程序流程图3.3 抽象数据类型定义ADT SORT 数据对象：D=随机产生的num（用户输入）个数据元素； 基本操作：int creat()；-产生随机数void insert_sort(struct element a, int n)；-直接插入排序void shell_sort(struct element a,int n)；-希尔排序void bubble_sort(struct element a,int n)；-冒泡排序int hoare(struct element a,int l,int h)；-快排的分区处理void quic
14、k_sort_1(struct element a,int n)；-非递归快排void quick_sort_2(struct element a,int l,int h)；-递归快排void jiandan_sort(struct element a,int n)；-简单排序void heap(struct element a,int i,int m)；-堆调整void heapsort(struct element a,int n)；-堆排序ADT SORT3.4 各种操作函数：（1）创建一个数组函数：int creat()；（2）输出数组函数：void print(struct element a,int n)；（3）保存函数：void save(struct element aSIZE,int n, char fileName ) （4）直接插入排序函数：voi
