地鐵建設(shè)問題數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告書

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

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

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

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

5、設(shè)鐵路的轄區(qū)名稱與權(quán)值、最終地鐵的總里程，詳見4.4.1測試部分。4、測試數(shù)據(jù)：四個城市abcd與其之間的距離權(quán)值，詳見4.4.1測試部分。4.2總體設(shè)計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)操作結(jié)果：構(gòu)造一個無向圖G；LocateDistri(Graph g,int u)操作結(jié)果：找出目標城市的位置；

6、Min(Graph g,closedge closedge)操作結(jié)果：求出點與點之間的最短路徑；Prim(G,G.distrinam1)操作結(jié)果：用普里姆算法找到連接各轄區(qū)的最短路；4.2.3主程序的流程主程序的流程如圖1所示：圖14.2.4各程序模塊之間的層次（調(diào)用）關(guān)系各程序模塊之間的層次（調(diào)用）關(guān)系如圖2所示：圖24.3詳細設(shè)計4.3.1預(yù)處理#include #include #include #include #define INFINITY 10000#define M 20 typedef struct /創(chuàng)建圖的結(jié)構(gòu)體 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個結(jié)點，創(chuàng)建轄區(qū)鄰接矩陣 int i=0,j,m,k,p; char a10,b10; printf(*歡迎使用本程序解決地鐵建設(shè)問題*n); printf(*請按照提示依次輸入相關(guān)信息*n); printf(*請輸入所有的轄區(qū)，以0作為結(jié)束標志*n); scanf(%s,g-Vi);/輸入結(jié)點值

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為結(jié)束標志*n); scanf(%s%s%d,a,b,&m); /輸入轄區(qū)結(jié)點與轄區(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ū)結(jié)點與轄區(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求最小生成樹的結(jié)點算法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ū)設(shè)為轄區(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(*得到應(yīng)建設(shè)地鐵的轄區(qū)與之間權(quán)值為:*n); for(i=1;ig.vexnum;i+) k=minimun(closedge,g); /求出最小生成樹T的下一個結(jié)點，第k結(jié)點 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)計地鐵的總建設(shè)路程為：%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ū)域代號和邊的權(quán)值，如圖5所示：圖 54.根據(jù)提示，輸入地鐵站的起始地點如圖6所示：圖 65.輸出最終結(jié)果，如圖7所示：圖 74.4.2分析1.調(diào)試過程中遇到的問題是如何解決的以與對設(shè)計與實現(xiàn)的回顧討論和分析在設(shè)計之初，我

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

16、權(quán)值時，當輸入錯誤的轄區(qū)時會有報錯提示，如圖8所示：圖84.5 附錄源程序：#include #include #include #include #define INFINITY 10000#define M 20 typedef struct /創(chuàng)建圖的結(jié)構(gòu)體 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個結(jié)點，創(chuàng)建轄區(qū)鄰接矩陣 int i=0,j,m,k,p; char a10,b10; printf(*歡迎使用本程序解決地鐵建設(shè)問題*n); printf(*請按照提示依次輸入相關(guān)信息*n); printf(*請輸入所有的轄區(qū)，以0作為結(jié)束標志*n); scanf(%s,g-Vi);/輸入結(jié)點值 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為結(jié)束標志*n); scanf(%s%s%d,a,b,&m); /輸入轄區(qū)結(jié)點與轄區(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ū)結(jié)點與轄區(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ū)設(shè)為轄區(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(*得到應(yīng)建設(shè)地鐵的轄區(qū)與之間權(quán)值為:*n); for(i=1;ig.vexnum;i+) k=minimun(closedge,g); /求出最小生成樹T的下一個結(jié)點，第k結(jié)點 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)計地鐵的總建設(shè)路程為：%d *n,money);void main()int i; Graph g; char a10; i=creatgraph(&g); if(i)printf(*請輸入起始地點為：*n);scanf(%s,a);MiniSpanTree_PRIM(g,