湖南大学数据结构试验7优先队列与堆问题

《湖南大学数据结构试验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、的内容有了更深的理解，正在看一些其他的程序，相信会有更多提高。六、