實驗七優(yōu)先隊列與堆實驗報告(共7頁)

1、實驗報告部分HUNAN UNIVERSITY課程實習(xí)報告題 目： 優(yōu)先隊列與堆 學(xué)生姓名 廖嘉琦 學(xué)生學(xué)號 20090820109 專業(yè)班級 通信一班 指導(dǎo)老師 夏艷 完 成 日 期 2010-11-2 一、需求分析（1） 本程序要求利用最小值堆實現(xiàn)一個優(yōu)先隊列。（2） 對于優(yōu)先隊列應(yīng)該支持如下操作：初始化隊列的init操作；獲得隊列中元素個數(shù)的size操作；判定隊列是否為空的empty操作；獲得隊列中最優(yōu)先的元素的值的top操作；向隊列中插入一個元素的push操作；刪除隊列中最優(yōu)先的元素的pop操作。（3） 利用優(yōu)先隊列存入所有病人的信息（編號和病情嚴(yán)重程度）。最后利用優(yōu)先隊列獲得病人看病的

2、次序。（4） 堆的數(shù)組的ID和和Priority由用戶通過鍵盤輸入，其取值范圍為（0， 216）。不對非法輸入做處理，即假設(shè)輸入都是合法的。（5） 在Dos界面輸出病人看病的次序。（6） 測試數(shù)據(jù)輸入1 152 33 54 205 101 1輸出23514二、概要設(shè)計抽象數(shù)據(jù)類型為實現(xiàn)上述程序的功能，應(yīng)以整數(shù)存儲用戶的輸入，以及計算出的結(jié)果。算法的基本思想（1） 根據(jù)題目要求，最小值堆采用數(shù)組作為物理存儲結(jié)構(gòu)，每個元素是一個結(jié)構(gòu)體變量，包含編號ID和病情嚴(yán)重程度Priority值，以Priority進行排序，最后由優(yōu)先隊列獲得病人看病的次序。 程序的流程程序由三個模塊組成：（1） 輸入模塊：完

3、成輸入結(jié)構(gòu)體數(shù)組中每個元素的ID和Priority節(jié)點個數(shù)，存儲在struct patient p30中。（2） 處理模塊：再定義一個類，將該數(shù)組作為參數(shù)傳給類，使數(shù)組變成一個優(yōu)先隊列。（3） 輸出模塊：屏幕上顯示排序后的病人看病次序。三、詳細(xì)設(shè)計物理數(shù)據(jù)類型題目要求輸入的正整數(shù)的取值范圍在（0， 216）之間，為了能夠存儲，采用C語言中的整型定義變量。在定義一個結(jié)構(gòu)體變量，存儲次序和病情程度。struct patientint ID;int Priority; 算法的具體步驟算法流程圖如下開始輸入病人的ID號和病情程度int a,b; cin>>a>>b;struct

4、 patient p30; int i=0;no(a!=-1)&&(b!=-1)yespi.ID=a;pi.Priority=b;i+; cin>>a>> b;minheap dui(p,i,30);Struct patient patient1;J=0;dui.pop(patient1); j+;cout<<patient1.ID<<endl;yesnoJ<i?結(jié)束輸入和輸出的格式輸入6 157 38 59 2010 10 /輸入病人的ID號和Priority1 1 /以-1結(jié)束輸出23514 /輸出病人的次序四、調(diào)試分析

5、略。五、測試結(jié)果輸入11 1512 313 514 2015 10 1 1 輸出23514 六、用戶使用說明（可選）1、本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為 正式實驗七.exe2、運行程序時提示輸入病人的ID號和Priority以-1結(jié)束七、實驗心得（可選）略。七、附錄（可選）正式試驗七.c 主程序#include<iostream.h>struct patientint ID;int Priority; /定義一個結(jié)構(gòu)體變量class minheapprivate:struct patient* Heap;int size;int n;void siftdown(int)

6、;public:minheap(struct patient * h,int num,int max) /包涵該數(shù)組、數(shù)組元素數(shù)目、數(shù)組的大小Heap=h;n=num;size=max;buildHeap(); /建立一個最小值堆int heapsize() const return n; /堆的大小bool isLeaf (int pos) const return (pos >=n/2)&&(pos<n); /判斷是否葉節(jié)點int leftchild(int pos) const return 2*pos+1; /得到左節(jié)點int rightchild(int

7、pos) const return 2*pos+2; /得到右節(jié)點int parent(int pos) const return (pos-1)/2; /得到父節(jié)點bool empty() if(n=0) return true; else return false; /判定隊列是否為空bool push(const struct patient&); /向隊列中插入一個元素 bool pop(struct patient&); /刪除隊列中最優(yōu)先的元素bool top(struct patient&); /獲得隊列中最優(yōu)先的元素的值void buildHeap()

8、for(int i=n/2-1;i>=0;i-) siftdown(i); /將一個數(shù)組按照堆的性質(zhì)重新建立;void minheap:siftdown(int pos) /往下建立最小值堆while (!isLeaf(pos) int j = leftchild(pos);int rc = rightchild(pos);if (rc<n) && (Heapj.Priority>Heaprc.Priority)j = rc; /先把Heapj設(shè)成子樹中的較小值if (!(Heappos.Priority>Heapj.Priority) return;

9、/結(jié)點若比子樹還小，就不必動struct patient temp;temp=Heappos;Heappos=Heapj;Heapj=temp; /交換結(jié)點與該子樹/swap(Heap, pos, j);pos = j; /把子樹設(shè)為當(dāng)前結(jié)點，再重復(fù)進行，往下建立最小值堆bool minheap: pop(struct patient& it) /刪除隊列中最優(yōu)先的元素 if (empty() return false; / 堆是空的 struct patient temp;temp=Heap0;Heap0=Heap-n;Heapn=temp; /把堆中的最小元素與最后一個元素交換/s

10、wap(Heap, 0, -n); if (n != 0) siftdown(0); /將第一個元素往后交換it = Heapn; / 返回最小元素 return true;bool minheap:push (const struct patient& val) /向隊列中插入一個元素if(n>=size)return false; /堆已滿int curr=n+;Heapcurr=val;while(curr!=0)&&(Heapcurr.Priority<Heapparent(curr).Priority)struct patient temp; te

11、mp=Heapcurr; Heapcurr=Heapparent(curr); Heapparent(curr)=temp;/swap(Heap,curr,);curr=parent(curr); /按照優(yōu)先值把元素插入堆中return true;bool minheap:top(struct patient& it)if(n=0) return false ;it=Heap0; /返回第一個元素，即最優(yōu)先元素return true;void main()cout<<"請輸入病人的ID號和病情程度，并以-1結(jié)束"<<endl;int a,b;cin>>a;cin>>b;struct patient p30; /定義一個結(jié)構(gòu)體數(shù)組 int i=0;while(a!=-1)&&(b!=-1) /如果a和b都不是-1，繼續(xù)往下pi.ID=a; /對結(jié)構(gòu)體變量的初始化pi.Priority=b;i+; cin>>a;cin>>b; /最后數(shù)組中一共有i個值 minheap dui