《应用堆实现一个优先队列.doc》由会员分享，可在线阅读，更多相关《应用堆实现一个优先队列.doc（25页珍藏版）》请在金锄头文库上搜索。
1、沈阳航空航天大学数据结构 课程设计报告题目： 应用堆实现一个优先队列院（系）：理学院专 业：信息与计算科学 班 级： 学 号： 姓 名： 指导教师： 2011年12月沈阳航空航天大学课程设计报告 目 录1题目介绍和功能要求11.1优先队列(priority queue)11.2 基本功能11.3 功能要求12 系统功能模块结构图22.1 系统功能结构框图22.2 系统主要模块的功能说明23 使用的数据结构的描述33.1 数据结构设计33.2 数据结构用法说明34 函数的描述55 算法流程图75.1 HeapAdjust函数75.2 CreateHeap 函数85.3 Print 函数85.3
2、Insert函数95.4 Minimun函数95.5 Extract_Min 函数106 测试/运行的结果11参考文献15附 录17I沈阳航空航天大学课程设计报告 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 功能要求 可设计要求以
3、堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的以部分。此处由于要用堆实现队列，所以堆结构的储存表示要求用数组。要求： 1. 设计并实现优先队列的数据结构，包括其上的基本操作； 2. 以堆结构为辅助结构实现优先队列的储存表示并实现其上的基本操作； 3. 实现优先队列的出队、入队操作； 4. 给出动态演示过程（选作）；2 系统功能模块结构图2.1 系统功能结构框图用堆实现优先队插入（入队）功能模块删除（出队）功能模块输出功能模块创建队列功能模块返回最小优先级功能模块将指定的值插入到集合S中删除集合S中优先级最高的值，并返回值把集合S中的元素按小头椎输出对于S中元素创
4、建小头椎返回集合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.1 数据结构设计优先队列是不同于先进先出队列的另一种队列。每次从队列中
5、取出的是具有最高优先权的元素，按照题意可知，建立了小顶堆，元素越小优先级越高。堆的定义：若含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
6、小顶堆调整a 图3.3 小顶堆调整b 图3.4 小顶堆调整c 图3.5 小顶堆调整d 图3.6 小顶堆调整e4 函数的描述 主要函数设计：（1） void Print(int *a,int t)作用：输出优先队列参数表：a 为存储优先队列的数组。 t 为参数，为0是直接输出优先队列；否则对要变换元素进行标记。如数字6：为与3和7比较。 图4.1例图（2）void CreateHeap(int *a)作用：对于数组a进行调整为有小顶堆。参数表：a 为存储优先队列的数组。算法思想：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选，用递归
7、方法调用HeapAdjust（）；（3）HeapAdjust(int *a,int s,int m)作用：参数表：a 为存储优先队列的数组。 s 为要调整的起始位置。 m 为要调整的末端位置。算法思想：通过 i个要满足且（i=s，2s，2s+1,3sm/2）（4）void Insert(int *a,int x)作用：将x插入到优先队列a中并把a调整为小顶堆。参数表：x 要插入的元素 a 为存储优先队列的数组。算法思想:先将x插入到a的最后位置，然后判断 是否成立，成立则互换，否则退出函数。（5）int Minimun(int *a)作用：返回优先队列中优先级最高的元素（这为最小元素）。参数表
8、：a 为存储优先队列的数组。算法思想：由于用的是小顶堆，所以 直接返回堆顶就行了。(6) int Extract_Min(int *a) 作用：从优先队列中删除优先级最高的元素（这为最小元素），并重新调整为小顶堆。参数表：a 为存储优 先队列的 数组。 算法思想：由于用的是小顶堆，所以直接返回堆顶，并删除堆顶，然后将堆的最后一个元素放到堆顶，在调用 HeapAdjust(int *a,int 1,int m)就行了。 5 算法流程图5.1 HeapAdjust函数开始、输入a，s，mac=as，j=2*s结束Nj=mj=2*jYjaj+1Yj=j+1acajNYas=aj; s=j; as=a
9、c; 图5.1 HeapAdjust流程图5.2 CreateHeap 函数开始输入ai=a0/2Ni0结束Yi=i-1;调用HeapAdjust(a,i,a0) 图5.2 CreateHeap 的流程图5.3 Print 函数开始i=0,ai1N结束Yaiai/2YNai=ai/2; i=i/2;ai=x; 图5.4 Insert函数流程图5.4 Minimun函数 开始输出a1结束 图 5.5 Minimun函数流程图5.5 Extract_Min 函数 开始 输入a；ma=a1;n=a0;a1=an;a0=a0-1;调用HeapAdjust(a,1,a0)输出ma结束 图 5.6 Ext
10、ract_Min 函数流程图6 测试/运行的结果 例如：输入49，38，65，97，76，13，27，49如下： 图 6.1 输入格式图初始堆为：图 6.2 初始堆 调整小顶堆过程为：图6.3 调整图调整后的小顶堆为： 图 6.4 调整后小顶堆图主函数功能操作如下：图 6.5 主函数功能操作图插入时选择功能1其输入如下： 图 6.6插入操作图插入过程如下：图 6.7 插入过程图返回最小值，选择功能4，结果如下：图 6.8返回最小值删除时选择功能2其过程如下： 图 6.9删除过程删除后结果如下： 图 6.10删除后结果沈阳航空航天大学课程设计报告 参考文献1 谭浩强著. C程序设计（ 第三版）.
11、 北京: 清华大学出版社,2005 2 数据结构: C语言版 /严蔚敏,吴伟明编著.北京:清华大学出版社,20073 汪杰 . 数据结构经典算法实现M. 北京：人民邮电出版社，20044 李春葆 . 数据结构解析（C语言版）M. 北京：清华大学出版社，2002沈阳航空航天大学课程设计报告 课程设计总结：经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。在此期间我失落过，也曾一度热情高涨。点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到，严密。3、在做设计的时候要有信心，有耐心，切勿浮躁。4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。通过这次的课程设计，让我更加了解到数据结构的重要性。以及它对我们专业的发展发挥的作用。对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。让我知道了学无止境的道理。指导教
