1、軟件學院課程設計報告書課程名稱數據結構課程設計 設計題目 地鐵建設問題 專業班級 學 號 姓 名指導教師2015年1月目錄1設計時間4.2設計目的.4.3設計任務44設計內容4.4.1需求分析54.2總體設計54.3詳細設計74.4測試與分析.7.4.4.1 測試1.24.4.2 分析1.34.5附錄145總結與展望20參考文獻22成績評定231設計時間2015年1月19日一2012年1月23日2設計目的通過課程設計，加深對數據結構這一課程所學內容的進一步理解與鞏固，加深對 結構化設計思想的理解，能對系統功能進行分析，并設計合理的模塊化結構。提高程序 開發功能，能運用合理的控制流程編寫清晰高效

2、的程序。訓練C程序調試能力，能將一 個中小型各級組織系統聯調通過。開發一個中小型系統，掌握系統研發全過程。培養分析問題、解決實際問題的能力。3設計任務某城市要在各個轄區之間修建地鐵，由于地鐵建設費用昂貴，因此需要合理安排地 鐵建設線路，使市民可以沿地鐵到達各個轄區，并使總費用最小。4設計內容設計思路：(1) 輸入各個轄區名稱和各轄區間直接距離(地鐵鋪設費用與距離成正比)。如:北京 到大連的直接距離是100公里(2) 根據轄區距離信息，計算出應該在哪些轄區建立地鐵線路。(3) 輸出應該建設的地鐵線路及所需建設總里程 。本程序中用到的所有抽象數據類型的定義；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需求分析輸出應該建設的地鐵線路及所需

4、建設總里程。要求輸出建設地鐵的最短路線,再利用其最短路線上的權值把總的里程計算出來，已達到最省的費用，實現該地鐵的建設。4.2總體設計1首先要了解本題中的要求，要用已經學的鄰接矩陣，根據輸入的轄區信息，建立圖 模型，使用的數據結構是無向圖，采用鄰接矩陣存儲。2. 根據普利姆算法計算最小生成樹。假設WN=(V,E)是一個含有n個頂點的連通 網，TV是WN上最小生成樹中頂點的集合，TE是最小生成樹中邊的集合。顯然，在 算法執行結束時，TV=V，而TE是E的一個子集。在算法開始執行時，TE為空集，TV 中只有一個頂點，因此，按普里姆算法構造最小生成樹的過程為：在所有其一個頂點已 經落在生成樹上，而另

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

6、函數圖14.3詳細設計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("所有的轄區,以0為結束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("轄區之間的路程，以0 0 0為結束標志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("沒有%s這個轄區n",a);return 0;if(p=-1)printf("沒有%s這個轄區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（” 總費用為:%dn",money）;4.4測試與分析441測試鄰接矩陣的建立及存儲： '! F:CYuYnbi nwv?temp,exe丨=|回！ 2S所有的轄區，以0為結束fusEun shenyang dalibeijing 01I轄區之間的路程，加0功結束麻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渚區之間的踣程，我0 0 0為結東標羔 £口sliLLti shenyan g 34fushun daLian 48beij iag 78sheny ang daliazi 56shenyang beij7Sdalian beijinff 33DOO起始地點：shenyangslieiLyarL f ushun 34 2;fu3hLin dalian 43 3 rlienyang b&i jing 總建役暮用為：i

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

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

15、煩重重，書上的算法根本行不通，(因為上面的是C+)后來我反復的來看書也整的一知半解的，通過老師的幫助，我又開始重做，在最 后才做出來。由于開始時對于問題的錯誤分析，浪費了不少時間。其實，由于自己的馬 虎也浪費了不少的時間在不必要的地方，女口：字母的大小寫，自負的定義上，但還好最 后這些都克服了，對我來說對數據結構又有了進一步的了解，繼續學習，豐富自己！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("所有的轄區,以0為結束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("轄區之間的路程，以0 0 0為結束標志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(”沒有%s這個轄區n",a);return 0;if(p=-1)printf("沒有%s這個轄區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(” 總費用為:%dn",money);void mai n()int i;Graph g;char a10;i=creatgraph(&g);if(i) printf("從哪里開始：")；sea nf("%s",a);Mi niSpa nTree_PRIM(g,a);5總結與展望通過這一周的課程設計，加深了我對 數據結構這門課程所學內容的進一步的理解與掌握；同時，通過對地鐵建設問題的開發，使得我將計算機課程所學知識與實際問題 很好地相聯接在了一起

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