实验七优先队列与堆实验报告.doc

《实验七优先队列与堆实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告部分HUNANUNIVERSITY课程实习报告题目：优先队列与堆学生姓名廖嘉琦学生学号专业班级通信一班指导老师夏艳完成日期2010-11-2一、需求分析（1）本程序要求利用最小值堆实现一个优先队列。（2）对于优先队列应该支持如下操作：初始化队列的init操作；获得队列中元素个数的size操作；判定队列是否为空的empty操作；获得队列中最优先的元素的值的top操作；向队列中插入一个元素的push操作；删除队列中最优先的元素的pop操作。（3）利用优先队列存入所有病人的信息（编号和病情严重程度）。最后利用优先队

2、列获得病人看病的次序。（4）堆的数组的ID和和Priority由用户通过键盘输入，其取值范围为（0，216）。不对非法输入做处理，即假设输入都是合法的。（5）在Dos界面输出病人看病的次序。（6）测试数据输入1152335420510－1－1输出23514二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。算法的基本思想（1）根据题目要求，最小值堆采用数组作为物理存储结构，每个元素是一个结构体变量，包含编号ID和病情严重程度Priority值，以Priority进行排序，最后由优先

3、队列获得病人看病的次序。。程序的流程程序由三个模块组成：（1）输入模块：完成输入结构体数组中每个元素的ID和Priority节点个数，存储在structpatientp[30]中。（2）处理模块：再定义一个类，将该数组作为参数传给类，使数组变成一个优先队列。（3）输出模块：屏幕上显示排序后的病人看病次序。三、详细设计物理数据类型题目要求输入的正整数的取值范围在（0，216）之间，为了能够存储，采用C语言中的整型定义变量。在定义一个结构体变量，存储次序和病情程度。structpatient{intID;intPrior

4、ity;};算法的具体步骤算法流程图如下开始输入病人的ID号和病情程度inta,b;cin>>a>>b;structpatientp[30];inti=0;no(a!=-1)&&(b!=-1)yesp[i].ID=a;p[i].Priority=b;i++;cin>>a>>b;minheapdui(p,i,30);Structpatientpatient1;J=0;dui.pop(patient1);j++;cout<

5、510//输入病人的ID号和Priority－1－1//以-1结束输出23514//输出病人的次序四、调试分析略。五、测试结果输入61573859201010－1－1输出23514六、用户使用说明（可选）1、本程序的运行环境为DOS操作系统，执行文件为正式实验七.exe2、运行程序时提示输入病人的ID号和Priority以-1结束七、实验心得（可选）略。七、附录（可选）正式试验七.c主程序#includestructpatient{intID;intPriority;};//定义一个结构体变量

6、classminheap{private:structpatient*Heap;intsize;intn;voidsiftdown(int);public:minheap(structpatient*h,intnum,intmax)//包涵该数组、数组元素数目、数组的大小{Heap=h;n=num;size=max;buildHeap();//建立一个最小值堆}intheapsize()const{returnn;}//堆的大小boolisLeaf(intpos)const{return(pos>=n/2)&&(po

7、s

8、olpop(structpatient&);//删除队列中最优先的元素booltop(structpatient&);//获得队列中最优先的元素的值voidbuildHeap(){for(inti=n/2-1;i>=0;i--)siftdown(i);}//将一个数组按照堆的性质重新建立};voidminheap::siftdown(intpo