[指导]应用堆实现一个优先队列

[指导]应用堆实现一个优先队列 沈阳航空航天大学 数据结构 课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 题目: 应用堆实现一个优先队列 院(系):理学院 专 业:信息与计算科学 班 级: 学 号: 姓 名: 指导教师: 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 数据结构用法说明 .................................................................... 4 4 函数的描述 ....................................................................................... 5 5 算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图 ....................................................................................... 7 5.1 HEAPADJUST函数 ..................................................................... 7 5.2 CREATEHEAP 函数 ...................................................................... 8 5.3 PRINT 函数 .................................................................................. 8 5.3 INSERT函数 ................................................................................. 9 5.4 MINIMUN函数 ........................................................................... 10 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 } ，满足下列关系时称作"小顶堆 " 或"大顶 " 。"堆顶" 元素为序列中的"最小值"或"最大值"。 k,,k,i2i (i,1,2,...n/2),k,,ki2i，1, 堆举例:{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 函数的描述 主要函数设计: (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) 作用: a[s，1...m]为小顶堆调整后a[s....m]为小顶堆。 参数表:a 为存储优先队列的数组。 s 为要调整的起始位置。 m 为要调整的末端位置。 算法思想:通过 i个要满足且(i=s，2s，2s+1,3s…m/2) ,k,,k且k,,k(i,s,...m/2)i2ii2i，1 (4)void Insert(int *a,int x) 作用:将x插入到优先队列a中并把a调整为小顶堆。 参数表:x 要插入的元素 a 为存储优先队列的数组。 算法思想:先将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 为存储优 先队列的 数组。 算法思想:由于用的是小顶堆，所以直接返回堆顶，并删除堆顶，然 后将堆的最后一个元素放到堆顶，在调用 HeapAdjust(int *a,int 1,int m)就行了。 5 算法流程图 5.1 HeapAdjust函数 开始 、 输入a，s，m ac=a[s]，j=2*s N j=2*j 结束 j<=m Y ja[j+1] j=j+1 Y ac>a[j] N Y a[s]=a[j]; s=j; a[s]=ac; 图5.1 HeapAdjust流程图 5.2 CreateHeap 函数 开始 输入a i=a[0]/2 N i>0 结束 i=i-1; Y 调用HeapAdjust(a,i,a[0]) 图5.2 CreateHeap 的流程图 5.3 Print 函数 开始 i=0,a N i1 结束 N Y a[i] 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf :经过一个星期的课程设计，过程曲折可谓一语难尽。整天都是对着电脑，不然就是翻阅资料。在此期间我失落过，也曾一度热情高涨。点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心，恒心才能做好事情。 根据我在课程设计中遇到得问题，我将在以后的学习过程中注意以下几点: 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 ，并在此基础上学会灵活运 用。 通过这次的课程设计，让我更加了解到数据结构的重要性。以及它对我们专 业的发展发挥的作用。对我们而言，知识上的收获很重要，但精神上的 丰收更加可喜。让我知道了学无止境的道理。 指导教师评语: 指导教师(签字): 年 月 日 课程设计成绩 附 录 #include "stdafx.h" #include "stdio.h" #include #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(a[0])/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(pow(2,i))-1;k++) { if(k==a[0]+1) break; for(j=1;j<=n/2;j++) printf(" "); if(k==t) printf("<%d>",a[k]); else printf("%d",a[k]); for(j=1;j<=n/2+1;j++) printf(" "); } printf("\n"); n=n/2; } } void HeapAdjust(int *a,int s,int m) //a[s+1...m]为小顶堆，调整后a[s...m]为小顶堆 { int j,ac=a[s]; for(j=2*s;j<=m;j*=2) { getchar(); Print(a,j/2); if(ja[j+1]) j++; if(ac0;i--) HeapAdjust(a,i,a[0]); getchar(); printf("调整后的为:\n"); Print(a,0); getchar(); } void Insert(int *a,int x) { int i,n=a[0]; a[n+1]=x; a[0]++; getchar(); Print(a,a[0]); for(i=a[0];i>1;) { if(a[i]