南京xx大学 数据结构 课程设计 堆排序 二叉排序树_精品.doc

南京XX大学 课 程 设 计 总 结 报 告 课程名称： 《数据结构 –使用C语言》 课设题目： 堆排序，二叉排序树 班级： 姓名： 学号： 指导教师： 课设成绩： 目 录 1 堆排序….............................................................................................. 3 1.1. 题目….......................................................................................... 3 1.2. 功能要求….................................................................................. 3 1.3. 算法设计 1.4. 算法分析 1.5. 算法流程 1.6. 算法程序 1.7. 编译运行结果 2 二叉排序树查找 2.1. 题目….......................................................................................... 2.2. 功能要求….................................................................................. 2.3. 算法设计 2.4. 算法流程 2.5. 算法程序 2.6. 编译运行结果 3 认识（收获）与体会 1堆排序 功能要求 输入一组正整数关键字（20个以内，以-1结束） 将输入数据存入数组； 调用初始堆构造函数，建立初始堆； 调用堆排序函数进行堆排序，结果仍在数组中； 调用输出函数输出数组中的结果排序值。 算法设计 * 大根堆的定义 若完全二叉树中任一结点的关键字值均大于等于孩子(若存在的话)结点的关键字值,则称此完全二叉树为大根堆。 * 算法思想（利用堆排序） ① 将欲排序的序列构造成一个大根堆顺序存储结构的序列（按完全二叉树的存储结构）； ② 删除此完全二叉树的根结点并输出（该结点关键字的值一定是最大（或最小）的； ③ 针对第②步操作的剩余结点组成的子序列，将其重新构造成一个新的大根堆； ④ 重复②、③的操作，直到删除输出所有的结点，由此得到的输出序列一定是有序序列。 主要操作：建立初始堆、重构堆 * 初始堆的构造 　若完全二叉树是堆→则其所有子树均应是堆. 由于叶结点为根的子树一定是堆，因此构造堆可从倒数第一的内结点为根的子树开始逐步将其构造成堆，直到将树根结点为根的整个子树构造成堆为止。 　 ① 若某子树已是堆,则无须重新构造; ② 若某子树还不是堆,则需调整结点的位置,使其成为堆; 用根结点的关键字与左、右孩子的关键字进行比较，如果根结点的大，说明其位置正确，则不调整；否则让根结点与左、右孩子中大的一个交换，交换后再从新的位置继续上述比较调整，直到位置正确或调整到叶结点为止。 * 堆的重构 原理与初始建堆子树的构造相同 * 实例解析 例a[]:0 1 2 3 4 5 6 7 8 24 10 90 77 16 25 33 89 67 ① 构造初始堆(大根堆） 　　 0 1 2 3 4 5 6 7 8 90 89 33 77 16 25 24 10 67 ② 删除根（放在表尾） ③ 重构堆 　　　 0 1 2 3 4 5 6 7 8 89 77 33 67 16 25 24 10 90 结果：0 1 2 3 4 5 6 7 8 10 16 24 25 33 67 77 89 90 1.4. 算法分析 　　 时间复杂度：Ｏ(n*log2n) 空间复杂度：Ｏ（１） 　　 稳　定　性：不稳定排序 1.5.算法流程 1.6.算法程序 #include stdio.h #include stdlib.h int i,n; int a[20];