下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

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

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

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

带着眼泪带着伤口去流浪
2017-09-26 0人阅读 举报 0 0 暂无简介

简介:本文档为《[指导]应用堆实现一个优先队列doc》,可适用于初中教育领域

指导应用堆实现一个优先队列沈阳航空航天大学数据结构课程设计报告题目:应用堆实现一个优先队列院(系):理学院专业:信息与计算科学班级:学号:姓名:指导教师:年月目录题目介绍和功能要求优先队列(PRIORITYQUEUE)基本功能功能要求系统功能模块结构图系统功能结构框图系统主要模块的功能说明使用的数据结构的描述数据结构设计数据结构用法说明函数的描述算法流程图HEAPADJUST函数CREATEHEAP函数PRINT函数INSERT函数MINIMUN函数EXTRACTMIN函数测试运行的结果参考文献附录题目介绍和功能要求优先队列(priorityqueue)是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素它可以用于很多场合的数据结构。基本功能Insert(S,x)将元素x插入到集合S(本题为数组A)并且把A调整为小头椎。Minimum(S返回S中的最小元素并且将A调整为小顶椎。ExtractMin(S)删除S中的最小关键字功能要求可设计要求以堆作为辅助结构实现一个优先队列。要将堆结构嵌入到队列结构中以作为其数据组织的以部分。此处由于要用堆实现队列所以堆结构的储存表示要求用数组。要求:设计并实现优先队列的数据结构包括其上的基本操作以堆结构为辅助结构实现优先队列的储存表示并实现其上的基本操作实现优先队列的出队、入队操作给出动态演示过程(选作)系统功能模块结构图系统功能结构框图用堆实现优先队插入(入队)删除(出队)输出功能模创建队列功返回最小优功能模块功能模块块能模块先级功能模块删除集合S中把集合S中的将指定的值对于S中元素返回集合S中优先级最高的元素按小头椎值并返回值输出插入到集合S创建小头椎优先级最小中的元素图系统的模块图系统主要模块的功能说明插入功能模块:Insert(A,x)将元素x插入到数组A并且把A调整为小头椎。删除功能模块:ExtractMin(A)删除数组A中的最小关键字并且将A调整为小顶椎。输出功能模块:Print(A)把集合S中的元素按小头堆输出。创建队列功能模块:CreateHeap(A)对于数组A中元素创建小头椎。返回最小优先级功能模块:Minimun(A)返回集合A中优先级最小的堆使用的数据结构的描述数据结构设计优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素按照题意可知建立了小顶堆元素越小优先级越高。堆的定义:若含n个元素的序列{k,k,…,kn}满足下列关系时称作"小顶堆"或"大顶"。"堆顶"元素为序列中的"最小值"或"最大值"。k,,k,ii(i,,,n),k,,kii,堆举例:{,,,,,,,}图小顶堆可将堆序列看成完全二叉树则堆顶元素(完全二叉树的根)必为序列中n个元素的最小值或最大值结合题目要求数据结构用法说明从无序序列的第n个元素(即此无序序列对应的完全二叉树的最后一个非终端结点)起至第一个元素止进行反复筛选例如:无序序列建成一个小顶堆{}图小顶堆调整a图小顶堆调整b图小顶堆调整c图小顶堆调整d图小顶堆调整e函数的描述主要函数设计:()voidPrint(int*a,intt)作用:输出优先队列参数表:a为存储优先队列的数组。t为参数为是直接输出优先队列否则对要变换元素进行标记。如数字:为与和比较。图例图()voidCreateHeap(int*a)对于数组a进行调整为有小顶堆。作用:参数表:a为存储优先队列的数组。算法思想:从无序序列的第n个元素(即此无序序列对应的完全二叉树的最后一个非终端结点)起至第一个元素止进行反复筛选用递归方法调用HeapAdjust()()HeapAdjust(int*a,ints,intm)作用:asm为小顶堆调整后asm为小顶堆。参数表:a为存储优先队列的数组。s为要调整的起始位置。m为要调整的末端位置。算法思想:通过i个要满足且(i=sss,s…m),k,,k且k,,k(i,s,m)iiii()voidInsert(int*a,intx)作用:将x插入到优先队列a中并把a调整为小顶堆。参数表:x要插入的元素a为存储优先队列的数组。算法思想:先将x插入到a的最后位置然后判断是否a(k),a(k)成立成立则互换否则退出函数。a(k)与a(k)()intMinimun(int*a)作用:返回优先队列中优先级最高的元素(这为最小元素)。参数表:a为存储优先队列的数组。算法思想:由于用的是小顶堆所以直接返回堆顶就行了。()intExtractMin(int*a)作用:从优先队列中删除优先级最高的元素(这为最小元素)并重新调整为小顶堆。参数表:a为存储优先队列的数组。算法思想:由于用的是小顶堆所以直接返回堆顶并删除堆顶然后将堆的最后一个元素放到堆顶在调用HeapAdjust(int*a,int,intm)就行了。算法流程图HeapAdjust函数开始、输入asmac=asj=*sNj=*j结束j<=mYj<maj>ajj=jYac>ajNYas=ajs=jas=ac图HeapAdjust流程图CreateHeap函数开始输入ai=aNi>结束i=iY调用HeapAdjust(a,i,a)图CreateHeap的流程图Print函数开始i=,aNi<aY输出优先队结束列aii=i图Print函数的流程图Insert函数开始输入xaa=an=aan=xi=ai>结束NYai<aiNYai=aii=iai=x图Insert函数流程图Minimun函数开始输出a结束图Minimun函数流程图ExtractMin函数开始输入ama=an=aa=ana=a调用HeapAdjust(a,,a)输出ma结束图ExtractMin函数流程图测试运行的结果例如:输入{}如下:图输入格式图初始堆为:图初始堆调整小顶堆过程为:图调整图调整后的小顶堆为:图调整后小顶堆图主函数功能操作如下:图主函数功能操作图插入时选择功能其输入如下:图插入操作图插入过程如下:图插入过程图返回最小值选择功能结果如下:图返回最小值删除时选择功能其过程如下:图删除过程删除后结果如下:图删除后结果参考文献谭浩强著C程序设计(第三版)北京:清华大学出版社,数据结构:C语言版严蔚敏,吴伟明编著北京:清华大学出版社,汪杰数据结构经典算法实现,M,北京:人民邮电出版社李春葆数据结构解析(C语言版),M,北京:清华大学出版社课程设计总结:经过一个星期的课程设计过程曲折可谓一语难尽。整天都是对着电脑不然就是翻阅资料。在此期间我失落过也曾一度热情高涨。点点滴滴令我回味无长。这次课程设计使我体会到只有做到细心耐心恒心才能做好事情。根据我在课程设计中遇到得问题我将在以后的学习过程中注意以下几点:、认真上好专业实验课多在实践中锻炼自己。、写程序的过程中要考虑周到严密。、在做设计的时候要有信心有耐心切勿浮躁。、认真的学习课本知识掌握课本中的知识点并在此基础上学会灵活运用。通过这次的课程设计让我更加了解到数据结构的重要性。以及它对我们专业的发展发挥的作用。对我们而言知识上的收获很重要但精神上的丰收更加可喜。让我知道了学无止境的道理。指导教师评语:指导教师(签字):年月日课程设计成绩附录#include"stdafxh"#include"stdioh"#include<mathh>#include<windowsh>#include<stringh>#include"stdlibh"#include<timeh>#defineMAX#defineINFvoidPrint(int*a,intt){inti,j,k,n,mm=int(log(a)log()INF)n=int(pow(,m))for(i=i<=mi){for(k=int(pow(,(i)))k<=int(pow(,i))k){if(k==a)breakfor(j=j<=nj)printf("")if(k==t)printf("<d>",ak)elseprintf("d",ak)for(j=j<=nj)printf("")}printf("n")n=n}}voidHeapAdjust(int*a,ints,intm)asm为小顶堆调整后asm为小顶堆{intj,ac=asfor(j=*sj<=mj*=){getchar()Print(a,j)if(j<maj>aj)jif(ac<aj)breakas=ajs=jas=ac}}voidCreateHeap(int*a){inti,nprintf("请输入要创建的个数")scanf("d",n)a=nprintf("请输入的数字n")for(i=i<=ni)scanf("d",ai)printf("当前堆为:n")Print(a,)getchar()printf("现在对其进行调整:n")for(i=ai>i)HeapAdjust(a,i,a)getchar()printf("调整后的为:n")Print(a,)getchar()}voidInsert(int*a,intx){inti,n=aan=xagetchar()Print(a,a)for(i=ai>){if(ai<ai){getchar()ai=aii=iai=xPrint(a,i)}elsebreak}}intMinimun(int*a){returna}intExtractMin(int*a){printf("原来的是:n")Print(a,)Sleep()intn,ma=an=aa=anaHeapAdjust(a,,n)getchar()printf("删除后的是:n")Print(a,)returnma}voidmenu(){system("cls")printf("ttt************************n")printf("ttt*请选择功能*n")printf("ttt*:插入(入队):*n")printf("ttt*:删除(出队):*n")printf("ttt*:输出:*n")printf("ttt*:返回最小值:*n")printf("ttt*:退出:*n")printf("ttt************************n")}voidmain(){intx,aMAX,gonga=CreateHeap(a)menu()scanf("d",gong)while(gong){switch(gong){case:printf("请输入插入数值n")scanf("d",x)Insert(a,x)breakcase:x=ExtractMin(a)printf("删除的元素:dn",x)breakcase:Print(a,)breakcase:x=Minimun(a)printf("最小值为:dn",x)case:breakdefault:menu()break}scanf("d",gong)}

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/22

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

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利