東北大學歐洲旅行數(shù)據(jù)結(jié)構(gòu)作業(yè)

1、數(shù)據(jù)結(jié)構(gòu)3部分設計函數(shù)描述部分設計函數(shù)描述?RailSystem(conststring輸出兩城市間的最少費用的路徑，調(diào)用calc_route(stringfromstringto)函數(shù)計算最少費用?calc_route(stringfromstringto)使用迪杰斯特拉算法計算from和to兩個城市間的最少費用的路徑（3）簡短明確地寫出你實驗所采用的存儲結(jié)構(gòu)及其用途，詳細說明其中的屬性的含義。1)mapoutgoing_servic

2、es用來保存由一個城市出發(fā)可以直接到達的城市名及這兩個城市之間的路徑信息。2)listms以service為指針的list表，保存兩城市間的路徑。3)mapcities用來保存所有城市信息，通過城市名查找該城市有關(guān)信息。4)priity_queueCheapestcidates存儲候選的遍歷城市，City是優(yōu)先隊列存儲的對象類型，vect是該對象的向量集合，Cheapest是比較規(guī)則。三、實驗環(huán)境三、實驗環(huán)境操作系統(tǒng)Win7、調(diào)試軟件V

3、S2012四、實驗過程與分析四、實驗過程與分析（1）描述你在進行實現(xiàn)時，主要的函數(shù)或操作內(nèi)部的主要算法，分析這個算法的時、空復雜度，并說明你設計的巧妙之處。該實驗主要用到了迪杰斯特拉算法，這個算法要求所有邊的權(quán)值非負，提出了按路徑長度遞增的順序逐步產(chǎn)生最短路徑的算法，首先求出長度最短的一條路徑，然后參照它求出長度次短的一條路徑，以此類推，指導頂點到其他頂點的最短路徑全部求完為止即可解決該實驗的問題。算法的時間復雜度是，空間復雜度為)(2

4、nO)(nO1)calc_route(stringfromstringto)函數(shù)利用優(yōu)先權(quán)隊列和迪杰斯特拉算法，計算任意兩城市之間費用最少的路徑，優(yōu)先權(quán)隊列按照費用由大到小的順序入隊。首先初始化所有城市的信息。通過迭代器遍歷它的鄰接鏈表，得到鄰接城市名，當這個城市未被被訪問過且從彈出的城市到該城市的費用大于這兩個鄰接城市間費用和出發(fā)城市目前的最少費用之和，更新從出發(fā)城市到該城市的費用，并且記錄這個城市的經(jīng)由城市為彈出的城市名并將這個城市