數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二歐洲旅行

1、實(shí) 驗(yàn) 報 告課程名稱：數(shù)據(jù)結(jié)構(gòu)班級：實(shí)驗(yàn)成績：實(shí)驗(yàn)名稱：歐洲旅行學(xué)號：批閱教師簽字：實(shí)驗(yàn)編號：實(shí)驗(yàn)二姓名實(shí)驗(yàn)日期：2012 年6 月 25 日指導(dǎo)教師：組號：實(shí)驗(yàn)時間：14 時00 分17 時00分一、實(shí)驗(yàn)?zāi)康募由顚D的表示法和圖的基本操作的理解；掌握用圖對實(shí)際問題進(jìn)行抽象的方法；掌握利用鄰接表求解非負(fù)權(quán)值、單源最短路徑的方法，即Dijkstra算法，同時掌握鄰接表的建立以及使用方法；學(xué)會使用STL中的map抽象實(shí)際問題，掌握有關(guān)map的基本操作二、實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟實(shí)驗(yàn)內(nèi)容：使用圖這種抽象的數(shù)據(jù)結(jié)構(gòu)存儲模擬的歐洲鐵路路線圖，應(yīng)用Dijkstra算法求得任意兩個城市之間的最少路費(fèi)，并給出路費(fèi)

2、最少的路徑的長度和所經(jīng)過的城市名。 抽象數(shù)據(jù)類型及設(shè)計函數(shù)描述抽象數(shù)據(jù)類型class City：維護(hù)一個城市的信息，包括城市名name，是否被訪問過的標(biāo)記visted，從某個城市到達(dá)該城市所需的總費(fèi)用total_fee和總路徑長度total_distance，求得最短路徑后路徑中到達(dá)該城市的城市名from_city。class Service：為鐵路系統(tǒng)模擬了兩個城市之間的直接路線，包括兩個城市之間直接到達(dá)的費(fèi)用fee，兩城市之間的直接距離distance，兩個城市間作為目的地的城市名destination。class RailSystem：用鄰接表模擬歐洲鐵路系統(tǒng)，該鄰接表使用數(shù)據(jù)結(jié)構(gòu)map

3、實(shí)現(xiàn)，map的key-value值對的數(shù)據(jù)類型分別為string和list，對應(yīng)出發(fā)城市名和該城市與它能夠到達(dá)的城市之間的Service鏈表。類RailSystem維護(hù)一個用來存儲城市的map，該map的key-value值對的數(shù)據(jù)類型分別為string和City*，對應(yīng)城市名和指向該城市的指針，以訪問該城市的有關(guān)信息設(shè)計函數(shù)描述RailSystem(const string& filename)構(gòu)造函數(shù)，調(diào)用load_services(string const &filename)函數(shù)讀取數(shù)據(jù)load_services(string const &filename) 讀取傳入的文件中的數(shù)據(jù)并

4、建立上述兩個map以模擬歐洲鐵路路線圖reset(void)遍歷cities圖，初始化所有城市的信息：visted未訪問，total_distance最大值，total_fee費(fèi)用最大值，from_city為空RailSystem(void)析構(gòu)函數(shù)，用delete將兩個map中所有使用new操作符開辟的空間刪除void output_cheapest_route(const string& from, const string& to, ostream& out);輸出兩城市間的最少費(fèi)用的路徑，調(diào)用calc_route(string from, string to)函數(shù)計算最少費(fèi)用calc_

5、route(string from, string to)使用Dijkstra算法計算from和to兩個城市間的最少費(fèi)用的路徑recover_route(const string& city)利用棧保存費(fèi)用最少的路徑經(jīng)由的城市名，彈棧后按正確順序輸出該路徑采用的存儲結(jié)構(gòu)mapstring, list outgoing_services用來保存由一個城市出發(fā)可以直接到達(dá)的城市名及這兩個城市之間的路徑信息。 list以service為指針的list表，保存兩城市間的路徑。map cities用來保存所有城市信息，通過城市名查找該城市有關(guān)信息。priority_queueCity*, vector,

6、 Cheapest candidates存儲候選的遍歷城市，City*是優(yōu)先隊(duì)列存儲的對象類型，vector是該對象的向量集合，Cheapest是比較規(guī)則。stack path存儲從出發(fā)城市到目標(biāo)城市的費(fèi)用最少的路徑經(jīng)由的城市名，輸出時彈棧將城市名按順序輸出。三、實(shí)驗(yàn)環(huán)境操作系統(tǒng)：Windows XP Windows 7 調(diào)試軟件：Microsoft visual studio 2008上機(jī)地點(diǎn)：綜合樓311機(jī)器臺號：無四、實(shí)驗(yàn)過程與分析主要算法load_services(string const &filename)函數(shù)讀入from和to城市后，首先判斷這兩個城市在cities這個map中是

7、否存在，若不存在則添加到map中。判斷過程需要遍歷整個map，而這里并沒有使用iterator，而是利用了map的find()函數(shù)，減少了空間和時間的使用。代碼如下 ( to的添加與其相似)if(cities.find (from) = cities.end()/from不在cities中將其插入City *cfrom = new City(from);cities.insert(pair(from,cfrom);另外，需要判斷outgoing_services中是否有from這個城市，若沒有將它添加到outgoing_services中。添加時先創(chuàng)建一個service保存from城市到to城

8、市的信息，新建一個空的list，將這個空的list和對應(yīng)的from添加到outgoing_services中，最后將service添加到outgoing_services中。代碼如下：Service *service = new Service(to,fee,distance);if(outgoing_services.find(from) = outgoing_services.end()/from不在outgoing_services中則to也不在list中將它們插入outgoing_serviceslist *l = new list();outgoing_services.insert

9、(pairstring,list(from,*l);outgoing_servicesfrom.push_back(service);calc_route(string from, string to)函數(shù)利用優(yōu)先權(quán)隊(duì)列和Dijkstra算法，計算任意兩城市之間費(fèi)用最少的路徑，優(yōu)先權(quán)隊(duì)列按照費(fèi)用由大到小的順序入隊(duì)。首先初始化所有城市的信息，把from城市的total_fee和total_distance設(shè)為0，from城市入隊(duì)，彈出隊(duì)列中第一個城市名，即當(dāng)前費(fèi)用最少的路徑的目標(biāo)城市，在outgoing_services中找到它對應(yīng)的城市并取得它對應(yīng)的list的迭代器，通過迭代器遍歷它的鄰接鏈表

10、(即與它鄰接的城市)，得到鄰接城市名，當(dāng)這個城市未被被訪問過且從彈出的城市到該城市的費(fèi)用大于這兩個鄰接城市間費(fèi)用和出發(fā)城市目前的最少費(fèi)用之和，更新從出發(fā)城市到該城市的費(fèi)用，記錄這個城市的經(jīng)由城市為彈出的城市名并將這個城市入棧，同時更新目前的路徑長度。代碼如下：reset();/初始化所有城市信息citiesfrom-total_fee = 0;citiesfrom-total_distance = 0;candidates.push(citiesfrom); /將出發(fā)城市入隊(duì)while(!candidates.empty()string from_city = candidates.top()

11、-name; /獲得出發(fā)城市名以便在后面得到它直接到達(dá)的城市名candidates.top()-visited = true;candidates.pop();list:iterator siter = outgoing_servicesfrom_city.begin();/在outgoing_services中找到from對應(yīng)的城市并取得from對應(yīng)的list的迭代器while(siter != outgoing_servicesfrom_city.end()string dest = (*siter)-destination;/得到鏈表中的出發(fā)城市可以直接到達(dá)的城市if(citiesdes

12、t-visited = false)&(*siter)-fee + citiesfrom_city-total_fee total_fee)citiesdest-total_fee = (*siter)-fee + citiesfrom_city-total_fee;citiesdest-total_distance = (*siter)-distance + citiesfrom_city-total_distance;citiesdest-from_city = from_city;candidates.push(citiesdest);/將與from鄰接的destination入隊(duì)當(dāng)循環(huán)

13、結(jié)束時就是當(dāng)前鏈表中費(fèi)用最小的城市siter +;該算法的時間復(fù)雜度為O（N2），在該算法中使用了優(yōu)先隊(duì)列對其進(jìn)行了優(yōu)化，優(yōu)先隊(duì)列的插入與刪除的時間都是 QUOTE ，在使得整個算法在實(shí)際的運(yùn)行時間上有了明顯的縮小。recover_route(const string& city)函數(shù)利用棧的先進(jìn)先出特性，將求得的路徑所經(jīng)由的城市名入棧再彈棧，則得到正序的路徑。代碼如下：stack path; /定義棧string final_path;string c = city;path.push(city); /將目標(biāo)城市入棧while(citiesc-from_city != ) /目標(biāo)城市經(jīng)過的城

14、市不為空時path.push(citiesc-from_city); /將目標(biāo)城市經(jīng)過的城市入棧c = citiesc-from_city; /得到下一個經(jīng)過的城市while(path.size()!=1) /避免多輸入一個to 判斷到棧的大小為時停止final_path+= (path.top() + to ); /輸出各個經(jīng)過的城市名path.pop(); /將棧內(nèi)的城市名彈棧更新top指向的值final_path += path.top(); /連接最后一個城市即出發(fā)城市path.pop(); /將出發(fā)城市彈棧return final_path;調(diào)試過程中發(fā)現(xiàn)的問題及改進(jìn)方法 = 1 *

15、 GB3 recover_route(const string& city) 函數(shù)將這條語句改為：final_path+= (path.top() + to );問題解決 = 2 * GB3 向outgoing_services中插入list時，總是插入兩遍，截圖如下(Mardrid的鏈表中有兩個Lisbon數(shù)據(jù))：將處理outgoing_services的代碼中插入list的語句移到循環(huán)外，先插入一個空的list，再將數(shù)據(jù)push進(jìn)這個list中Service *service = new Service(to,fee,distance);if(outgoing_services.find(

16、from) = outgoing_services.end()list *l = new list(); outgoing_services.insert(pairstring,list(from,*l); outgoing_servicesfrom.push_back(service);因?yàn)槌绦蛟O(shè)計中使用鏈?zhǔn)酱鎯Y(jié)構(gòu)，插入和刪除元素開銷少，操作簡便，所以具有可擴(kuò)展性 五、實(shí)驗(yàn)結(jié)果總結(jié)你的測試充分嗎？為什么？你是怎樣考慮的？答：充分。因?yàn)槲疫M(jìn)行了兩個不同城市之間的測試，同一個城市之間的測試以及輸入的城市名中存在表中沒有的城市的測試。因?yàn)槿我鈨蓚€城市之間都存在路徑，所以無法進(jìn)行不存在路徑的兩個城

17、市之間的測試，輸出結(jié)果分別如下：兩個不同城市間的測試：同一個城市間的測試：輸入的城市名中存在表中沒有的城市的測試：在你的問題解決方案中，為樹或圖選取了順序的還是鏈?zhǔn)降拇鎯Y(jié)構(gòu)？為什么要選取順序的或鏈?zhǔn)降拇鎯Y(jié)構(gòu)？答：選取了鏈?zhǔn)降拇鎯Y(jié)構(gòu)。由于該圖是一個稀疏圖，采用順序存儲結(jié)構(gòu)對空間的浪費(fèi)較大。并且對于采用Dijkstra算法，無論采用那種存儲結(jié)構(gòu)算法的時間復(fù)雜度都是相同的。用一段簡短的代碼及說明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。reset(); /初始化所有城市信息citiesfrom-total_fee = 0;citiesfrom-total_distance = 0;candida

18、tes.push(citiesfrom); /將出發(fā)城市入隊(duì)while(!candidates.empty()string from_city = candidates.top()-name; /獲得出發(fā)城市名以便在后面得到它直接到達(dá)的城名candidates.top()-visited = true;candidates.pop();list:iterator siter = outgoing_servicesfrom_city.begin();/在outgoing_services中找到from對應(yīng)的城市并取得from對應(yīng)的list的迭代器while(siter != outgoing_s

19、ervicesfrom_city.end() string dest = (*siter)-destination; /得到鏈表中的出發(fā)城市的鏈接城市if(citiesdest-visited = false)&(*siter)-fee + citiesfrom_city-total_fee total_fee)citiesdest-total_fee = (*siter)-fee + citiesfrom_city-total_fee;citiesdest-total_distance = (*siter)-distance + citiesfrom_city-total_distance;

20、citiesdest-from_city = from_city;candidates.push(citiesdest);/將與from鄰接的destination入隊(duì)當(dāng)循環(huán)結(jié)束時就是當(dāng)前鏈表中費(fèi)用最小的城市siter +;首先初始化所有城市的信息，把from城市的total_fee和total_distance設(shè)為0，from城市入隊(duì)，彈出隊(duì)列中第一個城市名，即當(dāng)前費(fèi)用最少的路徑的目標(biāo)城市，在outgoing_services中找到它對應(yīng)的城市并取得它對應(yīng)的list的迭代器，通過迭代器遍歷它的鄰接鏈表(即與它鄰接的城市)，得到鄰接城市名。當(dāng)這個城市未被被訪問過且從彈出的城市到該城市的費(fèi)用大于

21、這兩個鄰接城市間費(fèi)用和出發(fā)城市目前的最少費(fèi)用之和，更新從出發(fā)城市到該城市的費(fèi)用，記錄這個城市的經(jīng)由城市為彈出的城市名并將這個城市入棧，同時更新目前的路徑長度。在你的圖中使用了怎么樣數(shù)據(jù)結(jié)構(gòu)來優(yōu)化算法的性能？答：在圖中，我使用了棧的數(shù)據(jù)結(jié)構(gòu)來優(yōu)化算法的性能。程序在最后恢復(fù)所走路徑的函數(shù)中顯式的使用了棧stack path，采用的非遞歸算法：定義一個存放string的棧，把傳來的參數(shù)city即目標(biāo)城市壓入棧中，進(jìn)行一個while循環(huán)，從city城市開始向前遍歷，當(dāng)城市的from_city不為時，把from_city壓入棧中；用一個while循環(huán)，將棧中的元素依次彈出就是從from城市到to城市費(fèi)用少的路線。源程序的大致的執(zhí)行過程是怎樣的？其中，讀取文件創(chuàng)建圖的存儲即構(gòu)造RailSystem的實(shí)例，輸出路徑的函數(shù)中調(diào)用計算費(fèi)用最少的路徑的