地鐵課設(shè)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 沈 陽 工 程 學(xué) 院課 程 設(shè) 計(jì)設(shè)計(jì)題目：地鐵問題系 別 班級 學(xué)生姓名 學(xué)號 指導(dǎo)教師 職稱 講師、講師 起止日期：2015年6月15日起至2015年6月26日止 沈 陽 工 程 學(xué) 院課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)題目：地鐵問題課程設(shè)計(jì)的原始資料及依據(jù)地鐵建設(shè)問題描述：某城市要在其各個(gè)轄區(qū)之間修建地鐵來加快經(jīng)濟(jì)的發(fā)展，但由于建設(shè)地鐵的費(fèi)用昂貴，因此需合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總的建設(shè)費(fèi)用最小。二、課程設(shè)計(jì)主要內(nèi)容及要求 地鐵建設(shè)內(nèi)容及要

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

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

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

5、02.044 熊錫義主編C語言程序設(shè)計(jì)案例教程 大連理工大學(xué)出版社 09年3月版5嚴(yán)蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）. 北京:清華大學(xué)出版社.20076譚浩強(qiáng).C程序設(shè)計(jì).北京:清華大學(xué)出版社.1999.12沈 陽 工 程 學(xué) 院程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)成績評定表系（部）：計(jì)算機(jī)科學(xué)與技術(shù)系 班級：計(jì)算機(jī)B143 學(xué)生姓名： 王世杰 指 導(dǎo) 教 師 評 審 意 見評價(jià)內(nèi)容具 體 要 求權(quán)重評 分加權(quán)分調(diào)研論證能獨(dú)立查閱文獻(xiàn),收集資料；能制定課程設(shè)計(jì)方案和日程安排。0.15432工作能力態(tài)度工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好，能夠獨(dú)立完成設(shè)計(jì)工作， 0.25432工作量按期圓滿完成規(guī)定的設(shè)計(jì)

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

7、以4）分加權(quán)分合計(jì)評 閱 教 師 簽 名： 年 月 日答 辯 小 組 評 審 意 見評價(jià)內(nèi)容具 體 要 求權(quán)重評 分加權(quán)分學(xué)生匯報(bào)匯報(bào)準(zhǔn)備充分，思路清晰；語言表達(dá)準(zhǔn)確，概念清楚，論點(diǎn)正確，有層次，有重點(diǎn)，基本上反映了所完成任務(wù)的全部內(nèi)容；時(shí)間符合要求。0.55432答 辯思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。0.55432答辯小組評審成績（加權(quán)分合計(jì)乘以8）分加權(quán)分合計(jì)答辯小組教師簽名： 年 月 日課 程 設(shè) 計(jì) 總 評 成 績分沈 陽 工 程 學(xué) 院程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)成績評定表系（部）：計(jì)算機(jī)科學(xué)與技術(shù)系 班級：計(jì)算機(jī)B143 學(xué)生姓名： 張?jiān)评?指

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

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

10、入，有說服力。0.55432答辯小組評審成績（加權(quán)分合計(jì)乘以8）分加權(quán)分合計(jì)答辯小組教師簽名： 年 月 日課 程 設(shè) 計(jì) 總 評 成 績分沈 陽 工 程 學(xué) 院程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)成績評定表系（部）：計(jì)算機(jī)科學(xué)與技術(shù)系 班級：計(jì)算機(jī)B143 學(xué)生姓名： 王叢伍 指 導(dǎo) 教 師 評 審 意 見評價(jià)內(nèi)容具 體 要 求權(quán)重評 分加權(quán)分調(diào)研論證能獨(dú)立查閱文獻(xiàn),收集資料；能制定課程設(shè)計(jì)方案和日程安排。0.15432工作能力態(tài)度工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好，能夠獨(dú)立完成設(shè)計(jì)工作， 0.25432工作量按期圓滿完成規(guī)定的設(shè)計(jì)任務(wù)，工作量飽滿，難度適宜。0.25432說明書的質(zhì)量說明書立論正確，論

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

12、 審 意 見評價(jià)內(nèi)容具 體 要 求權(quán)重評 分加權(quán)分學(xué)生匯報(bào)匯報(bào)準(zhǔn)備充分，思路清晰；語言表達(dá)準(zhǔn)確，概念清楚，論點(diǎn)正確，有層次，有重點(diǎn)，基本上反映了所完成任務(wù)的全部內(nèi)容；時(shí)間符合要求。0.55432答 辯思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。0.55432答辯小組評審成績（加權(quán)分合計(jì)乘以8）分加權(quán)分合計(jì)答辯小組教師簽名： 年 月 日課 程 設(shè) 計(jì) 總 評 成 績分摘 要某城市要在其各個(gè)轄區(qū)之間修建地鐵來加快經(jīng)濟(jì)的發(fā)展，但由于建設(shè)地鐵的費(fèi)用昂貴，因此需合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總的建設(shè)費(fèi)用最小。地鐵建設(shè)可以緩解城市交通壓力。城市

13、交通問題，已經(jīng)成為現(xiàn)代人無法面對的通病。經(jīng)濟(jì)發(fā)展，汽車數(shù)量增長速度，遠(yuǎn)遠(yuǎn)快于城市道路的擴(kuò)張速度。地鐵這個(gè)交通的特點(diǎn)就是到達(dá)的快捷性和可靠性，運(yùn)載能力強(qiáng)，能夠在很短的時(shí)間運(yùn)輸大量的人群。運(yùn)行中不塞車，是城市中最具可靠性的交通工具。第二、增加地鐵交通體系，可以使城市規(guī)劃更加科學(xué)和合理。可以節(jié)約能源。緩解對石油、天然氣消耗的壓力?？梢詼p少污染。地鐵這種交通工具污染少?？梢怨?jié)省時(shí)間。因?yàn)椴蝗?，速度快，?jié)省上班族上下班的在途時(shí)間。 因此我們小組利用數(shù)據(jù)結(jié)構(gòu)輸入各條線路起點(diǎn)、終點(diǎn)和直接距離，建立無向圖，鄰接矩陣存儲(chǔ)輸出鄰接矩陣中的普利姆算法計(jì)算最小生成樹輸出最有線路。關(guān)鍵詞 數(shù)據(jù)結(jié)構(gòu) 最小生成樹 地鐵

14、鄰接矩陣目 錄 TOC o 1-3 h z u 第一章 問題分析1.1 引言數(shù)據(jù)結(jié)構(gòu)是存儲(chǔ)、組織的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索和技術(shù)有關(guān)。一般認(rèn)為，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是其在計(jì)算機(jī)內(nèi)的表示；此外討論一個(gè)數(shù)據(jù)結(jié)構(gòu)必須同時(shí)討論在該類數(shù)據(jù)上執(zhí)行的運(yùn)算才有意義。一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種，且各種影響數(shù)據(jù)處理的效率。在許多類型的的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)

15、計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)表明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過來，我們根據(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)致了許多種方法和的出現(xiàn)，語言就是其中之一。本次課程設(shè)計(jì)主要利用數(shù)據(jù)結(jié)構(gòu)中最小生成樹實(shí)現(xiàn)地鐵最優(yōu)線路問題。1.2背景 隨著經(jīng)濟(jì)的迅速發(fā)展，城市交通“外擁內(nèi)堵”，情況嚴(yán)峻，壓力巨大。我們?yōu)榱司徑獬鞘薪煌〒矶拢淖冞^去以地上交通為主的單一格局，構(gòu)建地上地

16、下立體交通體系，并通過與其他交通方式的有機(jī)銜接，將極大地緩解城市交通擁堵狀況，解決人民群眾出行難的問題，于是我們建立了地鐵建設(shè)項(xiàng)目。1.3 分析1.3.1 調(diào)試過程中的問題1.調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析： = 1 * GB3 開始準(zhǔn)備將轄區(qū)名和相應(yīng)距離同存儲(chǔ)在鄰接矩陣中，但因?yàn)閿?shù)據(jù)類型不同，這個(gè)想法難以實(shí)現(xiàn)；而且就算實(shí)現(xiàn)了，在后面的程序中操作也非常麻煩。所以我創(chuàng)建了一個(gè)結(jié)構(gòu)體數(shù)組用來存儲(chǔ)轄區(qū)名，這樣轄區(qū)名和數(shù)組下標(biāo)一一對應(yīng)，簡明、易懂、清晰。以后只要看數(shù)字所對應(yīng)的下標(biāo)存儲(chǔ)的是哪個(gè)轄區(qū)，就可以將其引用。 = 2 * GB3 運(yùn)行程序時(shí)，我要輸出最優(yōu)路線對應(yīng)的

17、轄區(qū)，所以在輸出時(shí)要直接引用結(jié)構(gòu)體數(shù)組，但怎么都不行，我就分模塊來調(diào)試，最后發(fā)現(xiàn)，原來是沒有將結(jié)構(gòu)體數(shù)組的地址傳過來。修改后，程序運(yùn)行正常。 = 3 * GB3 沒有使用指針，避免了指針指向錯(cuò)誤存儲(chǔ)區(qū)而造成的錯(cuò)誤。2.算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析，改進(jìn)設(shè)想：本程序的時(shí)間復(fù)雜度為o（n2），主要是for循環(huán)的作用。第二章 原理與運(yùn)行環(huán)境2.1 數(shù)據(jù)理論2.1.1 地鐵問題的數(shù)據(jù)理論1程序所能達(dá)到的功能：creatve（）-創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲(chǔ)轄區(qū)名 = 2 * GB2 CreateGraph（）-建立轄區(qū)間直接距離的無向圖，用鄰接矩陣存儲(chǔ)pri（）-輸出無向圖的鄰接矩陣prim（）-普利姆

18、算法計(jì)算無向圖的最小生成樹，輸出最優(yōu)路線2輸入的形式和輸入值的范圍：輸入數(shù)字和字母，字母為轄區(qū)名，數(shù)字為直接距離，名稱個(gè)數(shù)n，線路個(gè)數(shù)e，0en(n-1),直接距離weigth，0weigth999993輸出的形式：最佳建設(shè)路徑為：（轄區(qū)名-轄區(qū)名）-直接路徑2.2 運(yùn)行環(huán)境數(shù)據(jù)結(jié)構(gòu)程序的運(yùn)行環(huán)境為Microsoft visual c+ 6.02.2.1打開方法開始程序Microsoft visual stdio6.0Microsoft Visual C+ 6.0，如圖2-1所示。圖2-1打開Visual C+的方法2.2.2打開Microsoft visual stdio6.0運(yùn)行環(huán)境其工作

19、環(huán)境如圖2-2所示。 圖2-2 Visual C+工作環(huán)境2.2.3源程序的建立與編輯、連接建立C語言源程序文件。建立方法：選擇菜單命令“File” “New”或直接點(diǎn)擊對話框中的“New”，如圖2-3所示。 圖2-3建立C語言源程序文件程序的編輯與編譯。編輯完成后，選擇菜單欄中的“組建”“調(diào)試程序”， 或者直接點(diǎn)擊工具欄中“箭頭”按鈕，即可對程序進(jìn)行編譯。當(dāng)輸出區(qū)顯示“0 errors， 0 warnings ”時(shí)表示沒有錯(cuò)誤和警告，反之，則會(huì)按序號列出錯(cuò)誤和警告。雙擊錯(cuò)誤或警告，編輯標(biāo)志會(huì)出現(xiàn)在源文件可能出錯(cuò)的位置，我們可以在此對源程序中的錯(cuò)誤進(jìn)行更改。當(dāng)然有時(shí)提示位置不一定很準(zhǔn)確。程序的

20、編輯于編譯操作，如圖2-4所示。圖2-4 程序的編輯與編譯程序的執(zhí)行。單擊工具欄上的“深紅色感嘆號”按鈕，即可執(zhí)行剛編寫的程序。若程序完全正確，即可彈出運(yùn)行框。如圖2-5所示。圖2-5程序的執(zhí)行第三章 系統(tǒng)分析與設(shè)計(jì)3.1地鐵建設(shè)問題分析與設(shè)計(jì)3.1.1 系統(tǒng)的功能此系統(tǒng)為：某城市要在各個(gè)轄區(qū)之間修建地鐵，由于地鐵建設(shè)費(fèi)用昂貴，因此需要合理安排地鐵建設(shè)線路，使市民可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總費(fèi)用最小。其主功能模塊的流程圖如圖3-1所示。開始開始輸入轄區(qū)個(gè)數(shù)和轄區(qū)名輸入轄區(qū)個(gè)數(shù)和轄區(qū)名輸入線路個(gè)數(shù)輸入線路個(gè)數(shù)判斷0en(n-1) 判斷0en(n-1) Y輸入各條線路起點(diǎn)、終點(diǎn)和直接距離 輸入各

21、條線路起點(diǎn)、終點(diǎn)和直接距離建立無向圖，鄰接矩陣存儲(chǔ)建立無向圖，鄰接矩陣存儲(chǔ)輸出鄰接矩陣輸出鄰接矩陣普利姆算法計(jì)算最小生成樹普利姆算法計(jì)算最小生成樹輸出最優(yōu)線路和總里程輸出最優(yōu)線路和總里程結(jié)束結(jié)束第四章 系統(tǒng)功能實(shí)現(xiàn)4.1地鐵建設(shè)問題的系統(tǒng)功能實(shí)現(xiàn)4.1.1 定義主函數(shù)主函數(shù)是程序的入口，采用模塊化設(shè)計(jì)，首先聲明一些必要的變量函數(shù)如下：creatve（）-創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲(chǔ)轄區(qū)名 = 2 * GB2 CreateGraph（）-建立轄區(qū)間直接距離的無向圖，用鄰接矩陣存儲(chǔ)pri（）-輸出無向圖的鄰接矩陣prim（）-普利姆算法計(jì)算無向圖的最小生成樹，輸出最優(yōu)路線主函數(shù)調(diào)用各模塊的關(guān)系如下：主函數(shù)

22、main（）調(diào)用int creatve(city vexmax)創(chuàng)建結(jié)構(gòu)體數(shù)組存儲(chǔ)轄區(qū)名； = 2 * GB2 主函數(shù)main（）調(diào)用int CreateGraph(int gmax,int n,void pri(int gmax,int n)建立無向圖，用鄰接矩陣存儲(chǔ)； 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)計(jì)算最小生成樹，輸出最優(yōu)線路和總里程。源代碼如下：v

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

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

25、&e); while(e=n*(n-1)|n=max) error(); printf(輸入可建地鐵線線路個(gè)數(shù):); scanf(%d,&e); for(i=1;i=n;i+) for(j=1;j=n;j+) gij=inf; /* 初始化矩陣，全部元素設(shè)為無窮大 */ for(k=1;kn|v2n|v11|v21) error(); printf(輸入第 %d 條線路的起始轄區(qū),終點(diǎn)轄區(qū),直接距離:,k); scanf(%d%d%d,&v1,&v2,&weight); gv1v2=weight; gv2v1=weight; printf(n輸出存儲(chǔ)矩陣:n); pri(g,n); retur

26、n OK; 功能實(shí)現(xiàn)圖如圖4-3所示圖4-3 4.1.4輸出鄰接矩陣此時(shí)將鄰接矩陣存儲(chǔ)的結(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,i); for(j=1;j=n;j+) /* 輸出邊的權(quán)值 */ if(gij=inf) printf( t,354); else printf( %dt,gij); printf(n);功能實(shí)現(xiàn)如圖4-4所示圖4-4 4.1.5

27、普利姆算法求最小生成樹，輸出最優(yōu)路線用普利姆算法求出最短路程，則為地鐵建設(shè)的最優(yōu)路線。其源代碼如下：void prim(int gmax,int n,city vexmax) /* prim的函數(shù) */ int lowcostmax,closestmax; int i,j,k,min,s=0; for(i=2;i=n;i+) /* n個(gè)頂點(diǎn)，n-1條邊 */ lowcosti=g1i; /* 初始化 */ closesti=1; /* 頂點(diǎn)未加入到最小生成樹中 */ lowcost1=0; /* 標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 */ for(i=2;i=n;i+) /* 形成n-1條邊的生成樹 */ m

28、in=inf; k=0; for(j=2;j=n;j+) /* 尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 */ if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; s+=min; printf(%s-%s)-%dt,,,min); lowcostk=0; /* 頂點(diǎn)k加入U(xiǎn) */ for(j=2;j=n;j+) /* 修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值 */ if(gkjlowcostj) lowcostj=gkj; closestj=k; printf(n); printf(n修建地鐵最短總里

29、程為:); printf(%d,s); 功能實(shí)現(xiàn)如圖4-5所示圖4-5 結(jié)論 剛開始拿到題目的時(shí)候，沒有什么思路，就翻書看了普利姆算法，然后也在網(wǎng)上搜索了相關(guān)的資料。找到有相似的程序，但不符合我的題目的要求，不是鄰接矩陣存儲(chǔ)，輸入輸出也不行。于是，我們小組就仔細(xì)的看了程序，弄懂之后我們就開始編我的程序。經(jīng)過一個(gè)星期的奮斗，我們終于是把程序整出來了。這是一個(gè)堅(jiān)苦而又漫長的過程。看著勞動(dòng)成果，很欣慰！畢竟這是我們第一次自己動(dòng)腦筋做課程設(shè)計(jì)。通過這次課程設(shè)計(jì)我們深刻的理解了普利姆算法，同時(shí)理解了數(shù)據(jù)結(jié)構(gòu)中思想的嚴(yán)謹(jǐn)性和準(zhǔn)確性，在這次設(shè)計(jì)過程中讓我們各自找到了自己在設(shè)計(jì)過程中的缺點(diǎn)，我們大家意識(shí)到自己當(dāng)時(shí)學(xué)明白并不代表自己就真正的會(huì)，自己在看書是看明白了不一定就能在計(jì)算機(jī)上運(yùn)行，例如當(dāng)輸入為%c時(shí)候如果一個(gè)一個(gè)的輸入程序會(huì)把回車也當(dāng)做一個(gè)字符。再者就是在每次程序中出現(xiàn)的