排序综合-课程设计报告.docx

《排序综合-课程设计报告.docx》由会员分享，可在线阅读，更多相关《排序综合-课程设计报告.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序综合-课程设计报告 课程设计 课程设计名称：排序综合 专业班级： 0000000000000 学生姓名： 0000000000000 学号： 00000000000000 指导教师： 00000000000000 课程设计时间： 2022.6.21-2022.6.25 计算机科学与技术专业课程设计任务书 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页 信息科学与工程学院课程设计成绩评价表课程名称：数据结构课程设计 1、需求分析 1.1、直接插入排序 思路:设有一组关键字K1,K2,.,Kn,排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序

2、列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列. 1.2、希尔排序 思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,.,di=1 1.3、快速排序:（递归和非递归） 思路:以第一个关键字K1为控制字，将K1、K2、.Kn分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居

3、两个子区中间的适当位置。在子区内数据尚处于无序状态。 将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。 重复第（1）、（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.ke

4、yx.key，把记录rj移动到文件左边i所指向的位置;然后在文件左边修改i指针,i+，让ri.key与x.key相比较，当ri.key小于等于x.key 时，ri不移动，修改指针i，i-，直到ri.keyx.key, 把记录ri移动到文件右边j所指向的位置;然后在文件右边修改j指针j-。重复上面的步骤. 1.4、堆排序 思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排序大体分为两步处理： 初建堆，从堆的定义出发，当i=1、2、。、2/n时应满足ki=k2i和ki=k2i+1.所以先取i=n/2(它一定是第n个结点的双亲编号),将以i结点为根的子树调整为

5、堆，然后令i=i-1，将以不结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。 堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。 2、概要设计 2.1、头文件 #include #include #include #include 2.2 、ADT struct element int key; list20; struct rnode int key; int point; ; 2.3、各种操作函数： （

6、1）创建一个数组函数：int creat()； （2）输出数组函数：void print(struct element a20,int n)； （3）保存函数：void save(struct element aSIZE,int n, char fileName ) （4）直接插入排序函数：void insert_sort(element a, int n) （5）希尔排序函数：void shell(struct element a20,int n)； （6）快速排序函数（分区处理函数）：int hoare(struct element a20,int l,int h)； （7）非递归的快速排

7、序函数：void quick1(struct element a20,int n)； （8）递归的快速排序函数：void quick2(struct element a20,int l,int h)； （9）堆排序（调整堆的函数）：void heap(struct element a20,int i,int m)； （10）堆排序（主体函数）：void heapsort(struct element a20,int n)； （11）时间函数：start = clock();end = clock(); 2.4、主函数 Void main() 接受命令（选择要执行的操作）； 处理命令； 输出结果； 3、详细设计 3.1、程序源代码： #include #include #include #include #define SIZE 1000000 struct element int key; listSIZE; /创建一个数组/ int creat() int i,n; int num; n=0; printf(请输入元素个数:); scanf(%d,&num); for( i = 0;i num; i+ ) listn.key = rand() % 10000; n+;