实验七优先队列与堆实验报告(共7页).doc
精选优质文档-倾情为你奉上实验报告部分HUNAN UNIVERSITY课程实习报告题 目： 优先队列与堆 学生姓名 廖嘉琦 学生学号 专业班级 通信一班 指导老师 夏艳 完 成 日 期 2010-11-2 专心-专注-专业一、需求分析（1） 本程序要求利用最小值堆实现一个优先队列。（2） 对于优先队列应该支持如下操作：初始化队列的init操作；获得队列中元素个数的size操作；判定队列是否为空的empty操作；获得队列中最优先的元素的值的top操作；向队列中插入一个元素的push操作；删除队列中最优先的元素的pop操作。（3） 利用优先队列存入所有病人的信息（编号和病情严重程度）。最后利用优先队列获得病人看病的次序。（4） 堆的数组的ID和和Priority由用户通过键盘输入，其取值范围为（0， 216）。不对非法输入做处理，即假设输入都是合法的。（5） 在Dos界面输出病人看病的次序。（6） 测试数据输入1 152 33 54 205 101 1输出23514二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。算法的基本思想（1） 根据题目要求，最小值堆采用数组作为物理存储结构，每个元素是一个结构体变量，包含编号ID和病情严重程度Priority值，以Priority进行排序，最后由优先队列获得病人看病的次序。 程序的流程程序由三个模块组成：（1） 输入模块：完成输入结构体数组中每个元素的ID和Priority节点个数，存储在struct patient p30中。（2） 处理模块：再定义一个类，将该数组作为参数传给类，使数组变成一个优先队列。（3） 输出模块：屏幕上显示排序后的病人看病次序。三、详细设计物理数据类型题目要求输入的正整数的取值范围在（0， 216）之间，为了能够存储，采用C语言中的整型定义变量。在定义一个结构体变量，存储次序和病情程度。struct patientint ID;int Priority; 算法的具体步骤算法流程图如下开始输入病人的ID号和病情程度int a,b; cin>>a>>b;struct patient p30; int i=0;no(a!=-1)&&(b!=-1)yespi.ID=a;pi.Priority=b;i+; cin>>a>> b;minheap dui(p,i,30);Struct patient patient1;J=0;dui.pop(patient1); j+;cout<<patient1.ID<<endl;yesnoJ<i?结束输入和输出的格式输入6 157 38 59 2010 10 /输入病人的ID号和Priority1 1 /以-1结束输出23514 /输出病人的次序四、调试分析略。五、测试结果输入11 1512 313 514 2015 10 1 1 输出23514 六、用户使用说明（可选）1、本程序的运行环境为DOS操作系统，执行文件为 正式实验七.exe2、运行程序时提示输入病人的ID号和Priority以-1结束七、实验心得（可选）略。七、附录（可选）正式试验七.c 主程序#include<iostream.h>struct patientint ID;int Priority; /定义一个结构体变量class minheapprivate:struct patient* Heap;int size;int n;void siftdown(int);public:minheap(struct patient * h,int num,int max) /包涵该数组、数组元素数目、数组的大小Heap=h;n=num;size=max;buildHeap(); /建立一个最小值堆int heapsize() const return n; /堆的大小bool isLeaf (int pos) const return (pos >=n/2)&&(pos<n); /判断是否叶节点int leftchild(int pos) const return 2*pos+1; /得到左节点int rightchild(int pos) const return 2*pos+2; /得到右节点int parent(int pos) const return (pos-1)/2; /得到父节点bool empty() if(n=0) return true; else return false; /判定队列是否为空bool push(const struct patient&); /向队列中插入一个元素 bool pop(struct patient&); /删除队列中最优先的元素bool top(struct patient&); /获得队列中最优先的元素的值void buildHeap() for(int i=n/2-1;i>=0;i-) siftdown(i); /将一个数组按照堆的性质重新建立;void minheap:siftdown(int pos) /往下建立最小值堆while (!isLeaf(pos) int j = leftchild(pos);int rc = rightchild(pos);if (rc<n) && (Heapj.Priority>Heaprc.Priority)j = rc; /先把Heapj设成子树中的较小值if (!(Heappos.Priority>Heapj.Priority) return; /结点若比子树还小，就不必动struct patient temp;temp=Heappos;Heappos=Heapj;Heapj=temp; /交换结点与该子树/swap(Heap, pos, j);pos = j; /把子树设为当前结点，再重复进行，往下建立最小值堆bool minheap: pop(struct patient& it) /删除队列中最优先的元素 if (empty() return false; / 堆是空的 struct patient temp;temp=Heap0;Heap0=Heap-n;Heapn=temp; /把堆中的最小元素与最后一个元素交换/swap(Heap, 0, -n); if (n != 0) siftdown(0); /将第一个元素往后交换it = Heapn; / 返回最小元素 return true;bool minheap:push (const struct patient& val) /向队列中插入一个元素if(n>=size)return false; /堆已满int curr=n+;Heapcurr=val;while(curr!=0)&&(Heapcurr.Priority<Heapparent(curr).Priority)struct patient temp; temp=Heapcurr; Heapcurr=Heapparent(curr); Heapparent(curr)=temp;/swap(Heap,curr,);curr=parent(curr); /按照优先值把元素插入堆中return true;bool minheap:top(struct patient& it)if(n=0) return false ;it=Heap0; /返回第一个元素，即最优先元素return true;void main()cout<<"请输入病人的ID号和病情程度，并以-1结束"<<endl;int a,b;cin>>a;cin>>b;struct patient p30; /定义一个结构体数组 int i=0;while(a!=-1)&&(b!=-1) /如果a和b都不是-1，继续往下pi.ID=a; /对结构体变量的初始化pi.Priority=b;i+; cin>>a;cin>>b; /最后数组中一共有i个值 minheap dui(p,i,30); /建立一个类，使得该数组成为一个堆struct patient patient1;cout<<"病人的排序为:"<<endl;for(int j=0;j<i;j+)dui.pop(patient1);cout<<patient1.ID<<endl; /打印出排序后病人的ID
