数据结构实验二欧洲旅行

一、实验目的

1)加深对图的表示法和图的基本操作的理解；

2)掌握用图对实际问题进行抽象的方法；

3)掌握利用邻接表求解非负权值、单源最短路径的方法，即Dijkstra算法，同时掌握邻接表的建立以及使用方法；

4)学会使用STL中的map抽象实际问题，掌握有关map的基本操作

二、实验内容与实验步骤

（1）实验内容：

使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，应用Dijkstra算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。

（2）抽象数据类型及设计函数描述

1)抽象数据类型

class City：

维护一个城市的信息，包括城市名name，是否被访问过的标记visted，从某个城市到达该城市所需的总费用total_fee和总路径长度total_distance，求得最短路径后路径中到达该城市的城市名from_city。

class Service：

为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用fee，两城市之间的直接距离distance，两个城市间作为目的地的城市名destination。

class RailSystem：

用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map实现，map的key-value值对的数据类型分别为string和list<*Service>，对应出发城市名和该城市与它能够到达的城市之间的Service链表。类RailSystem维护一个用来存储城市的map，该map的key-value值对的数据类型分别为string和City*，对应城市名和指向该城市的指针，以访问该城市的有关信息

2)设计函数描述

●RailSystem(const string& filename)

构造函数，调用load_services(string const &filename)函数读取数据

●load_services(string const &filename) 

读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图

●reset(void)

遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大值，total_fee费用最大值，from_city为空

●~RailSystem(void)

析构函数，用delete将两个map中所有使用new操作符开辟的空间删除

●void output_cheapest_route(const string& from, const string& 

to, ostream& out);

输出两城市间的最少费用的路径，调用calc_route(string from, string to)函数计算最少费用

●calc_route(string from, string to)

使用Dijkstra算法计算from和to两个城市间的最少费用的路径

●recover_route(const string& city)

利用栈保存费用最少的路径经由的城市名，弹栈后按正确顺序输出该路径

（3）采用的存储结构

1)map > outgoing_services

用来保存由一个城市出发可以直接到达的城市名及这两个城市之间的路径信息。 

2)list

以service为指针的list表，保存两城市间的路径。

3)map cities

用来保存所有城市信息，通过城市名查找该城市有关信息。

4)priority_queue, Cheapest> candidates

存储候选的遍历城市，City*是优先队列存储的对象类型，vector是该对象的向量集合，Cheapest是比较规则。

5)stack path

存储从出发城市到目标城市的费用最少的路径经由的城市名，输出时弹栈将城市名按顺序输出。

三、实验环境

操作系统：Windows XP   Windows 7 

调试软件：Microsoft visual studio 2008

上机地点：综合楼311

机器台号：无

四、实验过程与分析

（1）主要算法

1)load_services(string const &filename)函数

读入from和to城市后，首先判断这两个城市在cities这个map中是否存在，若不存在则添加到map中。判断过程需要遍历整个map，而这里并没有使用iterator，而是利用了map的find()函数，减少了空间和时间的使用。代码如下 ( to的添加与其相似)——

if(cities.find (from) == cities.end()){//from不在cities中将其插入

                City *cfrom = new City(from);

                cities.insert(pair(from,cfrom));

    }

另外，需要判断outgoing_services中是否有from这个城市，若没有将它添加到outgoing_services中。添加时先创建一个service保存from城市到to城市的信息，新建一个空的list，将这个空的list和对应的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_services

    list *l = new list();                outgoing_services.insert(pair>(from,*l));

}

    outgoing_services[from].push_back(service);

2)calc_route(string from, string to)函数

利用优先权队列和Dijkstra算法，计算任意两城市之间费用最少的路径，优先权队列按照费用由大到小的顺序入队。

首先初始化所有城市的信息，把from城市的total_fee和total_distance设为0，from城市入队，弹出队列中第一个城市名，即当前费用最少的路径的目标城市，在outgoing_services中找到它对应的城市并取得它对应的list的迭代器，通过迭代器遍历它的邻接链表(即与它邻接的城市)，得到邻接城市名，当这个城市未被被访问过且从弹出的城市到该城市的费用大于这两个邻接城市间费用和出发城市目前的最少费用之和，更新从出发城市到该城市的费用，记录这个城市的经由城市为弹出的城市名并将这个城市入栈，同时更新目前的路径长度。代码如下：

reset();//初始化所有城市信息

cities[from]->total_fee = 0;

cities[from]->total_distance = 0;

candidates.push(cities[from]);  //将出发城市入队

while(!candidates.empty()){

    string from_city = candidates.top()->name;  //获得出发城市名以便在后面得到它直接到达的城市名

    candidates.top()->visited = true;

    candidates.pop();

list::iterator siter = outgoing_services[from_city].begin();//在outgoing_services中找到from对应的城市并取得from对应的list的迭代器

    while(siter != outgoing_services[from_city].end()){

        string dest = (*siter)->destination;    //得到链表中的出发城市可以直接到达的城市

if((cities[dest]->visited == false)&&((*siter)->fee + 

cities[from_city]->total_fee < cities[dest]->total_fee)){

cities[dest]->total_fee = (*siter)->fee +

cities[from_city]->total_fee;

            cities[dest]->total_distance = (*siter)->distance + 

cities[from_city]->total_distance;

            cities[dest]->from_city = from_city;

            candidates.push(cities[dest]);        //将与from邻接的destination入队当循环结束时就是当前链表中费用最小的城市

        }    

        siter ++;

    }

}

该算法的时间复杂度为O（N2），在该算法中使用了优先队列对其进行了优化，优先队列的插入与删除的时间都是，在使得整个算法在实际的运行时间上有了明显的缩小。

3)recover_route(const string& city)函数

利用栈的先进先出特性，将求得的路径所经由的城市名入栈再弹栈，则得到正序的路径。代码如下：

stack path;  //定义栈

string final_path;

string c = city;

path.push(city);  //将目标城市入栈

while(cities[c]->from_city != ""){  //目标城市经过的城市不为空时

        path.push(cities[c]->from_city);  //将目标城市经过的城市入栈

        c = cities[c]->from_city;  //得到下一个经过的城市

}

while(path.size()!=1){  //避免多输入一个to 判断到栈的大小为时停止

        final_path+= (path.top() + " to ");  //输出各个经过的城市名

        path.pop();  //将栈内的城市名弹栈更新top指向的值

}

final_path += path.top();  //连接最后一个城市即出发城市

path.pop();  //将出发城市弹栈

return final_path;

（2）调试过程中发现的问题及改进方法

recover_route(const string& city) 函数

将这条语句改为：final_path+= (path.top() + " to ");问题解决

向outgoing_services中插入list时，总是插入两遍，截图如下(Mardrid的链表中有两个Lisbon数据)：

将处理outgoing_services的代码中插入list的语句移到循环外，先插入一个空的list，再将数据push进这个list中

Service *service = new Service(to,fee,distance);

        if(outgoing_services.find(from) == outgoing_services.end()){

list *l = new list();             outgoing_services.insert(pair>(from,*l));

        }

       outgoing_services[from].push_back(service);

（3）因为程序设计中使用链式存储结构，插入和删除元素开销少，操作简便，所以具有可扩展性

五、实验结果总结

（1）你的测试充分吗？为什么？你是怎样考虑的？

答：充分。因为我进行了两个不同城市之间的测试，同一个城市之间的测试以及输

入的城市名中存在表中没有的城市的测试。因为任意两个城市之间都存在路径，所

以无法进行不存在路径的两个城市之间的测试，输出结果分别如下：两个不同城市

间的测试：

同一个城市间的测试：

输入的城市名中存在表中没有的城市的测试：

（2）在你的问题解决方案中，为树或图选取了顺序的还是链式的存储结构？为什么要选

取顺序的或链式的存储结构？

答：选取了链式的存储结构。由于该图是一个稀疏图，采用顺序存储结构对空间的

浪费较大。并且对于采用Dijkstra算法，无论采用那种存储结构算法的时间复杂

度都是相同的。

（3）用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。

reset();  //初始化所有城市信息

cities[from]->total_fee = 0;

cities[from]->total_distance = 0;

candidates.push(cities[from]);  //将出发城市入队

while(!candidates.empty()){

string from_city = candidates.top()->name;  //获得出发城市名以便在后面得到它直接到达的城名

candidates.top()->visited = true;

candidates.pop();

list::iterator siter = outgoing_services[from_city].begin();

//在outgoing_services中找到from对应的城市并取得from对应的list的迭代器

while(siter != outgoing_services[from_city].end()){

     string dest = (*siter)->destination;  //得到链表中的出发城市的链接城市

if((cities[dest]->visited == false)&&((*siter)->fee + 

cities[from_city]->total_fee < cities[dest]->total_fee)){

cities[dest]->total_fee = (*siter)->fee + cities[from_city]->total_fee;

cities[dest]->total_distance = (*siter)->distance + cities[from_city]->total_distance;

cities[dest]->from_city = from_city;

    candidates.push(cities[dest]);        

//将与from邻接的destination入队当循环结束时就是当前链表中费用最小的城市

}    

siter ++;

}

}

首先初始化所有城市的信息，把from城市的total_fee和total_distance设为0，from城市入队，弹出队列中第一个城市名，即当前费用最少的路径的目标城市，在outgoing_services中找到它对应的城市并取得它对应的list的迭代器，通过迭代器遍历它的邻接链表(即与它邻接的城市)，得到邻接城市名。当这个城市未被被访问过且从弹出的城市到该城市的费用大于这两个邻接城市间费用和出发城市目前的最少费用之和，更新从出发城市到该城市的费用，记录这个城市的经由城市为弹出的城市名并将这个城市入栈，同时更新目前的路径长度。

（4）在你的图中使用了怎么样数据结构来优化算法的性能？

答：在图中，我使用了栈的数据结构来优化算法的性能。

程序在最后恢复所走路径的函数中显式的使用了栈stack path，采用的非递归算法：定义一个存放string的栈，把传来的参数city即目标城市压入栈中，进行一个while循环，从city城市开始向前遍历，当城市的from_city不为""时，把from_city压入栈中；用一个while循环，将栈中的元素依次弹出就是从from城市到to城市费用少的路线。

（5）源程序的大致的执行过程是怎样的？

其中，读取文件创建图的存储即构造RailSystem的实例，输出路径的函数中调用计算费用最少的路径的方法calc_route(string from, string to) 和恢复求得的费用最少的路径的函数recover_route(const string& city)。

六、附录

（1）实验的参考资料

[1]Mark Allen Weiss著 张怀勇等译.数据结构与算法分析(第3版).北京.人民邮电出版社

[2]殷人昆主编.数据结构(用面向对象方法与C++语言描述)(第2版).北京.清华大学出版社

（2）思考题

a)在你的应用中使用了ＳＴＬ中的哪些容器？有什么用途？

答：我的应用中使用了STL中的列表(list)——由节点组成的双向链表，每个结点包含着一个元素 ；栈(stack)——后进先出的值的排列 ；优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列 ；映射(map) 由{键，值}对组成的集合，以某种作用于键对上的谓词排列 

用途——

1)map > outgoing_services

用来保存由一个城市出发可以直接到达的城市名及这两个城市之间的路径信息 

2)list

以service为指针的list表，保存两城市间的路径

3)map cities

用来保存所有城市信息，通过城市名查找该城市有关信息

4)priority_queue, Cheapest> candidates

存储候选的遍历城市，City*是优先队列存储的对象类型，vector是该对象的向量集合，Cheapest是比较规则

5)stack path

存储从出发城市到目标城市的费用最少的路径经由的城市名，输出时弹栈将城市名按顺序输出

b)假设一个图采用邻接多重表存储结构进行存储，在某一个结点的邻接结点链表中，结点的顺序是否会影响遍历的次序？

答：会，因为邻接表是图的一种链式存储结构，对图的每个顶点建立一个单链

表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点，它的遍历与链表的遍历相同。