數(shù)據(jù)結(jié)構(gòu)-程序設(shè)計--醫(yī)院選址問題

1、學(xué) 號 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書問題醫(yī)院選址問題起止日期： 2011年 12月 12 日 至 2011 年 12月16日學(xué)生姓名班級成績指導(dǎo)教師(簽字) 電子與信息工程系2011年 12月16日天津城市建設(shè)學(xué)院課程設(shè)計任務(wù)書20112012學(xué)年第1學(xué)期 電子與信息工程 系 軟件工程 專業(yè) 班級課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計題目： 醫(yī)院選址問題 完成期限：自 2011 年 12 月 12 日至 2011 年 12 月 16 日共 1 周設(shè)計依據(jù)、要求及主要內(nèi)容（可另加附頁）：一、設(shè)計目的熟悉各種數(shù)據(jù)結(jié)構(gòu)和運算，會使用數(shù)據(jù)結(jié)構(gòu)的基本操作解決一些實際問題。二、設(shè)計要求 （1）重視課程設(shè)計環(huán)

2、節(jié)，用嚴(yán)謹、科學(xué)和踏實的工作態(tài)度對待課程設(shè)計的每一項任務(wù)；（2）按照課程設(shè)計的題目要求，獨立地完成各項任務(wù)，嚴(yán)禁抄襲；凡發(fā)現(xiàn)抄襲，抄襲者與被抄襲者皆以零分計入本課程設(shè)計成績。凡發(fā)現(xiàn)實驗報告或源程序雷同，涉及的全部人員皆以零分計入本課程設(shè)計成績；（3）學(xué)生在接受設(shè)計任務(wù)后，首先要按設(shè)計任務(wù)書的要求編寫設(shè)計進程表；（4）認真編寫課程設(shè)計報告。三、設(shè)計內(nèi)容7醫(yī)院選址問題1)問題描述n個村莊之間的交通圖可以用有向網(wǎng)圖來表示，圖中邊<vi, vj>上的權(quán)值表示從村莊i到村莊j的道路長度?，F(xiàn)在要從這n個村莊中選擇一個村莊新建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個村莊，才能使所有的村莊離醫(yī)院都比較近？2

3、) 基本要求(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)所示。abcde1253214頂點偏心度a ¥b 6b 8d 5e 7 (a) (b) 圖7 帶權(quán)有向圖及各頂點的偏心度醫(yī)院選址問題的算法用偽代碼描述如下：1對加權(quán)有向圖，調(diào)用Floyd算法，求每對頂點間最短路徑長度的

4、矩陣；2對最短路徑長度矩陣的每列求大值，即得到各頂點的偏心度；3具有最小偏心度的頂點即為所求。四、參考文獻1王紅梅數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社2王紅梅數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實驗指導(dǎo)清華大學(xué)出版社一 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社一、需求分析輸入村莊的個數(shù)、名稱，輸入村莊間路的個數(shù)以及每條路的長度（權(quán)值）；程序根據(jù)權(quán)值以及路來求解得出醫(yī)院的地址。醫(yī)院的地址要求：每個村莊到醫(yī)院的路徑最長的值要最小。二、問題求解在現(xiàn)實中我會以其中為終點以同樣的速度在每個村莊走到終點的時間記錄下最長的時間為該點為終點時的一個值。難后比較那個點為終點時所用的時間值是最小的。 a b c d ea 1 3 5 7

5、b 2 4 6c 3 2 4d 1 3 7e 6 8 5三、總體設(shè)計醫(yī)院選址輸入函數(shù)輸出函數(shù)計算最短路徑求偏心度四、詳細設(shè)計輸入函數(shù)：Hospital<T>:Hospital(T a,int n,int e)vertexNum=n;arcNum=e;int i,j,k,value;for(i=0;i<vertexNum;i+)adjlisti.vertex=ai;adjlisti.firstedge=NULL;for(k=0;k<arcNum;k+)cout<<"輸入邊所依附的兩個頂點的序號"<<endl;cin>>

6、;i>>j;cout<<"輸入邊的權(quán)值"<<endl;cin>>value;ArcNode *s=new ArcNode;s->adjvex=j;s->info=value;s->next=adjlisti.firstedge;adjlisti.firstedge=s;計算最短路徑：/求最短路徑的長度for(i=0;i<countrynum;i+)for(j=0;j<countrynum;j+)for(k=0;k<countrynum;k+)if(valueij>0)if(valuei

7、k+valuekj<valueij&&valueik>0&&valuekj>0)valueij=valueik+valuekj;elseif(valueik>0&&valuekj>0)valueij=valueik+valuekj;求偏心度：/對最短路徑長度矩陣的每列求大值，即得到各頂點的偏心度for(j=0;j<countrynum;j+)for(i=0;i<countrynum;i+)if(sum<valueij&&valueij!=9999)sum=valueij;pj=sum;sum=0;輸出函數(shù)：cout<<"醫(yī)院地址應(yīng)該選在："<<adjlistm.vertex<<endl;五、調(diào)試與測試在測試中權(quán)值的初始話以及最短路徑的計算時出現(xiàn)沒賦值、賦值出錯等問題。if(valueij>0)來確定是否用k的中間值來求解求解最短路徑。六、關(guān)鍵源程序清單和執(zhí)行結(jié)果測試所用