基于C++实现（控制台）交通换乘规划【100011523】

# 课 程 设 计 报 告 **课程设计名称：数据结构课程设计** **课程设计题目：交通换乘规划** | 学 院： | 计算机学院 | | ---------- | ------------ | | 专 业： | 软件工程 | | 班 级： | 软件 1802 | | 学 号： | 183401050225 | | 姓 名： | 黄远鹏 | | 指导教师： | 滕一平 | # 一、题目介绍 ## 1.1 题目内容 ​ 某城市的公共交通由地铁和公交车组成，其中公交车分为空调车（每次 2 元钱）和普通车（每次 1 元）两种，地铁票价计算方式为 0~7 站 3 元，7~14 站 5 元，大于 14 站 8 元，请设计程序规划一个交通工具换乘方案。 ## 1.2 功能要求 - 设计合适的数据结构存储站点信息和连接关系信息； - 交通图至少应有 20 个结点代表各站点信息； - 能够保留各站点之间的交通方式以及预计通行时间； - 设计不止一种个性化的换乘方案，如时间最短、换乘次数最少、花费最小等。 # 二、系统功能分析 ## 2.1 功能分析 设计合适的数据结构存储站点信息和连接关系信息，交通图至少应有 20 个结点代表各站点信息。 考虑到一般的公交和地铁线路都是双向的，可以建立一个带权无向图，用顶点表示站点，边表示从一个站点到另一个站点有直达线路，边上的权值表示从一个站点到另一个站点所需付出的代价。这里假设图中没有重边。 在实际的交通线网中，边的个数与顶点的个数相比不会太少，交通线网应该是个稠密图，所以在图的实际存储中可采用邻接矩阵的存储结构。 能够保留各站点之间的交通方式以及预计通行时间，设计不止一种个性化的换乘方案，如时间最短、换乘次数最少、花费最小等。 根据题目要求，从实际情况出发考虑，应该满足用户的各种不同需求，如： - ① 仅考虑地铁线路，给出任意两地铁站之间的乘车方案； - ② 同时考虑地铁和公交线路，给出乘车方案。 乘车方案应当包括具体的乘车路线（途经的所有站点以及乘坐的具体线路）、总用时以及乘车费用。 ## 2.2 模块设计 系统功能模块的设计见图 2.1。  图 2.1 系统功能模块图 # 三、数据结构设计 ## 3.1 边的数据结构 边结构体 edge 包含两部分： - 数据部分：包括一个字符串 name 和车辆属性标志 type。name 用来存放这一条边所对应的公交（或地铁）的线路名称。车辆属性标志 type 用于区分不同的车辆类型，是自定义的枚举型变量：0 代表地铁（subway），1 代表普通公交（normal_bus），2 代表空调公交（air_bus），INF 代表无直达交通线路（none），其中 INF 表示无穷大，在实际存储中可以用一个比较大的整型数字表示（如 0x3f3f3f3f）。 - 操作部分：包括一个无参构造函数和一个带参构造函数。  图 3.1 边的数据结构 ## 3.2 图的数据结构 图类 graph 包含两部分：数据部分（见表 3.1）和操作部分（见表 3.2）。 表 3.1 graph 的数据部分 | 标识符 | 说明 | | --------- | ------------------------------------------------------------ | | vertexNum | 总顶点数，初始值为 0 | | vertices | 存放顶点信息，即每个站点的名称 | | index | 从具体的顶点信息到 vertices 中下标值的映射（用 hash 表实现） | | adjM | 邻接矩阵，存放边的具体信息 | 表 3.2 graph 的操作部分 | 函数名 | 说明 | | --------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | | insertVertex | 功能：在图中添加一个顶点；参数：一个字符串，代表站点名；返回值：bool 类型，添加成功返回 true，添加失败返回 false | | graph | 功能：无参构造函数 | | isVertexInGraph | 功能：判断一个站点是否已经在图里；参数：一个字符串，代表站点名；返回值：bool 类型，已经在图里返回 true，不在图里返回 false | | insertEdge | 功能：在图中添加一条边；参数：两个字符串，代表边的两个顶点；一个 edge 结构体，代表边的信息；返回值：bool 类型，添加成功返回 true，添加失败返回 false | | lessTime | 功能：输出“时间短”换乘方案；参数：两个字符串，分别代表起点和终点 | | findMin | 功能：lessTime 的辅助函数，用于在 Dijkstra 算法中寻找没有确认最短路径的顶点中到达耗时最小的；参数：两个数组，对应 Dijkstra 算法中的距离数组和标记数组（详见 4.3.1 节）；返回值：如果找到满足要求的顶点，返回这个顶点对应的下标；否则返回-1 | | subwayOnly | 功能：输出“只坐地铁”换乘方案；参数：两个字符串，分别代表起点和终点 |  图 3.2 图的数据结构 # 四、功能模块设计 ## 4.1 系统总流程 总体设计思路如下： - 首先要求用户加载地图文件，根据地图文件的内容在系统中建立图的存储结构。 - 用户输入起点和终点，并选择具体的乘车方案类型（时间最短或只坐地铁）。 - 根据用户的选择计算具体的乘车方案并输出相关信息。 系统有一定的纠错性，比如用户输入了一个不存在的站点，系统能够输出提示信息。 系统总流程如图 4.1 所示。  图 4.1 系统总流程 ## 4.2 加载地图 ### 4.2.1 主要函数 函数原型：void loadMap() 算法描述：通过调用 insertEdge 函数，以在图中插入边的方式建立起交通线网图。流程图见图 4.2。  图 4.2 加载地图的流程图 ### 4.2.2 子函数 **插入边的函数** 函数原型：bool graph::insertEdge(string vertex1_name, string vertex2_name, edge new_edge) 算法描述：先在图中插入两个顶点 vertex1 和 vertex2，再查询 vertex1 到 vertex2