數據結構課程設計—地鐵建設問題

1、軟 件 學 院課程設計報告書課程名稱 數據結構課程設計 設計題目 地鐵建設問題 專業(yè)班級 學 號 姓 名 指導教師 2015 年 1 月目錄1 設計時間32 設計目的33設計任務34 設計內容34.1需求分析34.2總體設計44.3詳細設計44.4測試與分析5測試5分析64.5 附錄75 總結與展望11參考文獻12成績評定121 設計時間 2015年1月19日2012年1月23日2 設計目的通過課程設計，加深對數據結構這一課程所學內容的進一步理解與鞏固，加深對結構化設計思想的理解，能對系統(tǒng)功能進行分析，并設計合理的模塊化結構。提高程序開發(fā)功能，能運用合理的控制流程編寫清晰高效的程序。訓練C程序

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

3、 VertexTypeMAX_NAMEtypedef struct VRType adj; InfoType *info; 、 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph;typedef struct VertexType adjvex; VRType lowcost;minsideMAX_VERTEX_NUM;4.1需求分析 輸出應該建設的地鐵線路及所需建設總里程。要求

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

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

6、界面 普里姆的構建及使用鄰接矩陣的建立及存儲MiniSpanTree_PRIMcreatgraphminimunlocatevex主函數結束 圖14.3詳細設計typedef struct char VM10; int RMM; int vexnum; Graph; int locatevex(Graph *g,char a10) int i; for(i=0;i<g->vexnum;i+) if(strcmp(a,g->Vi)=0) return i; if(i=g->vexnum) return -1; int creatgraph(Graph *g) int i=

7、0,j,m,k,p; char a10,b10; printf("所有的轄區(qū)，以0為結束n"); scanf("%s",g->Vi); while(strcmp("0",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ū)之間的路程，以0 0 0為結束標志n&qu

8、ot;); scanf("%s%s%d",a,b,&m); while(strcmp("0",a)!=0 | strcmp("0",b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);if(k=-1) printf("沒有%s這個轄區(qū)n",a); return 0; if(p=-1) printf("沒有%s這個轄區(qū)n",b); return 0;g->Rkp=g->Rpk=m;scanf("%s%s%d",a

9、,b,&m); return 1;struct tree int weizhi; int lowcost; ;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 k;void MiniSpanTree_PRIM(Graph g,char a10) struct

10、tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a); 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); money+=closedgek.lowcost; printf("%d:%s %s %dn",i,g.Vclosedgek.weizhi,g.Vk,closedg

11、ek.lowcost); closedgek.lowcost=0; for(j=0;j<g.vexnum;j+) if(g.Rkj<closedgej.lowcost) closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf("總費用為：%dn",money);4.4測試與分析4.4.1測試鄰接矩陣的建立及存儲：圖2普里姆算法： 圖34.4.2分析1.調試過程中遇到的問題及其解決方法（1）問題:在 for 循環(huán)語句中,循環(huán)變量使用控制錯誤 解決方法: 在 for 循環(huán)語句中,應該意識到:循環(huán)變量的執(zhí)行次數總是比循環(huán)

12、體的執(zhí)行次數多一次;即最后一次的循環(huán)體執(zhí)行完畢之后,循環(huán)變量又執(zhí)行了一次,但是循環(huán)體卻沒有再執(zhí)行了。（2）問題：二位數組在使用的時候數組未初始化：導致最后輸出的時候的鄰接矩陣出現錯誤；解決方法：根據輸出的窗口從代碼中分析發(fā)現錯誤，二維數組初始化之后，所得到的鄰接矩陣正確輸出。2.復雜度分析分析普里姆算法，假設網中有n個定點，則第一個進行初始化的循環(huán)語句的頻率為n，第二個循環(huán)語句的頻率為n-1。其中有兩個內循環(huán)：其一是在closedgev.lowcost中求最小值，其頻率為n-1;其二是重新選擇具有最小代價的變量，其頻度為n。由此，普里姆算法的時間復雜度為O(n*n),與網中的遍數無關。利用PR

13、IM算法生成最小生成樹時，求第k次的最短邊共需比較2(n-k)-1次，即時間復雜度為O(n-k)。3.思路探索開始分析問題時，我把問題想得過于簡單，結合老師講過得算法和書上得算法設計得，但本題不是這樣的，這個實際問題中有權值，而且這還是本題的關鍵，開始的時候造成了不少的麻煩，然后經過同學間得討論，才看出來我的錯誤來，及時改了過來。還有在普里姆的操作上，可謂是麻煩重重，書上的算法根本行不通，（因為上面的是C+）后來我反復的來看書也整的一知半解的，通過老師的幫助，我又開始重做，在最后才做出來。由于開始時對于問題的錯誤分析，浪費了不少時間。 其實，由于自己的馬虎也浪費了不少的時間在不必要的地方，如：

14、字母的大小寫，自負的定義上，但還好最后這些都克服了，對我來說對數據結構又有了進一步的了解，繼續(xù)學習，豐富自己！4.5 附錄#include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <string.h>#define INFINITY 10000#define M 20 typedef struct char VM10; int RMM; int vexnum; Graph; int locatevex(Graph *g,char a10) int i; for(i=0;

15、i<g->vexnum;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ū)，以0為結束n"); scanf("%s",g->Vi); while(strcmp("0",g->Vi)!=0) i+; scanf("%s",g->Vi); g->vexnum=i

16、; for(i=0;i<g->vexnum;i+) for(j=0;j<g->vexnum;j+) g->Rij=INFINITY; printf("轄區(qū)之間的路程，以0 0 0為結束標志n"); scanf("%s%s%d",a,b,&m); while(strcmp("0",a)!=0 | strcmp("0",b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);if(k=-1) printf("沒有%s這個轄區(qū)n&q

17、uot;,a); return 0; if(p=-1) printf("沒有%s這個轄區(qū)n",b); return 0;g->Rkp=g->Rpk=m;scanf("%s%s%d",a,b,&m); return 1;struct tree int weizhi; int lowcost; ;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

18、 && ai.lowcost!=0) if(ai.lowcost<ak.lowcost) k=i; return k;void MiniSpanTree_PRIM(Graph g,char a10) struct tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a); 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

19、+) k=minimun(closedge,g); money+=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) closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf("總費用為：%dn",money);void main()

20、 int i; Graph g; char a10; i=creatgraph(&g); if(i) printf("從哪里開始："); scanf("%s",a); MiniSpanTree_PRIM(g,a); 5 總結與展望通過這一周的課程設計，加深了我對數據結構這門課程所學內容的進一步的理解與掌握；同時，通過對地鐵建設問題的開發(fā)，使得我將計算機課程所學知識與實際問題很好地相聯接在了一起。初步的了解了我們所學的課本知識在實際中的應用。同時業(yè)培養(yǎng)了我開發(fā)一個中小型程序的能力。在這次對地鐵建設問題的開發(fā)過程中使我更加體會到細心耐心在程序設計中的

21、重要性，和同學的合作交流業(yè)讓自己學到了更多，發(fā)現自己在實際問題分析中的不足。通過本次課程設計，對圖的概念有了一個新的認識，在學習離散數學的時候，總覺得圖是很抽象的東西，但是在學習了數據結構與算法這門課程之后，我慢慢地體會到了其中的奧妙，圖能夠在計算機中存在，首先要捕捉他有哪些具體化、數字化的信息，比如說權值、頂點個數等，這也就說明了想要把生活中的信息轉化到計算機中必須用數字來完整的構成一個信息庫，而圖的存在，又涉及到了頂點之間的聯系。圖分為有向圖和無向圖，而無向圖又是有向圖在權值雙向相等下的一種特例，如何能在計算機中表示一個雙向權值不同的圖，這就是一件很巧妙的事情，經過了思考和老師同學的幫助，我用edgesij=up和edgesji=up就能實現了一個雙向圖信息的存儲。     對整個程序而言，Dijkstra算法始終都是核心內容，其實這個算法在實際思考中并不難，也許我們誰都知道找一個路徑最短的方法，及