欧洲旅行实验报告-东北大学.doc

实 验 报 告
课程名称：数据结构
班级：会计1203
实验成绩：
实验名称：欧洲旅行
学号：20120577
批阅教师签字：
实验编号：实验二
姓名：柳思杨
实验日期：2014 年 6 月29 日
指导教师：张明卫
组号：
实验时间：21时 00 分－21 时50 分

一、实验目的
1）加深对图的表示法和图的基本操作的理解，并可初步使用及操作；
2）掌握用图对实际问题进行抽象方法，可以解决基本的问题；
3）掌握利用邻接表求解非负权值、单源最短路径的方法，即利用迪杰斯特拉算法求最短路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题。
4）学会使用STL中的map抽象实际问题，掌握map，List的应用。

二、 实验内容与实验步骤
（1） 这个评估程序模拟欧洲铁路系统计算两个城市之间最便宜的路线。代表了铁路系统的图形如下图所示。

在这个程序中,构造一个加权图代表铁路服务与欧洲城市。每个服务从一个城市都有一个关联的目的地城市,费用(欧元),和一个距离(公里)。该程序处理用户输入的源和目的地城市。程序然后显示最便宜的路线从源到目的地城市。此外,对于每一个路线,总成本和总显示距离。文件services.txt包含的数据可用的服务。
（2） 简短描述你在实验中使用的数据结构及算法的基本原理。
这个程序利用三个主要类：City类、Service类和RailSystem类。City类和Service类的实现已经给出。City类保存一个城市的信息。Sevice类模拟铁路系统的铁路服务。这类包含的公共数据成员有目的地城市,费用,和距离。这两个类是RailSystem所使用的类。
RailSystem类模拟铁路系统使用一个邻接表表示。这些邻接列表用STL模板中map数据结构表示。具体地说,一个由string类型和List<Service* >构成的map类型代表了铁路系统。即map<string,List<Service*>>。下图是如何代表铁路系统的一部分。注意,机票费用和距离在简化画面中省略。

本质上,如上表示,一个对外服务的链表使用了一个包含城市名称的字符串作为下标。例如，在上面的照片中,马德里有三个外向服务:里斯本,伯尔尼,和巴黎。它与给出的铁路系统图的顶端匹配。
除了这种类型的map对象,另一种map类型的映射是用于城市名称映射到各城市的对象指针。即map<string,City*>。此map对象用于搜索算法。
这个程序的示例输出如下图所示。

使用的算法是一个djkstra最短路径算法。每个City是图中的一个节点，每个Service相关联的边缘,边缘的权:机票费用。我们的目标是找到最便宜的路线从源到目的地城市。
当要执行一个新的搜索,一个指向Service的指针代表最初开始城市应该添加到一个空候选队列。算法继续探索候选城市的Service,同时可能添加新的候选人名单。该算法用数字对每个City对象从原点到目前为止最便宜路线成本做标记。并存储在成员total_fee中。这个值可能在找到新路线后减少,变得更便宜,但不可能增加。
当复原实际的搜索路径,每个City对象包含一个字符串from_city，from_city代表最便宜路径上一个通过的城市名称，将在搜索算法被不断更新。比如说,如果检查出通过布鲁塞尔到巴黎是一个更便宜的路径,则更新对应于巴黎城市的City的变量total_fee,并设置其from_city等于“布鲁塞尔”。搜索完成后,算法得出最便宜的路线,并且通过from_city字符串可以遍历从目的地到原点的所有结点，以重建这条道路。
（3） 描述你采用ＳＴＬ中的什么容器或者类实现图的存储，在算法应用过程中使用什么数据结构或算法提高算法的效率。
图的存储结构：
①　 Map类map<string, List<Service*> > outgoing_services存储 铁路系统图。其中List<Service*>存储名称为string的城市其邻接 点的信息。
②　 Map类map<string, City*> cities存储搜索算法中的路径图。 City*指向名称为string的城市的最小路径信息。
其他数据结构：
①　 优先队列priority_queue<City*, vector<City*>, Cheapest>：搜索算法中，用优先队列存储候选城市结点，顶点直接得到最小费用城市的指针，可以提高算法效率。
②　 栈stack<string> :恢复最小费用的路径。
算法：
①　 最小路径算法，即djkstra算法。
②　 迭代。在遍历List<Service*>和map<string, list<Service*> >这些复杂数据结 构时，使用迭代器能提高算法效率。

三、实验环境
操作系统：Win7旗舰版；
调试软件名称：Visual studio；
版本号：Vs2010；
上机地点：寝室；
机器台号：笔记本

四、实验过程与分析
（1） 描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。
①　 void RailSystem::reset(void)：遍历map类cities中的对象，将以前产生的信息清楚，重新初始化。时间复杂度O(n)，空间复杂度O(1)。
②　 void RailSystem::load_services(string const &filename)：导入文件，构建铁路系统的模拟图。时间复杂度O(n)，空间复杂度O(1)。
③　 pair<int, int> RailSystem::calc_route(string from, string to)：实现最小路径算法，把信息存储在map<string,City*>中。时间复杂度O(n^2)，空间复杂度O(1)。
④　 string RailSystem::recover_route(const string& city)：还原从from到to的最小费用路径的路线。时间复杂度O(n)，空间复杂度O(1)。

（2） 你在调试过程中发现了怎样的问题？又做了怎样的改进？
①　 刚开始没有用priority_queue，是直接写出djkstra算法。因为当时没想明白要用在哪块，后来想明白了，把候选的压入队列，顶端直接得到目前费用最小的那一个，节省了算法的时间效率。
②　 对city进行初始化的时候，分成了两拨，其实没有必要，除了from城市其他都可以把total_fee和total_distance设置成无穷大。后面的循环会自动更新。
（3） 你的实验在解决类似问题时是否具有灵活的可修改性、可扩展性？
有。第一个问题就是去掉一个迭代器遍历的循环，因为优先队列直接得到最小值了。
第二个问题就是把多余的代码删除就行。
五、实验结果总结
回答以下问题：
（1） 你的测试充分吗？为什么？你是怎样考虑的？
我把城市作为目的城市正过来测，然后作为到达地反过来测，结果正确。
（2） 在你的问题解决方案中，为图选取了顺序的还是链式的存储结构？为什么要选取这种存储结构？
链式的。因为存储数量未知，链式支持动态存储。节省空间。
（3） 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。
①　 void RailSystem::load_services(string const &filename) {
ifstream inf(filename.c_str());
string from, to;
int fee, distance;
list<Service*>* l_s=new list<Service*>[cities.size()];
int i=0;
map<string,list<Service*>>::iterator iter;
list<Service*>::iterator iter1;
while ( inf.good() ) {
// Read in the from city, to city, the fee, and distance.
inf >> from >> to >> fee >> distance;
//把文件中的信息逐个保存在map中，名称string的城市作为引索，临界点信息存储在List<Service*>中。
if ( inf.good() ) {
pair<map<string,list<Service*>>::iterator,bool>Insert_Pair;
pair<map<string,City*>::iterator,bool>Insert_Pair1;
Insert_Pair=outgoing_services.insert(map<string,list<Service*>>::value_type (from,l_s[i]));
Insert_Pair1=cities.insert(map<string,City*>::value_type (to,new City(to)));
if(Insert_Pair1.second==true && Insert_Pair.second == true)i++;
outgoing_services.find(from)->second.insert(outgoing_services.find(from)->second.end(),new Service(to,fee,distance));
}
}
inf.close();
}

②　 pair<int, int> RailSystem::calc_route(string from, string to) {
priority_queue<City*, vector<City*>, Cheapest> candidates;
list<Service*>::iterator iter;
map<string,City*>::iterator iter1;
int min=INT_MAX;
//dkjstra算法计算到各城市之间的最小费用路径。
//cities初始化
for(iter1=cities.begin(); iter1!=cities.end();iter1++){
iter1->second->total_fee=INT_MAX;
iter1->second->from_city=from;
iter1->second->total_distance=INT_MAX;
}
cities[from]->visited=true;
cities[from]->total_fee=0;
cities[from]->total_distance=0;
cities[from]->from_city=from;
candidates.push(cities[from]);
//用循环更新最短路线
for(int i=cities.size();i>0;i--){
min=candidates.top()->total_fee;
min=candidates.top()->visited=true;
for(iter1=cities.begin();iter1!=cities.end();iter1++){
if(iter1->second->visited!=false)continue;
for(iter=outgoing_services[candidates.top()->name].begin();iter!=outgoing_services[candidates.top()->name].end();iter++)
if((*iter)->destination==iter1->second->name && ((*iter)->fee+candidates.top()->total_fee)<cities[(*iter)->destination]->total_fee){
cities[(*iter)->destination]->total_fee=(*iter)->fee+candidates.top()->total_fee;
cities[(*iter)->destination]->total_distance=(*iter)->distance+candidates.top()->total_distance;
cities[iter1->second->name]->from_city=candidates.top()->name;
candidates.push(iter1->second);
}
}
candidates.pop();
}
// Return the total fee and total distance.
// Return (INT_MAX, INT_MAX) if not path is found.
if (cities[to]->visited) {
return pair<int,int>(cities[to]->total_fee, cities[to]->total_distance);
} else {
return pair<int,int>(INT_MAX, INT_MAX);
}

}

（4） 在你的图中使用了怎么样数据结构来优化算法的性能？
①　 栈
②　 优先队列
（5） 源程序的大致的执行过程是怎样的？
Reset（刷新）—>load(载入文件，构建铁路系统模拟图)—>cac_route(计算两城市之间最短路径)—>print(打印总费用和总距离，以及路线)

请清晰、准确、详细地回答上面的问题，要求标点符号正确无误，图表表示符合规范。你的报告应至少超出一页的文字描述，注意你描述的文字一定要叙述流畅，具有较好的逻辑性。
六、附录
（1） 如果你对这个实验还有其他的解决方案或设想，或对我们的实验方案有什么意见，请在此描述。
实验报告有些问题重复了，答起来有点心累，建议简化一些
（2） 实验参考的资料
《数据结构（面向对象方法与C++语言描述）》
（3） 回答思考题
a) 在你的应用中使用了ＳＴＬ中的哪些容器？有什么用途？
Stack栈：反方向打印出from_city,正好是一条路线。
List表：存储结点的邻接节点，作为邻接表。
Priority_queque优先队列：自动排序，快速得到最小值。
Map图：存储地图和路线。
b) 假设一个图采用邻接表存储结构进行存储，在某一个结点的邻接结点链表中，结点的顺序是否会影响到最短路径算法的结果？
不会。
（4）选作：查询以下内容的有关知识
a)最短路径求解问题在工程中的应用。