全國交通咨詢模擬分解

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

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

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

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

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

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

7、ey); II在兩個站點間插入邊與權(quán)值。 Railroadline( int num, string n); II將鐵路線的標(biāo)號和鐵路的名稱進行初始化 II查詢兩點間的所有線路(遞歸) 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類中： 在對鐵路線進行構(gòu)造對鐵路線的編號、名字、通行標(biāo)志進行賦值； railroadline:railroadline（int num string n, string m） :number（ num）, name（ n）, mark（ n） 文件讀入 鐵路線讀入 將鐵路線的所屬編號、名字、所經(jīng)過的點、所經(jīng)過的點的出發(fā)時間、到達時間進行讀入 While （文件未結(jié)束） 讀入鐵路線的編號、名字 While （a！ =-1） 將經(jīng)過的點存

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

10、e刪除該邊儲存的此條鐵路線 Else If（該城市位于此鐵路線第一個） If （該點與后一個站點只有一條鐵路經(jīng)過）刪除邊 Else刪除該邊儲存的此條鐵路線 Else If （該點與前一個站點只有一條鐵路經(jīng)過）刪除邊 Else刪除該邊儲存的此條鐵路線 If （該點與后一個站點只有一條鐵路經(jīng)過）刪除邊 Else刪除該邊儲存的此條鐵路線 兩個站臺之間的所有路線可能排序 1 ! 采用快速排序+插入排序進行排序 L 按升序?qū)⑺薪Y(jié)果輸出 排序功能 void quickSort( Num( /先調(diào)用改進算法 Qsort使之基本有序 長度大于k時遞歸,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ào) 試和修改，將一些未考慮情況增加了一些判斷和循環(huán)，從而使各站點之間的信息進行較好的 建立。其次是對路線的查找，采用遞歸，通過不斷地調(diào)試，將所有路線找出，在計算一條線 路中所用到的時間時，由于使用過多的結(jié)構(gòu)體，使得在寫程序時過于復(fù)雜，為了解決這一問 題，最終將所有點所包括的一些信息用有意義的英文字符表示，增加了程序的可讀性，使得 讀寫時更加通俗易懂。 (2 )算法的

12、時間空間復(fù)雜度分析： 剛開始對費用和時間進行排序時使用的是冒泡排序，時間復(fù)雜度為0(n2)使用效率并不 高，后經(jīng)過對比采用快速排序+插入排序，此排序既降低了時間復(fù)雜度，同時也避免了當(dāng)原 本序列為順序時，時間復(fù)雜度降為冒泡排序。 4. 用戶手冊 1) 在壓縮包里含有 測試數(shù)據(jù).txt,將文本中的內(nèi)容復(fù)制、粘貼到運行程序的控制臺中，程序 將會實現(xiàn)各個功能。 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 達發(fā) 到岀 毀口臺 SS站 過I 經(jīng)在在 線線線 扶鐵鐵 3) Vertex.txt文件中各數(shù)據(jù)的說明： 0/站臺編號 Be i J/站臺簡稱 北京/站臺名稱 4 仃 Hul X9二-:汗 20036032 4 0 1 丄 780572264 800581137 212624453 詁臺1的編號、站臺2的編號、站臺1與站臺澗的費用 5. 測試數(shù)據(jù)及測試結(jié)果 1)選擇出行方式 火車 根據(jù)選擇，系統(tǒng)對飛機或火車交通圖進行構(gòu)建 2）選擇區(qū)間 E:vs2O12的扁哩文件全國交謹(jǐn)咨詢模擬Y福興Dmbug徒國交通咨詢腳一薛H.exe| = |間

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

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

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

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