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

沈阳航空航天大学 数据结构 课程设计报告 题目： 应用堆实现一个优先队列 院（系）：学院 专 业： 班 级： 学 号： 姓 名： 指导教师： 2011年月 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优先队列(priority queue) 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素2 系统功能模块结构图 2.1 系统功能结构框图 图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.1 数据结构设计 优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素n个元素的序列 {k1,k2 ,…,kn } ，满足下列关系时称作小顶堆 或大顶 。堆顶 元素为序列中的最小值或最大值。 堆举例：{12,36,24,85,47,30,53,91} 图3.1 小顶堆 可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中 n个元素的最小值或最大值 结合题目要求 3.2 数据结构用法说明 从无序序列的第?n/2?个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选 例如：无序序列建成一个小顶堆{49，38，65，97，76，13，27，49} 图3.2 小顶堆调整a 图3.3 小顶堆调整b 图3.4 小顶堆调整c 图3.5 小顶堆调整d 图3.6 小顶堆调整e 4 函数的描述 主要函数设计： 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) 作用： 参数表：a 为存储优先队列的数组。 s 为要调整的起始位置。 m 为要调整的末端位置。 算法思想：通过 i个要满足且（i=s，2s，2s+1,3s…m/2） （4）void Insert(int *a,int x) 作用：将x插入到优先队列a中并把a调整为小顶堆。 参数表：x 要插入的元素 a 为存储优先队列的数组。 算法思想:先将x插入到a的最后位置，然后判断 是否成立，成立则互换，否则退出函数。 （5）int Minimun(int *a) 作用：返回优先队列中优先级最高的元素（这为最小元素）。 参数表：a 为存储优先队列的数组。 算法思想：由于用的是小顶堆，所以 直接返回堆顶就行了。 (6) int Extract_Min(int *a) 作用：从优先队列中删除优先级最高的元素（这