东北大学欧洲旅行数据结构作业.doc

数 据 结 构实 验 报 告课程名称：数据结构班级：软件赴日1101实验成绩：实验名称：欧洲旅行学号：20112271批阅教师签字：实验编号：实验二姓名：贾志远实验日期：20013 年 6月 20 日指导教师： 组号：实验时间： 20 时03分 22 时43分1、 实验目的1) 加深对图的表示法和图的基本操作的理解，并可初步使用及操作；2) 掌握用图对实际问题进行抽象的方法，可以解决基本的问题；3) 掌握利用邻接表求解非负权值、单源最短路径的方法，即利用迪杰斯特拉算法求最短路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题；4) 学会使用STL中的map抽象实际问题，掌握map，List,，priority_queue等的应用。二、实验内容与实验步骤（1） 简短明确地写出实验的内容使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，通过迪杰斯特拉算法求出欧洲旅行最少花费的路线。该实验应用迪杰斯特拉算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。 （2） 简短描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明你的解决设想 抽象数据类型class City：维护一个城市的信息，包括城市名name，是否被访问过的标记visited，从某个城市到达该城市所需的总费用total_fee和总路径长度total_distance，求得最短路径后路径中到达该城市的城市名from_city。class RailSystem：用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map实现，map的cities-outgoing_services值对的数据类型分别为string和list，对应出发城市名和该城市与它能够到达的城市之间的Service链表。class Service：为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用fee，两城市之间的直接距离distance，还有经过的城市destination。部分设计函数描述l RailSystem(const string& filename)构造函数，调用load_services(string const &filename)函数读取数据l load_services(string const &filename) 读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图l reset(void)遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大值，total_fee费用最大值，from_city为空l RailSystem(void)析构函数，用delete将两个map中所有使用new操作符开辟的空间删除l void output_cheapest_route(const string& from, const string& to, ostream& out);输出两城市间的最少费用的路径，调用calc_route(string from, string to)函数计算最少费用l calc_route(string from, string to)使用迪杰斯特拉算法计算from和to两个城市间的最少费用的路径（3） 简短明确地写出你实验所采用的存储结构及其用途，详细说明其中的属性的含义。1) mapstring, list outgoing_services用来保存由一个城市出发可以直接到达的城市名及这两个城市之间的路径信息。 2) list ms 以service为指针的list表，保存两城市间的路径。3) map cities用来保存所有城市信息，通过城市名查找该城市有关信息。4) priority_queueCity*, vector, Cheapest candidates存储候选的遍历城市，City*是优先队列存储的对象类型，vector是该对象的向量集合，Cheapest是比较规则。三、实验环境操作系统Win7、调试软件VS2012四、实验过程与分析（1） 描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。该实验主要用到了迪杰斯特拉算法，这个算法要求所有边的权值非负，提出了按路径长度递增的顺序逐步产生最短路径的算法，首先求出长度最短的一条路径，然后参照它求出长度次短的一条路径，以此类推，指导顶点到其他顶点的最短路径全部求完为止即可解决该实验的问题。 算法的时间复杂度是，空间复杂度为1) calc_route(string from, string to)函数利用优先权队列和迪杰斯特拉算法，计算任意两城市之间费用最少的路径，优先权队列按照费用由大到小的顺序入队。首先初始化所有城市的信息。通过迭代器遍历它的邻接链表，得到邻接城市名，当这个城市未被被访问过且从弹出的城市到该城市的费用大于这两个邻接城市间费用和出发城市目前的最少费用之和，更新从出发城市到该城市的费用，并且记录这个城市的经由城市为弹出的城市名并将这个城市入栈，同时更新目前的路径长度。代码如下： priority_queueCity*, vector, Cheapest candidates;City* city=citiesfrom;city-total_fee=0;city-total_distance=0;candidates.push(city);while(!candidates.empty()while(city = candidates.top()-visited)candidates.pop();city-visited=true;candidates.pop();list service_list = outgoing_servicescity-name;for(Service* service;!service_list.empty();service_list.pop_front()service = service_list.front();if(citiesservice-destination-total_fee(city-total_fee+service-fee)citiesservice-destination-total_fee = city-total_fee + service-fee;citiesservice-destination-from_city = city-name;citiesservice-destination-total_distance = city-total_distance + service-distance;candidates.push(citiesservice-destination);if (citiesto-visited)return pair(citiesto-total_fee,citiesto-total_distance);elsereturn pair(INT_MAX, INT_MAX); 在该算法中使用了优先队列对其进行了优化，使得整个算法在实际的运行时间上有了明显的缩小。2） load_services(string)函数读入from和to城市后，首先判断这两个城市在cities这个map中是否存在，若不存在则添加到map中。判断过程需要遍历整个map，这里利用了map的find()函数，减少了空间和时间的使用。代码如下 ： ifstream inf(filename.c_str();string from, to;int fee, distance;while (inf.good()inf from to fee distance;if (inf.good()mapstring, list :iterator mp = outgoing_services.find(from);if(mp=outgoing_services.end()list ms;ms.push_front(new Service(to,fee,distance);outgoing_services.insert(pairstring, list(from, ms);cities.insert(pair(from, new City(from);else(mp-second).push_front(new Service(to,fee,distance);inf.close();3）recover_route(const string& city)函数利用栈的先进先出特性，将求得的路径所经由的城市名入栈再弹栈，则得到正序的路径。主要代码如下： string back=city;string all=city;while(back = cities.find(back)-second-from_city)!=) all = back+ to +all;return all;（2） 你在调试过程中发现了怎样的问题？又做了怎样的改进？ priority_queue堆在内部对象数据更改后无法进行重排。 发现在vs2012会返回错误，但是点击忽略后还是可以直接运行得到结果。如图：点击忽略后出现结果，如图：五、实验结果总结回答以下问题：（1） 你的测试充分吗？为什么？你是怎样考虑的？ 答：我的测试充分，对每条线都进行了双向检验并且测试了不存在的城市名，返回了如图结果：而对存在的城市则返回如图：对同一个城市则返回（2） 在你的问题解决方案中，为树或图选取了顺序的还是链式的存储结构？为什么要选取顺序的或链式的存储结构？ 在我的问题解决方案中选取了链式的存储结构。由于该图是一个稀疏图，采用顺序存储结构对空间的浪费较大，并且对于采用迪杰斯特拉算法，无论采用那种存储结构算法的时间复杂度都是相同的。所以我选择了链式的存储结构。（3） 用一段简短的代码及说明论述你的应用中主要的函数的主要处理部分。 priority_queueCity*, vector, Cheapest candidates;City* city=citiesfrom;city-total_fee=0;city-total_distance=0;candidates.push(city);while(!candidates.empty()while(city = candidates.top()-visited)candidates.pop();city-visited=true;candidates.pop();list service_list = outgoing_servicescity-name;for(Service* service;!service_list.empty();service_list.pop_front()service = service_list.front();if(citiesservice-destination-total_fee(city-total_fee+service-fee)citiesservice-destination-total_fee = city-total_fee + service-fee;citiesservice-destination-from_city = city-name;citiesservice-destination-total_distance = city-total_distance + service-distance;candidates.push(citiesservice-destination);if (citiesto-visited)return pair(citiesto-total_fee,citiesto-total_distance);elsereturn pair(INT_MAX, INT_MAX); from城市先入队，弹出队列中第一个城市名，即当前费用最少的路径的目标城市，在outgoing_services中找到它对应的城市并取得它对应的list的迭代器，通过迭代器遍历它的邻接链表，得到邻接城市名，判断城市是否被访问了，如果这个城市未被访问且从弹出的城市到该城市的费用大于这两个邻接城市间费用和出发城市目前的最少费用之和，更新从出发城市到该城市的费用，记录这个城市名并将这个城市入栈，同时更新当下的路径长度。（4） 树和图的应用算法中，无论是递归或非递归的算法都要用到栈这种数据结构，试论述你的算法设计中，栈是被显式地还是隐式地使用？栈内元素可能达到的最大数是多少？ 在图中，使用了栈的数据结构来优化算法的性能。 程序在最后恢复所走路径的函数中隐式地使用了栈。用一个while循环，将栈中的元素依次弹出就是从from城市到to城市费用少的路线。（5） 源程序的大致的执行过程是怎样的？开始程序否目的地是否已被访问是结束程序去除重复元素找出服务队列，找出最小花费路径判断城市是否已被访问过且费用是否比原费用少从堆栈中取出最优化路径和城市（元素）否是把元素加入堆首先读文件将所有数据赋值,通过键盘输入旅行的起点和终点,在所给文件信息范围内则声明一个集合,用于存储最短路径的集合,然后根据周围的城市选择花费最小的路径，添加到集合中，最后返回路径信息。其中，读取文件创建图的存储即构造RailSystem的实例，输出路径的函数中调用计算费用最少的路径的方法calc_route(string from, string to) 和恢复求得的费用最少的路径的函数recover_route(const string& city)。请清晰、准确、详细地回答上面的问题，要求标点符号正确无误，图表表示符合规范。你的报告应至少超出一页的文字描述，注意你描述的文字一定要叙述