资源描述:
《湖南大学数据结构试验7优先队列与堆问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、HUNANUNIVERSITY课程实习报告题目:优先队列与堆问题学生姓名刘乐学生学号20080820208专业班级通信工程2班指导老师朱宁波完成日期2010年5月31日一、需求分析:1.本程序来自于实际问题中医生看病是由病人严重程度来决定的,护士给病人ID的同时,也给其相应的权值,这样医生开始看病权值越小即越严重,就优先看病。2.本程序要求:(1)利用最小值堆实现一个优先队列。(2)利用优先队列存入病人信息,最后确定优先队列看病的次序。3在dos系统下输入ID和priority。4测试数据:二、概要设计为实现上述功能需要用到顺序表的存储结构。算法基本思想堆
2、排序的算法教材上已经给得很清楚,而此实验要求用最小堆实现,故只要建堆后,反复“筛选”将此序列看成一个完全二叉树,则最后一个非终端节点是{n/2}个元素,由此筛选只需要从第{n/2}个元素开始,不断构造小顶堆,即从上到下比较把孩子节点较小的和父节点交换,逐层实现,最后得到有序最小堆。程序设计流程程序由三个模块组成:(1)输入模块:dos系统下输入病人的ID和priority(1)最小堆排序模块:最小堆函数实现无序变为有序化。(2)输出模块:输出权值由小到大排列的ID。一、详细设计1.构造一个顺序表的存储结构用来存储病人的ID和priority#typedef
3、struct{intid;intkey;}xinxiType;//病人信息typedefstruct{xinxiTyper[MAXSIZE];MAXSIZE已经在初始化定义为1000intlength;}Sqlist;//存储顺序结构typedefSqlistHeapType;voidInitial(HeapType*H){inti;for(i=0;i<=MAXSIZE;i++){H->r[i].id=0;//身份编号H->r[i].key=0;//优先权值H->length=0;}2入队函数:voidCreatHeap(HeapType*H,inta,i
4、ntb){H->length++;H->r[H->length].id=a;H->r[H->length].key=b;//读入病人的ID和priority}3小顶堆的实现:intbijiao(inta,intb){if(a>b)return1;elsereturn0;}//构造一个比较函数voidHeapAdjust(HeapType*H,ints,intm){intj;H->r[0]=H->r[s];//设置一个哨站for(j=2*s;j<=m;j*=2){if(jr[j].key,H->r[j+1].key))j++;//
5、把父节点所要比较的较小子结点给出if(!bijiao(H->r[0].key,H->r[j].key))break;//父节点比子结点较小的小跳出循环,则此部分已经为最小堆H->r[s]=H->r[j];//如果父节点比子结点较小的大则交换之s=j;}H->r[s]=H->r[0];//把原来父节点值赋给较小的子结点或父节点}voidHeapSort(HeapType*H){inti;for(i=H->length/2;i>0;i--)//从n/2开始递减调用调整函数,直到最后一个HeapAdjust(H,i,H->length);for(i=H->len
6、gth;i>1;i--){H->r[0]=H->r[1];//设置哨站H->r[1]=H->r[i];H->r[i]=H->r[0];将堆顶记录当前未经排序序列最后一个记录相交换HeapAdjust(H,1,i-1);逐步将剩余点调整为小顶堆}}4主函数voidmain(){intx=0,y=0,i;HeapType*H;H=(HeapType*)malloc(sizeof(HeapType));//分配存储空间Initial(H);printf("输入病人ID和病人priority值",x,y);while(x!=-1&&y!=-1){scanf("
7、%d,%d",&x,&y);if(x==-1)break;CreatHeap(H,x,y);}HeapSort(H);for(i=H->length;i>=1;i--)printf("%dt",H->r[i].id);printf("");}四、调试分析:算法的时空分析:算法时间复杂度在最坏情况下为o(nlogn)输入输出格式:五、实验心得:本次实验也是在宿舍完成的,因此去了就是让助教老师看了一下就通过了,因为书上用到大顶堆解决排序的问题程序给的已经很全面,我就主要用这种方法实现了最小堆,所以还是难度不大,这次实验不仅熟悉了堆排序内容,而且对新学
8、的内容有了更深的理解,正在看一些其他的程序,相信会有更多提高。六、