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

1、軟件學(xué)院課程設(shè)計報告書課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目 地鐵建設(shè)問題專業(yè)班級 學(xué) 號姓 名 指導(dǎo)教師 2013 年 1 月目錄 TOC o 1-5 h z HYPERLINK l bookmark14 o Current Document 1設(shè)計時刻1 HYPERLINK l bookmark16 o Current Document 2設(shè)計目的1 HYPERLINK l bookmark18 o Current Document 3設(shè)計任務(wù)1 HYPERLINK l bookmark20 o Current Document 4設(shè)計內(nèi)容1 HYPERLINK l bookmark22 o C

2、urrent Document 需求分析1整體設(shè)計2 HYPERLINK l bookmark52 o Current Document 詳細(xì)設(shè)計4測試與分析11測試11 HYPERLINK l bookmark72 o Current Document 分析13附錄14 HYPERLINK l bookmark94 o Current Document 5總結(jié)與展望20參考文南犬22 HYPERLINK l bookmark102 o Current Document 成績評定221設(shè)計時間2013年1月16日至2013年1月21 日2設(shè)計目的數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程，是計算機科學(xué)的算

3、法理論基礎(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è)計報告。嚴(yán)格實施課程設(shè)計這一環(huán)節(jié)，對于學(xué)生基本程序設(shè)計素養(yǎng)的培養(yǎng)和軟件 工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。3設(shè)計任務(wù)某城市要在各個轄區(qū)之間修建地鐵，由于地鐵建設(shè)費用昂貴，因此需要合理安排 地鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各個轄區(qū)，并使總費用最小。輸入各個轄區(qū)名稱和各轄區(qū)間直接距離(地鐵鋪設(shè)費用與距離成正比)；根據(jù)轄區(qū)距離信息，計算

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

5、離權(quán)值，詳見測試部分?？傮w設(shè)計數(shù)據(jù)類型的定義1圖的鄰接矩陣存儲數(shù)據(jù)類型定義：typedef structchar VM10;int RMM;int vexnum;Graph;)2輔助數(shù)組數(shù)據(jù)類型定義：typedef structint adjvex;int lowcost;closedgeMAX;基本操作：CreateCity(&G)操作結(jié)果：構(gòu)造一個無向圖G；LocateDistri(Graph g,int u)操作結(jié)果：找出目標(biāo)城市的位置；Min(Graph g,closedge closedge)操作結(jié)果：求出點與點之間的最短路徑；Prim(G,l)操作結(jié)果：用普里姆算法找到連接各轄區(qū)的

6、最短路;主程序的流程主程序的流程如圖1所示:創(chuàng)建轄區(qū)無向圖*輸出轄區(qū)無向圖 的鄰接矩陣求解轄區(qū)圖g的 最小生成樹T求解轄區(qū)u在轄 區(qū)圖呂中的位置P各程序模塊之間的層次（調(diào)用）關(guān)系各程序模塊之間的層次（調(diào)用）關(guān)系如圖2所示:圖2詳細(xì)設(shè)計預(yù)處理#include #include #include #include #define INFINITY 10000#define M 20typedef struct owcost!=0) m=1;PRIM算法及輸出void MiniSpanTree_PRIM(Graph g,char a10)struct tree closedgeM;int i,j,k

7、,money=0;k=locatevex(&g,a);for(i=0;iv;i+)if(i!=k)closedgei.lowcost=ki; eizhi=k; owcost=O;owcost;printf(%d:%s %s %dn,i,closedgek.weizhi,k,closedgek.lowcost); owcost=0; owcost) eizhi=k;closedgej.lowcost=kj;printf(*據(jù)統(tǒng)計地鐵的總建設(shè)路程為：%d *n,money);4,3,6主函數(shù)模塊void main()名稱，如圖4所示:名稱，如圖4所示:tts 示轄 照有 按所木瞇信息嚴(yán)卄e.乍為結(jié)

8、束標(biāo)志*圖43根據(jù)需要，依次輸入各個區(qū)域代號和邊的權(quán)值，如圖5所示:卜請輸入轄區(qū)之間的路程，以邸0為結(jié)東標(biāo)志其a c 3k d 7k a 0h c 8b d 5b b Qc d 4c c 0d d 00 0 0圖54根據(jù)提示，輸入地鐵站的起始地點如圖6所示:” ncmxxHX請輸入起始地點為-mxmxxHxx b圖65.輸出最終結(jié)果，如圖7所示：*根據(jù)您的輸入建立鄰接表為:共*：0： ：9： ：3： ：7：191 101 I8i i5i!3! !8! !0! !4!7! !5! !4! !0!T導(dǎo)到應(yīng)建設(shè)地鐵的轄區(qū)及之間權(quán)值為:l：b d 52：d c 4*據(jù)統(tǒng)甘地鐵的總建設(shè)路彈閃:12 X“

9、*感謝使用本穗序，謝謝I 心圖7分析1.調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析在設(shè)計之初，我對于整個算法的思路的理解并不清晰。最首要的任務(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ù)雜度為0(3)，空間復(fù)雜度為0(2n)表達(dá)是求值，主要是運 用棧的相

10、關(guān)知識解決的問題。在此問題之中要運用到函數(shù)的多次調(diào)用等等。3.針對可能出現(xiàn)的輸入錯誤，作出相應(yīng)的應(yīng)對措施：如輸入轄區(qū)之間的權(quán)值時，當(dāng)輸入錯誤的轄區(qū)時會有報錯提示，如圖8所示:簡有 使所 迎頁 歡*輸簡有 使所 迎頁 歡*輸程示轄決地鐵建迓問題”請輸入轄區(qū)之間的路程，以陰0回為結(jié)東標(biāo)志幵a b 7b c 3 2*對不起，輸入錯誤！役有這個轄區(qū)*圖8附錄源程序：#include #include #include #include #define INFINITY 10000#define M 20typedef struct owcost!=0)m=1;k=i;if(m=1 & ai.lowco

11、st!=0)if(ai.lowcostvak.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;iv;i+)if(i!=k)closedgei.lowcost=ki; eizhi=k; owcost=O;owcost;printf(%d:%s %s %dn,i,closedgek.weizhi,k,closedgek.lowcost);owcost=0; owcost) eizhi=k;clo

12、sedgej.lowcost=kj;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,a);printf(*感謝使用本程序，謝謝！ *nn );5總結(jié)與展望對于本程序的總結(jié)與展望雖然在規(guī)定的時間內(nèi)基本上完成了課程設(shè)計所要求的學(xué)習(xí)任務(wù)，但是由于個人能 力以及時間上的局限性，造成設(shè)計的程序還存在著很多需要改進(jìn)的地方。比如沒有很 完整多樣的輸入與輸出的報錯處理程序，不

13、能很好的應(yīng)對程序在使用過程中出現(xiàn)的各 種錯誤和突發(fā)事件；還有在轄區(qū)之間權(quán)值的輸入過程中必須輸入每個轄區(qū)與自身的 “o”權(quán)值，否則會造成輸出錯誤的鄰接表等等問題。我希望在今后的學(xué)習(xí)生活中，在老師的教導(dǎo)下，更加刻苦努力地學(xué)習(xí)相關(guān)知識，進(jìn)一步完善這個程序。對于數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的總結(jié)此次課程設(shè)計讓我更加深入了解大一學(xué)到的C語言和這個學(xué)期學(xué)到的數(shù)據(jù)結(jié)構(gòu) 課程。課設(shè)題目要求不僅要求對課本知識有較深刻的了解，同時要求程序設(shè)計者有較 強的思維和動手能力和更加了解編程思想和編程技巧。程序設(shè)計時，不能怕遇到錯誤，在實際操作過程中犯的一些錯誤還會有意外的收 獲，這正是實踐操作的意義所在。在具體操作中鞏固這學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)的理論知 識，達(dá)到課程設(shè)計的基本目的，也發(fā)現(xiàn)自己的不足之出，如程序邏輯的理解力不夠強 等等。與此同時，我也體會到C語言所具有的語句簡潔，使用靈活，執(zhí)行效率高等特 點。特別是對圖這種數(shù)據(jù)