应用堆实现一个优先队列

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、2 CREATEHEAP 函数 . 85.3 PRINT 函数 . 85.3 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中的最小元素，并

3、且将A调整为小顶椎。3 Extract_Min(S)删除S中的最小关键字1.3 功能要求可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中，以作为其数据组织的以部分。此处由于要用堆实现队列，所以堆结构的储存表示要求用数组。要求：1. 设计并实现优先队列的数据结构，包括其上的基本操作；2. 以堆结构为辅助结构实现优先队列的储存表示并实现其上的基本操作；3. 实现优先队列的出队、入队操作；4. 给出动态演示过程（选作）；1沈阳航空航天大学课程设计报告2 系统功能模块结构图2.1 系统功能结构框图图2.1系统的模块图2.2 系统主要模块的功能说明1.插入功能模块：Insert(A

4、,x) 将元素x插入到数组A，并且把A调整为小头椎。 2. 删除功能模块：Extract_Min(A)，删除数组A中的最小关键字，并且将A调整为小顶椎。 3. 输出功能模块：Print(A)把集合S中的元素按小头堆输出。 4. 创建队列功能模块：CreateHeap(A) 对于数组A中元素创建小头椎。 5. 返回最小优先级功能模块：Minimun(A) 返回集合A中优先级最小的堆2沈阳航空航天大学课程设计报告3 使用的数据结构的描述3.1 数据结构设计优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素，按照题意可知，建立了小顶堆，元素越小优先级越高。堆的定义：若

5、含n个元素的序列 k1,k2 ,kn ，满足下列关系时称作"小顶堆" 或"大顶" 。"堆顶" 元素为序列中的"最小值"或"最大值"。ki<=k2i (i=1,2,.n/2)ki<=k2i+1堆举例：12,36,24,85,47,30,53,91图3.1 小顶堆可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中 n个元素的最小值或最大值 结合题目要求3.2 数据结构用法说明从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进

6、行反复筛选3沈阳航空航天大学课程设计报告例如：无序序列建成一个小顶堆49，38，65，97，76，13，27，49图3.2 小顶堆调整a 图3.3 小顶堆调整b图3.4 小顶堆调整c 图3.5 小顶堆调整d图3.6 小顶堆调整e4沈阳航空航天大学课程设计报告4 函数的描述主要函数设计：（1） void Print(int *a,int t)作用：输出优先队列参数表：a 为存储优先队列的数组。t 为参数，为0是直接输出优先队列；否则对要变换元素进行标记。如数字6：为与3和7比较。图4.1例图（2）void CreateHeap(int *a)作用：对于数组a进行调整为有小顶堆。参数表：a 为存储

7、优先队列的数组。算法思想：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选，用递归方法调用HeapAdjust（）；（3）HeapAdjust(int *a,int s,int m)作用：as+1.m为小顶堆调整后as.m为小顶堆。参数表：a 为存储优先队列的数组。s 为要调整的起始位置。m 为要调整的末端位置。算法思想：通过 i个要满足且（i=s，2s，2s+1,3sm/2）ki<=k2i且ki<=k2i+1(i=s,.m/2)（4）void Insert(int *a,int x)作用：将x插入到优先队列a中并把a调

8、整为小顶堆。参数表：x 要插入的元素a 为存储优先队列的数组。5沈阳航空航天大学课程设计报告算法思想:先将x插入到a的最后位置，然后判断a(k) a(k/2) 是否成立，成立则a(k)与a(k/2) 互换，否则退出函数。（5）int Minimun(int *a)作用：返回优先队列中优先级最高的元素（这为最小元素）。参数表：a 为存储优先队列的数组。算法思想：由于用的是小顶堆，所以 直接返回堆顶就行了。(6) int Extract_Min(int *a)作用：从优先队列中删除优先级最高的元素（这为最小元素），并重新调整为小顶堆。参数表：a 为存储优 先队列的 数组。算法思想：由于用的是小顶堆

9、，所以直接返回堆顶，并删除堆顶，然后将堆的最后一个元素放到堆顶，在调用 HeapAdjust(int*a,int 1,int m)就行了。6沈阳航空航天大学课程设计报告 5 算法流程图5.1 HeapAdjust函数图5.1 HeapAdjust流程图7沈阳航空航天大学课程设计报告5.2 CreateHeap 函数图5.2 CreateHeap 的流程图5.3 Print 函数图5.3 Print 函数的流程图8沈阳航空航天大学课程设计报告5.3 Insert函数图5.4 Insert函数流程图5.4 Minimun函数图 5.5 Minimun函数流程图9沈阳航空航天大学课程设计报告5.5

10、Extract_Min 函数图 5.6 Extract_Min 函数流程图10沈阳航空航天大学课程设计报告 6 测试/运行的结果例如：输入49，38，65，97，76，13，27，49如下：图 6.1 输入格式图初始堆为：图 6.2 初始堆调整小顶堆过程为：11沈阳航空航天大学课程设计报告图6.3 调整图调整后的小顶堆为：图 6.4 调整后小顶堆图主函数功能操作如下：图 6.5 主函数功能操作图12沈阳航空航天大学课程设计报告插入时选择功能1其输入如下：图 6.6插入操作图插入过程如下：图 6.7 插入过程图返回最小值，选择功能4，结果如下：图 6.8返回最小值13沈阳航空航天大学课程设计报告

11、删除时选择功能2其过程如下：删除后结果如下：图 6.9删除过程 图 6.10删除后结果14沈阳航空航天大学课程设计报告参考文献1 谭浩强著. C程序设计（ 第三版）. 北京: 清华大学出版社,20052 数据结构: C语言版 /严蔚敏,吴伟明编著.北京:清华大学出版社,20073 汪杰 . 数据结构经典算法实现M. 北京：人民邮电出版社，20044 李春葆 . 数据结构解析（C语言版）M. 北京：清华大学出版社，200215沈阳航空航天大学课程设计报告16沈阳航空航天大学课程设计报告附 录#include "stdafx.h"#include "stdio.h&q

12、uot;#include <math.h>#include<windows.h>#include<string.h>#include "stdlib.h "#include<time.h>#define MAX 100#define INF 0.00001void 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<=m;i+) for(k=int(pow(2,(i-1);k<=int(

13、pow(2,i)-1;k+) if(k=a0+1) break; for(j=1;j<=n/2;j+) printf(" "); if(k=t) printf("<%d>",ak); else printf("%d",ak); for(j=1;j<=n/2+1;j+) printf(" ");17沈阳航空航天大学课程设计报告void HeapAdjust(int *a,int s,int m) /as+1.m为小顶堆，调整后as.m为小顶堆 int j,ac=as; for(j=2*s;j&

14、lt;=m;j*=2) getchar(); printf("n"); n=n/2; Print(a,j/2); if(j<m && aj>aj+1) j+; if(ac<aj) break;as=aj;void CreateHeap(int *a)int i,n; s=j; as=ac; printf("请输入要创建的个数 ");scanf("%d",&n); a0=n;printf("请输入的数字n");for(i=1;i<=n;i+) scanf("%

15、d",&ai); printf("当前堆为：n");18沈阳航空航天大学课程设计报告Print(a,0);getchar();printf("现在对其进行调整：n");for(i=a0/2;i>0;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;i>1;)if

16、(ai<ai/2)getchar();ai=ai/2;i=i/2;ai=x;Print(a,i);else break;19沈阳航空航天大学课程设计报告int Minimun(int *a)int Extract_Min(int *a)printf("原来的是:n"); Print(a,0); Sleep(2000); int n,ma=a1; n=a0; a1=an; a0-; return a1;HeapAdjust(a,1,n-1);void menu()system( "cls "); printf("ttt*n");

17、printf("ttt* 请选择功能 *n"); printf("ttt*1:插入(入队)： *n"); printf("ttt*2:删除(出队)： *n"); printf("ttt*3:输出： *n"); printf("ttt*4:返回最小值： *n");20getchar(); printf("删除后的是:n"); Print(a,0); return ma;沈阳航空航天大学课程设计报告printf("ttt*0:退出： *n"); printf("ttt*n");void main()int x,aMAX+1,gong;a0=0;CreateHeap(a);menu();scanf("%d",&gong);while(gong)switch(gong)case 1:printf("请输入插入数值n");scanf(&quo