地鐵建設(shè)問(wèn)題

1、軟件學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目 題目建設(shè)問(wèn)題專業(yè)班級(jí) 軟件11-02學(xué)號(hào)姓名 指導(dǎo)教師唐曉亮2013年1月20日目錄 TOC o 1-5 h z HYPERLINK l bookmark14 o Current Document 設(shè)計(jì)時(shí)間2 HYPERLINK l bookmark17 o Current Document 設(shè)計(jì)目的2 HYPERLINK l bookmark20 o Current Document 設(shè)計(jì)任務(wù)2 HYPERLINK l bookmark23 o Current Document 設(shè)計(jì)內(nèi)容2 HYPERLINK l bookmark28 o Cu

2、rrent Document 4.1需求分析24.2總體設(shè)計(jì)24.2.1主函數(shù)流程圖24.3詳細(xì)設(shè)計(jì)34.3.2函數(shù)調(diào)用關(guān)系34.3.3主要模塊的算法描述34.4測(cè)試與分析3測(cè)試3分析44.5附錄4 HYPERLINK l bookmark38 o Current Document 總結(jié)與展望71設(shè)計(jì)時(shí)間2012年1月5日2設(shè)計(jì)目的設(shè)計(jì)各轄區(qū)之間最短地鐵，使修建費(fèi)用最少3設(shè)計(jì)任務(wù)某城市要在各個(gè)轄區(qū)之間修建地鐵，由于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地鐵 建設(shè)線路，使市民可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總費(fèi)用最小。4設(shè)計(jì)內(nèi)容輸入各個(gè)轄區(qū)名稱和各轄區(qū)間直接距離(地鐵鋪設(shè)費(fèi)用與距離成正比)。根據(jù)轄區(qū)距離

3、信息，計(jì)算出應(yīng)該在哪些轄區(qū)建立地鐵線路。輸出應(yīng)該建設(shè)的地鐵線路及所需建設(shè)總里程。結(jié)束4.2需求分析（1）本程序設(shè)計(jì)計(jì)算城市內(nèi)各轄區(qū)間修建地鐵的最短路程。（2）運(yùn)行時(shí)，輸入轄區(qū)的名稱，各轄區(qū)之間用空格鍵隔開(kāi)，以#輸入結(jié)束。（3）輸入各轄區(qū)間距離時(shí)，先輸入兩轄區(qū)名稱，再輸入距離。（4）最后計(jì)算最短距離來(lái)得出最少費(fèi)用。4.3詳細(xì)設(shè)計(jì)P163采用鄰接矩陣存儲(chǔ)構(gòu)造無(wú)向圖P175普利姆算法生成最小樹(shù)4.4測(cè)試與分析4.4.1測(cè)試廣I D:xi rij i a n we nj ianj i aCu Ya nb i nwwte mp ,exed 情選擇功能：1（鐵路建設(shè)）。（退出1請(qǐng)輸入所有的轄區(qū)，以#為輸入

4、結(jié)束標(biāo)志A B C D #請(qǐng)輸入轄區(qū)和轄區(qū)之間的路程，以櫥為結(jié)束標(biāo)志A B 14B C 16C D 23A C 35A D 18B D 25C D 22# # 0請(qǐng)輸入從哪里開(kāi)始：A1:A B 142：B C 163：A D 18總費(fèi)用為：4g信選擇功蠢：1（鐵路建設(shè)）。（退出4.4.2分析調(diào)試時(shí)，在輸入數(shù)據(jù)時(shí)，再輸完數(shù)據(jù)后要再次按下空格鍵，再輸入結(jié)束符號(hào)才會(huì)結(jié)束 本次輸入進(jìn)入下一個(gè)輸入。且不能輸入與本次輸入無(wú)關(guān)的數(shù)據(jù)或者超出本次輸入限制的數(shù)據(jù)，否則顯示錯(cuò)誤，將 重新輸入。4.5附錄#include #include #include #include #define INFINITY 100

5、00#define M 20typedef structchar VM10;int RMM;int vexnum;Graph;int locatevex(Graph *g,char a10)int i;for(i=0;ivexnum;i+)if(strcmp(a,g-Vi)=0)return i;if(i=g-vexnum)return -1;int creatgraph(Graph *g)int i=0,j,m,k,p;char a10,b10;printf(-請(qǐng)輸入所有的轄區(qū)，以#為輸入結(jié)束標(biāo)志n);scanf(%s”,g-Vi);while(strcmp(#”,g-Vi) !=0)i+;

6、scanf(%s,g-Vi);g-vexnum=i;for(i=0;ivexnum;i+)for(j=0;j vexnum;j +)g-Rij=INFINITY;printf(請(qǐng)輸入轄區(qū)和轄區(qū)之間的路程，以#為結(jié)束標(biāo)志n);scanf(%s%s%d,a,b,&m);while(strcmp(#,a)!=0 | strcmp(#,b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);if(k=-1)printf(沒(méi)有、這個(gè)轄區(qū)n,a);return 0;if(p=-1)printf(沒(méi)有、這個(gè)轄區(qū)n,b);return 0;g-Rkp=g-Rpk=m;

7、scanf(%s%s%d”,a,b,&m);return 1;struct tree構(gòu)造最小生成樹(shù)int weizhi;int lowcost;int minimun(struct tree *a,Graph g)int i,k,m=0;for(i=0;ig.vexnum;i+)if(m=0 & ai.lowcost!=0)m=1;k=i;if(m=1 & ai.lowcost!=0)if(ai .lowcostak .lowcost) k=i;return k;void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM;int

8、i,j,m,k,money=0;k=locatevex(&g,a);if(k=-1)printf(沒(méi)有、這個(gè)轄區(qū)，無(wú)法求解n,a);return 0;for(i=0;ig.vexnum;i+)if(i!=k)closedgei.lowcost=g.Rki;closedgei.weizhi=k;closedgek.lowcost=0;for(i=1;ig.vexnum;i+)k=minimun(closedge,g);money+=closedgek .lowcost;printf(%d:%s %s %dn”,i,g.V closedgek.weizhi ,g.Vk,closedgek.lowc

9、ost);closedgek.lowcost=0;for(j=0;jg.vexnum;j+)if(g.Rkjclosedgej.lowcost)closedgej.weizhi=k;closedgej.lowcost=g.Rkj;printf(總費(fèi)用為：dn”,money); void main() int i,j,k;Graph g;char a10;printf(請(qǐng)選擇功能：1 (鐵路建設(shè))0 (退出)n);scanf(%d,&k);while(k)i=creatgraph(&g);if(i)printf(-請(qǐng)輸入從哪里開(kāi)始：，scanf(%s,a);MiniSpanTree_PRIM(g

10、,a);printf(請(qǐng)選擇功能：1 (鐵路建設(shè))0 (退出)n);scanf(%d,&k);5總結(jié)與展望本程序，本次編譯涉及數(shù)據(jù)結(jié)構(gòu)最小生成樹(shù)以及圖的構(gòu)造等編譯。先要構(gòu)造結(jié)構(gòu)體， 在定義時(shí)應(yīng)要注意盡量將賦值空間增大，以防止調(diào)試時(shí)輸入數(shù)據(jù)超出運(yùn)算范圍。再進(jìn)行函 數(shù)的編譯調(diào)用，構(gòu)造無(wú)向圖用鄰接矩陣進(jìn)行存儲(chǔ)，這些編譯代碼，書上都有介紹，但不可 盡抄，書上的只是一個(gè)模板，根據(jù)程序設(shè)計(jì)任務(wù)將變量進(jìn)行修改，構(gòu)造圖之后，運(yùn)用最小 生成樹(shù)原理，用普利姆算法對(duì)整個(gè)程序變量進(jìn)行編譯，最后進(jìn)入主函數(shù)，就直接調(diào)用函數(shù) 進(jìn)行運(yùn)算輸入的數(shù)據(jù)，輸出運(yùn)算結(jié)果。這次程序的編譯讓我對(duì)圖的遍歷理解的更加深入，最小生成樹(shù)問(wèn)題不僅可以運(yùn)算本次 程序?qū)Φ罔F建造最少費(fèi)用問(wèn)題，更可以運(yùn)用于一系列的最短距離等問(wèn)題，解決甚多復(fù)雜問(wèn) 題！極其具有實(shí)用性！參考文獻(xiàn)1屈輝立，陳可明