《数据结构》设计实验资料.doc

 PAGE \* MERGEFORMAT 24 HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY 数据结构 课程设计报告 课设题目：多种排序方式的比较专 业：计算机科学与技术班 级：姓 名：张浩然完成日期：指导教师： 目录 1、引言 1.1课设目的3 1.2课设内容3 2、需求分析 2.1任务与分析3 2.2功能模块的划分3 3、总体设计 4、详细设计 4.1冒泡排序5 4.2快速排序6 4.3直接插入排序7 4.5折半插入排序7 4.4堆排序7 5、调试结果 5.1冒泡排序测试8 5.2快速排序测试8 5.3直接插入排序测试9 5.4折半插入排序测试9 5.5堆排序测试10 5.6输入错误10 6、课程设计总结11 1.1课程设计目的 学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养数据抽象能力和软件设计的能力。通过全部过程培养和锻炼的钻研能力、动手能力、分析问题和解决问题的实际能力。 1.2课程设计内容 本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的几种排序方法的任意一种进行排序。包括冒泡排序，直接插入排序，折半插入排序，堆排序和快速排序。对于每一种排序算法可以输出初始序列和每一趟的排序结果。 2.1任务与分析 任务： 利用随机函数产生N个随机整数，对这些数进行多种方法进行排序。 分析： 本系统实现了几种常用的排序方法，包括：折半插入排序、直接插入排序、冒泡排序、快速排序（递归）、堆排序。 2.2功能模块的划分 2..2.1 输入模块 利用随机函数产生N个随机整数，个数由用户从键盘中自己输入。 2.2.2选择模块 在菜单中选择相应的编号来选择采用何种排序算法，算法包括：冒泡排序、直接插入排序、折半插入、快速排序（递归）、堆排序。 2.2.3输出模块 输出排序前或排序后的数据元素到屏幕显示，并且输出每一趟的排序结果显示在屏幕上。 2.2.4各个排序模块 具体的设计思路在后序的详细设计中将系统的介绍。 总体设计（框图结构） 排序小软件 错误再次输入 堆排序 折半插入排序 快速排序 冒泡排序 直接插入排序 退出 开始 调用欢迎界面函数showmenu() Startface() 选择操作项 错误再次输入 直接插入排序 冒泡排序 折半插入排序 退出 堆排序 快速排序 结束 详细设计 4.1冒泡排序 冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。 过程描述如下图所示： 图3.3 冒泡排序的比较结果 （1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。 （2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。 （3）、重复步骤（2），直到无序区中只剩下一个记录。 4.2快速排序 首先用两个指针i、j分别指向首，以第一个元素为关键字，该关键字所属的记录另存储在一个x变量中。从文件右端元素r[j].key开始与控制字x.key相比较，当r[j].key大于等于x.key时，r[j]不移动，修改指针j，j--，直到r[j].keyx.key，把记录r[j]移动到文件左边i所指向的位置;然后在文件左边修改i指针,i++，让r[i].key与x.key相比较，当r[i].key小于等于x.key时，r[i]不移动，修改指针i，i--，直到r[i].keyx.key, 把记录r[i]移动到文件右边j所指向的位置;然后在文件右边修改j指针j--。重复上面的步骤. 初始关键字序列 72 6 57 88 60 42 83 73 48 85 i j j 进行1次交换之后 48 6 57 88 60 42 83 73 85