全國(guó)交通咨詢模擬分解

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告 實(shí)驗(yàn)題目：5組+全國(guó)交通咨詢模擬 班級(jí)：191132-04 姓名：薛福興 學(xué)號(hào)：20131000447 指導(dǎo)老師：郭艷 完成日期：2015年07月 5組+全國(guó)交通模擬咨詢系統(tǒng) 3 1. 需求分析3 1.1、解決問題：3 1.2、程序的功能：3 1.3、輸入和輸出的形式： 3 2. 設(shè)計(jì)4 2.1設(shè)計(jì)思想4 2.2設(shè)計(jì)表示 5 2.3詳細(xì)設(shè)計(jì)5 3. 調(diào)試分析10 4. 用戶手冊(cè)10 5. 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果 10 6. 參考文獻(xiàn)14 7. 總結(jié)14 8. 檢查過后對(duì)程序的修改(07.25) 15 5組+全國(guó)交通模擬咨詢系統(tǒng) 1、需求分析 1.1、解決問題： 城市之間有兩

2、種交通工具：火車和飛機(jī)。出于不同目的的旅客對(duì)交通工具有不同的要求。 例如，因公出差的旅客希望在旅途中的時(shí)間盡可能短， 出門旅游的游客則期望旅費(fèi)盡可能省。 編制一個(gè)全國(guó)城市間的交通咨詢程序，為旅客提供兩種最優(yōu)決策的交通咨詢。 1.2、程序的功能： 讀取城市信息文件并在程序運(yùn)行時(shí)動(dòng)態(tài)加載到內(nèi)存；提供對(duì)城市信息進(jìn)行編輯 （如 添加或刪除）的功能。 讀取列車時(shí)刻表和飛機(jī)航班表并在程序運(yùn)行時(shí)動(dòng)態(tài)加載到內(nèi)存；提供對(duì)列車時(shí)刻表 和飛機(jī)航班表進(jìn)行編輯（增設(shè)或刪除）的功能。 用戶輸入城市起點(diǎn)和終點(diǎn)，以及決策選項(xiàng)（最快到達(dá)或最省錢到達(dá)）后，系統(tǒng)針對(duì) 用戶所選的決策策略提供城市起點(diǎn)到城市終點(diǎn)間的所有不重復(fù)的可行方案

3、（按照最優(yōu)到最差 的順序排序輸出）。全程只考慮一種交通工具。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)應(yīng)盡可能快地實(shí)現(xiàn)查詢和排序。 旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。 咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。 1.3、輸入和輸出的形式： 功能：模擬全國(guó)交通咨詢系統(tǒng)對(duì)費(fèi)用或運(yùn)行時(shí)間的最佳方案進(jìn)行排序。 數(shù)據(jù)流入：將站臺(tái)、鐵路線的信息通過讀取文件的方式進(jìn)行對(duì)圖的建立。 數(shù)據(jù)流出：在退出程序時(shí)對(duì)修改過的文件進(jìn)行保存。 程序流程圖：資源管理器流程圖如圖 2 設(shè)計(jì) 2.1設(shè)計(jì)思想 一、數(shù)據(jù)與操作的特性 數(shù)據(jù)特性分析 在本項(xiàng)目共包含2大類。 1.1.1）AdjLWGraph 類 AdjLWGraph類為圖的鄰接表，內(nèi)含seqlis

4、t類的頂點(diǎn)Vertices私有數(shù)據(jù)成員，numOfEdges代 表圖中所含邊數(shù)。 1.1.2）Railroadline 類 Railroadline類為鐵路線所含含的信息，number為鐵路線編號(hào)、name為鐵路線的名稱、S_allv 中存儲(chǔ)的為鐵路線所經(jīng)過的站、S_rrl中存儲(chǔ)火車到達(dá)每個(gè)站的時(shí)間、S_orrl中存儲(chǔ)火車在該 點(diǎn)的出發(fā)時(shí)間。 操作特性分析 1.2.1）構(gòu)造兩個(gè)類，分別用于存儲(chǔ)站點(diǎn)（站點(diǎn)之間的聯(lián)系）、鐵路線。 1.2.2）通過讀取文件的格式將數(shù)據(jù)讀入項(xiàng)目中。 1.2.3）通過在已創(chuàng)建好的圖中，對(duì)站點(diǎn)、鐵路線進(jìn)行增加。 1.2.4）通過輸入兩個(gè)站點(diǎn)并選擇最快方式or最省錢方式，并

5、對(duì)所有結(jié)果按升序進(jìn)行排序。 1.2.5）對(duì)站點(diǎn)和鐵路線進(jìn)行增加與刪除。 二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 邏輯結(jié)構(gòu)設(shè)計(jì)： 在AdjLWGraph類中存放著站點(diǎn)，站點(diǎn)中含有每個(gè)站點(diǎn)的名稱、簡(jiǎn)稱、兩點(diǎn)之間所屬鐵 路線、站點(diǎn)的編號(hào)以及和此站點(diǎn)相連的站點(diǎn)的信息。 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)： 通過采取鄰接表的格式，將站與站之間的聯(lián)系進(jìn)行構(gòu)建。在數(shù)據(jù)讀入時(shí)，將鐵路線進(jìn)行 構(gòu)建。 三、算法設(shè)計(jì) 總體設(shè)計(jì) 全國(guó)交通咨詢模擬系統(tǒng) b1 _1 r 選擇區(qū)間 1J 添加or刪除城市 U丄 r計(jì) 增加or刪除時(shí)刻表 - J 選擇決策（省錢or快速） 詢問是否加入鐵路線 添加城帀 刪除城市 * * 添加鐵路 修改鐵路 1 1 3 刪除鐵路 （ 1

6、 修改兩點(diǎn)間的 1 費(fèi)用 主要算法的基本思想 在讀入讀出中，對(duì)圖的點(diǎn)與邊進(jìn)行構(gòu)建，對(duì)鐵路線所經(jīng)過的點(diǎn)與鐵路線的名稱進(jìn)行構(gòu)建。 在找符合條件的所有路線時(shí)，采用遞歸。 在對(duì)所有符合條件的所有可能進(jìn)行組合，并計(jì)算出時(shí)間、與費(fèi)用，采用數(shù)組進(jìn)行存取。 對(duì)所有可能采用快速排序 +插入排序，然后進(jìn)行輸出。 2.2設(shè)計(jì)表示 函數(shù)調(diào)用關(guān)系圖 D皇國(guó)交通西詢模擬一薜福去祇沖可 函數(shù)接口規(guī)格說明 void ifile1( AdjLWGraph II將邊間所 有路線讀岀。讀入引用數(shù)組 S_line中。 void In sertEdge( const int v1, con st int v2, double Mon

7、ey); II在兩個(gè)站點(diǎn)間插入邊與權(quán)值。 Railroadline( int num, string n); II將鐵路線的標(biāo)號(hào)和鐵路的名稱進(jìn)行初始化 II查詢兩點(diǎn)間的所有線路(遞歸) void Circle1( int v0, int j, int k, SeqList m_vec SeqList AdjLWGraph:AdjLWGraph( con st int sz):Vertices(sz) num OfEdges = 0; Vertex(EdgeListNode * ptr =NULL):adjhead(ptr) Vertex(VT d,stri ng n, EdgeListNode

8、 *ptr=NULL):b_ name(d), name( n), nu mber(G _nu mber+),adjhead(ptr) Railroadli ne類中： 在對(duì)鐵路線進(jìn)行構(gòu)造對(duì)鐵路線的編號(hào)、名字、通行標(biāo)志進(jìn)行賦值； railroadline:railroadline（int num string n, string m） :number（ num）, name（ n）, mark（ n） 文件讀入 鐵路線讀入 將鐵路線的所屬編號(hào)、名字、所經(jīng)過的點(diǎn)、所經(jīng)過的點(diǎn)的出發(fā)時(shí)間、到達(dá)時(shí)間進(jìn)行讀入 While （文件未結(jié)束） 讀入鐵路線的編號(hào)、名字 While （a！ =-1） 將經(jīng)過的點(diǎn)存

9、儲(chǔ) While （a！ =-1） 將經(jīng)過的點(diǎn)的出發(fā)時(shí)間存儲(chǔ) While （a！ =-1） 將經(jīng)過的點(diǎn)的到達(dá)時(shí)間存儲(chǔ) 站臺(tái)讀入 將鐵站臺(tái)的名稱、簡(jiǎn)稱進(jìn)行讀入。 將站點(diǎn)與站點(diǎn)的距離進(jìn)行讀入。 while （1） 將站臺(tái)的名稱、編號(hào)、簡(jiǎn)稱讀入 對(duì)圖進(jìn)行初始化（既將點(diǎn)添加入圖中） 將兩點(diǎn)間的權(quán)值讀入圖中 增加站點(diǎn) 刪除站臺(tái) Void Delete_city（） 輸入要?jiǎng)h除的城市 for （所有線路） 將鐵路線中所含有該城市的點(diǎn)刪除并修改該點(diǎn)后面站點(diǎn)的出發(fā)與到達(dá)時(shí)間; 增加該城市在此條線路前后兩個(gè)站點(diǎn)的權(quán)值； If （該城市位于此鐵路線最后一個(gè)） If （該點(diǎn)與前一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊 Els

10、e刪除該邊儲(chǔ)存的此條鐵路線 Else If（該城市位于此鐵路線第一個(gè)） If （該點(diǎn)與后一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊 Else刪除該邊儲(chǔ)存的此條鐵路線 Else If （該點(diǎn)與前一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊 Else刪除該邊儲(chǔ)存的此條鐵路線 If （該點(diǎn)與后一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊 Else刪除該邊儲(chǔ)存的此條鐵路線 兩個(gè)站臺(tái)之間的所有路線可能排序 1 ! 采用快速排序+插入排序進(jìn)行排序 L 按升序?qū)⑺薪Y(jié)果輸出 排序功能 void quickSort( Num( /先調(diào)用改進(jìn)算法 Qsort使之基本有序 長(zhǎng)度大于k時(shí)遞歸,k為指定的數(shù) 并調(diào)用的Partition 算法 Part

11、ition函數(shù)為將小于基準(zhǔn)的數(shù)放基準(zhǔn)數(shù)前，將大于基準(zhǔn)的數(shù)放基準(zhǔn)數(shù)后 再用插入排序?qū)居行蛐蛄信判?3 .調(diào)試分析 (1 )調(diào)試過程中遇到的問題解決與分析； 開始最大的難點(diǎn)是如何將各點(diǎn)之間的信息進(jìn)行建立。在對(duì)各鐵路線增加時(shí)，通過不斷調(diào) 試和修改，將一些未考慮情況增加了一些判斷和循環(huán)，從而使各站點(diǎn)之間的信息進(jìn)行較好的 建立。其次是對(duì)路線的查找，采用遞歸，通過不斷地調(diào)試，將所有路線找出，在計(jì)算一條線 路中所用到的時(shí)間時(shí)，由于使用過多的結(jié)構(gòu)體，使得在寫程序時(shí)過于復(fù)雜，為了解決這一問 題，最終將所有點(diǎn)所包括的一些信息用有意義的英文字符表示，增加了程序的可讀性，使得 讀寫時(shí)更加通俗易懂。 (2 )算法的

12、時(shí)間空間復(fù)雜度分析： 剛開始對(duì)費(fèi)用和時(shí)間進(jìn)行排序時(shí)使用的是冒泡排序，時(shí)間復(fù)雜度為0(n2)使用效率并不 高，后經(jīng)過對(duì)比采用快速排序+插入排序，此排序既降低了時(shí)間復(fù)雜度，同時(shí)也避免了當(dāng)原 本序列為順序時(shí)，時(shí)間復(fù)雜度降為冒泡排序。 4. 用戶手冊(cè) 1) 在壓縮包里含有 測(cè)試數(shù)據(jù).txt,將文本中的內(nèi)容復(fù)制、粘貼到運(yùn)行程序的控制臺(tái)中，程序 將會(huì)實(shí)現(xiàn)各個(gè)功能。 2) Railroadline.txt文件中各數(shù)據(jù)的說明： o 8 0 5 o o 0 3 8 8 1 K o 4 4 7 2 6 8 2 7 7 8 3 1 3 -P 5 1 1 n 一 2 2 i 50 線錢 Ir4r6 驚 41717 鐵

13、鐵 / 4 9 / 9 o 9 4 8 O 18 8 2 2 達(dá)發(fā) 到岀 毀口臺(tái) SS站 過I 經(jīng)在在 線線線 扶鐵鐵 3) Vertex.txt文件中各數(shù)據(jù)的說明： 0/站臺(tái)編號(hào) Be i J/站臺(tái)簡(jiǎn)稱 北京/站臺(tái)名稱 4 仃 Hul X9二-:汗 20036032 4 0 1 丄 780572264 800581137 212624453 詁臺(tái)1的編號(hào)、站臺(tái)2的編號(hào)、站臺(tái)1與站臺(tái)澗的費(fèi)用 5. 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果 1)選擇出行方式 火車 根據(jù)選擇，系統(tǒng)對(duì)飛機(jī)或火車交通圖進(jìn)行構(gòu)建 2）選擇區(qū)間 E:vs2O12的扁哩文件全國(guó)交謹(jǐn)咨詢模擬Y福興Dmbug徒國(guó)交通咨詢腳一薛H.exe| = |間

14、 選擇區(qū)間 選擇岀發(fā)地 選擇目的地 2鬣附 北京 1、 運(yùn)春番站臺(tái)為:北京一-石家莊鄭州武長(zhǎng)沙-株洲一-廣州 経過的路線為：1000 1000 1000 1000 1000 1000 曲耗日寸為：祁小時(shí)4分鐘 總費(fèi)甬:2304 SSffi站臺(tái)為：北京一-天津一-濟(jì)南一-.一鄭州一-武JX長(zhǎng)沙一- 株洲一. 路線為：10011001100110041000100010001000 為:旺小時(shí)45分鐘 =56小時(shí)45分鐘 總費(fèi)甬:2?93 產(chǎn)春前站臺(tái)為:北京一-石家莊鄭州武長(zhǎng)沙一-株洲一-廣州 會(huì). 用 過耗費(fèi) 經(jīng)總總 線為:10161016 :57小時(shí)19分鐘 2304 迓壽前站臺(tái)為:北京一-石

15、家莊一-鄭州一-武漢一-長(zhǎng)沙一-株洲一-廣州 3）添加城市 4）刪除城市 卜増加城市 卜除城帀 L刪除城市的名字 Sts 5）增加列車 -増加列李 fei 4、修玫兩點(diǎn)間的費(fèi)用 詁輸入火車的名字 K49? 需添加的站臺(tái)的個(gè)數(shù) 北京0 亡世石家莊2 鄭州M 武漢4 長(zhǎng)沙5 株洲召上褥？藥津& 迸吏9 三州H 西女加 灑勅：烏魯木拆眈阿址山口辭 玉雞24W25鍵稜優(yōu)陋 探圳2 命輸入所需經(jīng)過的站（標(biāo)號(hào)八出發(fā)時(shí)間、到達(dá)時(shí)間： 1 546 5毘0 27訊0 &騎 12 730 ?45 站臺(tái)廣州到站臺(tái)探圳的費(fèi)用 103 站臺(tái)深圳到站臺(tái)九曲的費(fèi)用 50 6）刪除列車 卜増加創(chuàng)至 :ii：j| 矢修改兩占間

16、的費(fèi)用 輸入要?jiǎng)h除的列車的名稱 94321 7）修改列車 8）修改兩點(diǎn)間的費(fèi)用 幘輸入你所要操作的數(shù)字 3 増加列 列 k、 2 處修改兩點(diǎn)間的費(fèi)用 4 輸人要修改哪個(gè)城市到哪個(gè)城市的費(fèi)用 6. 參考文獻(xiàn) 數(shù)據(jù)結(jié)構(gòu)（C+語言描述）（朱戰(zhàn)力著） 7 .總結(jié) 此次上機(jī)實(shí)驗(yàn)應(yīng)用了圖實(shí)現(xiàn)了全國(guó)交通咨詢模擬系統(tǒng)，在此次編程中，我不僅對(duì)此次編 譯程序的算法思想有了新的認(rèn)識(shí)，還讓我深刻的體會(huì)到了圖的重要性以及其應(yīng)用的方便，并 且對(duì)鄰接表加深了印象， 應(yīng)用了書本中的算法思想， 對(duì)我以后的編譯以及完成新的程序有很 大的幫助。 通過這次課程設(shè)計(jì)練習(xí)， 使我更深刻地理解了圖的使用。完成整個(gè)程序設(shè)計(jì)使我對(duì)圖和 鄰接表

17、的掌握的更加熟練，同時(shí)采用數(shù)組，對(duì)存儲(chǔ)的內(nèi)部更加了解。 同時(shí)通過計(jì)算最短用時(shí)和最少費(fèi)用并對(duì)其采用快速排序+插入排序，使用遞歸實(shí)現(xiàn)一些 的功能，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識(shí)。并在完成課程設(shè)計(jì)的過程主動(dòng)查閱了相關(guān)資料， 學(xué)到了不少課本上沒有的技術(shù)知識(shí)。 經(jīng)過這次課程設(shè)計(jì)，我深刻認(rèn)識(shí)到算法在程序設(shè)計(jì)中的重要性，一個(gè)完整的程序總是由 若干個(gè)函數(shù)構(gòu)成的，這些相應(yīng)的函數(shù)體現(xiàn)了算法的基本思想。 編程是一件枯燥乏味工作，但是只要認(rèn)真鉆研，我們會(huì)從中學(xué)到很多在課本上學(xué)不到或 者無法在課堂上掌握的知識(shí)，同時(shí)也能從中感受到編程的樂趣。興趣是可以培養(yǎng)的，只要堅(jiān) 持下去，面對(duì)困難我們總能夠找到解決問題的方法。 8.檢查過后對(duì)程序的修改（07.25） 在檢查過程中，發(fā)現(xiàn)我對(duì)數(shù)據(jù)的排序?qū)懙牟缓茫?采用冒泡排序，大大增加了程序的時(shí)間 和空間