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

HUNAN UNIVERSITY课程实习报告题 目：优先队列与堆问题 学生姓名 刘乐 学生学号 20080820208 专业班级 通信工程2班 指导老师 朱宁波 完 成 日 期 2010年5月31日 一、 需 求 分 析：1. 本程序来自于实际问题中医生看病是由病人严重程度来决定的，护士给病人ID的同时，也给其相应的权值，这样医生开始看病权值越小即越严重，就优先看病。2. 本程序要求：（1）利用最小值堆实现一个优先队列。（2）利用优先队列存入病人信息，最后确定优先队列看病的次序。3在dos系统下输入ID和priority。4测试数据：二、 概要设计为实现上述功能需要用到顺序表的存储结构。算法基本思想堆排序的算法教材上已经给得很清楚，而此实验要求用最小堆实现，故只要建堆后，反复“筛选”将此序列看成一个完全二叉树，则最后一个非终端节点是n/2个元素，由此筛选只需要从第n/2个元素开始，不断构造小顶堆，即从上到下比较把孩子节点较小的和父节点交换，逐层实现，最后得到有序最小堆。程序设计流程程序由三个模块组成：（1） 输入模块：dos系统下输入病人的ID和priority（2） 最小堆排序模块：最小堆函数实现无序变为有序化。（3） 输出模块：输出权值由小到大排列的ID。三、 详细设计1. 构造一个顺序表的存储结构用来存储病人的ID和priority#typedef structint id;int key;xinxiType; /病人信息 typedef structxinxiType rMAXSIZE; MAXSIZE已经在初始化定义为1000int length;Sqlist; /存储顺序结构 typedef Sqlist HeapType; void Initial(HeapType *H) int i;for(i=0;iri.id=0; /身份编号 H-ri.key=0; /优先权值 H-length=0;2 入队函数:void CreatHeap(HeapType *H,int a,int b) H-length+;H-rH-length.id=a;H-rH-length.key=b; /读入病人的ID和priority3小顶堆的实现：int bijiao(int a,int b)if(ab)return 1;else return 0; /构造一个比较函数void HeapAdjust(HeapType *H,int s,int m)int j;H-r0=H-rs; / 设置一个哨站for(j=2*s;j=m;j*=2)if(jrj.key,H-rj+1.key)j+; / 把父节点所要比较的较小子结点给出if(!bijiao(H-r0.key,H-rj.key)break; /父节点比子结点较小的小跳出循环，则此部分已经为最小堆H-rs=H-rj;/如果父节点比子结点较小的大则交换之s=j;H-rs=H-r0;/把原来父节点值赋给较小的子结点或父节点 void HeapSort(HeapType *H)int i;for(i=H-length/2;i0;i-) /从n/2开始递减调用调整函数，直到最后一个 HeapAdjust(H,i,H-length);for(i=H-length;i1;i-) H-r0=H-r1;/设置哨站 H-r1=H-ri;H-ri=H-r0;将堆顶记录当前未经排序序列最后一个记录相交换HeapAdjust(H,1,i-1);逐步将剩余点调整为小顶堆4主函数void main( ) int x=0,y=0,i;HeapType *H; H = (HeapType *)malloc(sizeof(HeapType);/分配存储空间Initial(H); printf(输入病人ID和病人priority值n,x,y);while(x!=-1&y!=-1) scanf(%d,%dn,&x,&y); if(x=-1) break; CreatHeap(H,x,y); HeapSort(H);for(i=H-length;i=1;i-)printf(%dt,H-ri.id);printf(n);四、调试分析：算法的时空分析：算法时间复杂度在最坏情况下为o（nlogn）输入输出格式：五、 实验心得：本次实验也是在宿舍完成的，因此去了就是让助教老师看了一下就通过了，因为书上用到大顶堆解决排序的问题程序给的已经很全面，我就主要用这种方法实现了最小堆，所以还是难度不大，这次实验不仅熟悉了堆排序内容，而且对新学的内容有了更深的理解，正在看一些其他的程序，相信会有更多提高。六、 实验源程序：#include#include#define MAXSIZE 1000typedef structint id;int key;xinxiType; typedef structxinxiType rMAXSIZE;int length;Sqlist; typedef Sqlist HeapType; void Initial(HeapType *H) int i;for(i=0;iri.id=0; H-ri.key=0; H-length=0;void CreatHeap(HeapType *H,int a,int b) H-length+;H-rH-length.id=a;H-rH-length.key=b;int bijiao(int a,int b)if(ab)return 1;else return 0;void HeapAdjust(HeapType *H,int s,int m)int j;H-r0=H-rs;for(j=2*s;j=m;j*=2)if(jrj.key,H-rj+1.key)j+;if(!bijiao(H-r0.key,H-rj.key)break;H-rs=H-rj;s=j;H-rs=H-r0;void HeapSort(HeapType *H)int i;for(i=H-length/2;i0;i-) HeapAdjust(H,i,H-length);for(i=H-length;i1;i-) H-r0=H-r1; H-r1=H-ri;H-ri=H-r0;HeapAdjust(H,1,i-1);void main( ) int x=0,y=0,i;HeapType *H; H = (HeapType *)malloc(sizeof(HeapType);Initial(H); printf(输入病人ID和病人priority值n,