數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)：地鐵建設(shè)問(wèn)題

1、.軟件學(xué)院課程設(shè)計(jì)報(bào)告書課程名稱數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)題目地鐵建設(shè)問(wèn)題專業(yè)班級(jí)學(xué)號(hào)姓名專業(yè)資料.指導(dǎo)教師2014年 1月17日專業(yè)資料.目錄1設(shè)計(jì)時(shí)間 .12設(shè)計(jì)目的 .13 設(shè)計(jì)任務(wù) .14設(shè)計(jì)容 .14.1總體設(shè)計(jì) .14.2需求分析 .24.3詳細(xì)設(shè)計(jì) .34.4測(cè)試與分析 .54.4.1 測(cè)試 .54.4.2 分析 .64.5附錄 .75總結(jié)與展望 .13參考文獻(xiàn) .15成績(jī)?cè)u(píng)定 .16專業(yè)資料.1 設(shè)計(jì)時(shí)間2014 年1月15日2 設(shè)計(jì)目的設(shè)計(jì)各轄區(qū)之間最短地鐵，使修建費(fèi)用最少3 設(shè)計(jì)任務(wù)某城市要在各個(gè)轄區(qū)之間修建地鐵，由于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各

2、個(gè)轄區(qū)，并使總費(fèi)用最小。4 設(shè)計(jì)容(1) 輸入各個(gè)轄區(qū)名稱和各轄區(qū)間直接距離（地鐵鋪設(shè)費(fèi)用與距離成正比） 。(2) 根據(jù)轄區(qū)距離信息，計(jì)算出應(yīng)該在哪些轄區(qū)建立地鐵線路。(3) 輸出應(yīng)該建設(shè)的地鐵線路及所需建設(shè)總里程。4.1 總體設(shè)計(jì)專業(yè)資料.圖 4-1 算法圖4.2 需求分析（1 ）本程序設(shè)計(jì)計(jì)算城市各轄區(qū)間修建地鐵的最短路程。（2 ）運(yùn)行時(shí)，輸入轄區(qū)的名稱，各轄區(qū)之間用空格鍵隔開，以# 輸入結(jié)束。（3 ）輸入各轄區(qū)間距離時(shí)，先輸入兩轄區(qū)名稱，再輸入距離。專業(yè)資料.（4 ）最后計(jì)算最短距離來(lái)得出最少費(fèi)用。4.3 詳細(xì)設(shè)計(jì)采用鄰接矩陣存儲(chǔ)構(gòu)造無(wú)向圖int creatgraph(Graph *g)

3、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+;scanf( "%s" ,g->Vi);g->vexnum=i;for (i=0;i<g->vexnum;i+)for (j=0;j<g->vexnum;j+)g->Rij=INFINITY;printf( "請(qǐng)輸入轄區(qū)和

4、轄區(qū)之間的路程，以# 為結(jié)束標(biāo)志 n" );scanf( "%s%s%d" ,a,b,&m);while (strcmp( "#" ,a)!=0 | strcmp("#" ,b)!=0 | m!=0)專業(yè)資料.k=locatevex(g,a);p=locatevex(g,b);if (k=-1)printf( " 沒有 %s這個(gè)轄區(qū) n" ,a);return0;if (p=-1)printf( " 沒有 %s這個(gè)轄區(qū) n" ,b);return0;g->Rkp=g-&g

5、t;Rpk=m;scanf( "%s%s%d" ,a,b,&m);return1;普利姆算法生成最小樹structtree/ 構(gòu)造最小生成樹 /int weizhi;int lowcost;專業(yè)資料.int minimun(struct tree *a,Graph g)int i,k,m=0;for (i=0;i<g.vexnum;i+)if (m=0 && ai.lowcost!=0)m=1;k=i;if (m=1 && ai.lowcost!=0)if (ai.lowcost<ak.lowcost)k=i;return

6、k;4.4 測(cè)試與分析測(cè)試專業(yè)資料.圖 4-1 正確測(cè)試結(jié)果圖 4-2 錯(cuò)誤測(cè)試結(jié)果分析調(diào)試時(shí)，在輸入數(shù)據(jù)時(shí)，再輸完數(shù)據(jù)后要再次按下空格鍵，再輸入結(jié)束符號(hào)才會(huì)結(jié)束本次輸入進(jìn)入下一個(gè)輸入。且不能輸入與本次輸入無(wú)關(guān)的數(shù)據(jù)或者超出本次輸入限制的數(shù)據(jù)，否則顯示錯(cuò)誤，將重新輸入。專業(yè)資料.4.5附錄#include< stdio .h>#include< stdlib.h>#include< malloc .h >#include< string.h>#defineINFINITY10000#defineM 20typedefstructcharVM10;

7、intRMM;intvexnum;Graph;int locatevex(Graph*g,char a10)int i;for (i= 0;i< g -> vexnum;i + )if (strcmp(a,g -> Vi) = 0)returni;if (i= g -> vexnum)return- 1;專業(yè)資料.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 -> V

8、i);while (strcmp( "#" ,g -> Vi) != 0)i+ ;scanf( "%s" ,g -> Vi);g -> vexnum = i;for (i= 0;i < g -> vexnum;i + )for (j= 0;j< g -> vexnum;j + )g -> Rij = INFINITY;printf( "請(qǐng)輸入轄區(qū)和轄區(qū)之間的路程，以# 為結(jié)束標(biāo)志 n" );scanf( "%s%s%d" ,a,b,& m);while (st

9、rcmp( "#" ,a)!= 0 | strcmp( "#" ,b)!= 0 | m != 0)k= locatevex(g,a);p = locatevex(g,b);if (k=- 1)專業(yè)資料.printf( " 沒有 %s這個(gè)轄區(qū) n" ,a);return0;if (p=- 1)printf( " 沒有 %s這個(gè)轄區(qū) n" ,b);return0;g -> Rkp = g -> Rpk = m;scanf( "%s%s%d" ,a,b, & m);return1;

10、structtree/ 構(gòu)造最小生成樹 /int weizhi;int lowcost;int minimun(struct tree *a,Graph g)int i,k,m = 0;專業(yè)資料.for (i= 0;i < g .vexnum;i + )if (m = 0 &&ai .lowcost != 0)m = 1;k= i;if (m = 1 &&ai .lowcost != 0)if (ai .lowcost < ak .lowcost)k= i;returnk;void MiniSpanTree_PRIM(Graph g,char a10

11、)structtree closedgeM;int i,j,k,money= 0;k= locatevex(& g,a);if (k=- 1)專業(yè)資料.printf( " 沒有 %s這個(gè)轄區(qū)，無(wú)法求解 n" ,a);return0;for (i= 0;i < g .vexnum;i + )if (i!= k)closedgei.lowcost = g .Rki;closedgei.weizhi = k;closedgek.lowcost = 0;for (i= 1;i< g .vexnum;i + )k= minimun(closedge,g);mone

12、y += closedgek.lowcost;printf( "%d:%s%s%dn" ,i,g .Vclosedgek.weizhi ,g .Vk,closedgek.lowcost);closedgek.lowcost = 0;for (j= 0;j< g .vexnum;j + )if (g .Rkj < closedgej.lowcost)專業(yè)資料.closedgej.weizhi = k;closedgej.lowcost = g .Rkj;printf( " 總費(fèi)用為： %dn" ,money);void main()int i,

13、k;Graph g;char a10;printf( "請(qǐng)選擇功能：1 （鐵路建設(shè)）0（退出） n" );scanf( "%d" ,& k);while (k)i= creatgraph(& g);if (i)專業(yè)資料.printf( " 請(qǐng)輸入從哪里開始： ");scanf( "%s" ,a);MiniSpanTree_PRIM(g,a);printf( " 請(qǐng)選擇功能：1 （鐵路建設(shè)）0（退出） n" );scanf( "%d" ,& k);5 總結(jié)與展望本程序，本次編譯涉及數(shù)據(jù)結(jié)構(gòu)最小生成樹以及圖的構(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)用最小生成樹原理，用普利姆算法對(duì)整個(gè)程序變量進(jìn)行編譯，最后進(jìn)入主函數(shù)，就直接調(diào)用函數(shù)進(jìn)行運(yùn)算輸入的數(shù)據(jù)，輸出運(yùn)算結(jié)果。這次程序的編譯讓我對(duì)圖的遍歷理解的更加深入，最小生成樹問(wèn)題不僅可以運(yùn)算本次程序?qū)Φ罔F建造最少費(fèi)用問(wèn)題，更可以運(yùn)用于一系列的最短距離等問(wèn)題，解決甚