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

《东北大学欧洲旅行数据结构作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构9实验报告课程名称：数据结构班级：软件赴日1101实验成绩：实验名称：欧洲旅行学号：20112271批阅教师签字：实验编号：实验二姓名：贾志远实验日期：20013年6月20日指导教师：组号：实验时间：20时03分－22时43分一、实验目的1)加深对图的表示法和图的基本操作的理解，并可初步使用及操作；2)掌握用图对实际问题进行抽象的方法，可以解决基本的问题；3)掌握利用邻接表求解非负权值、单源最短路径的方法，即利用迪杰斯特拉算法求最短路径，同时掌握邻接表的建立以及使用方法，能够解决相关的问题；4)学会使用STL中的map抽象实际问题，掌握map，Li

2、st,，priority_queue等的应用。二、实验内容与实验步骤（1）简短明确地写出实验的内容使用图这种抽象的数据结构存储模拟的欧洲铁路路线图，通过迪杰斯特拉算法求出欧洲旅行最少花费的路线。该实验应用迪杰斯特拉算法求得任意两个城市之间的最少路费，并给出路费最少的路径的长度和所经过的城市名。（2）简短描述抽象数据类型或设计的函数描述，说明为什么要使用这种抽象数据类型，并说明你的解决设想抽象数据类型classCity：维护一个城市的信息，包括城市名name，是否被访问过的标记visited，从某个城市到达该城市所需的总费用total_fee和总路径长度to

3、tal_distance，求得最短路径后路径中到达该城市的城市名from_city。classRailSystem：用邻接表模拟欧洲铁路系统，该邻接表使用数据结构map实现，map的cities--outgoing_services值对的数据类型分别为string和list<*Service>，对应出发城市名和该城市与它能够到达的城市之间的Service链表。classService：为铁路系统模拟了两个城市之间的直接路线，包括两个城市之间直接到达的费用fee，两城市之间的直接距离distance，还有经过的城市destination。9部分设计函数描述l

4、RailSystem(conststring&filename)构造函数，调用load_services(stringconst&filename)函数读取数据lload_services(stringconst&filename)读取传入的文件中的数据并建立上述两个map以模拟欧洲铁路路线图lreset(void)遍历cities图，初始化所有城市的信息：visted未访问，total_distance最大值，total_fee费用最大值，from_city为空l~RailSystem(void)析构函数，用delete将两个map中所有使用new操作符

5、开辟的空间删除lvoidoutput_cheapest_route(conststring&from,conststring&to,ostream&out);输出两城市间的最少费用的路径，调用calc_route(stringfrom,stringto)函数计算最少费用lcalc_route(stringfrom,stringto)使用迪杰斯特拉算法计算from和to两个城市间的最少费用的路径（1）简短明确地写出你实验所采用的存储结构及其用途，详细说明其中的属性的含义。1)map>outgoing_service

6、s用来保存由一个城市出发可以直接到达的城市名及这两个城市之间的路径信息。2)listms以service为指针的list表，保存两城市间的路径。3)mapcities用来保存所有城市信息，通过城市名查找该城市有关信息。4)priority_queue,Cheapest>candidates存储候选的遍历城市，City*是优先队列存储的对象类型，vector是该对象的向量集合，Cheapest是比较规则。三、实验环境操作系统Win7、调试软件VS2012四、

7、实验过程与分析（1）描述你在进行实现时，主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明你设计的巧妙之处。该实验主要用到了迪杰斯特拉算法，这个算法要求所有边的权值非负，提出了按路径长度递增的顺序逐步产生最短路径的算法，首先求出长度最短的一条路径，然后参照它求出长度次短的一条路径，以此类推，指导顶点到其他顶点的最短路径全部求完为止即可解决该实验的问题。算法的时间复杂度是，空间复杂度为1)calc_route(stringfrom,stringto)函数利用优先权队列和迪杰斯特拉算法，计算任意两城市之间费用最少的路径，优先权队列按照费用由大到

8、小的顺序入队。首先初始化所有城市的信息。通过迭代器遍历它的邻接链表