地鐵建設問題數(shù)據(jù)結構課程設計報告書

1、 . PAGE22 / NUMPAGES24 . 軟 件 學 院課程設計報告書課程名稱 數(shù)據(jù)結構課程設計 設計題目 地鐵建設問題 專業(yè)班級 學 號 姓 名 指導教師 2013年 1 月目 錄 TOC o 1-3 h z u HYPERLINK l _Toc2819976591 設計時間1HYPERLINK l _Toc2819976602 設計目的1HYPERLINK l _Toc2819976613設計任務1HYPERLINK l _Toc2819976624 設計容1HYPERLINK l _Toc2819976634.1需求分析1HYPERLINK l _Toc2819976644.2總

2、體設計2HYPERLINK l _Toc2819976654.3詳細設計4HYPERLINK l _Toc2819976664.4測試與分析11HYPERLINK l _Toc2819976674.4.1測試11HYPERLINK l _Toc2819976684.4.2分析13HYPERLINK l _Toc2819976694.5 附錄14HYPERLINK l _Toc2819976705 總結與展望20HYPERLINK l _Toc281997671參考文獻22HYPERLINK l _Toc281997672成績評定221 設計時間2013年1月16日至2013年1月21日2 設計

3、目的數(shù)據(jù)結構是計算機專業(yè)的核心課程，是計算機科學的算法理論基礎和軟件設計的技術基礎。數(shù)據(jù)結構是實踐性很強的課程。課程設計是加強學生實踐能力的一個強有力手段。要求學生掌握數(shù)據(jù)結構的應用、算法的編寫、類C語言的算法轉換成C程序并上機調試的基本方法。課程設計要求學生在完成程序設計的同時能夠寫出比較規(guī)的設計報告。嚴格實施課程設計這一環(huán)節(jié)，對于學生基本程序設計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用。3設計任務某城市要在各個轄區(qū)之間修建地鐵，由于地鐵建設費用昂貴，因此需要合理安排地鐵建設線路，使市民可以沿地鐵到達各個轄區(qū)，并使總費用最小。1. 輸入各個轄區(qū)名稱和各轄區(qū)間直接距離（地鐵鋪

4、設費用與距離成正比）；2. 根據(jù)轄區(qū)距離信息，計算出應該在哪些轄區(qū)建立地鐵線路；3. 輸出應該建設的地鐵線路與所需建設總里程。4 設計容 4.1需求分析1、程序所能達到的功能：(1)根據(jù)輸入的轄區(qū)信息，建立圖模型，使用的數(shù)據(jù)結構是無向圖，采用鄰接矩陣存儲。(2)根據(jù)普利姆算法計算最小生成樹。(3)輸入各個轄區(qū)代號，名稱和各轄區(qū)間直接距離（地鐵鋪設費用與距離成正比）。(4)根據(jù)轄區(qū)距離信息，計算出應該在哪些轄區(qū)建立地鐵線路。(5)輸出應該建設的地鐵線路與所需建設總里程。2、輸入的形式與容：包括城市名稱、城市間距離權值、起始地點，詳見4.4.1測試部分。3、輸出的形式與容： 包括生成的鄰接表、應建

5、設鐵路的轄區(qū)名稱與權值、最終地鐵的總里程，詳見4.4.1測試部分。4、測試數(shù)據(jù)：四個城市abcd與其之間的距離權值，詳見4.4.1測試部分。4.2總體設計4.2.1數(shù)據(jù)類型的定義1.圖的鄰接矩陣存儲數(shù)據(jù)類型定義：typedef struct char VM10; int RMM;int vexnum;Graph;）2.輔助數(shù)組數(shù)據(jù)類型定義：typedef structint adjvex;int lowcost;closedgeMAX;4.2.2基本操作：CreateCity(&G)操作結果：構造一個無向圖G；LocateDistri(Graph g,int u)操作結果：找出目標城市的位置；

6、Min(Graph g,closedge closedge)操作結果：求出點與點之間的最短路徑；Prim(G,G.distrinam1)操作結果：用普里姆算法找到連接各轄區(qū)的最短路；4.2.3主程序的流程主程序的流程如圖1所示：圖14.2.4各程序模塊之間的層次（調用）關系各程序模塊之間的層次（調用）關系如圖2所示：圖24.3詳細設計4.3.1預處理#include #include #include #include #define INFINITY 10000#define M 20 typedef struct /創(chuàng)建圖的結構體 char VM10; /頂點數(shù)組，用來存儲轄區(qū)的值即轄區(qū)的

7、名稱 int RMM; /鄰接矩陣，鄰接矩陣的元素值為轄區(qū)之間的距離 int vexnum; /轄區(qū)的個數(shù)Graph; struct tree int weizhi; int lowcost;4.3.2創(chuàng)建轄區(qū)無向圖的算法int creatgraph(Graph *g) /創(chuàng)建轄區(qū)無向圖，圖中含有n個結點，創(chuàng)建轄區(qū)鄰接矩陣 int i=0,j,m,k,p; char a10,b10; printf(*歡迎使用本程序解決地鐵建設問題*n); printf(*請按照提示依次輸入相關信息*n); printf(*請輸入所有的轄區(qū)，以0作為結束標志*n); scanf(%s,g-Vi);/輸入結點值

8、while(strcmp(0,g-Vi)!=0) i+; scanf(%s,g-Vi); g-vexnum=i; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINITY;/初始化 printf(*請輸入轄區(qū)之間的路程，以0 0 0為結束標志*n); scanf(%s%s%d,a,b,&m); /輸入轄區(qū)結點與轄區(qū)之間的距離 while(strcmp(0,a)!=0 | strcmp(0,b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);/查找a,b在圖中的位置 if(k=-1) printf(

9、*對不起，輸入錯誤，沒有%s這個轄區(qū)*n,a);return 0; if(p=-1) printf(*對不起，輸入錯誤，沒有%s這個轄區(qū)*n,b);return 0;g-Rkp=g-Rpk=m;/k到p和p到k之間的距離一樣 scanf(%s%s%d,a,b,&m); /輸入轄區(qū)結點與轄區(qū)之間的距離 return 1;struct tree int weizhi; int lowcost;int minimun(struct tree *a,Graph g) /求出第k轄區(qū)，此時i轄區(qū)與k轄區(qū)之間的距離最短int i,k,m=0; for(i=0;ig.vexnum;i+) if(m=0 &

10、ai.lowcost!=0) m=1; k=i; if(m=1 & ai.lowcost!=0)if(ai.lowcostak.lowcost)k=i; return k;4.3.3定位函數(shù)int locatevex(Graph *g,char a10) /查找轄區(qū)u在轄區(qū)圖中的位置int i;for(i=0;ivexnum;i+)/循環(huán)執(zhí)行條件是當u=Vi時停止，求i值if(strcmp(a,g-Vi)=0)return i; if(i=g-vexnum)return -1; 4.3.4求最小生成樹的結點算法int minimun(struct tree *a,Graph g) /求出第k轄

11、區(qū)，此時i轄區(qū)與k轄區(qū)之間的距離最短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;4.3.5PRIM算法與輸出void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM; int i,j,k,money=0; k=locatevex(&g,a);for(i=0;ig.vexnum;i+) if(i!=k) closedgei.low

12、cost=g.Rki; /兩轄區(qū)k，i之間的距離closedgei.weizhi=k; /與轄區(qū)i相鄰的最近的轄區(qū)設為轄區(qū)k closedgek.lowcost=0;/初始化，U=uprintf(*根據(jù)您的輸入建立鄰接表為:*n); for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) printf(|%d| ,g.Rij); printf(nn); printf(*得到應建設地鐵的轄區(qū)與之間權值為:*n); for(i=1;ig.vexnum;i+) k=minimun(closedge,g); /求出最小生成樹T的下一個結點，第k結點 money+=clo

13、sedgek.lowcost; printf(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); /輸出生成樹的邊 closedgek.lowcost=0; /第k頂點并入U集 for(j=0;jg.vexnum;j+) if(g.Rkjclosedgej.lowcost) /新頂點并入集后，選擇新的邊，將小的邊放到輔助數(shù)組中 closedgej.weizhi=k; closedgej.lowcost=g.Rkj; printf(*據(jù)統(tǒng)計地鐵的總建設路程為：%d *n,money);4,3,6主函數(shù)模塊void main()i

14、nt i; Graph g; char a10; i=creatgraph(&g); if(i)printf(*請輸入起始地點為：*n); scanf(%s,a); MiniSpanTree_PRIM(g,a);printf(*感使用本程序，！*n);4.4測試與分析4.4.1測試測試數(shù)據(jù)：1.以圖3為例圖 32.輸入城市區(qū)域名稱，如圖4所示：圖 43.根據(jù)需要，依次輸入各個區(qū)域代號和邊的權值，如圖5所示：圖 54.根據(jù)提示，輸入地鐵站的起始地點如圖6所示：圖 65.輸出最終結果，如圖7所示：圖 74.4.2分析1.調試過程中遇到的問題是如何解決的以與對設計與實現(xiàn)的回顧討論和分析在設計之初，我

15、對于整個算法的思路的理解并不清晰。最首要的任務就是選擇合適的計算思路，并加以實現(xiàn)。經過查閱，我發(fā)現(xiàn)解決此類問題的核心思想就是最小生成樹的生成。于是我選用普利姆算法和簡潔明了的鄰接矩陣存儲結構。在實驗過程中遇到的最大難題是普里姆算法的編寫。通過在書上和網上查閱資料，詢問同學老師，結合之前上機實驗的經驗，我理清思路。經過編寫，調試，最終完成了程序的設計。2.算法的時間復雜度和空間復雜度的分析本程序算法的時間復雜度為O(n3)，空間復雜度為O(2n) 表達是求值，主要是運用棧的相關知識解決的問題。在此問題之中要運用到函數(shù)的多次調用等等。3.針對可能出現(xiàn)的輸入錯誤，作出相應的應對措施：如輸入轄區(qū)之間的

16、權值時，當輸入錯誤的轄區(qū)時會有報錯提示，如圖8所示：圖84.5 附錄源程序：#include #include #include #include #define INFINITY 10000#define M 20 typedef struct /創(chuàng)建圖的結構體 char VM10; /頂點數(shù)組，用來存儲轄區(qū)的值即轄區(qū)的名稱 int RMM; /鄰接矩陣，鄰接矩陣的元素值為轄區(qū)之間的距離 int vexnum; /轄區(qū)的個數(shù)Graph; int locatevex(Graph *g,char a10) /查找轄區(qū)u在轄區(qū)圖中的位置int i; for(i=0;ivexnum;i+)/循環(huán)執(zhí)行

17、條件是當u=Vi時停止，求i值if(strcmp(a,g-Vi)=0) return i; if(i=g-vexnum) return -1; int creatgraph(Graph *g) /創(chuàng)建轄區(qū)無向圖，圖中含有n個結點，創(chuàng)建轄區(qū)鄰接矩陣 int i=0,j,m,k,p; char a10,b10; printf(*歡迎使用本程序解決地鐵建設問題*n); printf(*請按照提示依次輸入相關信息*n); printf(*請輸入所有的轄區(qū)，以0作為結束標志*n); scanf(%s,g-Vi);/輸入結點值 while(strcmp(0,g-Vi)!=0) i+; scanf(%s,g

18、-Vi); g-vexnum=i; for(i=0;ivexnum;i+)for(j=0;jvexnum;j+) g-Rij=INFINITY;/初始化 printf(*請輸入轄區(qū)之間的路程，以0 0 0為結束標志*n); scanf(%s%s%d,a,b,&m); /輸入轄區(qū)結點與轄區(qū)之間的距離 while(strcmp(0,a)!=0 | strcmp(0,b)!=0 | m!=0) k=locatevex(g,a); p=locatevex(g,b);/查找a,b在圖中的位置if(k=-1) printf(*對不起，輸入錯誤，沒有%s這個轄區(qū)*n,a);return 0; if(p=-1

19、)printf(*對不起，輸入錯誤，沒有%s這個轄區(qū)*n,b);return 0;g-Rkp=g-Rpk=m;/k到p和p到k之間的距離一樣 scanf(%s%s%d,a,b,&m); /輸入轄區(qū)結點與轄區(qū)之間的距離 return 1;struct tree int weizhi; int lowcost;int minimun(struct tree *a,Graph g) /求出第k轄區(qū)，此時i轄區(qū)與k轄區(qū)之間的距離最短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!

20、=0)if(ai.lowcostak.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;ig.vexnum;i+) if(i!=k) closedgei.lowcost=g.Rki; /兩轄區(qū)k，i之間的距離closedgei.weizhi=k; /與轄區(qū)i相鄰的最近的轄區(qū)設為轄區(qū)k closedgek.lowcost=0;/初始化，U=uprintf(*根據(jù)您的輸入建立鄰接表為:*n)

21、; for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) printf(|%d| ,g.Rij); printf(nn); printf(*得到應建設地鐵的轄區(qū)與之間權值為:*n); for(i=1;ig.vexnum;i+) k=minimun(closedge,g); /求出最小生成樹T的下一個結點，第k結點 money+=closedgek.lowcost; printf(%d:%s %s %dn,i,g.Vclosedgek.weizhi,g.Vk,closedgek.lowcost); /輸出生成樹的邊 closedgek.lowcost=0; /第k頂點并入U集 for(j=0;jg.vexnum;j+) if(g.Rkjclosedgej.lowcost) /新頂點并入集后，選擇新的邊，將小的邊放到輔助數(shù)組中closedgej.weizhi=k;closedgej.lowcost=g.Rkj;printf(*據(jù)統(tǒng)計地鐵的總建設路程為：%d *n,money);void main()int i; Graph g; char a10; i=creatgraph(&g); if(i)printf(*請輸入起始地點為：*n);scanf(%s,a);MiniSpanTree_PRIM(g,