优先队列与堆实验报告附c++源码Word格式文档下载.docx
《优先队列与堆实验报告附c++源码Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《优先队列与堆实验报告附c++源码Word格式文档下载.docx（10页珍藏版）》请在冰点文库上搜索。
-1-1
输出：
编号2编号1编号5编号4编号3
二、概要设计
抽象数据类型
构建了一个病人信息类，只用于存储病人信息（编号，病情严重程度）：
classNode{
public:
intID;
//记录病人编号
intPriority;
//记录病人病情严重程度
};
构建了一个最小值堆类，采用数组实现，成员变量、函数详细信息如下：
classMinHeap
{
private:
Node*heap;
//根结点，也是数组头元素的地址
intmaxSize,num;
//maxSize为堆元素最多个数，num记录元素个数
voidsiftdown（int）;
//将结点移动到符合要求的位置
voidswap（Node&
Node&
）;
//交换两结点的值
MinHeap（int）;
boolisEmpty（）;
//判断堆是否为空
boolisLeaf（int）;
//判断是不是叶结点
boolpush（constNode）;
//插入结点
boolpop（Node&
//删除根结点
inttop（）;
//返回根结点的ID
intl_ChildPos（int）;
//获得左结点的位置
intr_ChildPos（int）;
//获得右结点的位置
intparentPos（int）;
//获得妇结点的位置
算法的基本思想
1.最小值堆采用数组作为物理存储结构，每个元素是一个结构体变量，包含编号ID和病情严重程度Priority值；
2.用户输入一个病人信息，就用插入法，插进堆里，输入完毕时，就是一个符合要求的堆
3.用户录入－1－1表示输入结束；
4.输出：
每输出一个最小值，就删掉一个，然后继续整理成最小值堆，继续输出。
程序的流程
初始化一个空堆->
插入病人信息到合适位置->
当堆不为空，输出最小值，删掉最小值，直到堆为空。
算法的具体步骤
1.输入病人信息，构建成堆：
每输入一个病人信息，就将该病人信息移至堆中合适位置
boolMinHeap:
:
push（constNodein）//向堆里插入结点
if（num>
maxSize）
returnfalse;
intcurr=num++;
heap[curr]=in;
while（（curr!
=0）&
&
heap[curr].Priority<
heap[parentPos（curr）].Priority）
{
swap（heap[curr],heap[parentPos（curr）]）;
curr=parentPos（curr）;
}
returntrue;
}
2.输出根结点的值，并删除根结点，直到堆为空：
pop（Node&
it）//删除根结点
if（num==0）
swap（heap[0],heap[--num]）;
if（num!
=0）
siftdown（0）;
//因为最后一个元素与根结点交换值，需要将根//结点移到合适位置，实现如下
it=heap[num];
将某位置的结点向下移到合适位置的函数：
voidMinHeap:
siftdown（intpos）//将pos上的结点移到合适的位置
while（!
isLeaf（pos））
intl=l_ChildPos（pos）,r=r_ChildPos（pos）;
if（（r<
num）&
（heap[l].Priority>
heap[r].Priority））
l=r;
if（heap[l].Priority>
=heap[pos].Priority）
return;
swap（heap[l],heap[pos]）;
pos=l;
算法的时空分析
因为使用的是插入法建堆，每次插入，有可能要从数的底部移动到顶部，因此，最差情况下时间代价为Θ（㏒n），插入n个病人信息的时间代价为Θ（n㏒n）。
在删除结点后，需要将根结点向下移到合适位置，最坏的情况移动的最大距离为移到底部，时间复杂度为Θ（n）。
输入和输出的格式
输入
输入“-1-1”结束输入//提示
等待输入
输出
编号按病情排序结果//提示
输出结果
三、测试结果
四、用户使用说明
1.需要输入“-1-1”结束输入；
2.默认最大的病人信息量为40个。
五、实验心得
这个实验比较简单，因为可以参考书上的算法和源码。
但还是有出错的地方，就是在使用数组时，只定义了一个与数组类型相同的指针，就将那指针做数组名使用，因此编译出错。
六、附录（源码）
#include<
iostream>
usingnamespacestd;
//根结点
//maxSize为该堆的做多元素个数，num记录当前堆里结点数目
MinHeap:
MinHeap（intsize）//构造函数
heap=newNode[size];
num=0;
maxSize=size;
isEmpty（）//判断是否为空
intMinHeap:
l_ChildPos（intpos）//获得左结点的位置
return2*pos+1;
r_ChildPos（intpos）//获得右结点的位置
return2*pos+2;
parentPos（intpos）//获得父结点的位置
return（pos-1）/2;
swap（Node&
aNode,Node&
bNode）//交换两个结点的值
Nodetemp;
temp=aNode;
aNode=bNode;
bNode=temp;
isLeaf（intpos）//判断是否为叶结点
return（pos>
=num/2）&
（pos<
num）;
siftdown（0）;
intmain（）
MinHeaponeHeap（40）;
cout<
<
"
输入\"
-1-1\"
结束输入"
<
endl;
while
（1）{
cin>
>
temp.ID>
temp.Priority;
if（temp.ID==-1&
temp.Priority==-1）
break;
oneHeap.push（temp）;
编号按病情排序结果：
"
oneHeap.isEmpty（））
oneHeap.pop（temp）;
temp.ID<
'
\t'
;
return0;
升级会员 