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

沈阳航空航天大学沈阳航空航天大学 数据结构数据结构 课程设计报告课程设计报告 题目：题目： 应用堆实现一个优先队列应用堆实现一个优先队列 院（系）：理学院院（系）：理学院 专专 业：信息与计算科学业：信息与计算科学 班班 级：级： 学学 号：号： 姓姓 名：名： 指导教师：指导教师： 2011 年年 12 月月 目目 录录 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) 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高 优先权的元素 ，它可以用于很多场合的数据结构。 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.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.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 例如：无序序列建成一个小顶堆49，38，65，97，76，13，27，49 图 3.2 小顶堆调整 a 图 3.3 小顶堆调整 b 图 3.4 小顶堆调整 c 图 3.5 小顶堆调整 d 图 3.6 小顶堆调整 e 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) 作用作用：为小顶堆。为小顶堆调整后.1msamsa 参数表参数表：a 为存储优先队列的数组。 s 为要调整的起始位置。 m 为要调整的末端位置。 算法思想算法思想：通过 i 个要满足且（i=s，2s，2s+1,3sm/2） （4）void Insert(int *a,int x) 作用作用：将 x 插入到优先队列 a 中并把 a 调整为小顶堆。 参数表参数表：x 要插入的元素 a 为存储优先队列的数组。 s,.m/2)(ikkkk 12ii2ii 且 算法思想算法思想:先将 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)就行了。 5 算法流程图 5.1 HeapAdjust 函数函数 、 图 5.1 HeapAdjust 流程图 开始 输入 a，s，m ac=as，j=2*s jaj+1 j=j+1 acaj as=aj; s=j; as=ac; 结束j=2*j N N Y Y Y 5.2 CreateHeap 函数函数 图 5.2 CreateHeap 的流程图 5.3 Print 函数函数 开始 i=0,a i0 调用 HeapAdjust(a,i,a0) 结束 i=i-1; N Y 5.3 Insert 函数函数 图 5.4 Insert 函数流程图 5.4 Minimun 函数函数 开始 输出 a1 结束 图 5.5 Minimun 函数流程图 开始 输入 x，a a0=a0+1;n=a0;an=x;i =a0 i1 ai #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(a0)/log(2)+INF)+1; n=int(pow(2,m)-1; for(i=1;i“,ak); else printf(“%d“,ak); for(j=1;jaj+1) j+; if(ac0;i-) HeapAdjust(a,i,a0); getchar(); printf(“调整后的为：n“); Print(a,0); getchar(); void Insert(int *a,int x) int i,n=a0; an+1=x; a0+; getchar(); Print(a,a0); for(i=a0;i1;) if(aiai/2) getchar(); ai=ai/2; i=i/2; ai=x; Print(a,i); else break; int Minimun(int *a) return a1; int Extract_Min(int *a) printf(“原来的是:n“); Print(a,0); Sleep(2000); int n,ma=a1; n=a0; a1=an; a0-; HeapAdjust(a,1,n-1); getchar(); printf(“删除后的是:n“); Print(a,0); return ma; void menu() system( “cls “); printf(“ttt*n“); printf(“ttt* 请选择功能 *n“); printf(“ttt*1:插入(入队)： *n“); printf(“ttt*2:删除(出队)： *n“); printf(“ttt*3:输出： *n“); printf(“ttt*4:返回最小值： *n“); printf(“ttt*0:退出： *n“); printf(“ttt*n“); void main() int x,aMAX+1,gong; a0=0; CreateHeap(a); menu(); scanf(“%d“, while(gong) switch(gong) case 1: printf(“请输入插