地鐵課設(shè)報告

《地鐵課設(shè)報告》由會員分享，可在線閱讀，更多相關(guān)《地鐵課設(shè)報告（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 沈 陽 工 程 學(xué) 院 課 程 設(shè) 計 設(shè)計題目：地鐵問題 系 別 班級 學(xué)生姓名 學(xué)號 指導(dǎo)教師 職稱 講師、講師 起止日期：2015 年 6月 15日起至 2015年 6月 26日止 沈 陽 工 程 學(xué) 院 課程設(shè)計任務(wù)書 課程設(shè)計題目：地鐵問題 一、 課程設(shè)計的原始資料及依據(jù) 地鐵建設(shè)問題描述：某城市要在其各個轄區(qū)之間修建地鐵來加快經(jīng)濟的發(fā)展，但由于建 設(shè)地鐵的費用昂貴，因此需合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達各個轄區(qū)，并 使總的建設(shè)費用最小。 二、課程設(shè)計主要內(nèi)容及要求 地鐵建設(shè)內(nèi)容及要求 （1）從包含各轄區(qū)的地圖文件中讀入名稱和各轄區(qū)間的直

2、接距離。 （2）根據(jù)讀入的各轄區(qū)間距離信息，計算應(yīng)該建設(shè)哪些轄區(qū)建的地鐵線路。 （3）輸出應(yīng)該建設(shè)的地鐵路線及所需建設(shè)的總里程信息。 三、對課程設(shè)計說明書撰寫內(nèi)容、格式、字?jǐn)?shù)的要求 1課程設(shè)計說明書是體現(xiàn)和總結(jié)課程設(shè)計成果的載體，主要內(nèi)容包括：設(shè)計題目、設(shè)計目 的、設(shè)備器材、設(shè)計原理及內(nèi)容、設(shè)計步驟、遇到的問題及解決方法、設(shè)計總結(jié)、設(shè)計小組 評語、參考文獻等。一般不應(yīng)少于 3000 字。 2在適當(dāng)位置配合相應(yīng)的實驗原理圖、數(shù)據(jù)通路圖、微程序流程圖、實驗接線圖、微指令 代碼表等圖表進行說明。應(yīng)做到文理通順，內(nèi)容正確完整，書寫工整，裝訂整齊。 3設(shè)計總結(jié)部分主要寫本人完成工作簡介以及自己的設(shè)計體會

3、，包括通過課程設(shè)計學(xué)到了 什么，哪里遇到了困難，解決的辦法以及今后的目標(biāo)。 4課程設(shè)計說明書手寫或打印均可。手寫要用學(xué)校統(tǒng)一的課程設(shè)計用紙，用黑或藍黑墨水 工整書寫；打印時采用 A4 紙，頁邊距均為 20mm，正文采用宋體小四號字，行間距 18 磅。 文中大標(biāo)題采用黑體小三號字，一級節(jié)標(biāo)題采用黑體四號字，二級節(jié)標(biāo)題采用黑體小四號字， 表題與圖題采用宋體五號字。 5課程設(shè)計說明書裝訂順序為：封面、任務(wù)書、任務(wù)分工表、成績評定表、目錄、正文、參考文獻。 磅。文中大標(biāo)題采用黑體小三號字，一級節(jié)標(biāo)題采用黑體四號字，二級節(jié)標(biāo)題采用黑體小四 號字，表題與圖題采用宋體五號字。 5課程設(shè)計說明書裝訂順序為：封

4、面、任務(wù)書、任務(wù)分工表、成績評定表、目錄、正 文、參考文獻。 四、設(shè)計完成后應(yīng)提交成果的種類、數(shù)量、質(zhì)量等方面的要求 1完成“任務(wù)書”中指定的操作功能，運行穩(wěn)定。 2課程設(shè)計說明書。 五、時間進度安排 順序 階段日期 計 劃 完 成 內(nèi) 容 備注 1 第 1 天 閱讀資料 2 第 23 天 系統(tǒng)分析設(shè)計 3 第 47 天 程序編制、調(diào)試及運行 4 第 89 天 成績評定 5 第 10 天 撰寫課程設(shè)計說明書 六、主要參考資料（文獻） 1滕國文.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.北京:清華大學(xué)出版社.2010.09 2 Mark Allen Weiss 編著. 數(shù)據(jù)結(jié)構(gòu)與算法分析. 北京: 人民郵電出版社.20

5、07 3李春葆.數(shù)據(jù)結(jié)構(gòu)（C 語言版）習(xí)題與解析.北京:清華大學(xué)出版社.2002..04 4 熊錫義主編 C 語言程序設(shè)計案例教程 大連理工大學(xué)出版社 09 年 3 月版 5嚴(yán)蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)（C 語言版）. 北京:清華大學(xué)出版社.2007 6譚浩強.C 程序設(shè)計.北京:清華大學(xué)出版社.1999.12 沈 陽 工 程 學(xué) 院 程序設(shè)計基礎(chǔ)課程設(shè)計成績評定表 系（部）：計算機科學(xué)與技術(shù)系 班級：計算機B143 學(xué)生姓名： 王世杰 指 導(dǎo) 教 師 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 調(diào)研 論證 能獨立查閱文獻,收集資料；能制定課程設(shè)計方 案和日程安排

6、。 0.1 5 4 3 2 工作能力 態(tài)度 工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好， 能夠獨立完成設(shè)計工作， 0.2 5 4 3 2 工作量 按期圓滿完成規(guī)定的設(shè)計任務(wù)，工作量飽滿，難度適宜。 0.2 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊 全，圖表完備，書寫工整規(guī)范。 0.5 5 4 3 2 指導(dǎo)教師評審成績 （加權(quán)分合計乘以 8） 分 加權(quán)分合計 指 導(dǎo) 教 師 簽 名： 年 月 日 評 閱 教 師 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 查閱 文獻 查閱文獻有一定廣泛性

7、；有綜合歸納資料的能 力 0.2 5 4 3 2 工作量 工作量飽滿，難度適中。 0.5 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊 全，圖表完備，書寫工整規(guī)范。 0.3 5 4 3 2 評閱教師評審成績 （加權(quán)分合計乘以 4） 分 加權(quán)分合計 評 閱 教 師 簽 名： 年 月 日 答 辯 小 組 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 學(xué)生匯報 匯報準(zhǔn)備充分，思路清晰；語言表達準(zhǔn)確，概 念清楚，論點正確，有層次，有重點，基本上 反映了所完成任務(wù)的全部內(nèi)容；時間符合要求。 0.5 5 4

8、 3 2 答 辯 思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。 0.5 5 4 3 2 答辯小組評審成績 （加權(quán)分合計乘以 8） 分 加權(quán)分合計 答辯小組教師簽名： 年 月 日 課 程 設(shè) 計 總 評 成 績 分 沈 陽 工 程 學(xué) 院 程序設(shè)計基礎(chǔ)課程設(shè)計成績評定表 系（部）：計算機科學(xué)與技術(shù)系 班級：計算機B143 學(xué)生姓名： 張云朗 指 導(dǎo) 教 師 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 調(diào)研 論證 能獨立查閱文獻,收集資料；能制定課程設(shè)計方 案和日程安排。 0.1 5 4 3 2 工作能力 態(tài)度 工作態(tài)度認(rèn)真

9、，遵守紀(jì)律，出勤情況是否良好， 能夠獨立完成設(shè)計工作， 0.2 5 4 3 2 工作量 按期圓滿完成規(guī)定的設(shè)計任務(wù)，工作量飽滿，難度適宜。 0.2 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊 全，圖表完備，書寫工整規(guī)范。 0.5 5 4 3 2 指導(dǎo)教師評審成績 （加權(quán)分合計乘以 8） 分 加權(quán)分合計 指 導(dǎo) 教 師 簽 名： 年 月 日 評 閱 教 師 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 查閱 文獻 查閱文獻有一定廣泛性；有綜合歸納資料的能 力 0.2 5 4 3 2 工作量

10、 工作量飽滿，難度適中。 0.5 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊 全，圖表完備，書寫工整規(guī)范。 0.3 5 4 3 2 評閱教師評審成績 （加權(quán)分合計乘以 4） 分 加權(quán)分合計 評 閱 教 師 簽 名： 年 月 日 答 辯 小 組 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 學(xué)生匯報 匯報準(zhǔn)備充分，思路清晰；語言表達準(zhǔn)確，概 念清楚，論點正確，有層次，有重點，基本上 反映了所完成任務(wù)的全部內(nèi)容；時間符合要求。 0.5 5 4 3 2 答 辯 思路清晰；回答問題有理論依據(jù)，基本概

11、念清楚；主要問題回答準(zhǔn)確，深入，有說服力。 0.5 5 4 3 2 答辯小組評審成績 （加權(quán)分合計乘以 8） 分 加權(quán)分合計 答辯小組教師簽名： 年 月 日 課 程 設(shè) 計 總 評 成 績 分 沈 陽 工 程 學(xué) 院 程序設(shè)計基礎(chǔ)課程設(shè)計成績評定表 系（部）：計算機科學(xué)與技術(shù)系 班級：計算機B143 學(xué)生姓名： 王叢伍 指 導(dǎo) 教 師 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 調(diào)研 論證 能獨立查閱文獻,收集資料；能制定課程設(shè)計方 案和日程安排。 0.1 5 4 3 2 工作能力 態(tài)度 工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好， 能夠獨立完成設(shè)計工作，

12、0.2 5 4 3 2 工作量 按期圓滿完成規(guī)定的設(shè)計任務(wù)，工作量飽滿，難度適宜。 0.2 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊 全，圖表完備，書寫工整規(guī)范。 0.5 5 4 3 2 指導(dǎo)教師評審成績 （加權(quán)分合計乘以 8） 分 加權(quán)分合計 指 導(dǎo) 教 師 簽 名： 年 月 日 評 閱 教 師 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 查閱 文獻 查閱文獻有一定廣泛性；有綜合歸納資料的能 力 0.2 5 4 3 2 工作量 工作量飽滿，難度適中。 0.5 5 4 3 2 說明書

13、的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語準(zhǔn)確，符號統(tǒng)一，編號齊 全，圖表完備，書寫工整規(guī)范。 0.3 5 4 3 2 評閱教師評審成績 （加權(quán)分合計乘以 4） 分 加權(quán)分合計 評 閱 教 師 簽 名： 年 月 日 答 辯 小 組 評 審 意 見 評價內(nèi)容 具 體 要 求 權(quán)重 評 分 加權(quán)分 學(xué)生匯報 匯報準(zhǔn)備充分，思路清晰；語言表達準(zhǔn)確，概 念清楚，論點正確，有層次，有重點，基本上 反映了所完成任務(wù)的全部內(nèi)容；時間符合要求。 0.5 5 4 3 2 答 辯 思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。 0.5 5

14、4 3 2 答辯小組評審成績 （加權(quán)分合計乘以 8） 分 加權(quán)分合計 答辯小組教師簽名： 年 月 日 課 程 設(shè) 計 總 評 成 績 分 摘 要 某城市要在其各個轄區(qū)之間修建地鐵來加快經(jīng)濟的發(fā)展，但由于建設(shè)地鐵的費用昂貴， 因此需合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達各個轄區(qū)，并使總的建設(shè)費用最小。 地鐵建設(shè)可以緩解城市交通壓力。城市交通問題，已經(jīng)成為現(xiàn)代人無法面對的通病。經(jīng)濟發(fā) 展，汽車數(shù)量增長速度，遠遠快于城市道路的擴張速度。地鐵這個交通的特點就是到達的快 捷性和可靠性，運載能力強，能夠在很短的時間運輸大量的人群。運行中不塞車，是城市中 最具可靠性的交通工具。第二、增加地鐵交通體

15、系，可以使城市規(guī)劃更加科學(xué)和合理?？梢?節(jié)約能源。緩解對石油、天然氣消耗的壓力?？梢詼p少污染。地鐵這種交通工具污染少。可 以節(jié)省時間。因為不塞車，速度快，節(jié)省上班族上下班的在途時間。 因此我們小組利用數(shù)據(jù)結(jié)構(gòu)輸入各條線路起點、終點和直接距離，建立無向圖，鄰接矩 陣存儲輸出鄰接矩陣中的普利姆算法計算最小生成樹輸出最有線路。 關(guān)鍵詞 數(shù)據(jù)結(jié)構(gòu) 最小生成樹 地鐵 鄰接矩陣 目 錄 摘 要 .........................................................................................................

16、............................................I 第一章 問題分析 ................................................................................................................................1 1.1 引言 ............................................................................................................

17、................................1 1.2 背景 ............................................................................................................................................1 1.3 分析 ..............................................................................................................

18、..............................1 1.3.1 調(diào)試過程中的問題 .................................................................................................................1 第二章 原理與運行環(huán)境 ....................................................................................................................2 2.1 數(shù)據(jù)理論

19、 ....................................................................................................................................2 2.1.1 地鐵問題的數(shù)據(jù)理論 .............................................................................................................2 2.2 運行環(huán)境 .............................

20、.......................................................................................................2 2.2.1 打開方法 .................................................................................................................................2 2.2.2 打開 MICROSOFT VISUAL STDIO6.0 運行環(huán)境 .............

21、............................................................3 2.2.3 源程序的建立與編輯、連接 .................................................................................................4 第三章 系統(tǒng)分析與設(shè)計 ............................................................................................................

22、........6 3.1 地鐵建設(shè)問題分析與設(shè)計 ........................................................................................................6 3.1.1 系統(tǒng)的功能 .............................................................................................................................6 第四章 系統(tǒng)功能實現(xiàn) ..................

23、......................................................................................................7 4.1 地鐵建設(shè)問題的系統(tǒng)功能實現(xiàn) ................................................................................................7 4.1.1 定義主函數(shù) ....................................................................

24、.........................................................7 4.1.2 創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲轄區(qū)名 .............................................................................................8 4.1.3 創(chuàng)建無向圖，鄰接矩陣存儲 .................................................................................................9 4.1.4 輸出

25、鄰接矩陣 .......................................................................................................................10 4.1.5 普利姆算法求最小生成樹，輸出最優(yōu)路線 .......................................................................11 結(jié)論 .......................................................................

26、.............................................................................14 致謝 ....................................................................................................................................................15 參考文獻 .............................................................

27、...............................................................................16 第一章 問題分析 1.1 引言 數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定 關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效 率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。 一般認(rèn)為，一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏 輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu) 的實現(xiàn)形式，是其在計算機內(nèi)的表示；

28、此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí) 行的運算才有意義。一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理 的效率。在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大 型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了 最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反 過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都 是非常重要的。選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因 素。這種洞見導(dǎo)致了許多種軟件設(shè)計方法和程序設(shè)計語言的出現(xiàn)，面

29、向?qū)ο蟮某绦蛟O(shè)計語言 就是其中之一。 本次課程設(shè)計主要利用數(shù)據(jù)結(jié)構(gòu)中最小生成樹實現(xiàn)地鐵最優(yōu)線路問題。 1.2 背景 隨著經(jīng)濟的迅速發(fā)展，城市交通“外擁內(nèi)堵” ，情況嚴(yán)峻，壓力巨大。我們?yōu)榱司徑獬鞘?交通擁堵，改變過去以地上交通為主的單一格局，構(gòu)建地上地下立體交通體系，并通過與其 他交通方式的有機銜接，將極大地緩解城市交通擁堵狀況，解決人民群眾出行難的問題，于 是我們建立了地鐵建設(shè)項目。 1.3 分析 1.3.1 調(diào)試過程中的問題 1.調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析： 開始準(zhǔn)備將轄區(qū)名和相應(yīng)距離同存儲在鄰接矩陣中，但因為數(shù)據(jù)類型不同，這個想法 難以實現(xiàn)；而且

30、就算實現(xiàn)了，在后面的程序中操作也非常麻煩。所以我創(chuàng)建了一個結(jié)構(gòu)體數(shù) 組用來存儲轄區(qū)名，這樣轄區(qū)名和數(shù)組下標(biāo)一一對應(yīng)，簡明、易懂、清晰。以后只要看數(shù)字 所對應(yīng)的下標(biāo)存儲的是哪個轄區(qū)，就可以將其引用。 運行程序時，我要輸出最優(yōu)路線對應(yīng)的轄區(qū)，所以在輸出時要直接引用結(jié)構(gòu)體數(shù)組， 但怎么都不行，我就分模塊來調(diào)試，最后發(fā)現(xiàn)，原來是沒有將結(jié)構(gòu)體數(shù)組的地址傳過來。修 改后，程序運行正常。 沒有使用指針，避免了指針指向錯誤存儲區(qū)而造成的錯誤。 2.算法的時間復(fù)雜度和空間復(fù)雜度的分析，改進設(shè)想： 本程序的時間復(fù)雜度為 o（n2） ，主要是 for 循環(huán)的作用。 第二章 原理與運行環(huán)境 2.1 數(shù)據(jù)理論 2.

31、1.1 地鐵問題的數(shù)據(jù)理論 1程序所能達到的功能： creatve（）---創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲轄區(qū)名 CreateGraph（）---建立轄區(qū)間直接距離的無向圖，用鄰接矩陣存儲 pri（）---輸出無向圖的鄰接矩陣 prim（）---普利姆算法計算無向圖的最小生成樹，輸出最優(yōu)路線 2輸入的形式和輸入值的范圍： 輸入數(shù)字和字母，字母為轄區(qū)名，數(shù)字為直接距離，名稱個數(shù) n，線路個數(shù) e，0

32、 visual c++ 6.0 2.2.1 打開方法 開始程序Microsoft visual stdio6.0Microsoft Visual C++ 6.0，如圖 2-1 所示。 圖 2-1 打開 Visual C++的方法 2.2.2 打開 Microsoft visual stdio6.0 運行環(huán)境 其工作環(huán)境如圖 2-2 所示。 圖 2-2 Visual C++工作環(huán)境 2.2.3 源程序的建立與編輯、連接 建立 C 語言源程序文件。建立方法：選擇菜單命令“File” “New”或直接點擊對 話框中的“New ”，如圖 2-3 所示。 圖 2-3 建立 C 語言源程序文件

33、程序的編輯與編譯。編輯完成后，選擇菜單欄中的“組建”“調(diào)試程序” ， 或者直 接點擊工具欄中“箭頭”按鈕，即可對程序進行編譯。 當(dāng)輸出區(qū)顯示“0 errors， 0 warnings ”時表示沒有錯誤和警告，反之，則會按序號列 出錯誤和警告。雙擊錯誤或警告，編輯標(biāo)志會出現(xiàn)在源文件可能出錯的位置，我們可以在此 對源程序中的錯誤進行更改。當(dāng)然有時提示位置不一定很準(zhǔn)確。 程序的編輯于編譯操作，如圖 2-4 所示。 圖 2-4 程序的編輯與編譯 程序的執(zhí)行。單擊工具欄上的“深紅色感嘆號”按鈕，即可執(zhí)行剛編寫的程序。若程 序完全正確，即可彈出運行框。如圖 2-5 所示。 圖 2-5 程序的執(zhí)行 第三章

34、系統(tǒng)分析與設(shè)計 3.1 地鐵建設(shè)問題分析與設(shè)計 3.1.1 系統(tǒng)的功能 此系統(tǒng)為：某城市要在各個轄區(qū)之間修建地鐵，由于地鐵建設(shè)費用昂貴，因此需要合理 安排地鐵建設(shè)線路，使市民可以沿地鐵到達各個轄區(qū)，并使總費用最小。 其主功能模塊的流程圖如圖 3-1 所示。 N Y 開始 判斷 0

35、地鐵建設(shè)問題的系統(tǒng)功能實現(xiàn) 4.1.1 定義主函數(shù) 主函數(shù)是程序的入口，采用模塊化設(shè)計，首先聲明一些必要的變量函數(shù)如下： creatve（）---創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲轄區(qū)名 CreateGraph（）---建立轄區(qū)間直接距離的無向圖，用鄰接矩陣存儲 pri（）---輸出無向圖的鄰接矩陣 prim（）---普利姆算法計算無向圖的最小生成樹，輸出最優(yōu)路線 主函數(shù)調(diào)用各模塊的關(guān)系如下： 主函數(shù) main（）調(diào)用 int creatve(city vexmax)創(chuàng)建結(jié)構(gòu)體數(shù)組存儲轄區(qū)名； 主函數(shù) main（）調(diào)用 int CreateGraph(int gmax,int n,void pri(int

36、gmax,int n))建立 無向圖，用鄰接矩陣存儲； int CreateGraph(int gmax,int n,void pri(int gmax,int n))調(diào)用 void pri(int gmax, int n)輸出鄰接矩陣； 主函數(shù) main（）調(diào)用 void prim(int gmax,int n,city vexmax)計算最小生成樹，輸出 最優(yōu)線路和總里程。 源代碼如下： void main() /* 主函數(shù) */ int gmaxmax,n; city vexmax; n=creatve(vex); CreateGra

37、ph(g,n,pri); printf(nn最佳建設(shè)路線為:n); printf((轄區(qū)名----轄區(qū)名)---直接距離nn); prim(g,n,vex); 功能實現(xiàn)圖如圖 4-1 所示。 圖 4-1 初始化界面 4.1.2 創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲轄區(qū)名 進入主程序頁面后，應(yīng)輸入各個轄區(qū)名，并調(diào)用函數(shù)對輸入的轄區(qū)名進行存儲。 源代碼如下： int creatve(city vexmax)//創(chuàng)建轄區(qū)名數(shù)組 int i,n; printf(設(shè)置轄區(qū)的個數(shù): );//城市中轄區(qū)的個數(shù) scanf(%d, for(i=1;i

38、intf(第%d個城市轄區(qū)名稱為: ,i); scanf(%s,vexi.name); return(n); 功能實現(xiàn)圖 4-2 所示。 圖 4-2 4.1.3 創(chuàng)建無向圖，鄰接矩陣存儲 按照地鐵建設(shè)問題的要求，要將各個轄區(qū)為頂點作為圖，并用鄰接矩陣將其存儲。 其源代碼如下： int CreateGraph(int gmax,int n,void pri(int gmax,int n)) /* 建立無向圖 */ int e,i,j,k,v1=0,v2=0,weight=0; printf(輸入可建地鐵線線路個數(shù):); scanf(%d, while(e

39、=n*(n-1)||n=max) error(); printf(輸入可建地鐵線線路個數(shù):); scanf(%d, for(i=1;i<=n;i++) for(j=1;j<=n;j++) gij=inf; /* 初始化矩陣，全部元素設(shè)為無窮大 */ for(k=1;kn||v2n||v1<1||v2<1) error(); printf(輸入第 %d 條線路的起始轄區(qū),終點轄區(qū),直接距離:,k); scanf(%d%d%d, gv1v2=w

40、eight; gv2v1=weight; printf(n輸出存儲矩陣:n); pri(g,n); return OK; 功能實現(xiàn)圖如圖 4-3 所示 圖 4-3 4.1.4 輸出鄰接矩陣 此時將鄰接矩陣存儲的結(jié)果顯示一下，以便檢查下一步中結(jié)果的正確性。 其源代碼如下： void pri(int gmax,int n) /* 輸出無向圖的鄰接矩陣 */ int i,j; for(i=0;i<=n;i++) printf( %dt,i); for(i=1;i<=n;i++) printf(n %dt

41、,i); for(j=1;j<=n;j++) /* 輸出邊的權(quán)值 */ if(gij==inf) printf( t,354); else printf( %dt,gij); printf(n); 功能實現(xiàn)如圖 4-4 所示 圖 4-4 4.1.5 普利姆算法求最小生成樹，輸出最優(yōu)路線 用普利姆算法求出最短路程，則為地鐵建設(shè)的最優(yōu)路線。 其源代碼如下： void prim(int gmax,int n,city vexmax) /* prim的函數(shù) */ int

42、 lowcostmax,closestmax; int i,j,k,min,s=0; for(i=2;i<=n;i++) /* n個頂點，n-1條邊 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 頂點未加入到最小生成樹中 */ lowcost1=0; /* 標(biāo)志頂點1加入U集合 */ for(i=2;i<=n;i++) /* 形成n-1條邊的生成樹 */ min=inf;

43、k=0; for(j=2;j<=n;j++) /* 尋找滿足邊的一個頂點在U,另 一個頂點在V的最小邊 */ if((lowcostj

44、他頂點邊的權(quán) 值 */ if(gkj

45、們就開始編我的程序。經(jīng)過一個星 期的奮斗，我們終于是把程序整出來了。這是一個堅苦而又漫長的過程?？粗鴦趧映晒?，很 欣慰！畢竟這是我們第一次自己動腦筋做課程設(shè)計。 通過這次課程設(shè)計我們深刻的理解了普利姆算法，同時理解了數(shù)據(jù)結(jié)構(gòu)中思想的嚴(yán)謹(jǐn)性 和準(zhǔn)確性，在這次設(shè)計過程中讓我們各自找到了自己在設(shè)計過程中的缺點，我們大家意識到 自己當(dāng)時學(xué)明白并不代表自己就真正的會，自己在看書是看明白了不一定就能在計算機上運 行，例如當(dāng)輸入為%c 時候如果一個一個的輸入程序會把回車也當(dāng)做一個字符。再者就是在 每次程序中出現(xiàn)的老問題，在函數(shù)調(diào)用時如果傳值和傳址弄混那么在函數(shù)調(diào)用過程中就會出 現(xiàn)傳不回地址或者傳回的值為亂碼

46、。在以后的每個程序中我們一定會盡自己最大努力，在每 個程序中我都細心地去敲入每個字符，函數(shù)調(diào)用過程中先想明白在往上面寫。我們一定會繼 續(xù)努力，不辜負父母和老師對我的期望！ 致謝 本文是在曹福毅老師和李波老師的熱情關(guān)心和指導(dǎo)下完成的。從課程設(shè)計的前期準(zhǔn)備工 作到最后的修改，還得到了老師提出的許多寶貴的意見和建議，使我們小組受益非淺。特別 是在最后的測試修改階段，給我提了很多建議，使我能順利的完成課程設(shè)計。在短暫的兩周 的相處時間里，老師淵博的知識、敏銳的思路和實事求是的工作作風(fēng)給我留下了深刻的印象， 這促使我們小組有了很大的進步，謹(jǐn)此向我的指導(dǎo)老師表示衷心的感謝和崇高的敬意。 在論文完成過程中，

47、我們還得到了很多同學(xué)的熱心幫助，他們在我們做課程設(shè)計的這段 時間，給予我?guī)椭c支持，這也是我能順利完成課程設(shè)計的重要因素。本人向他們表示深深 的謝意！ 我們也要感謝和我一起學(xué)習(xí)共同進步的其他同學(xué)，有不會的問題我也常常請教身邊的同 學(xué)。合作的學(xué)習(xí)模式我們間形成了深厚的友誼以及合作精神。這對我們將來的學(xué)習(xí)生活和工 作生活將產(chǎn)生積極的影響。只有團結(jié)協(xié)作才能更好的完成任務(wù)目標(biāo)。 最后向在百忙之中評審本文的老師表示衷心的感謝！ 參考文獻 1范策等編著.算法與數(shù)據(jù)結(jié)構(gòu)（C 語言版） .北京：機械工業(yè)出版社，2004 2徐孝凱編著.數(shù)據(jù)結(jié)構(gòu)實用教程（第二版） .北京：清華大學(xué)出版社，2006 3徐孝凱.數(shù)據(jù)

48、結(jié)構(gòu)輔導(dǎo)與提高實用教程（第二版） .北京：清華大學(xué)出版社，2003 4胡學(xué)剛.算法與數(shù)據(jù)結(jié)構(gòu)算法設(shè)計指導(dǎo).北京：清華大學(xué)出版社，1999 5張乃孝等.數(shù)據(jù)結(jié)構(gòu)C++與面向?qū)ο蟮耐緩?北京：高等教育出版社，2001 6耿國華等.數(shù)據(jù)結(jié)構(gòu)C 語言描述.西安：西安電子科技大學(xué)出版社，2002 7殷人昆.數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅc C++語言描述.北京：清華大學(xué)出版社， 2007 8李春葆.數(shù)據(jù)結(jié)構(gòu)（C 語言）習(xí)題與解析.北京：清華大學(xué)出版社，2002 9鄧俊輝.數(shù)據(jù)結(jié)構(gòu)與算法（Java 描述） .北京：機械工業(yè)出版社，2006 10張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.電子工業(yè)出版社.2004.10 11張乃孝等.數(shù)據(jù)結(jié)構(gòu)C++與面向?qū)ο蟮耐緩?北京：高等教育出版社，2001 12蘇德富.計算機算法設(shè)計與分析.北京：電子工業(yè)出版社，2001