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

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

数据结构课程实验指导书-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}}

1 / 7
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功