醫(yī)院選址問題.doc

課程設(shè)計任務(wù)書20112012學(xué)年第1學(xué)期電子與信息工程 系 計算機科學(xué)與技術(shù) 專業(yè) 班級課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計題目： 醫(yī)院選址問題 完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周一、 設(shè)計目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實際問題。二、 設(shè)計要求 1. 重視課程設(shè)計環(huán)節(jié)，用嚴謹、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；2. 按照課程設(shè)計的題目要求，獨立地完成各項任務(wù)，嚴禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實驗報告或源程序雷同，涉及的全部人員皆以零分計入本課程設(shè)計成績；3. 學(xué)生在接受設(shè)計任務(wù)后，首先要按設(shè)計任務(wù)書的要求編寫設(shè)計進程表；4. 認真編寫課程設(shè)計報告。三、 設(shè)計內(nèi)容醫(yī)院選址問題1. 問題描述n個村莊之間的交通圖可以用有向網(wǎng)圖來表示，圖中邊上的權(quán)值表示從村莊i到村莊j的道路長度。現(xiàn)在要從這n個村莊中選擇一個村莊新建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使所有的村莊離醫(yī)院都比較近？2. 基本要求(1) 建立模型，設(shè)計存儲結(jié)構(gòu)；(2) 設(shè)計算法完成問題求解；(3) 分析算法的時間復(fù)雜度。3. 設(shè)計思想醫(yī)院選址問題實際是求有向圖中心點的問題。首先定義頂點的偏心度。設(shè)圖G=（V，E），對任一頂點k，稱E(k)=maxd(i, k)（iV）為頂點k的偏心度。顯然，偏心度最小的頂點即為圖G的中心點。如圖7(a)所示是一個帶權(quán)有向圖，其各頂點的偏心度如圖(b)所示。123451253214頂點偏心度a b 6b 8d 5e 7 (a) (b) 圖7 帶權(quán)有向圖及各頂點的偏心度醫(yī)院選址問題的算法用偽代碼描述如下：1對加權(quán)有向圖，調(diào)用Floyd算法，求每對頂點間最短路徑長度的矩陣；2對最短路徑長度矩陣的每列求大值，即得到各頂點的偏心度；3具有最小偏心度的頂點即為所求?！舅伎碱}】圖的存儲結(jié)構(gòu)和算法的設(shè)計需要一定的靈活性和技巧。從醫(yī)院選址問題的求解過程，你有什么感想？ 答：通過將圖存儲的方法很多，這兒用數(shù)組，簡單化數(shù)據(jù)，可以更好的編號和運行程序。四、 參考文獻1王紅梅數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社2王紅梅數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實驗指導(dǎo)清華大學(xué)出版社3嚴蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社2目錄一、需求分析1二、概要設(shè)計1三、詳細設(shè)計2四、調(diào)試分析4五、核心源程序清單和執(zhí)行結(jié)果6六、感想與體會10一、 需求分析1 程序的功能；從n個村莊中選擇一個村莊新建一所醫(yī)院，使這所醫(yī)院離所有村莊都比較近。2 輸入輸出的要求；輸入：每個村莊的起點、終點和距離。輸出：離所有村莊都比較近的醫(yī)院位置3 測試數(shù)據(jù)。 123451253214頂點偏心度a b 6b 8d 5e 7 (a) (b) 圖1 帶權(quán)有向圖及各頂點的偏心度上圖為測試數(shù)據(jù)二、 概要設(shè)計該程序使用數(shù)組存儲矩陣，即順序表存儲結(jié)構(gòu)。開始A：輸入村莊數(shù)B：輸入道路數(shù)C：create函數(shù)得到原始鄰接矩陣Floyd算法將每一對頂點的路徑編程最短路徑minp函數(shù)找出最小偏心度的村莊程序結(jié)束三、 詳細設(shè)計/Floyd算法將每一對頂點的路徑編程最短路徑void Floyd(int distM,int m)int i,j;for(int k=0;km;k+) for(i=0;im;i+)for(j=0;jm;j+)if(distik+distkjdistij)distij=distik+distkj;coutendl每對頂點路徑最短的鄰接矩陣為：endlendl;cout=endl;for(i=0;im;i+)for(j=0;jm;j+)if(distij!=100)cout ;coutdistij ;coutendl;cout=endl;/Minp函數(shù)求最小偏心度的村莊void minp(int cM,int m) int inmaxM;int i,j;for(i=0;im;i+)inmaxi=0;for(j=0;jm;j+) int t=0;for(i=0;im;i+)if(tcij)t=cij;inmaxj=t;coutendl村莊的偏心度依次為：;for(i=0;im;i+) coutinmaxi ;coutendl;int max=inmax0;int l;for(i=0;im;i+) /比較inmax數(shù)組中元素的大小，并輸出最小元素下標+1,即為建醫(yī)院的地點if(inmaximax)max=inmaxi;l=i;cout所以醫(yī)院應(yīng)該建在村莊l+1中endl;void create(int n,int l,int cM) coutendl =endl;int i,j,weight;for(i=0;in;i+)for(j=0;jn;j+) cij=Maxint;cii=0;for(int k=0;kl;k+)cout請輸入第k+1ijweight; if(in|in|jMaxint|weight0)cout輸入非法，請重輸該邊的所有值endl;goto C;ci-1j-1=weight;cout =endlendl;cout整理得到原始鄰接矩陣為：endl;cout=endl;for(i=0;in;i+)for(j=0;jn;j+)if(cij!=100)cout ;coutcij ;coutendl;cout=endlendl;四、 調(diào)試分析通過題目所給例子進行測試和分析，最終得到結(jié)構(gòu)如下截圖：五、 核心源程序清單和執(zhí)行結(jié)果09710207鄭朋（數(shù)據(jù)結(jié)構(gòu)）.cpp/ 09710207鄭朋（數(shù)據(jù)結(jié)構(gòu)）.cpp : 定義控制臺應(yīng)用程序的入口點。/#include stdafx.hint _tmain(int argc, _TCHAR* argv)return 0;#includeusing namespace std;const int Maxint=100;const int M=50; /定義村莊個數(shù)的最大值void Floyd(int distM,int m)/Floyd算法將每一對頂點的路徑編程最短路徑int i,j;for(int k=0;km;k+) for(i=0;im;i+)for(j=0;jm;j+)if(distik+distkjdistij)distij=distik+distkj;coutendl每對頂點路徑最短的鄰接矩陣為：endlendl;cout=endl;for(i=0;im;i+)for(j=0;jm;j+)if(distij!=100)cout ;coutdistij ;coutendl;cout=endl;void minp(int cM,int m) /該函數(shù)用于找出最小偏心度的村莊int inmaxM;int i,j;for(i=0;im;i+)inmaxi=0;for(j=0;jm;j+) /inmax數(shù)組用來保存最短路徑,即鄰接矩陣每一列的最大值，也就是每個村莊的偏心度int t=0;for(i=0;im;i+)if(tcij)t=cij;inmaxj=t;coutendl村莊的偏心度依次為：;for(i=0;im;i+) coutinmaxi ;coutendl;int max=inmax0;int l;for(i=0;im;i+) /比較inmax數(shù)組中元素的大小，并輸出最小元素下標+1,即為建醫(yī)院的地點if(inmaximax)max=inmaxi;l=i;cout所以醫(yī)院應(yīng)該建在村莊l+1中endl;void create(int n,int l,int cM) coutendl =endl;int i,j,weight;for(i=0;in;i+)for(j=0;jn;j+) cij=Maxint;cii=0;for(int k=0;kl;k+)cout請輸入第k+1ijweight; if(in|in|jMaxint|weight0)cout輸入非法，請重輸該邊的所有值endl;goto C;ci-1j-1=weight;cout =endlendl;cout整理得到原始鄰接矩陣為：endl;cout=endl;for(i=0;in;i+)for(j=0;jn;j+)if(cij!=100)cout ;coutcij ;coutendl;cout=endlendl;void main()coutendl;cout 醫(yī)院選址問題，請按以下步驟操作endl;cout =endlendl;cout將所有村莊和道路分別從編號（即、.）endl;int arcMM; /用于存儲圖的鄰接矩陣int m;A: coutm;if(mM|m0)cout對不起，輸入的數(shù)值不合法，請重新輸入！endlendl;goto A;int e;B: coute;if(e(m*(m-1)|e0)cout對不起，輸入的數(shù)值不合法！endlendl;goto B;create(m,e,arc);Floyd(arc,m);minp(arc,m); cout=運行結(jié)束=endl;cout endl;cout / endl;cout / endl;cout / 祝老師同學(xué)們：endl;cout .-. endl;cout . a_a . 春節(jié)愉快合家歡樂！endl;cout =(_)= endl;cout . ._I_. . 心想事成紅包拿來！endl;cout _/.-._ endl;cout #(_)# endl;六、 感想與體會編程是一件很枯燥的事情，但也