1、 数据结构课程设计 设计说明书 内部堆排序算法的实现 学 生 姓 名 学号 班级 计 本 092 成绩 指 导 教 师 计算机科学与技术系计算机科学与技术系 20112011 年年 9 9 月月 9 9 日日 课程设计任务书 20112012 学年第一学期学年第一学期 课程设计名称： 数据结构课程设计 设计题目： 内部堆排序算法的实现 完成期限：自 2011 年 8 月 29 日至 2011 年 9 月 9 日共 2 周 设计依据、要求及主要内容： 堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右 孩子(若存在)结点的关键字。如关键字序列(10，15，56
2、，25，30，70)和(70，56，30，25，15，10)分 别满足堆性质(1)和(2)，故它们均是堆。 大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又 称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。 注意：堆中任一子树亦是堆。以上讨论的堆实际上是二叉堆(Binary Heap)， 大根堆排序的基本思想： 先将初始文件 R1n建成一个大根堆,此堆为初始的无序区。 再将关键字最大的记录 R1(即堆顶)和无序区的最后一个记录 Rn交换， 由此得到新的无序区 R1n-1和有序区 Rn，且满足 R1n-1.ke
3、ysRn.key。 由于交换后新的根 R1可能违反堆性质，故应将当前无序区 R1n-1调整为堆。然后再次将 R1n-1中关键字最大的记录 R1和该区间的最后一个记录 Rn-1交换， 由此得到新的无序区 R1n-2 和有序区 Rn-1n，且仍满足关系 R1n-2.keysRn-1n.keys，同样要将 R1n-2调整为堆。 要求 ： （1）给出一个符合堆序列的一组数，能够建立大根堆和小根堆。 （2）界面友好，可操作性强。 （3）能够实现数据个数的变化输入，并建立相应的堆。 指导教师（签字） ： 教研室主任（签字） ： 批准日期： 年 月 日 摘摘 要要 随着计算机技术的发展，为了查找方便，通常希
4、望通过排序使表是按关键字有序的。本课题利用 简单选择排序中的堆排序方法，通过建立大、小根堆，并对数据元素进行排序输出，实现对用户输入 的一组可以组成堆的数据元素进行处理，使其按关键字排成为一个有序的序列，从而有效地提高了查 找效率。 关键词关键词：堆；排序；查找 目目 录录 1 1 课题描述课题描述 . 1 2 2 设计过程设计过程 . 2 2.1 2.1 流程图流程图 2 2.1.12.1.1 函数设计思想流程图函数设计思想流程图 2 2.1.22.1.2 程序流程图程序流程图 2 2.22.2 分步程序设计分步程序设计. 7 2.2.1 2.2.1 建立堆函数建立堆函数. 7 2.2.22.2.2 输出堆函数输出堆函数 7 2.2.32.2.3 输出已排序数组函数
