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

沈 陽(yáng) 工 程 學(xué) 院 課 程 設(shè) 計(jì) 設(shè)計(jì)題目：地鐵問題 系 別 班級(jí) 學(xué)生姓名 學(xué)號(hào) 指導(dǎo)教師 職稱 講師、講師 起止日期：2015 年 6月 15日起至 2015年 6月 26日止 沈 陽(yáng) 工 程 學(xué) 院 課程設(shè)計(jì)任務(wù)書 課程設(shè)計(jì)題目：地鐵問題 一、 課程設(shè)計(jì)的原始資料及依據(jù) 地鐵建設(shè)問題描述：某城市要在其各個(gè)轄區(qū)之間修建地鐵來(lái)加快經(jīng)濟(jì)的發(fā)展，但由于建 設(shè)地鐵的費(fèi)用昂貴，因此需合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達(dá)各個(gè)轄區(qū)，并 使總的建設(shè)費(fèi)用最小。 二、課程設(shè)計(jì)主要內(nèi)容及要求 地鐵建設(shè)內(nèi)容及要求 （1）從包含各轄區(qū)的地圖文件中讀入名稱和各轄區(qū)間的直接距離。 （2）根據(jù)讀入的各轄區(qū)間距離信息，計(jì)算應(yīng)該建設(shè)哪些轄區(qū)建的地鐵線路。 （3）輸出應(yīng)該建設(shè)的地鐵路線及所需建設(shè)的總里程信息。 三、對(duì)課程設(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ì)小組 評(píng)語(yǔ)、參考文獻(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é)部分主要寫本人完成工作簡(jiǎn)介以及自己的設(shè)計(jì)體會(huì)，包括通過課程設(shè)計(jì)學(xué)到了 什么，哪里遇到了困難，解決的辦法以及今后的目標(biāo)。 4課程設(shè)計(jì)說明書手寫或打印均可。手寫要用學(xué)校統(tǒng)一的課程設(shè)計(jì)用紙，用黑或藍(lán)黑墨水 工整書寫；打印時(shí)采用 A4 紙，頁(yè)邊距均為 20mm，正文采用宋體小四號(hào)字，行間距 18 磅。 文中大標(biāo)題采用黑體小三號(hào)字，一級(jí)節(jié)標(biāo)題采用黑體四號(hào)字，二級(jí)節(jié)標(biāo)題采用黑體小四號(hào)字， 表題與圖題采用宋體五號(hào)字。 5課程設(shè)計(jì)說明書裝訂順序?yàn)椋悍饷?、任?wù)書、任務(wù)分工表、成績(jī)?cè)u(píng)定表、目錄、正文、參考文獻(xiàn)。 磅。文中大標(biāo)題采用黑體小三號(hào)字，一級(jí)節(jié)標(biāo)題采用黑體四號(hào)字，二級(jí)節(jié)標(biāo)題采用黑體小四 號(hào)字，表題與圖題采用宋體五號(hào)字。 5課程設(shè)計(jì)說明書裝訂順序?yàn)椋悍饷妗⑷蝿?wù)書、任務(wù)分工表、成績(jī)?cè)u(píng)定表、目錄、正 文、參考文獻(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 天 成績(jī)?cè)u(píng)定 5 第 10 天 撰寫課程設(shè)計(jì)說明書 六、主要參考資料（文獻(xiàn)） 1滕國(guó)文.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).北京:清華大學(xué)出版社.2010.09 2 Mark Allen Weiss 編著. 數(shù)據(jù)結(jié)構(gòu)與算法分析. 北京: 人民郵電出版社.2007 3李春葆.數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言版）習(xí)題與解析.北京:清華大學(xué)出版社.2002.04 4 熊錫義主編 C 語(yǔ)言程序設(shè)計(jì)案例教程 大連理工大學(xué)出版社 09 年 3 月版 5嚴(yán)蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言版）. 北京:清華大學(xué)出版社.2007 6譚浩強(qiáng).C 程序設(shè)計(jì).北京:清華大學(xué)出版社.1999.12 沈 陽(yáng) 工 程 學(xué) 院 程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)成績(jī)?cè)u(píng)定表 系（部）：計(jì)算機(jī)科學(xué)與技術(shù)系 班級(jí)：計(jì)算機(jī)B143 學(xué)生姓名： 王世杰 指 導(dǎo) 教 師 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 調(diào)研 論證 能獨(dú)立查閱文獻(xiàn),收集資料；能制定課程設(shè)計(jì)方 案和日程安排。 0.1 5 4 3 2 工作能力 態(tài)度 工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好， 能夠獨(dú)立完成設(shè)計(jì)工作， 0.2 5 4 3 2 工作量 按期圓滿完成規(guī)定的設(shè)計(jì)任務(wù)，工作量飽滿，難度適宜。 0.2 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊 全，圖表完備，書寫工整規(guī)范。 0.5 5 4 3 2 指導(dǎo)教師評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 8） 分 加權(quán)分合計(jì) 指 導(dǎo) 教 師 簽 名： 年 月 日 評(píng) 閱 教 師 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 查閱 文獻(xiàn) 查閱文獻(xiàn)有一定廣泛性；有綜合歸納資料的能 力 0.2 5 4 3 2 工作量 工作量飽滿，難度適中。 0.5 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊 全，圖表完備，書寫工整規(guī)范。 0.3 5 4 3 2 評(píng)閱教師評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 4） 分 加權(quán)分合計(jì) 評(píng) 閱 教 師 簽 名： 年 月 日 答 辯 小 組 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 學(xué)生匯報(bào) 匯報(bào)準(zhǔn)備充分，思路清晰；語(yǔ)言表達(dá)準(zhǔn)確，概 念清楚，論點(diǎn)正確，有層次，有重點(diǎn)，基本上 反映了所完成任務(wù)的全部?jī)?nèi)容；時(shí)間符合要求。 0.5 5 4 3 2 答 辯 思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。 0.5 5 4 3 2 答辯小組評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 8） 分 加權(quán)分合計(jì) 答辯小組教師簽名： 年 月 日 課 程 設(shè) 計(jì) 總 評(píng) 成 績(jī) 分 沈 陽(yáng) 工 程 學(xué) 院 程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)成績(jī)?cè)u(píng)定表 系（部）：計(jì)算機(jī)科學(xué)與技術(shù)系 班級(jí)：計(jì)算機(jī)B143 學(xué)生姓名： 張?jiān)评?指 導(dǎo) 教 師 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 調(diào)研 論證 能獨(dú)立查閱文獻(xiàn),收集資料；能制定課程設(shè)計(jì)方 案和日程安排。 0.1 5 4 3 2 工作能力 態(tài)度 工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好， 能夠獨(dú)立完成設(shè)計(jì)工作， 0.2 5 4 3 2 工作量 按期圓滿完成規(guī)定的設(shè)計(jì)任務(wù)，工作量飽滿，難度適宜。 0.2 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊 全，圖表完備，書寫工整規(guī)范。 0.5 5 4 3 2 指導(dǎo)教師評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 8） 分 加權(quán)分合計(jì) 指 導(dǎo) 教 師 簽 名： 年 月 日 評(píng) 閱 教 師 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 查閱 文獻(xiàn) 查閱文獻(xiàn)有一定廣泛性；有綜合歸納資料的能 力 0.2 5 4 3 2 工作量 工作量飽滿，難度適中。 0.5 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊 全，圖表完備，書寫工整規(guī)范。 0.3 5 4 3 2 評(píng)閱教師評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 4） 分 加權(quán)分合計(jì) 評(píng) 閱 教 師 簽 名： 年 月 日 答 辯 小 組 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 學(xué)生匯報(bào) 匯報(bào)準(zhǔn)備充分，思路清晰；語(yǔ)言表達(dá)準(zhǔn)確，概 念清楚，論點(diǎn)正確，有層次，有重點(diǎn)，基本上 反映了所完成任務(wù)的全部?jī)?nèi)容；時(shí)間符合要求。 0.5 5 4 3 2 答 辯 思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。 0.5 5 4 3 2 答辯小組評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 8） 分 加權(quán)分合計(jì) 答辯小組教師簽名： 年 月 日 課 程 設(shè) 計(jì) 總 評(píng) 成 績(jī) 分 沈 陽(yáng) 工 程 學(xué) 院 程序設(shè)計(jì)基礎(chǔ)課程設(shè)計(jì)成績(jī)?cè)u(píng)定表 系（部）：計(jì)算機(jī)科學(xué)與技術(shù)系 班級(jí)：計(jì)算機(jī)B143 學(xué)生姓名： 王叢伍 指 導(dǎo) 教 師 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 調(diào)研 論證 能獨(dú)立查閱文獻(xiàn),收集資料；能制定課程設(shè)計(jì)方 案和日程安排。 0.1 5 4 3 2 工作能力 態(tài)度 工作態(tài)度認(rèn)真，遵守紀(jì)律，出勤情況是否良好， 能夠獨(dú)立完成設(shè)計(jì)工作， 0.2 5 4 3 2 工作量 按期圓滿完成規(guī)定的設(shè)計(jì)任務(wù)，工作量飽滿，難度適宜。 0.2 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊 全，圖表完備，書寫工整規(guī)范。 0.5 5 4 3 2 指導(dǎo)教師評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 8） 分 加權(quán)分合計(jì) 指 導(dǎo) 教 師 簽 名： 年 月 日 評(píng) 閱 教 師 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 查閱 文獻(xiàn) 查閱文獻(xiàn)有一定廣泛性；有綜合歸納資料的能 力 0.2 5 4 3 2 工作量 工作量飽滿，難度適中。 0.5 5 4 3 2 說明書的 質(zhì)量 說明書立論正確，論述充分，結(jié)論嚴(yán)謹(jǐn)合理， 文字通順，技術(shù)用語(yǔ)準(zhǔn)確，符號(hào)統(tǒng)一，編號(hào)齊 全，圖表完備，書寫工整規(guī)范。 0.3 5 4 3 2 評(píng)閱教師評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 4） 分 加權(quán)分合計(jì) 評(píng) 閱 教 師 簽 名： 年 月 日 答 辯 小 組 評(píng) 審 意 見 評(píng)價(jià)內(nèi)容 具 體 要 求 權(quán)重 評(píng) 分 加權(quán)分 學(xué)生匯報(bào) 匯報(bào)準(zhǔn)備充分，思路清晰；語(yǔ)言表達(dá)準(zhǔn)確，概 念清楚，論點(diǎn)正確，有層次，有重點(diǎn)，基本上 反映了所完成任務(wù)的全部?jī)?nèi)容；時(shí)間符合要求。 0.5 5 4 3 2 答 辯 思路清晰；回答問題有理論依據(jù)，基本概念清楚；主要問題回答準(zhǔn)確，深入，有說服力。 0.5 5 4 3 2 答辯小組評(píng)審成績(jī) （加權(quán)分合計(jì)乘以 8） 分 加權(quán)分合計(jì) 答辯小組教師簽名： 年 月 日 課 程 設(shè) 計(jì) 總 評(píng) 成 績(jī) 分 摘 要 某城市要在其各個(gè)轄區(qū)之間修建地鐵來(lái)加快經(jīng)濟(jì)的發(fā)展，但由于建設(shè)地鐵的費(fèi)用昂貴， 因此需合理安排地鐵的建設(shè)路線，使乘客可以沿地鐵到達(dá)各個(gè)轄區(qū)，并使總的建設(shè)費(fèi)用最小。 地鐵建設(shè)可以緩解城市交通壓力。城市交通問題，已經(jīng)成為現(xiàn)代人無(wú)法面對(duì)的通病。經(jīng)濟(jì)發(fā) 展，汽車數(shù)量增長(zhǎng)速度，遠(yuǎn)遠(yuǎn)快于城市道路的擴(kuò)張速度。地鐵這個(gè)交通的特點(diǎn)就是到達(dá)的快 捷性和可靠性，運(yùn)載能力強(qiáng)，能夠在很短的時(shí)間運(yùn)輸大量的人群。運(yùn)行中不塞車，是城市中 最具可靠性的交通工具。第二、增加地鐵交通體系，可以使城市規(guī)劃更加科學(xué)和合理?？梢?節(jié)約能源。緩解對(duì)石油、天然氣消耗的壓力?？梢詼p少污染。地鐵這種交通工具污染少。可 以節(jié)省時(shí)間。因?yàn)椴蝗嚕俣瓤?，?jié)省上班族上下班的在途時(shí)間。 因此我們小組利用數(shù)據(jù)結(jié)構(gòu)輸入各條線路起點(diǎn)、終點(diǎn)和直接距離，建立無(wú)向圖，鄰接矩 陣存儲(chǔ)輸出鄰接矩陣中的普利姆算法計(jì)算最小生成樹輸出最有線路。 關(guān)鍵詞 數(shù)據(jù)結(jié)構(gòu) 最小生成樹 地鐵 鄰接矩陣 目 錄 摘 要 .I 第一章 問題分析 .1 1.1 引言 .1 1.2 背景 .1 1.3 分析 .1 1.3.1 調(diào)試過程中的問題 .1 第二章 原理與運(yùn)行環(huán)境 .2 2.1 數(shù)據(jù)理論 .2 2.1.1 地鐵問題的數(shù)據(jù)理論 .2 2.2 運(yùn)行環(huán)境 .2 2.2.1 打開方法 .2 2.2.2 打開 MICROSOFT VISUAL STDIO6.0 運(yùn)行環(huán)境 .3 2.2.3 源程序的建立與編輯、連接 .4 第三章 系統(tǒng)分析與設(shè)計(jì) .6 3.1 地鐵建設(shè)問題分析與設(shè)計(jì) .6 3.1.1 系統(tǒng)的功能 .6 第四章 系統(tǒng)功能實(shí)現(xiàn) .7 4.1 地鐵建設(shè)問題的系統(tǒng)功能實(shí)現(xiàn) .7 4.1.1 定義主函數(shù) .7 4.1.2 創(chuàng)建結(jié)構(gòu)體數(shù)組，存儲(chǔ)轄區(qū)名 .8 4.1.3 創(chuàng)建無(wú)向圖，鄰接矩陣存儲(chǔ) .9 4.1.4 輸出鄰接矩陣 .10 4.1.5 普利姆算法求最小生成樹，輸出最優(yōu)路線 .11 結(jié)論 .14 致謝 .15 參考文獻(xiàn) .16 第一章 問題分析 1.1 引言 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定 關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效 率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。 一般認(rèn)為，一個(gè)數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來(lái)的。對(duì)數(shù)據(jù)元素間邏 輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計(jì)算機(jī)內(nèi)存儲(chǔ)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(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)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理 的效率。在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)基本的設(shè)計(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ì)反 過來(lái)，我們根據(jù)特定算法來(lái)選擇數(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è)計(jì)方法和程序設(shè)計(jì)語(yǔ)言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言 就是其中之一。 本次課程設(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)建地上地下立體交通體系，并通過與其 他交通方式的有機(jī)銜接，將極大地緩解城市交通擁堵狀況，解決人民群眾出行難的問題，于 是我們建立了地鐵建設(shè)項(xiàng)目。 1.3 分析 1.3.1 調(diào)試過程中的問題 1.調(diào)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析： 開始準(zhǔn)備將轄區(qū)名和相應(yīng)距離同存儲(chǔ)在鄰接矩陣中，但因?yàn)閿?shù)據(jù)類型不同，這個(gè)想法 難以實(shí)現(xiàn)；而且就算實(shí)現(xiàn)了，在后面的程序中操作也非常麻煩。所以我創(chuàng)建了一個(gè)結(jié)構(gòu)體數(shù) 組用來(lái)存儲(chǔ)轄區(qū)名，這樣轄區(qū)名和數(shù)組下標(biāo)一一對(duì)應(yīng)，簡(jiǎn)明、易懂、清晰。以后只要看數(shù)字 所對(duì)應(yīng)的下標(biāo)存儲(chǔ)的是哪個(gè)轄區(qū)，就可以將其引用。 運(yùn)行程序時(shí)，我要輸出最優(yōu)路線對(duì)應(yīng)的轄區(qū)，所以在輸出時(shí)要直接引用結(jié)構(gòu)體數(shù)組， 但怎么都不行，我就分模塊來(lái)調(diào)試，最后發(fā)現(xiàn)，原來(lái)是沒有將結(jié)構(gòu)體數(shù)組的地址傳過來(lái)。修 改后，程序運(yùn)行正常。 沒有使用指針，避免了指針指向錯(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ū)名 CreateGraph（）-建立轄區(qū)間直接距離的無(wú)向圖，用鄰接矩陣存儲(chǔ) pri（）-輸出無(wú)向圖的鄰接矩陣 prim（）-普利姆算法計(jì)算無(wú)向圖的最小生成樹，輸出最優(yōu)路線 2輸入的形式和輸入值的范圍： 輸入數(shù)字和字母，字母為轄區(qū)名，數(shù)字為直接距離，名稱個(gè)數(shù) n，線路個(gè)數(shù) e，0<e<n(n-1),直接距離 weigth，0<weigth<99999 3輸出的形式： 最佳建設(shè)路徑為： （轄區(qū)名-轄區(qū)名）-直接路徑 2.2 運(yùn)行環(huán)境 數(shù)據(jù)結(jié)構(gòu)程序的運(yùn)行環(huán)境為 Microsoft 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 運(yùn)行環(huán)境 其工作環(huán)境如圖 2-2 所示。 圖 2-2 Visual C+工作環(huán)境 2.2.3 源程序的建立與編輯、連接 建立 C 語(yǔ)言源程序文件。建立方法：選擇菜單命令“File” “New”或直接點(diǎn)擊對(duì) 話框中的“New ”，如圖 2-3 所示。 圖 2-3 建立 C 語(yǔ)言源程序文件 程序的編輯與編譯。編輯完成后，選擇菜單欄中的“組建”“調(diào)試程序” ， 或者直 接點(diǎn)擊工具欄中“箭頭”按鈕，即可對(duì)程序進(jìn)行編譯。 當(dāng)輸出區(qū)顯示“0 errors， 0 warnings ”時(shí)表示沒有錯(cuò)誤和警告，反之，則會(huì)按序號(hào)列 出錯(cuò)誤和警告。雙擊錯(cuò)誤或警告，編輯標(biāo)志會(huì)出現(xiàn)在源文件可能出錯(cuò)的位置，我們可以在此 對(duì)源程序中的錯(cuò)誤進(jìn)行更改。當(dāng)然有時(shí)提示位置不一定很準(zhǔn)確。 程序的編輯于編譯操作，如圖 2-4 所示。 圖 2-4 程序的編輯與編譯 程序的執(zhí)行。單擊工具欄上的“深紅色感嘆號(hào)”按鈕，即可執(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 所示。 N Y 開始 判斷 0<e<n(n-1) 輸入線路個(gè)數(shù) 建立無(wú)向圖，鄰接矩陣 存儲(chǔ) 輸入轄區(qū)個(gè)數(shù)和轄區(qū)名 輸入各條線路起點(diǎn)、終 點(diǎn)和直接距離 普利姆算法計(jì)算最小生 成樹 輸出最優(yōu)線路和總里程 結(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ū)名 CreateGraph（）-建立轄區(qū)間直接距離的無(wú)向圖，用鄰接矩陣存儲(chǔ) pri（）-輸出無(wú)向圖的鄰接矩陣 prim（）-普利姆算法計(jì)算無(wú)向圖的最小生成樹，輸出最優(yōu)路線 主函數(shù)調(diào)用各模塊的關(guān)系如下： 主函數(shù) main（）調(diào)用 int creatve(city vexmax)創(chuàng)建結(jié)構(gòu)體數(shù)組存儲(chǔ)轄區(qū)名； 主函數(shù) main（）調(diào)用 int CreateGraph(int gmax,int n,void pri(int gmax,int n)建立 無(wú)向圖，用鄰接矩陣存儲(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)線路和總里程。 源代碼如下： void 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è)面后，應(yīng)輸入各個(gè)轄區(qū)名，并調(diào)用函數(shù)對(duì)輸入的轄區(qū)名進(jìn)行存儲(chǔ)。 源代碼如下： int creatve(city vexmax)/創(chuàng)建轄區(qū)名數(shù)組 int i,n; printf(設(shè)置轄區(qū)的個(gè)數(shù): );/城市中轄區(qū)的個(gè)數(shù) scanf(%d, for(i=1;i<n+1;i+)/建立城市轄區(qū)名數(shù)組 printf(第%d個(gè)城市轄區(qū)名稱為: ,i); scanf(%s,vexi.name); return(n); 功能實(shí)現(xiàn)圖 4-2 所示。 圖 4-2 4.1.3 創(chuàng)建無(wú)向圖，鄰接矩陣存儲(chǔ) 按照地鐵建設(shè)問題的要求，要將各個(gè)轄區(qū)為頂點(diǎn)作為圖，并用鄰接矩陣將其存儲(chǔ)。 其源代碼如下： int CreateGraph(int gmax,int n,void pri(int gmax,int n) /* 建立無(wú)向圖 */ int e,i,j,k,v1=0,v2=0,weight=0; printf(輸入可建地鐵線線路個(gè)數(shù):); scanf(%d, while(e=n*(n-1)|n=max) error(); printf(輸入可建地鐵線線路個(gè)數(shù):); scanf(%d, for(i=1;i<=n;i+) for(j=1;j<=n;j+) gij=inf; /* 初始化矩陣，全部元素設(shè)為無(wú)窮大 */ for(k=1;kn|v2n|v1<1|v2<1) error(); printf(輸入第 %d 條線路的起始轄區(qū),終點(diǎn)轄區(qū),直接距離:,k); scanf(%d%d%d, gv1v2=weight; gv2v1=weight; printf(n輸出存儲(chǔ)矩陣:n); pri(g,n); return OK; 功能實(shí)現(xiàn)圖如圖 4-3 所示 圖 4-3 4.1.4 輸出鄰接矩陣 此時(shí)將鄰接矩陣存儲(chǔ)的結(jié)果顯示一下，以便檢查下一步中結(jié)果的正確性。 其源代碼如下： void pri(int gmax,int n) /* 輸出無(wú)向圖的鄰接矩陣 */ 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 普利姆算法求最小生成樹，輸出最優(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條邊的生成樹 */ min=inf; k=0; for(j=2;j<=n;j+) /* 尋找滿足邊的一個(gè)頂點(diǎn)在U,另 一個(gè)頂點(diǎn)在V的最小邊 */ if(lowcostj<min) k=j; s+=min; printf(%s-%s)-%dt,vexclosestk.name,vexk.name,min); lowcostk=0; /* 頂點(diǎn)k加入U(xiǎn) */ for(j=2;j<=n;j+) /* 修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán) 值 */ if(gkj<lowcostj) lowcostj=gkj; closestj=k; printf(n); printf(n修建地鐵最短總里程為:); printf(%d,s); 功能實(shí)現(xiàn)如圖 4-5 所示 圖 4-5 結(jié)論 剛開始拿到題目的時(shí)候，沒有什么思路，就翻書看了普利姆算法，然后也在網(wǎng)上搜索了 相關(guān)的資料。找到有相似的程序，但不符合我的題目的要求，不是鄰接矩陣存儲(chǔ)，輸入輸出 也不行。于是，我們小組就仔細(xì)的看了程序，弄懂之后我們就開始編我的程序。經(jīng)過一個(gè)星 期的奮斗，我們終于是把程序整出來(lái)了。這是一個(gè)堅(jiān)苦而又漫長(zhǎng)的過程?？粗鴦趧?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)的老問題，在函數(shù)調(diào)用時(shí)如果傳值和傳址弄混那么在函數(shù)調(diào)用過程中就會(huì)出 現(xiàn)傳不回地址或者傳回的值為亂碼。在以后的每個(gè)程序中我們一定會(huì)盡自己最大努力，在每 個(gè)程序中我都細(xì)心地去敲入每個(gè)字符，函數(shù)調(diào)用過程中先想明白在往上面寫。我們一定會(huì)繼 續(xù)努力，不辜負(fù)父母和老師對(duì)我的期望！ 致謝 本文是在曹福毅老師和李波老師的熱情關(guān)心和指導(dǎo)下完成的。從課程設(shè)計(jì)的前期準(zhǔn)備工 作到最后的修改，還得到了老師提出的許多寶貴的意見和建議，使我們小組受益非淺。特別 是在最后的測(cè)試修改階段，給我提了很多建議，使我能順利的完成課程設(shè)計(jì)。在短暫的兩周 的相處時(shí)間里，老師淵博的知識(shí)、敏銳的思路和實(shí)事求是的工作作風(fēng)給我留下了深刻的印象， 這促使我們小組有了很大的進(jìn)步，謹(jǐn)此向我的指導(dǎo)老師表示衷心的感謝和崇高的敬意。 在論文完成過程中，我們還得到了很多同學(xué)的熱心幫助，他們?cè)谖覀冏稣n程設(shè)計(jì)的這段 時(shí)間，給予我?guī)椭c支持，這也是我能順利完成課程設(shè)計(jì)的重要因素。本人向他們表示深深 的謝意！ 我們也要感謝和我一起學(xué)習(xí)共同進(jìn)步的其他同學(xué)，有不會(huì)的問題我也常常請(qǐng)教身邊的同 學(xué)。合作的學(xué)習(xí)模式我們間形成了深厚的友誼以及合作精神。這對(duì)我們將來(lái)的學(xué)習(xí)生活和工 作生活將產(chǎn)生積極的影響。只有團(tuán)結(jié)協(xié)作才能更好的完成任務(wù)目標(biāo)。 最后向在百忙之中評(píng)審本文的老師表示衷心的感謝！ 參考文獻(xiàn) 1范策等編著.算法與數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言版） .北京：機(jī)械工業(yè)出版社，2004 2徐孝凱編著.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版） .北京：清華大學(xué)出版社，2006 3徐孝凱.數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高實(shí)用教程（第二版） .北京：清華大學(xué)出版社，2003 4胡學(xué)剛.算法與數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo).北京：清華大學(xué)出版社，1999 5張乃孝等.數(shù)據(jù)結(jié)構(gòu)C+與面向?qū)ο蟮耐緩?北京：高等教育出版社，2001 6耿國(guó)華等.數(shù)據(jù)結(jié)構(gòu)C 語(yǔ)言描述.西安：西安電子科技大學(xué)出版社，2002 7殷人昆.數(shù)據(jù)結(jié)構(gòu)用面向?qū)ο蠓椒ㄅc C+語(yǔ)言描述.北京：清華大學(xué)出版社， 2007 8李春葆.數(shù)據(jù)結(jié)構(gòu)（C 語(yǔ)言）習(xí)題與解析.北京：清華大學(xué)出版社，2002 9鄧俊輝.數(shù)據(jù)結(jié)構(gòu)與算法（Java 描述） .北京：機(jī)械工業(yè)出版社，2006 10張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.電子工業(yè)出版社.2004.10 11張乃孝等.數(shù)據(jù)結(jié)構(gòu)C+與面向?qū)ο蟮耐緩?北京：高等教育出版社，2001 12蘇德富.計(jì)算機(jī)算法設(shè)計(jì)與分析.北京：電子工業(yè)出版社，2001