优先队列与堆实验报告附c++源码.docx
- 文档编号:1397569
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:10
- 大小:42.30KB
优先队列与堆实验报告附c++源码.docx
《优先队列与堆实验报告附c++源码.docx》由会员分享,可在线阅读,更多相关《优先队列与堆实验报告附c++源码.docx(10页珍藏版)》请在冰点文库上搜索。
优先队列与堆实验报告附c++源码
优先队列与堆(病人看病顺序)
一、需求分析
1.本程序采用最小值堆实现一个优先队列,最小值堆是用的数组实现;
2.优先队列支持如下操作:
初始化队列的初始化操作(在构建对象的时候实现);获得队列中元素个数;判定队列是否为空;获得队列中最优先的元素的值;向队列中插入一个元素;删除队列中最有先的元素;
3.优先队列中,存有病人的信息(编号和病情严重程度),此程序
4.测试数据:
输入:
编号1严重程度1
编号2严重程度2
编号3严重程度3
编号4严重程度4
编号5严重程度5
-1-1
输出:
编号2编号1编号5编号4编号3
二、概要设计
抽象数据类型
构建了一个病人信息类,只用于存储病人信息(编号,病情严重程度):
classNode{
public:
intID;//记录病人编号
intPriority;//记录病人病情严重程度
};
构建了一个最小值堆类,采用数组实现,成员变量、函数详细信息如下:
classMinHeap
{
private:
Node*heap;//根结点,也是数组头元素的地址
intmaxSize,num;//maxSize为堆元素最多个数,num记录元素个数
voidsiftdown(int);//将结点移动到符合要求的位置
voidswap(Node&,Node&);//交换两结点的值
public:
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 { swap(heap[curr],heap[parentPos(curr)]); curr=parentPos(curr); } returntrue; } 2.输出根结点的值,并删除根结点,直到堆为空: boolMinHeap: : pop(Node&it)//删除根结点 { if(num==0) returnfalse; swap(heap[0],heap[--num]); if(num! =0) siftdown(0);//因为最后一个元素与根结点交换值,需要将根//结点移到合适位置,实现如下 it=heap[num]; returntrue; } 将某位置的结点向下移到合适位置的函数: voidMinHeap: : siftdown(intpos)//将pos上的结点移到合适的位置 { while(! isLeaf(pos)) { intl=l_ChildPos(pos),r=r_ChildPos(pos); if((r 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 usingnamespacestd; classNode{ public: intID; intPriority; }; classMinHeap { private: Node*heap;//根结点 intmaxSize,num;//maxSize为该堆的做多元素个数,num记录当前堆里结点数目 voidsiftdown(int);//将结点移动到符合要求的位置 voidswap(Node&,Node&);//交换两结点的值 public: MinHeap(int); boolisEmpty();//判断堆是否为空 boolisLeaf(int);//判断是不是叶结点 boolpush(constNode);//插入结点 boolpop(Node&);//删除根结点 intl_ChildPos(int);//获得左结点的位置 intr_ChildPos(int);//获得右结点的位置 intparentPos(int);//获得妇结点的位置 }; MinHeap: : MinHeap(intsize)//构造函数 { heap=newNode[size]; num=0; maxSize=size; } boolMinHeap: : isEmpty()//判断是否为空 { if(num! =0) returnfalse; returntrue; } intMinHeap: : l_ChildPos(intpos)//获得左结点的位置 { return2*pos+1; } intMinHeap: : r_ChildPos(intpos)//获得右结点的位置 { return2*pos+2; } intMinHeap: : parentPos(intpos)//获得父结点的位置 { return(pos-1)/2; } voidMinHeap: : swap(Node&aNode,Node&bNode)//交换两个结点的值 { Nodetemp; temp=aNode; aNode=bNode; bNode=temp; } boolMinHeap: : isLeaf(intpos)//判断是否为叶结点 { return(pos>=num/2)&&(pos } boolMinHeap: : push(constNodein)//向堆里插入结点 { if(num>maxSize) returnfalse; intcurr=num++; heap[curr]=in; while((curr! =0)&&heap[curr].Priority { swap(heap[curr],heap[parentPos(curr)]); curr=parentPos(curr); } returntrue; } boolMinHeap: : pop(Node&it)//删除根结点 { if(num==0) returnfalse; swap(heap[0],heap[--num]); if(num! =0) siftdown(0); it=heap[num]; returntrue; } voidMinHeap: : siftdown(intpos)//将pos上的结点移到合适的位置 { while(! isLeaf(pos)) { intl=l_ChildPos(pos),r=r_ChildPos(pos); if((r l=r; if(heap[l].Priority>=heap[pos].Priority) return; swap(heap[l],heap[pos]); pos=l; } } intmain() { Nodetemp; MinHeaponeHeap(40); cout<<"输入\"-1-1\"结束输入"< while (1){ cin>>temp.ID>>temp.Priority; if(temp.ID==-1&&temp.Priority==-1) break; oneHeap.push(temp); } cout<<"编号按病情排序结果: "< while(! oneHeap.isEmpty()) { oneHeap.pop(temp);cout< } cout< return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 优先 队列 实验 报告 c+ 源码
![提示](https://static.bingdoc.com/images/bang_tan.gif)