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

数据结构课程实验指导书－1－实验报告部分HUNANUNIVERSITY课程实习报告题目：优先队列与堆学生姓名廖嘉琦学生学号20090820109专业班级通信一班指导老师夏艳完成日期2010-11-2数据结构课程实验指导书－2－一、需求分析（1）本程序要求利用最小值堆实现一个优先队列。（2）对于优先队列应该支持如下操作：初始化队列的init操作；获得队列中元素个数的size操作；判定队列是否为空的empty操作；获得队列中最优先的元素的值的top操作；向队列中插入一个元素的push操作；删除队列中最优先的元素的pop操作。（3）利用优先队列存入所有病人的信息（编号和病情严重程度）。最后利用优先队列获得病人看病的次序。（4）堆的数组的ID和和Priority由用户通过键盘输入，其取值范围为（0，216）。不对非法输入做处理，即假设输入都是合法的。（5）在Dos界面输出病人看病的次序。（6）测试数据输入1152335420510－1－1输出23514二、概要设计抽象数据类型为实现上述程序的功能，应以整数存储用户的输入，以及计算出的结果。算法的基本思想（1）根据题目要求，最小值堆采用数组作为物理存储结构，每个元素是一个结构体变量，包含编号ID和病情严重程度Priority值，以Priority进行排序，最后由优先队列获得病人看病的次序。。程序的流程程序由三个模块组成：（1）输入模块：完成输入结构体数组中每个元素的ID和Priority节点个数，存储在structpatientp[30]中。（2）处理模块：再定义一个类，将该数组作为参数传给类，使数组变成一个优先队列。（3）输出模块：屏幕上显示排序后的病人看病次序。三、详细设计物理数据类型题目要求输入的正整数的取值范围在（0，216）之间，为了能够存储，采用C语言中的整型定义变量。在定义一个结构体变量，存储次序和病情程度。数据结构课程实验指导书－3－structpatient{intID;intPriority;};算法的具体步骤算法流程图如下开始输入病人的ID号和病情程度minheapdui(p,i,30);inta,b;cinab;structpatientp[30];inti=0;(a!=-1)&&(b!=-1)p[i].ID=a;p[i].Priority=b;i++;cinab;noyesJi?结束dui.pop(patient1);j++;coutpatient1.IDendl;noyesStructpatientpatient1;J=0;数据结构课程实验指导书－4－输入和输出的格式输入61573859201010//输入病人的ID号和Priority－1－1//以-1结束输出23514//输出病人的次序四、调试分析略。五、测试结果输入111512313514201510－1－1输出23514六、用户使用说明（可选）1、本程序的运行环境为DOS操作系统，执行文件为正式实验七.exe2、运行程序时提示输入病人的ID号和Priority以-1结束数据结构课程实验指导书－5－七、实验心得（可选）略。七、附录（可选）正式试验七.c主程序#includeiostream.hstructpatient{intID;intPriority;};//定义一个结构体变量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)&&(posn);}//判断是否叶节点intleftchild(intpos)const{return2*pos+1;}//得到左节点intrightchild(intpos)const{return2*pos+2;}//得到右节点intparent(intpos)const{return(pos-1)/2;}//得到父节点boolempty(){if(n==0)returntrue;elsereturnfalse;}//判定队列是否为空boolpush(conststructpatient&);//向队列中插入一个元素boolpop(structpatient&);//删除队列中最优先的元素booltop(structpatient&);//获得队列中最优先的元素的值voidbuildHeap()数据结构课程实验指导书－6－{for(inti=n/2-1;i=0;i--)siftdown(i);}//将一个数组按照堆的性质重新建立};voidminheap::siftdown(intpos)//往下建立最小值堆{while(!isLeaf(pos)){intj=leftchild(pos);intrc=rightchild(pos);if((rcn)&&(Heap[j].PriorityHeap[rc].Priority))j=rc;//先把Heap[j]设成子树中的较小值if(!(Heap[pos].PriorityHeap[j].Priority))return;//结点若比子树还小，就不必动structpatienttemp;temp=Heap[pos];Heap[pos]=Heap[j];Heap[j]=temp;//交换结点与该子树//swap(Heap,pos,j);pos=j;//把子树设为当前结点，再重复进行，往下建立最小值堆}}boolminheap::pop(structpatient&it)//删除队列中最优先的元素{if(empty())returnfalse;//堆是空的structpatienttemp;temp=Heap[0];Heap[0]=Heap[--n];Heap[n]=temp;//把堆中的最小元素与最后一个元素交换//swap(Heap,0,--n);if(n!=0)siftdown(0);//将第一个元素往后交换it=Heap[n];//返回最小元素returntrue;}boolminheap::push(conststructpatient&val)//向队列中插入一个元素{if(n=size)returnfalse;//堆已满intcurr=n++;Heap[curr]=val;while((curr!=0)&&(Heap[curr].PriorityHeap[parent(curr)].Priority))数据结构课程实验指导书－7－{structpatienttemp;temp=Heap[curr];Heap[curr]=Heap[parent(curr)];Heap[parent(curr)]=temp;//swap(Heap,curr,);curr=parent(curr);}//按照优先值把元素插入堆中returntrue;}boolminheap::top(structpatient&it){if(n==0)returnfalse;it=Heap[0];//返回第一个元素，即最优先元素returntrue;}voidmain(){cout请输入病人的ID号和病情程度，并以-1结束endl;inta,b;cina;cinb;structpatientp[30];//定义一个结构体数组inti=0;while((a!=-1)&&(b!=-1))//如果a和b都不是-1，继续往下{p[i].ID=a;//对结构体变量的初始化p[i].Priority=b;i++;cina;cinb;}//最后数组中一共有i个值minheapdui(p,i,30);//建立一个类，使得该数组成为一个堆structpatientpatient1;cout病人的排序为:endl;for(intj=0;ji;j++){dui.pop(patient1);coutpatient1.IDendl;//打印出排序后病人的ID}}