优先队列与堆数据结构实验报告

《优先队列与堆数据结构实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、优先队列与堆问题描述：假设某医生看病人的顺序是由病人的病情严重程度来决定。护士按照所有病人来医院的时间顺序给病人编号ID,依次为1,2,3n;并且根据病人的病情严重程度设置Priority值，病越重，Priority的值越小。当医生开始工作时，护士根据病人的Priority值，由小到大依次安排病人看病。试为护士编写程序安排病人看病的先后次序。基本要求：(1)利用最小值堆实现一个优先队列。(2)对于优先队列应该支持如下操作：初始化队列的init操作；获得队列中元素个数的size操作；判定队列是否为空的enpty操作；萩得队列中最优先的元素的值的top

2、操作；向队列中插入一个元素的push操作；删除队列中最优先的元素的pop操作。(3)利用优先队列存入所有病人的信息(编号和病情严重程度)，最后利用优先队列获得病人看病的次序。需求分析：1、输入形式：输入文件的每一行有两个整数index和value,分别表示病人的ID和Priority值，病越重，Priority的值越小。最后一行数据以-1-1结束，相应的这组数据不应处理2、输出形式：将病人的看病优先序列输出，每个病人的数据占一行，只需输出其m3、功能描述:使得每一个病人都能够公平公正的得到看病的合法次序，为医院解决秩序问题，更好地为病人服务。4、输

3、入输出样例：输入：1152335420510-1-1输出：235145、效率分析:qiog(n))抽象数据结构类型：数据结构类型描述：typedefstruct{intid;.//病人的ID编号intvalue;//病人病情的严重程度{PriorityQueue;优先队列的基本操作：voidInit_Queue()function:初始化队列voidinsert_Queue(PriorityQueueq)function:将兀素q插入优先队列中的合适位值intdel_Queue()function：删除队列头的元素，并返回其IDVoidEmpty_

4、Queue()function：判断队列是否为空队列概要设计：优先队列是基于堆的思想来实现的，相应的插入、删除、以及对优先队列的维护都是通过堆的思想来实现的，而在很实验中我是通过对堆的数组表示后改造为队列的，其本质思想都是相通的，都是基于堆的思想来实现快速的查询工作！详细设计：主题思想是通过分块、分步的方法设计的：1、voidInit_Queue()function:初$台f匕队歹ll2、voidinsert_Queue(PriorityQueueq)function:将元素q插入优先队列中的合适位值3、intdel_Queue()function

5、：删除队列头的元素，并返回其ID4、VoidEmpty_Queue()function：判断队列是否为空队列5、在nadn()i(

6、

7、用上述函数来实现程序的功能实现提示：(1)最小值堆采用数组作为物理存储结构，每个元素是一个结构体变量，铋含编号ID和病情严重程度Priority值。(2)川户录入一1一1表示输入结束。具体代码ncludeusingnamespacestd;林defineMax1001intlast;typedefstructintid;intvalue;}PriorityQueue;PriorityQucuche

8、ap[Max];voidinit_Queue(){_last=0;}voidinscrt^Qucuc(PriorityQucucq){inti=++last;while(i!=1&&q.value

9、i++;if(heaptci].value>qy.value)break;heap[i]=heap[ci];i-ci;ci*=2;}heap[i]=qy;returnqx.id;}intmain(){Init_Qucuc();PriorityQueueq;intindex,v,n=0;while(cin〉〉index>〉v)if(index==-l&&v==-l)break;n++;q.id=index;q.value=v;insert_Queue(q);}for(inti=0;i

10、tem("pause”)；return0;运行结果:eXeUJ-hktoseqoratrStmdAsser:ucI'口