全國交通咨詢模擬

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告實(shí)驗(yàn)題目：5組+全國交通咨詢模擬班級：-04姓名：薛福興學(xué)號：指導(dǎo)老師：郭艷完成日期：2015年07月5組 + 全國交通模擬咨詢系統(tǒng)31、需求分析31.1、解決問題：31.2、程序的功能：31.3、輸入和輸出的形式：32設(shè)計(jì)42.1 設(shè)計(jì)思想42.2 設(shè)計(jì)表示 52.3 詳細(xì)設(shè)計(jì)53調(diào)試分析104用戶手冊105測試數(shù)據(jù)及測試結(jié)果106參考文獻(xiàn)147總結(jié)148檢查過后對程序的修改(07.25)155組 + 全國交通模擬咨詢系統(tǒng)1、需求分析 1.1、解決問題： 城市之間有兩種交通工具：火車和飛機(jī)。出于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時(shí)間盡

2、可能短，出門旅游的游客則期望旅費(fèi)盡可能省。編制一個(gè)全國城市間的交通咨詢程序，為旅客提供兩種最優(yōu)決策的交通咨詢。1.2、程序的功能： 1 讀取城市信息文件并在程序運(yùn)行時(shí)動(dòng)態(tài)加載到內(nèi)存；提供對城市信息進(jìn)行編輯（如添加或刪除）的功能。2 讀取列車時(shí)刻表和飛機(jī)航班表并在程序運(yùn)行時(shí)動(dòng)態(tài)加載到內(nèi)存；提供對列車時(shí)刻表和飛機(jī)航班表進(jìn)行編輯（增設(shè)或刪除）的功能。3 用戶輸入城市起點(diǎn)和終點(diǎn)，以及決策選項(xiàng)（最快到達(dá)或最省錢到達(dá)）后，系統(tǒng)針對用戶所選的決策策略提供城市起點(diǎn)到城市終點(diǎn)間的所有不重復(fù)的可行方案（按照最優(yōu)到最差的順序排序輸出）。全程只考慮一種交通工具。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)應(yīng)盡可能快地實(shí)現(xiàn)查詢和排序。4 旅途中耗費(fèi)的

3、總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。5 咨詢以用戶和計(jì)算機(jī)的對話方式進(jìn)行。1.3、輸入和輸出的形式： 1 功能：模擬全國交通咨詢系統(tǒng)對費(fèi)用或運(yùn)行時(shí)間的最佳方案進(jìn)行排序。2 數(shù)據(jù)流入：將站臺、鐵路線的信息通過讀取文件的方式進(jìn)行對圖的建立。3 數(shù)據(jù)流出：在退出程序時(shí)對修改過的文件進(jìn)行保存。4 程序流程圖：資源管理器流程圖如圖2設(shè)計(jì) 2.1 設(shè)計(jì)思想 一、數(shù)據(jù)與操作的特性 1 數(shù)據(jù)特性分析在本項(xiàng)目共包含2大類。1.1.1)AdjLWGraph類AdjLWGraph類為圖的鄰接表，內(nèi)含seqlist類的頂點(diǎn)Vertices私有數(shù)據(jù)成員，numOfEdges代表圖中所含邊數(shù)。1.1.2)Railroadli

4、ne類Railroadline類為鐵路線所含含的信息，number為鐵路線編號、name為鐵路線的名稱、S_allv中存儲(chǔ)的為鐵路線所經(jīng)過的站、S_rrl中存儲(chǔ)火車到達(dá)每個(gè)站的時(shí)間、S_orrl中存儲(chǔ)火車在該點(diǎn)的出發(fā)時(shí)間。2 操作特性分析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)建好的圖中，對站點(diǎn)、鐵路線進(jìn)行增加。1.2.4)通過輸入兩個(gè)站點(diǎn)并選擇最快方式or最省錢方式，并對所有結(jié)果按升序進(jìn)行排序。1.2.5)對站點(diǎn)和鐵路線進(jìn)行增加與刪除。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1 邏輯結(jié)構(gòu)設(shè)計(jì)： 在AdjLWGraph類

5、中存放著站點(diǎn)，站點(diǎn)中含有每個(gè)站點(diǎn)的名稱、簡稱、兩點(diǎn)之間所屬鐵路線、站點(diǎn)的編號以及和此站點(diǎn)相連的站點(diǎn)的信息。2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)： 通過采取鄰接表的格式，將站與站之間的聯(lián)系進(jìn)行構(gòu)建。在數(shù)據(jù)讀入時(shí)，將鐵路線進(jìn)行構(gòu)建。三、算法設(shè)計(jì) 1 總體設(shè)計(jì)選擇區(qū)間添加or刪除城市增加or刪除時(shí)刻表添加城市刪除城市選擇決策(省錢or快速）全國交通咨詢模擬系統(tǒng)詢問是否加入鐵路線添加鐵路刪除鐵路修改鐵路修改兩點(diǎn)間的費(fèi)用2 主要算法的基本思想 在讀入讀出中，對圖的點(diǎn)與邊進(jìn)行構(gòu)建，對鐵路線所經(jīng)過的點(diǎn)與鐵路線的名稱進(jìn)行構(gòu)建。 在找符合條件的所有路線時(shí)，采用遞歸。 在對所有符合條件的所有可能進(jìn)行組合，并計(jì)算出時(shí)間、與費(fèi)用，采用數(shù)

6、組進(jìn)行存取。 對所有可能采用快速排序+插入排序，然后進(jìn)行輸出。2.2 設(shè)計(jì)表示 1 函數(shù)調(diào)用關(guān)系圖2 函數(shù)接口規(guī)格說明void ifile1(AdjLWGraph &g2) /將圖進(jìn)行讀入，通過引用修改圖。void GetEdgRoadline(const int v1,const int v2,SeqList &S_line)const; /將邊間所有路線讀出。讀入引用數(shù)組S_line中。void InsertEdge(const int v1, const int v2, double Money); /在兩個(gè)站點(diǎn)間插入邊與權(quán)值。Railroadline(int num,string n)

7、; /將鐵路線的標(biāo)號和鐵路的名稱進(jìn)行初始化/查詢兩點(diǎn)間的所有線路(遞歸)void Circle1(int v0, int j, int k, SeqList m_vec, SeqList &m_total,Edg &w)/此函數(shù)傳入所有邊的信息、m_total用于存儲(chǔ)所有符合條件的路線所經(jīng)過的點(diǎn)。/查詢兩點(diǎn)間的所有線路的所有可能（裝站or不轉(zhuǎn)）和算時(shí)間和費(fèi)用(遞歸)void Circle2(int vi,int vj,int i,int j,int v_end,SeqList &temp,SeqList &M_t,AdjLWGraph &G,SeqList &S_rrl)/此函數(shù)傳入?yún)?shù)有：M

8、_t所有符合條件的路線、temp存放某條路線所經(jīng)過點(diǎn)之間的線路、S_rrl存儲(chǔ)對所有是否轉(zhuǎn)站的可能進(jìn)行存入。三、數(shù)據(jù)類型定義AdjLWGraph類AdjLWGraph類為圖的鄰接表，內(nèi)含seqlist類的頂點(diǎn)Vertices私有數(shù)據(jù)成員，numOfEdges代表圖中所含邊數(shù)。Railroadline類Railroadline類為鐵路線所含含的信息，number為鐵路線編號、name為鐵路線的名稱、S_allv中存儲(chǔ)的為鐵路線所經(jīng)過的站、S_rrl中存儲(chǔ)火車到達(dá)每個(gè)站的時(shí)間、S_orrl中存儲(chǔ)火車在該點(diǎn)的出發(fā)時(shí)間。2.3 詳細(xì)設(shè)計(jì) （6個(gè)主要功能）1 構(gòu)造數(shù)據(jù)類型AdjLWGraph類中：在對圖

9、進(jìn)行構(gòu)建的同時(shí)，也要對每個(gè)站點(diǎn)與站點(diǎn)之間的聯(lián)系進(jìn)行構(gòu)造；AdjLWGraph:AdjLWGraph(const int sz):Vertices(sz)numOfEdges = 0;Vertex(EdgeListNode * ptr =NULL):adjhead(ptr) Vertex(VT d,string n, EdgeListNode *ptr=NULL):b_name(d),name(n),number(G_number+),adjhead(ptr)Railroadline類中：在對鐵路線進(jìn)行構(gòu)造對鐵路線的編號、名字、通行標(biāo)志進(jìn)行賦值；railroadline:railroadline

10、(int num, string n, string m) :number(num), name(n), mark(m)2 文件讀入鐵路線讀入 將鐵路線的所屬編號、名字、所經(jīng)過的點(diǎn)、所經(jīng)過的點(diǎn)的出發(fā)時(shí)間、到達(dá)時(shí)間進(jìn)行讀入While（文件未結(jié)束）讀入鐵路線的編號、名字While（a！=-1）將經(jīng)過的點(diǎn)存儲(chǔ)While（a！=-1）將經(jīng)過的點(diǎn)的出發(fā)時(shí)間存儲(chǔ)While（a！=-1）將經(jīng)過的點(diǎn)的到達(dá)時(shí)間存儲(chǔ)站臺讀入 將鐵站臺的名稱、簡稱進(jìn)行讀入。 將站點(diǎn)與站點(diǎn)的距離進(jìn)行讀入。while (1)將站臺的名稱、編號、簡稱讀入對圖進(jìn)行初始化（既將點(diǎn)添加入圖中）將兩點(diǎn)間的權(quán)值讀入圖中3 增加站點(diǎn)輸入站點(diǎn)名稱與簡

11、稱是否加入已有鐵路線YN輸入需加入鐵路線名稱退出輸入需插入的位置對該鐵路線進(jìn)行更新4 刪除站臺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)過）刪除邊Else 刪除該邊儲(chǔ)存的此條鐵路線Else If（該城市位于此鐵路線第一個(gè)）If（該點(diǎn)與后一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊Else 刪除該邊儲(chǔ)存的此條鐵路線ElseIf（該點(diǎn)與前一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊Else 刪除該邊儲(chǔ)存的此條鐵路線If（

12、該點(diǎn)與后一個(gè)站點(diǎn)只有一條鐵路經(jīng)過）刪除邊Else 刪除該邊儲(chǔ)存的此條鐵路線5 兩個(gè)站臺之間的所有路線可能排序輸入兩個(gè)站臺選擇決策最快方式最省錢方式采用快速排序+插入排序進(jìn)行排序采用遞歸將兩個(gè)站臺間所有路線找出采用遞歸將所有路線的可能進(jìn)行組合存儲(chǔ)并計(jì)算時(shí)間與費(fèi)用（兩點(diǎn)之間存在多條鐵路線的情況）按升序?qū)⑺薪Y(jié)果輸出6 排序功能void quickSort(Num (&r)100, int n, int k) qsort_improve(r,0,n,k);/先調(diào)用改進(jìn)算法Qsort使之基本有序 長度大于k時(shí)遞歸, k為指定的數(shù) 并調(diào)用的Partition算法 Partition函數(shù)為將小于基準(zhǔn)的數(shù)放

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

14、用的是冒泡排序，時(shí)間復(fù)雜度為O(n2)使用效率并不高，后經(jīng)過對比采用快速排序+插入排序，此排序既降低了時(shí)間復(fù)雜度，同時(shí)也避免了當(dāng)原本序列為順序時(shí)，時(shí)間復(fù)雜度降為冒泡排序。4用戶手冊 1) 在壓縮包里含有測試數(shù)據(jù).txt,將文本中的內(nèi)容復(fù)制、粘貼到運(yùn)行程序的控制臺中，程序?qū)?huì)實(shí)現(xiàn)各個(gè)功能。2) Railroadline.txt文件中各數(shù)據(jù)的說明：3) Vertex.txt文件中各數(shù)據(jù)的說明：4) Edge.txt文件中各數(shù)據(jù)的說明：5測試數(shù)據(jù)及測試結(jié)果 1) 選擇出行方式根據(jù)選擇，系統(tǒng)對飛機(jī)或火車交通圖進(jìn)行構(gòu)建2) 選擇區(qū)間3) 添加城市4) 刪除城市5) 增加列車6) 刪除列車7) 修改列車8

15、) 修改兩點(diǎn)間的費(fèi)用6參考文獻(xiàn) 數(shù)據(jù)結(jié)構(gòu)（c+語言描述）（朱戰(zhàn)力著）7總結(jié) 此次上機(jī)實(shí)驗(yàn)應(yīng)用了圖實(shí)現(xiàn)了全國交通咨詢模擬系統(tǒng)，在此次編程中，我不僅對此次編譯程序的算法思想有了新的認(rèn)識，還讓我深刻的體會(huì)到了圖的重要性以及其應(yīng)用的方便，并且對鄰接表加深了印象，應(yīng)用了書本中的算法思想，對我以后的編譯以及完成新的程序有很大的幫助。 通過這次課程設(shè)計(jì)練習(xí)，使我更深刻地理解了圖的使用。完成整個(gè)程序設(shè)計(jì)使我對圖和鄰接表的掌握的更加熟練，同時(shí)采用數(shù)組，對存儲(chǔ)的內(nèi)部更加了解。 同時(shí)通過計(jì)算最短用時(shí)和最少費(fèi)用并對其采用快速排序+插入排序，使用遞歸實(shí)現(xiàn)一些的功能，加深了對數(shù)據(jù)結(jié)構(gòu)的理解和認(rèn)識。并在完成課程設(shè)計(jì)的過程主動(dòng)查閱了相關(guān)資料，學(xué)到了不少課本上沒有的技術(shù)知識。 經(jīng)過這次課程設(shè)計(jì)，我深刻認(rèn)識到算法在程序設(shè)計(jì)中的重要性，一個(gè)完整的程序總是由若干個(gè)函數(shù)構(gòu)成的，這些相應(yīng)的函數(shù)體現(xiàn)了算法的基本思想。 編程是一件枯燥乏味工作，但是只要認(rèn)真鉆研，我們會(huì)從中學(xué)到很多在課本上學(xué)不到或者無法在課堂上掌握的知識，同時(shí)也能從中感受到編程的樂趣。興趣是可以培養(yǎng)的，只要堅(jiān)持下去，面對困難我們總能夠找到解決問題的方法。8檢查過后對程序的修改(07.25)在檢查過程中，發(fā)現(xiàn)我對數(shù)據(jù)的排序?qū)懙牟缓?，采用冒泡排序，大大增加了程序的時(shí)間和空間的復(fù)雜度，在經(jīng)過對排序的對比