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

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

3、) 基本要求(1) 建立模型，設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)；(2) 設(shè)計(jì)算法完成問題求解；(3) 分析算法的時(shí)間復(fù)雜度。3) 設(shè)計(jì)思想醫(yī)院選址問題實(shí)際是求有向圖中心點(diǎn)的問題。首先定義頂點(diǎn)的偏心度。設(shè)圖G=（V，E），對(duì)任一頂點(diǎn)k，稱E(k)=maxd(i, k)（iV）為頂點(diǎn)k的偏心度。顯然，偏心度最小的頂點(diǎn)即為圖G的中心點(diǎn)。如圖7(a)所示是一個(gè)帶權(quán)有向圖，其各頂點(diǎn)的偏心度如圖(b)所示。abcde1253214頂點(diǎn)偏心度a ¥b 6b 8d 5e 7 (a) (b) 圖7 帶權(quán)有向圖及各頂點(diǎn)的偏心度醫(yī)院選址問題的算法用偽代碼描述如下：1對(duì)加權(quán)有向圖，調(diào)用Floyd算法，求每對(duì)頂點(diǎn)間最短路徑長(zhǎng)度的

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

5、b 2 4 6c 3 2 4d 1 3 7e 6 8 5三、總體設(shè)計(jì)醫(yī)院選址輸入函數(shù)輸出函數(shù)計(jì)算最短路徑求偏心度四、詳細(xì)設(shè)計(jì)輸入函數(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<<"輸入邊所依附的兩個(gè)頂點(diǎn)的序號(hào)"<<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;計(jì)算最短路徑：/求最短路徑的長(zhǎng)度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;求偏心度：/對(duì)最短路徑長(zhǎng)度矩陣的每列求大值，即得到各頂點(diǎn)的偏心度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)試與測(cè)試在測(cè)試中權(quán)值的初始話以及最短路徑的計(jì)算時(shí)出現(xiàn)沒賦值、賦值出錯(cuò)等問題。if(valueij>0)來確定是否用k的中間值來求解求解最短路徑。六、關(guān)鍵源程序清單和執(zhí)行結(jié)果測(cè)試所用