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

數(shù)據(jù)結(jié)構(gòu)實驗報告年6月日時時分4)priority_queue等的應(yīng)用。）簡短明確地寫出實驗的內(nèi)容）設(shè)想：。：用鄰接表模擬歐洲鐵路系統(tǒng)，該鄰接表使用數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，的和：。2~RailSystem(void)析構(gòu)函數(shù)，用delete將兩個map中所有使用操作符開辟的空間刪除）簡短明確地寫出你實驗所采用的存儲結(jié)構(gòu)及其用途，詳細(xì)說明其中的屬性的含義。1)map<string,list<Service*>>outgoing_services用來保存由一個城市出發(fā)可以直接到達(dá)的城市名及這兩個城市之間的路徑信息。2)list<Service*>以3)map<string,City*>cities4)）描述你在進(jìn)行實現(xiàn)時，主要的函數(shù)或操作內(nèi)部的主要算法，分析這個算法的時、空復(fù)雜度，并說明你設(shè)計的巧妙之處。時間復(fù)雜度是O(n2)，空間復(fù)雜度為O(n)calc_route(stringfrom,string函數(shù)通過迭代器遍歷它的鄰接鏈表，得到鄰接城市名，當(dāng)這個城市未被被訪問過且從彈出的城市到該城市的費(fèi)用大于這兩個鄰接城市間費(fèi)用和出發(fā)城市目前的最少費(fèi)用之和，更新從出發(fā)城市到該城市的費(fèi)用，并且記錄這個城市的經(jīng)由城市為彈出的城市名并將這個城市入棧，同時更新目前的路徑長度。代碼如下：3priority_queue<City*,vector<City*>,Cheapest>candidates;City*city=cities[from];city->total_fee=0;candidates.push(city);list<Service*>service_list=outgoing_services[city->name];if(cities[service->destination]->total_fee>(city->total_fee+service->fee))cities[service->destination]->total_fee=city->total_fee+service->fee;cities[service->destination]->total_distance=city->total_distance+service->distance;}}}if(cities[to]->visited){returnpair<int,int>(cities[to]->total_fee,cities[to]->total_distance);}else{returnpair<int,int>(INT_MAX,INT_MAX);}2）load_services(string)函數(shù)讀入from和to城市后，首先判斷這兩個城市在cities這個map中是否存在，若不存在則添加到map中。判斷過程需要遍歷整個，這里利用了map的find()函數(shù)，減少了空間和時間的使用。代碼如下：ifstreaminf(filename.c_str());stringfrom,to;intfee,distance;while(inf.good()){inf>>from>>to>>fee>>distance;if(inf.good()){map<string,list<Service*>>::iteratormp=outgoing_services.find(from);if(mp==outgoing_services.end()){list<Service*>ms;ms.push_front(newService(to,fee,distance));outgoing_services.insert(pair<string,list<Service*>>(from,ms));4cities.insert(pair<string,City*>(from,newCity(from)));(mp->second).push_front(newService(to,fee,distance));}}inf.close();3）recover_route(conststring&函數(shù)利用棧的先進(jìn)先出特性，將求得的路徑所經(jīng)由的城市名入棧再彈棧，則得到正序的路徑。主要代碼如下：stringback=city;stringall=city;while((back=cities.find(back)->second->from_city)!="")all=back+"to"+all;}returnall;）你在調(diào)試過程中發(fā)現(xiàn)了怎樣的問題？又做了怎樣的改進(jìn)？priority_queue堆在內(nèi)部對象數(shù)據(jù)更改后無法進(jìn)行重排。發(fā)現(xiàn)在vs2012會返回錯誤，但是點擊忽略后還是可以直接運(yùn)行得到結(jié)果。如圖：點擊忽略后出現(xiàn)結(jié)果，如圖：5）而對存在的城市則返回如圖：對同一個城市則返回）6）priority_queue<City*,vector<City*>,Cheapest>candidates;City*city=cities[from];city->total_fee=0;candidates.push(city);if(cities[service->destination]->total_fee>(city->total_fee+service->fee)){cities[service->destination]->total_fee=city->total_fee+service->fee;cities[service->destination]->from_city=city->name;=city->total_distance+service->distance;candidates.push(cities[service->destination]);}}}if(cities[to]->visited){returnpair<int,int>(cities[to]->total_fee,cities[to]->total_distance);}returnpair<int,int>(INT_MAX,INT_MAX);}outgoing_