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

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

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

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

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