应用堆实现一个优先队列.doc

沈阳航空航天大学沈阳航空航天大学 数据结构数据结构 课程设计报告课程设计报告 题目 题目 应用堆实现一个优先队列应用堆实现一个优先队列 院 系 理学院院 系 理学院 专专 业 信息与计算科学业 信息与计算科学 班班 级 级 学学 号 号 姓姓 名 名 指导教师 指导教师 2011 年年 12 月月 沈阳航空航天大学课程设计报告 I 目目 录录 1 题目介绍和功能要求题目介绍和功能要求 1 1 1 优先队列 PRIORITY QUEUE 1 1 2 基本功能 1 1 3 功能要求 1 2 系统功能模块结构图系统功能模块结构图 2 2 1 系统功能结构框图 2 2 2 系统主要模块的功能说明 2 3 使用的数据结构的描述使用的数据结构的描述 3 3 1 数据结构设计 3 3 2 数据结构用法说明 3 4 函数的描述函数的描述 5 5 算法流程图算法流程图 7 5 1 HEAPADJUST函数 7 5 2 CREATEHEAP 函数 8 5 3 PRINT 函数 8 5 3 INSERT函数 9 5 4 MINIMUN函数 9 5 5 EXTRACT MIN 函数 10 6 测试测试 运行的结果运行的结果 11 参考文献参考文献 15 附附 录录 17 沈阳航空航天大学课程设计报告 1 1 题目介绍和功能要求 1 1 优先队列优先队列 priority queue 是不同于先进先出队列的另一种队列 每次从队列中取出的是具有最高 优先权的元素 它可以用于很多场合的数据结构 1 2 基本功能基本功能 1 Insert S x 将元素 x 插入到集合 S 本题为数组 A 并且把 A 调整为小头椎 2 Minimum S0 返回 S 中的最小元素 并且将 A 调整为小顶椎 3 Extract Min S 删除 S 中的最小关键字 1 3 功能要求功能要求 可设计要求以堆作为辅助结构实现一个优先队列 要将堆结构嵌入到队列 结构中 以作为其数据组织的以部分 此处由于要用堆实现队列 所以堆结构的 储存表示要求用数组 要求 1 设计并实现优先队列的数据结构 包括其上的基本操作 2 以堆结构为辅助结构实现优先队列的储存表示并实现其上的基本操作 3 实现优先队列的出队 入队操作 4 给出动态演示过程 选作 沈阳航空航天大学课程设计报告 2 2 系统功能模块结构图 2 1 系统功能结构框图系统功能结构框图 用堆实现优先 队 插入 入队 功能模块 删除 出队 功能模块 输出功能模块创建队列功能 模块 返回最小优先 级功能模块 将指定的值插 入到集合 S 中 删除集合 S 中 优先级最高的 值 并返回值 把集合 S 中的 元素按小头椎 输出 对于 S 中元 素创建小头椎 返回集合 S 中优先级最小 的元素 图 2 1 系统的模块图 2 2 系统主要模块的功能说明系统主要模块的功能说明 1 插入功能模块 Insert A x 将元素 x 插入到数组 A 并且把 A 调整为小头椎 2 删除功能模块 Extract Min A 删除数组 A 中的最小关键字 并且将 A 调整为小顶椎 3 输出功能模块 Print A 把集合 S 中的元素按小头堆输出 4 创建队列功能模块 CreateHeap A 对于数组 A 中元素创建小头椎 5 返回最小优先级功能模块 Minimun A 返回集合 A 中优先级最小的堆 沈阳航空航天大学课程设计报告 3 3 使用的数据结构的描述 3 1 数据结构设计数据结构设计 优先队列是不同于先进先出队列的另一种队列 每次从队列中取出 的是具有最高优先权的元素 按照题意可知 建立了小顶堆 元素越小 优先级越高 堆的定义 若含 n 个元素的序列 k1 k2 kn 满足下列关系时称作 小顶 堆 或 大顶 堆顶 元素为序列中的 最小值 或 最大值 堆举例 12 36 24 85 47 30 53 91 图 3 1 小顶堆 可将堆序列看成完全二叉树 则堆顶元素 完全二叉树的根 必为序列中 n 个元素的最小值或最大值 结合题目要求 3 2 数据结构用法说明数据结构用法说明 从无序序列的第 n 2 个元素 即此无序序列对应的完全二叉树的最后一个非终 端结点 起 至第一个元素止 进行反复筛选 1 2 n 2 i kk kk 12ii 2ii 沈阳航空航天大学课程设计报告 4 例如 无序序列建成一个小顶堆 49 38 65 97 76 13 27 49 图 3 2 小顶堆调整 a 图 3 3 小顶堆调整 b 图 3 4 小顶堆调整 c 图 3 5 小顶堆调整 d 图 3 6 小顶堆调整 e 沈阳航空航天大学课程设计报告 5 4 函数的描述 主要函数设计 1 void Print int a int t 作用作用 输出优先队列 参数表参数表 a 为存储优先队列的数组 t 为参数 为 0 是直接输出优先队列 否则对要变换元素 进行标记 如数字 6 为与 3 和 7 比较 图 4 1 例图 2 void CreateHeap int a 作用作用 对于数组 a 进行调整为有小顶堆 参数表参数表 a 为存储优先队列的数组 算法思想算法思想 从无序序列的第 n 2 个元素 即此无序序列对应的完 全二叉树的最后一个非终端结点 起 至第一个元素止 进行反复筛选 用递归方法调用 HeapAdjust 3 HeapAdjust int a int s int m 作用作用 为小顶堆 为小顶堆调整后 1 msamsa 参数表参数表 a 为存储优先队列的数组 s 为要调整的起始位置 m 为要调整的末端位置 算法思想算法思想 通过 i 个要满足且 i s 2s 2s 1 3s m 2 4 void Insert int a int x 作用作用 将 x 插入到优先队列 a 中并把 a 调整为小顶堆 参数表参数表 x 要插入的元素 a 为存储优先队列的数组 s m 2 ikkkk 12ii2ii 且 沈阳航空航天大学课程设计报告 6 算法思想算法思想 先将 x 插入到 a 的最后位置 然后判断 是否 a k 2 a k 成立 成立则互换 否则退出函数 a k 2 a k 与 5 int Minimun int a 作用作用 返回优先队列中优先级最高的元素 这为最小元素 参数表参数表 a 为存储优先队列的数组 算法思想算法思想 由于用的是小顶堆 所以 直接返回堆顶就行了 6 int Extract Min int a 作用作用 从优先队列中删除优先级最高的元素 这为最小元素 并重 新调整为小顶堆 参数表参数表 a 为存储优 先队列的 数组 算法思想算法思想 由于用的是小顶堆 所以直接返回堆顶 并删除堆顶 然 后将堆的最后一个元素放到堆顶 在调用 HeapAdjust int a int 1 int m 就行了 沈阳航空航天大学课程设计报告 7 5 算法流程图 5 1 HeapAdjust 函数函数 图 5 1 HeapAdjust 流程图 开始 输入 a s m ac a s j 2 s j m ja j 1 j j 1 ac a j a s a j s j a s ac 结束j 2 j N N Y Y Y 沈阳航空航天大学课程设计报告 8 5 2 CreateHeap 函数函数 图 5 2 CreateHeap 的流程图 5 3 Print 函数函数 开始 i 0 a i0 调用 HeapAdjust a i a 0 结束 i i 1 N Y 沈阳航空航天大学课程设计报告 9 5 3 Insert 函数函数 图 5 4 Insert 函数流程图 5 4 Minimun 函数函数 开始 输出 a 1 结束 图 5 5 Minimun 函数流程图 开始 输入 x a a 0 a 0 1 n a 0 a n x i a 0 i 1 a i a i 2 a i a i 2 i i 2 a i x 结束 N Y N Y 沈阳航空航天大学课程设计报告 10 5 5 Extract Min 函数函数 图 5 6 Extract Min 函数流程图 开始 输入 a ma a 1 n a 0 a 1 a n a 0 a 0 1 调用 HeapAdjust a 1 a 0 输出 ma 结束 沈阳航空航天大学课程设计报告 11 6 测试 运行的结果 例如 输入 49 38 65 97 76 13 27 49 如下 图 6 1 输入格式图 初始堆为 图 6 2 初始堆 调整小顶堆过程为 沈阳航空航天大学课程设计报告 12 图 6 3 调整图 调整后的小顶堆为 图 6 4 调整后小顶堆图 主函数功能操作如下 图 6 5 主函数功能操作图 沈阳航空航天大学课程设计报告 13 插入时选择功能 1 其输入如下 图 6 6 插入操作图 插入过程如下 图 6 7 插入过程图 返回最小值 选择功能 4 结果如下 图 6 8 返回最小值 沈阳航空航天大学课程设计报告 14 删除时选择功能 2 其过程如下 图 6 9 删除过程 删除后结果如下 图 6 10 删除后结果 沈阳航空航天大学课程设计报告 15 参考文献 1 谭浩强著 C 程序设计 第三版 北京 清华大学出版社 2005 2 数据结构 C 语言版 严蔚敏 吴伟明编著 北京 清华大学出版社 2007 3 汪杰 数据结构经典算法实现 M 北京 人民邮电出版社 2004 4 李春葆 数据结构解析 C 语言版 M 北京 清华大学出版社 2002 沈阳航空航天大学课程设计报告 16 课程设计总结 课程设计总结 经过一个星期的课程设计 过程曲折可谓一语难尽 整天 都是对着电脑 不然就是翻阅资料 在此期间我失落过 也曾一度热情高涨 点点滴滴令我回味无长 这次课程设计使我体会到只有做到细心耐心 恒心才 能做好事情 根据我在课程设计中遇到得问题 我将在以后的学习过程中注意以下几点 1 认真上好专业实验课 多在实践中锻炼自己 2 写程序的过程中要考虑周到 严密 3 在做设计的时候要有信心 有耐心 切勿浮躁 4 认真的学习课本知识 掌握课本中的知识点 并在此基础上学会灵活运 用 通过这次的课程设计 让我更加了解到数据结构的重要性 以及它对我们 专业的发展发挥的作用 对我们而言 知识上的收获很重要 但精神上 的丰收更加可喜 让我知道了学无止境的道理 指导教师评语 指导教师 签字 年 月 日 沈阳航空航天大学课程设计报告 17 课程设计成绩 附 录 include stdafx h include stdio h include include include include stdlib h include define MAX 100 define INF 0 00001 void Print int a int t int i j k n m m int log a 0 log 2 INF 1 n int pow 2 m 1 for i 1 i m i for k int pow 2 i 1 k int pow 2 i 1 k if k a 0 1 break for j 1 j n 2 j printf if k t printf a k else printf d a k 沈阳航空航天大学课程设计报告 18 for j 1 j n 2 1 j printf printf n n n 2 void HeapAdjust int a int s int m a s 1 m 为小顶堆 调整后 a s m 为小顶堆 int j ac a s for j 2 s j m j 2 getchar Print a j 2 if ja j 1 j if ac a j break a s a j s j a s ac void CreateHeap int a int i n printf 请输入要创建的个数 scanf d a 0 n printf 请输入的数字 n for i 1 i0 i HeapAdjust a i a 0 getchar printf 调整后的为 n Print a 0 getchar void Insert int a int x int i n a 0 a n 1 x a 0 getchar Print a a 0 for i a 0 i 1 if a i a i 2 getchar a i a i 2 i i 2 a i x Print a i 沈阳航空航天大学课程设计报告 20 else break int Minimun int a return a 1 int Extract Min int a printf 原来的是 n Print a 0 Sleep 2000 int n ma a 1 n a 0 a 1 a n a 0 HeapAdjust a 1 n 1 getchar printf 删除后的是 n Print a 0 return ma void menu system cls printf t t t n printf t t t 请选择功能 n printf t t t 1 插入 入队 n printf t t t 2 删除 出队 n 沈阳航空航天大学课程设计报告 21 printf t t t 3 输出 n printf t t t 4 返回最小值 n printf t t t 0 退出 n printf t t t n void main int x a MAX 1