1、沈陽航空航天大學數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計報告題目： 應(yīng)用堆實現(xiàn)一個優(yōu)先隊列院（系）：理學院專 業(yè)：信息與計算科學班 級：學 號：姓 名：指導教師：2011年12月沈陽航空航天大學課程設(shè)計報告目 錄1題目介紹和功能要求 . 11.1優(yōu)先隊列(PRIORITY QUEUE) . 11.2 基本功能 . 11.3 功能要求 . 12 系統(tǒng)功能模塊結(jié)構(gòu)圖 . 22.1 系統(tǒng)功能結(jié)構(gòu)框圖 . 22.2 系統(tǒng)主要模塊的功能說明 . 23 使用的數(shù)據(jù)結(jié)構(gòu)的描述 . 33.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計 . 33.2 數(shù)據(jù)結(jié)構(gòu)用法說明 . 34 函數(shù)的描述 . 55 算法流程圖 . 75.1 HEAPADJUST函數(shù) . 75.

2、2 CREATEHEAP 函數(shù) . 85.3 PRINT 函數(shù) . 85.3 INSERT函數(shù) . 95.4 MINIMUN函數(shù) . 95.5 EXTRACT_MIN 函數(shù) . 106 測試/運行的結(jié)果 . 11參考文獻 . 15附 錄 . 17I沈陽航空航天大學課程設(shè)計報告1題目介紹和功能要求1.1優(yōu)先隊列(priority queue) 是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素，它可以用于很多場合的數(shù)據(jù)結(jié)構(gòu)。1.2 基本功能1 Insert(S,x)將元素x插入到集合S（本題為數(shù)組A），并且把A調(diào)整為小頭椎。 2 Minimum(S0返回S中的最小元素，并

3、且將A調(diào)整為小頂椎。3 Extract_Min(S)刪除S中的最小關(guān)鍵字1.3 功能要求可設(shè)計要求以堆作為輔助結(jié)構(gòu)實現(xiàn)一個優(yōu)先隊列。要將堆結(jié)構(gòu)嵌入到隊列結(jié)構(gòu)中，以作為其數(shù)據(jù)組織的以部分。此處由于要用堆實現(xiàn)隊列，所以堆結(jié)構(gòu)的儲存表示要求用數(shù)組。要求：1. 設(shè)計并實現(xiàn)優(yōu)先隊列的數(shù)據(jù)結(jié)構(gòu)，包括其上的基本操作；2. 以堆結(jié)構(gòu)為輔助結(jié)構(gòu)實現(xiàn)優(yōu)先隊列的儲存表示并實現(xiàn)其上的基本操作；3. 實現(xiàn)優(yōu)先隊列的出隊、入隊操作；4. 給出動態(tài)演示過程（選作）；1沈陽航空航天大學課程設(shè)計報告2 系統(tǒng)功能模塊結(jié)構(gòu)圖2.1 系統(tǒng)功能結(jié)構(gòu)框圖圖2.1系統(tǒng)的模塊圖2.2 系統(tǒng)主要模塊的功能說明1.插入功能模塊：Insert(A

4、,x) 將元素x插入到數(shù)組A，并且把A調(diào)整為小頭椎。 2. 刪除功能模塊：Extract_Min(A)，刪除數(shù)組A中的最小關(guān)鍵字，并且將A調(diào)整為小頂椎。 3. 輸出功能模塊：Print(A)把集合S中的元素按小頭堆輸出。 4. 創(chuàng)建隊列功能模塊：CreateHeap(A) 對于數(shù)組A中元素創(chuàng)建小頭椎。 5. 返回最小優(yōu)先級功能模塊：Minimun(A) 返回集合A中優(yōu)先級最小的堆2沈陽航空航天大學課程設(shè)計報告3 使用的數(shù)據(jù)結(jié)構(gòu)的描述3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計優(yōu)先隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素，按照題意可知，建立了小頂堆，元素越小優(yōu)先級越高。堆的定義：若

5、含n個元素的序列 k1,k2 ,kn ，滿足下列關(guān)系時稱作"小頂堆" 或"大頂" 。"堆頂" 元素為序列中的"最小值"或"最大值"。ki<=k2i (i=1,2,.n/2)ki<=k2i+1堆舉例：12,36,24,85,47,30,53,91圖3.1 小頂堆可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中 n個元素的最小值或最大值 結(jié)合題目要求3.2 數(shù)據(jù)結(jié)構(gòu)用法說明從無序序列的第n/2個元素（即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進

6、行反復(fù)篩選3沈陽航空航天大學課程設(shè)計報告例如：無序序列建成一個小頂堆49，38，65，97，76，13，27，49圖3.2 小頂堆調(diào)整a 圖3.3 小頂堆調(diào)整b圖3.4 小頂堆調(diào)整c 圖3.5 小頂堆調(diào)整d圖3.6 小頂堆調(diào)整e4沈陽航空航天大學課程設(shè)計報告4 函數(shù)的描述主要函數(shù)設(shè)計：（1） void Print(int *a,int t)作用：輸出優(yōu)先隊列參數(shù)表：a 為存儲優(yōu)先隊列的數(shù)組。t 為參數(shù)，為0是直接輸出優(yōu)先隊列；否則對要變換元素進行標記。如數(shù)字6：為與3和7比較。圖4.1例圖（2）void CreateHeap(int *a)作用：對于數(shù)組a進行調(diào)整為有小頂堆。參數(shù)表：a 為存儲

7、優(yōu)先隊列的數(shù)組。算法思想：從無序序列的第n/2個元素（即此無序序列對應(yīng)的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進行反復(fù)篩選，用遞歸方法調(diào)用HeapAdjust（）；（3）HeapAdjust(int *a,int s,int m)作用：as+1.m為小頂堆調(diào)整后as.m為小頂堆。參數(shù)表：a 為存儲優(yōu)先隊列的數(shù)組。s 為要調(diào)整的起始位置。m 為要調(diào)整的末端位置。算法思想：通過 i個要滿足且（i=s，2s，2s+1,3sm/2）ki<=k2i且ki<=k2i+1(i=s,.m/2)（4）void Insert(int *a,int x)作用：將x插入到優(yōu)先隊列a中并把a調(diào)

8、整為小頂堆。參數(shù)表：x 要插入的元素a 為存儲優(yōu)先隊列的數(shù)組。5沈陽航空航天大學課程設(shè)計報告算法思想:先將x插入到a的最后位置，然后判斷a(k) a(k/2) 是否成立，成立則a(k)與a(k/2) 互換，否則退出函數(shù)。（5）int Minimun(int *a)作用：返回優(yōu)先隊列中優(yōu)先級最高的元素（這為最小元素）。參數(shù)表：a 為存儲優(yōu)先隊列的數(shù)組。算法思想：由于用的是小頂堆，所以 直接返回堆頂就行了。(6) int Extract_Min(int *a)作用：從優(yōu)先隊列中刪除優(yōu)先級最高的元素（這為最小元素），并重新調(diào)整為小頂堆。參數(shù)表：a 為存儲優(yōu) 先隊列的 數(shù)組。算法思想：由于用的是小頂堆

9、，所以直接返回堆頂，并刪除堆頂，然后將堆的最后一個元素放到堆頂，在調(diào)用 HeapAdjust(int*a,int 1,int m)就行了。6沈陽航空航天大學課程設(shè)計報告 5 算法流程圖5.1 HeapAdjust函數(shù)圖5.1 HeapAdjust流程圖7沈陽航空航天大學課程設(shè)計報告5.2 CreateHeap 函數(shù)圖5.2 CreateHeap 的流程圖5.3 Print 函數(shù)圖5.3 Print 函數(shù)的流程圖8沈陽航空航天大學課程設(shè)計報告5.3 Insert函數(shù)圖5.4 Insert函數(shù)流程圖5.4 Minimun函數(shù)圖 5.5 Minimun函數(shù)流程圖9沈陽航空航天大學課程設(shè)計報告5.5

10、Extract_Min 函數(shù)圖 5.6 Extract_Min 函數(shù)流程圖10沈陽航空航天大學課程設(shè)計報告 6 測試/運行的結(jié)果例如：輸入49，38，65，97，76，13，27，49如下：圖 6.1 輸入格式圖初始堆為：圖 6.2 初始堆調(diào)整小頂堆過程為：11沈陽航空航天大學課程設(shè)計報告圖6.3 調(diào)整圖調(diào)整后的小頂堆為：圖 6.4 調(diào)整后小頂堆圖主函數(shù)功能操作如下：圖 6.5 主函數(shù)功能操作圖12沈陽航空航天大學課程設(shè)計報告插入時選擇功能1其輸入如下：圖 6.6插入操作圖插入過程如下：圖 6.7 插入過程圖返回最小值，選擇功能4，結(jié)果如下：圖 6.8返回最小值13沈陽航空航天大學課程設(shè)計報告

11、刪除時選擇功能2其過程如下：刪除后結(jié)果如下：圖 6.9刪除過程 圖 6.10刪除后結(jié)果14沈陽航空航天大學課程設(shè)計報告參考文獻1 譚浩強著. C程序設(shè)計（ 第三版）. 北京: 清華大學出版社,20052 數(shù)據(jù)結(jié)構(gòu): C語言版 /嚴蔚敏,吳偉明編著.北京:清華大學出版社,20073 汪杰 . 數(shù)據(jù)結(jié)構(gòu)經(jīng)典算法實現(xiàn)M. 北京：人民郵電出版社，20044 李春葆 . 數(shù)據(jù)結(jié)構(gòu)解析（C語言版）M. 北京：清華大學出版社，200215沈陽航空航天大學課程設(shè)計報告16沈陽航空航天大學課程設(shè)計報告附 錄#include "stdafx.h"#include "stdio.h&q

12、uot;#include <math.h>#include<windows.h>#include<string.h>#include "stdlib.h "#include<time.h>#define MAX 100#define INF 0.00001void Print(int *a,int t)int i,j,k,n,m; m=int(log(a0)/log(2)+INF)+1; n=int(pow(2,m)-1; for(i=1;i<=m;i+) for(k=int(pow(2,(i-1);k<=int(

13、pow(2,i)-1;k+) if(k=a0+1) break; for(j=1;j<=n/2;j+) printf(" "); if(k=t) printf("<%d>",ak); else printf("%d",ak); for(j=1;j<=n/2+1;j+) printf(" ");17沈陽航空航天大學課程設(shè)計報告void HeapAdjust(int *a,int s,int m) /as+1.m為小頂堆，調(diào)整后as.m為小頂堆 int j,ac=as; for(j=2*s;j&

14、lt;=m;j*=2) getchar(); printf("n"); n=n/2; Print(a,j/2); if(j<m && aj>aj+1) j+; if(ac<aj) break;as=aj;void CreateHeap(int *a)int i,n; s=j; as=ac; printf("請輸入要創(chuàng)建的個數(shù) ");scanf("%d",&n); a0=n;printf("請輸入的數(shù)字n");for(i=1;i<=n;i+) scanf("%

15、d",&ai); printf("當前堆為：n");18沈陽航空航天大學課程設(shè)計報告Print(a,0);getchar();printf("現(xiàn)在對其進行調(diào)整：n");for(i=a0/2;i>0;i-)HeapAdjust(a,i,a0);getchar();printf("調(diào)整后的為：n");Print(a,0);getchar();void Insert(int *a,int x)int i,n=a0;an+1=x;a0+;getchar();Print(a,a0);for(i=a0;i>1;)if

16、(ai<ai/2)getchar();ai=ai/2;i=i/2;ai=x;Print(a,i);else break;19沈陽航空航天大學課程設(shè)計報告int Minimun(int *a)int Extract_Min(int *a)printf("原來的是:n"); Print(a,0); Sleep(2000); int n,ma=a1; n=a0; a1=an; a0-; return a1;HeapAdjust(a,1,n-1);void menu()system( "cls "); printf("ttt*n");

17、printf("ttt* 請選擇功能 *n"); printf("ttt*1:插入(入隊)： *n"); printf("ttt*2:刪除(出隊)： *n"); printf("ttt*3:輸出： *n"); printf("ttt*4:返回最小值： *n");20getchar(); printf("刪除后的是:n"); Print(a,0); return ma;沈陽航空航天大學課程設(shè)計報告printf("ttt*0:退出： *n"); printf("ttt*n");void main()int x,aMAX+1,gong;a0=0;CreateHeap(a);menu();scanf("%d",&gong);while(gong)switch(gong)case 1:printf("請輸入插入數(shù)值n");scanf(&quo