应用堆实现一个优先队列

《应用堆实现一个优先队列》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、沈阳航空航天大学数据结构课程设计报告题目：应用堆实现一个优先队列院（系）：理学院专业：信息与计算科学班级：学号：姓名：指导教师：2011年12月沈阳航空航天大学课程设计报告目录1题目介绍和功能要求11.1优先队列(priorityqueue)11.2基本功能11.3功能要求12系统功能模块结构图22.1系统功能结构框图22.2系统主要模块的功能说明23使用的数据结构的描述33.1数据结构设计33.2数据结构用法说明34函数的描述55算法流程图75.1HeapAdjust函数75.2CreateHeap函数85.3Print函数85.3Insert函数95.4Minimun函数9

2、5.5Extract_Min函数106测试/运行的结果11参考文献15附录1723沈阳航空航天大学课程设计报告1题目介绍和功能要求1.1优先队列(priorityqueue)是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素，它可以用于很多场合的数据结构。1.2基本功能1Insert(S,x)将元素x插入到集合S（本题为数组A），并且把A调整为小头椎。2Minimum(S0返回S中的最小元素，并且将A调整为小顶椎。3Extract_Min(S)删除S中的最小关键字1.3功能要求可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为

3、其数据组织的以部分。此处由于要用堆实现队列，所以堆结构的储存表示要求用数组。要求：1.设计并实现优先队列的数据结构，包括其上的基本操作；2.以堆结构为辅助结构实现优先队列的储存表示并实现其上的基本操作；3.实现优先队列的出队、入队操作；4.给出动态演示过程（选作）；23沈阳航空航天大学课程设计报告2系统功能模块结构图2.1系统功能结构框图用堆实现优先队插入（入队）功能模块删除（出队）功能模块输出功能模块创建队列功能模块返回最小优先级功能模块将指定的值插入到集合S中删除集合S中优先级最高的值，并返回值把集合S中的元素按小头椎输出对于S中元素创建小头椎返回集合S中优先级最小的元素图

4、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中优先级最小的堆23沈阳航空航天大学课程设计报告3使用的数据结构的描述3.1数据结构设计优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优

5、先权的元素，按照题意可知，建立了小顶堆，元素越小优先级越高。堆的定义：若含n个元素的序列{k1,k2,…,kn}，满足下列关系时称作"小顶堆"或"大顶"。"堆顶"元素为序列中的"最小值"或"最大值"。堆举例：{12,36,24,85,47,30,53,91}图3.1小顶堆可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值结合题目要求3.2数据结构用法说明从无序序列的第ën/2û个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选23沈阳航空航天大学课程设计报告例如：无序序列建成一个小顶堆{49，38，6

6、5，97，76，13，27，49}图3.2小顶堆调整a图3.3小顶堆调整b图3.4小顶堆调整c图3.5小顶堆调整d图3.6小顶堆调整e23沈阳航空航天大学课程设计报告4函数的描述主要函数设计：（1）voidPrint(int*a,intt)作用：输出优先队列参数表：a为存储优先队列的数组。t为参数，为0是直接输出优先队列；否则对要变换元素进行标记。如数字6：为与3和7比较。图4.1例图（2）voidCreateHeap(int*a)作用：对于数组a进行调整为有小顶堆。参数表：a为存储优先队列的数组。算法思想：从无序序列的第ën/2û个元素（即此无序序列对应的完全二叉树的最后一个

7、非终端结点）起，至第一个元素止，进行反复筛选，用递归方法调用HeapAdjust（）；（3）HeapAdjust(int*a,ints,intm)作用：参数表：a为存储优先队列的数组。s为要调整的起始位置。m为要调整的末端位置。算法思想：通过i个要满足且（i=s，2s，2s+1,3s…m/2）（4）voidInsert(int*a,intx)作用：将x插入到优先队列a中并把a调整为小顶堆。参数表：x要插入的元素a为存储优先队列的数组。23沈阳航空航天大学课程设计报告算法思想:先将x插入到a的