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

1、軟件學(xué)院課程設(shè)計(jì)報(bào)告書(shū)課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目 地鐵建設(shè)問(wèn)題 專業(yè)班級(jí) 學(xué) 號(hào) 姓 名指導(dǎo)教師2015年1月目錄1設(shè)計(jì)時(shí)間4.2設(shè)計(jì)目的.4.3設(shè)計(jì)任務(wù)44設(shè)計(jì)內(nèi)容4.4.1需求分析54.2總體設(shè)計(jì)54.3詳細(xì)設(shè)計(jì)74.4測(cè)試與分析.7.4.4.1 測(cè)試1.24.4.2 分析1.34.5附錄145總結(jié)與展望20參考文獻(xiàn)22成績(jī)?cè)u(píng)定231設(shè)計(jì)時(shí)間2015年1月19日一2012年1月23日2設(shè)計(jì)目的通過(guò)課程設(shè)計(jì)，加深對(duì)數(shù)據(jù)結(jié)構(gòu)這一課程所學(xué)內(nèi)容的進(jìn)一步理解與鞏固，加深對(duì) 結(jié)構(gòu)化設(shè)計(jì)思想的理解，能對(duì)系統(tǒng)功能進(jìn)行分析，并設(shè)計(jì)合理的模塊化結(jié)構(gòu)。提高程序 開(kāi)發(fā)功能，能運(yùn)用合理的控制流程編寫(xiě)清晰高效

2、的程序。訓(xùn)練C程序調(diào)試能力，能將一 個(gè)中小型各級(jí)組織系統(tǒng)聯(lián)調(diào)通過(guò)。開(kāi)發(fā)一個(gè)中小型系統(tǒng)，掌握系統(tǒng)研發(fā)全過(guò)程。培養(yǎng)分析問(wèn)題、解決實(shí)際問(wèn)題的能力。3設(shè)計(jì)任務(wù)某城市要在各個(gè)轄區(qū)之間修建地鐵，由于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地 鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總費(fèi)用最小。4設(shè)計(jì)內(nèi)容設(shè)計(jì)思路：(1) 輸入各個(gè)轄區(qū)名稱和各轄區(qū)間直接距離(地鐵鋪設(shè)費(fèi)用與距離成正比)。如:北京 到大連的直接距離是100公里(2) 根據(jù)轄區(qū)距離信息，計(jì)算出應(yīng)該在哪些轄區(qū)建立地鐵線路。(3) 輸出應(yīng)該建設(shè)的地鐵線路及所需建設(shè)總里程 。本程序中用到的所有抽象數(shù)據(jù)類(lèi)型的定義；typedef char In foTy

3、petypedef char VertexTypeMAX_NAMEtypedef structVRType adj;In foType *info; 、ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vex num,arcnum; MGraph;typedef structVertexType adjvex;VRType lowcost;mi nsideMAX_VERTEX_NUM;4.1需求分析輸出應(yīng)該建設(shè)的地鐵線路及所需

4、建設(shè)總里程。要求輸出建設(shè)地鐵的最短路線,再利用其最短路線上的權(quán)值把總的里程計(jì)算出來(lái)，已達(dá)到最省的費(fèi)用，實(shí)現(xiàn)該地鐵的建設(shè)。4.2總體設(shè)計(jì)1首先要了解本題中的要求，要用已經(jīng)學(xué)的鄰接矩陣，根據(jù)輸入的轄區(qū)信息，建立圖 模型，使用的數(shù)據(jù)結(jié)構(gòu)是無(wú)向圖，采用鄰接矩陣存儲(chǔ)。2. 根據(jù)普利姆算法計(jì)算最小生成樹(shù)。假設(shè)WN=(V,E)是一個(gè)含有n個(gè)頂點(diǎn)的連通 網(wǎng)，TV是WN上最小生成樹(shù)中頂點(diǎn)的集合，TE是最小生成樹(shù)中邊的集合。顯然，在 算法執(zhí)行結(jié)束時(shí)，TV=V，而TE是E的一個(gè)子集。在算法開(kāi)始執(zhí)行時(shí)，TE為空集，TV 中只有一個(gè)頂點(diǎn)，因此，按普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程為：在所有其一個(gè)頂點(diǎn)已 經(jīng)落在生成樹(shù)上，而另

5、一個(gè)頂點(diǎn)尚未落在生成樹(shù)上”的邊中取一條權(quán)值為最小的邊，逐條 加在生成樹(shù)上，直至生成樹(shù)中含有n-1條邊為止。3. 了解了這些就可以實(shí)現(xiàn)它的基本操作，然后構(gòu)建一個(gè)鄰接矩陣，輸入各個(gè)轄區(qū)構(gòu)成 一個(gè)無(wú)向連通圖，并把直接距離當(dāng)作權(quán)值來(lái)標(biāo)記，之后，進(jìn)行普里姆的算法，使其生成 最小生成樹(shù)，并帶有權(quán)值了，把這些轄區(qū)輸出，并把最小路徑和最少的費(fèi)用輸出，這樣 就完成了操作。本題出現(xiàn)的調(diào)用函數(shù)是：i=creatgraph(&g);Mi niSpa nTree_PRIM(g,a);k=locatevex(&g,a);mi nimun( struct tree *a,Graph g)；主程序流程圖：”主

6、函數(shù)圖14.3詳細(xì)設(shè)計(jì)typedef structchar VM10;int RMM;int vex num;Graph;int locatevex(Graph *g,char a10)int i;for(i=0;i<g->vex nu m;i+)if(strcmp(a,g->Vi)=0)return i;if(i=g->vex num)return -1;int creatgraph(Graph *g)int i=O,j,m,k,p;char a10,b10;printf("所有的轄區(qū),以0為結(jié)束n");sca nf("%s",

7、g->Vi);while(strcmp("0",g->Vi)!=0)i+;sca nf("%s",g->Vi);g->vex num=i;for(i=0;i<g->vex nu m;i+)for(j=0;j<g->vex nu m;j+)g->Rij=INFINITY;printf("轄區(qū)之間的路程，以0 0 0為結(jié)束標(biāo)志n");sca nf("%s%s%d",a,b,&m);while(strcmp("O",a)!=O | strc

8、mp("O",b)!=O | m!=0)k=locatevex(g,a); p=locatevex(g,b);if(k=-1)printf("沒(méi)有%s這個(gè)轄區(qū)n",a);return 0;if(p=-1)printf("沒(méi)有%s這個(gè)轄區(qū)n",b);return 0;g->Rkp=g->Rpk=m；scan f("%s%s%d",a,b,&m);return 1;struct treeint weizhi;int lowcost;int minimun( struct tree *a,Graph

9、g)int i,k,m=O;for(i=0;i<g.vex nu m;i+)if(m=0 && ai.lowcost!=0)m=1;k=i;if(m=1 && ai.lowcost!=0)if(ai.lowcost<ak .lo wcost)k=i;return k;void Mi niSpa nTree_PRIM(Graph g,char a10)struct tree closedgeM;int i,j,k,m on ey=0;k=locatevex(&g,a);for(i=0;i<g.vex nu m;i+)if(i!=k)clo

10、sedgei.lowcost=g.Rki;closedgei.weizhi=k;closedgeko wcost=0;for(i=1;i<g.vex nu m;i+)k=minimun( closedge,g);mon ey+=closedgek .lo wcost;prin tf("%d:%s %s%dn",i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost);closedgek .lo wcost=0;for(j=0;j<g.vex nu m;j+)if(g.Rkj<closedgej.lowcost)closed

11、gej.weizhi=k;closedgej.lowcost=g.Rk|;printf（” 總費(fèi)用為:%dn",money）;4.4測(cè)試與分析441測(cè)試鄰接矩陣的建立及存儲(chǔ)： '! F:CYuYnbi nwv?temp,exe丨=|回！ 2S所有的轄區(qū)，以0為結(jié)束fusEun shenyang dalibeijing 01I轄區(qū)之間的路程，加0功結(jié)束麻f usliun sKenyang 34fushun dalian 48 fushun bei j ing' 76 shsnyang dalian shenyan? b e i j ing 78 ialian beij

12、ing 89普里姆算法:事 F:CYuYanbrnwwtemp.exe=旦22所有的希山以。為塔束fuEhun shenyang dalian. Beijing 0渚區(qū)之間的踣程，我0 0 0為結(jié)東標(biāo)羔 £口sliLLti shenyan g 34fushun daLian 48beij iag 78sheny ang daliazi 56shenyang beij7Sdalian beijinff 33DOO起始地點(diǎn)：shenyangslieiLyarL f ushun 34 2;fu3hLin dalian 43 3 rlienyang b&i jing 總建役暮用為：i

13、soPress any ieyeon+inuft442分析1. 調(diào)試過(guò)程中遇到的問(wèn)題及其解決方法(1)問(wèn)題:在for循環(huán)語(yǔ)句中，循環(huán)變量使用控制錯(cuò)誤解決方法：在for循環(huán)語(yǔ)句中，應(yīng)該意識(shí)到：循環(huán)變量的執(zhí)行次數(shù)總是比循環(huán)體的執(zhí)行次數(shù)多一次；即最后一次的循環(huán)體執(zhí)行完畢之后，循環(huán)變量又執(zhí)行了一次，但是循環(huán)體卻沒(méi) 有再執(zhí)行了。(2)問(wèn)題：二位數(shù)組在使用的時(shí)候數(shù)組未初始化：導(dǎo)致最后輸出的時(shí)候的鄰接矩陣出現(xiàn) 錯(cuò)誤；解決方法：根據(jù)輸出的窗口從代碼中分析發(fā)現(xiàn)錯(cuò)誤，二維數(shù)組初始化之后，所得到 的鄰接矩陣正確輸出。2. 復(fù)雜度分析分析普里姆算法，假設(shè)網(wǎng)中有n個(gè)定點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語(yǔ)句的頻率為n，第二個(gè)循

14、環(huán)語(yǔ)句的頻率為n-1。其中有兩個(gè)內(nèi)循環(huán)：其一是在closedgev.lowcost中 求最小值，其頻率為n-1;其二是重新選擇具有最小代價(jià)的變量，其頻度為n。由此，普 里姆算法的時(shí)間復(fù)雜度為 0(n*n),與網(wǎng)中的遍數(shù)無(wú)關(guān)。利用PRIM算法生成最小生成樹(shù)時(shí)，求第k次的最短邊共需比較2(n-k)-1次，即時(shí)間復(fù)雜度為O(n-k)。3. 思路探索開(kāi)始分析問(wèn)題時(shí)，我把問(wèn)題想得過(guò)于簡(jiǎn)單，結(jié)合老師講過(guò)得算法和書(shū)上得算法設(shè)計(jì)得，但本題不是這樣的，這個(gè)實(shí)際問(wèn)題中有權(quán)值，而且這還是本題的關(guān)鍵，開(kāi)始的時(shí)候 造成了不少的麻煩，然后經(jīng)過(guò)同學(xué)間得討論，才看出來(lái)我的錯(cuò)誤來(lái)，及時(shí)改了過(guò)來(lái)。還 有在普里姆的操作上，可謂是麻

15、煩重重，書(shū)上的算法根本行不通，(因?yàn)樯厦娴氖荂+)后來(lái)我反復(fù)的來(lái)看書(shū)也整的一知半解的，通過(guò)老師的幫助，我又開(kāi)始重做，在最 后才做出來(lái)。由于開(kāi)始時(shí)對(duì)于問(wèn)題的錯(cuò)誤分析，浪費(fèi)了不少時(shí)間。其實(shí)，由于自己的馬 虎也浪費(fèi)了不少的時(shí)間在不必要的地方，女口：字母的大小寫(xiě)，自負(fù)的定義上，但還好最 后這些都克服了，對(duì)我來(lái)說(shuō)對(duì)數(shù)據(jù)結(jié)構(gòu)又有了進(jìn)一步的了解，繼續(xù)學(xué)習(xí)，豐富自己！4.5附錄#in elude <stdio.h>#i nclude <stdlib.h>#in elude <malloc.h>#i nclude <stri ng.h>#defi ne INFIN

16、ITY10000#defi ne M 20typedef structchar VM10;int RMM;int vex num;Graph;int locatevex(Graph *g,char a10)int i;for(i=0;i<g->vex nu m;i+)if(strcmp(a,g->Vi)=0) return i;if(i=g->vex num)return -1;int creatgraph(Graph *g)int i=O,j,m,k,p;char a10,b10;printf("所有的轄區(qū),以0為結(jié)束n");sca nf(&quo

17、t;%s",g->Vi);while(strcmp("O",g->Vi)!=O)i+;sca nf("%s",g->Vi);g->vex num=i;for(i=0;i<g->vex nu m;i+)for(j=0;jvg->vex nu m;j+)g->Rij=INFINITY;printf("轄區(qū)之間的路程，以0 0 0為結(jié)束標(biāo)志n");sca nf("%s%s%d",a,b,&m);while(strcmp("0",a)!=

18、0 | strcmp("0",b)!=0 | m!=0)k=locatevex(g,a); p=locatevex(g,b);if(k=-1)printf(”沒(méi)有%s這個(gè)轄區(qū)n",a);return 0;if(p=-1)printf("沒(méi)有%s這個(gè)轄區(qū)n",b);return 0;g->Rkp=g->Rpk=m；scan f("%s%s%d",a,b,&m);return 1;struct treeint weizhi;int lowcost;int mi nimun( struct tree *a,Gr

19、aph g)int i,k,m=0;for(i=0;i<g.vex nu m;i+)if(m=O && ai.lowcost!=0)m=1;k=i;if(m=1 && ai.lowcost!=0)if(ai.lowcost<ak.lowcost)k=i;return k;void Mi niSpa nTree_PRIM(Graph g,char a10)struct tree closedgeM;int i,j,k,m on ey=0;k=locatevex(&g,a);for(i=0;i<g.vex nu m;i+)if(i!=k)c

20、losedgei.lowcost=g.Rki;closedgei.weizhi=k;closedgeko wcost=0;for(i=1;i<g.vex nu m;i+)k=minimun( closedge,g);mon ey+=closedgek .lo wcost;prin tf("%d:%s %s%dn",i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost);closedgek .lo wcost=0;for(j=0;j<g.vex nu m;j+)if(g.Rkj<closedgej.lowcost)clos

21、edgej.weizhi=k;closedgej.lowcost=g.Rkj;printf(” 總費(fèi)用為:%dn",money);void mai n()int i;Graph g;char a10;i=creatgraph(&g);if(i) printf("從哪里開(kāi)始：")；sea nf("%s",a);Mi niSpa nTree_PRIM(g,a);5總結(jié)與展望通過(guò)這一周的課程設(shè)計(jì)，加深了我對(duì) 數(shù)據(jù)結(jié)構(gòu)這門(mén)課程所學(xué)內(nèi)容的進(jìn)一步的理解與掌握；同時(shí)，通過(guò)對(duì)地鐵建設(shè)問(wèn)題的開(kāi)發(fā)，使得我將計(jì)算機(jī)課程所學(xué)知識(shí)與實(shí)際問(wèn)題 很好地相聯(lián)接在了一起

22、。初步的了解了我們所學(xué)的課本知識(shí)在實(shí)際中的應(yīng)用。同時(shí)業(yè)培養(yǎng)了我開(kāi)發(fā)一個(gè)中小型程序的能力。在這次對(duì)地鐵建設(shè)問(wèn)題的開(kāi)發(fā)過(guò)程中使我更加體會(huì)到細(xì)心耐心在程序設(shè)計(jì)中的重要性，和同學(xué)的合作交流業(yè)讓自己學(xué)到了更多，發(fā)現(xiàn)自己在實(shí)際問(wèn)題分析中的不足。通過(guò)本次課程設(shè)計(jì)，對(duì)圖的概念有了一個(gè)新的認(rèn)識(shí)，在學(xué)習(xí) 離散數(shù)學(xué)的時(shí)候，總覺(jué)得圖是很抽象的東西，但是在學(xué)習(xí)了 數(shù)據(jù)結(jié)構(gòu)與算法這門(mén)課程之后，我慢慢地體會(huì)到了其中的奧妙，圖能夠在計(jì)算機(jī)中存在，首先要捕捉他有哪些具 體化、數(shù)字化的信息，比如說(shuō)權(quán)值、頂點(diǎn)個(gè)數(shù)等，這也就說(shuō)明了想要把生活中的信息轉(zhuǎn) 化到計(jì)算機(jī)中必須用數(shù)字來(lái)完整的構(gòu)成一個(gè)信息庫(kù)，而圖的存在，又涉及到了頂點(diǎn)之間的聯(lián)系。圖分為有向圖和無(wú)向圖，而無(wú)向圖又是有向圖在權(quán)值雙向相等下的一種特例，如何能在計(jì)算機(jī)中表示一個(gè)雙向權(quán)值不同的圖，這就是一件很巧妙的事情，經(jīng)過(guò)了思考和老師同學(xué)的幫助，我用edgesij=up和edgesji=up就能實(shí)現(xiàn)了一個(gè)雙向圖信息的 存儲(chǔ)。對(duì)整個(gè)程序而言，Dijks