基于C++实现（控制台）全国交通咨询模拟【100010852】

# 全国交通咨询模拟 ## 一、需求分析 1、提供对城市信息进行编辑（添加或删除的功能）；提供对列车时刻表和飞机航班进行编辑（添加或删除）的功能。（提供文件形式输入和键盘输入两种方式） 2、提供两种最优决策：最快或最省钱到达。全程只考虑一种交通工具。 3、旅途中耗费的总时间应该包括中转站的等候时间 4、咨询以用户和计算机对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地 ## 二、概要设计 ### 1、数据类型   ### 2、基本操作 ``` void editEdgeFromFile(struct graph *g); //从文件读入并且编辑边 void editEdgeFromUser(struct graph *g); //从用户读入并且编辑边 void editCityFromUser(struct graph *gt,struct graph *ga); //从用户读入并且编辑城市 void editCityFromFile(struct graph *gt,struct graph *ga); //从文件读入并且编辑城市 int getnum(int &i,char* tempstr); //读取从文件输入的数字 void buileFromUser(struct graph *g); //根据用户输入的边建立一个图 void buileFromFile(struct graph *g); //根据文件输入的边建立一个图 void initializeGraph(struct graph *g); //初始化一个图 void city_edit(struct graph *gt,struct graph *ga); //编辑城市 void edge_edit(struct graph *g); //编辑边 void buildgraph(struct graph *g); //建立一个图 void dijkstra_money(struct graph* g,int x,struct edgenode pre[]) //据 dijkstra 算法计算最省钱路径 void inquire_money(struct graph* gt,struct graph* ga) //查询最省钱路径 void dijkstra_time(struct graph* g,int x,struct edgenode pre[]) //根据 dijkstra 算法计算最快到达路径 void inquire_time(struct graph* gt,struct graph* ga) //查询最快到达路径 void inquire_menu(struct graph* gt,struct graph* ga) //查询菜单 void manage_menu(struct graph* gt,struct graph* ga) //管理菜单 void main_menu(struct graph* gt,struct graph* ga) //主菜单 ``` 3、流程以及调用关系    ## 三、详细分析 ### 1、插入删除操作（包括初始的建图） （1）初始的建图（图的初始化） <img src="wps37DD.tmp.jpg" alt="img" style="zoom:67%;" />  （2）城市的插入删除  （3）边的插入删除 可以看到对于图的编辑就是基本的图的节点和边等的插入和删除操作。 在建立初始的图和插入的时候，会分离节点（具体分析见下面）。 ### 2、最省钱和最快路径  首先输入起点和终点，再使用 dijktra 算法找到“最短路”。其中使用 pre 记录路径，方便接下来的依次打印。 使用最短路算法，其中值得注意的是若起始时间在旅客到达该站之前，旅客是无法乘坐该趟火车/飞机的。加了一个判断，保证了算法的真实性。 值得注意的是为了保证在求最快到达的时候包括了等待时间，每个有两条或者两条以上路径交汇的节点要分成两个节点或者多个节点。并且将等待时间形成一条边从一个节点指向其分离出来的节点，然后再进行 dijkstra 算法。 ## 四、设计和调试分析 1、在文件读入的时候会出现一些问题，因为没有讲过文件读入，所以在文件读入时的内存分配上有些问题，经过排查，使用了正确的文件读入方式。 2、考虑道路网多是稀疏网，故采用邻接表作存储结构，其空间复杂度为 O(e)，此时的时间复杂度也为 O(e)。构建邻接表的时间度为 O(n+e)，多分离节点其时间复杂度不超过 O(e)。核心算法基于 dijkstra 算法，其时间复杂度为 O()。输出路径的时间复杂度不超过 O(e)。由此，本算法的总时间复杂度不超过 O()。 3、采用了较为简单的 dijkstra 算法，但是考虑到实际的情况（列车的时间冲突和等待时间）。在该算法上进行了一些修改，所以在处理实际问题的时候，不能简单的套用算法，要进行适当的修改。 五、用户手册 1、首先要求输入初始的图（以文件输入为例）   2、接着进入主菜单  3、可以选择查询或者管理，输入错误会报错  4、查询火车，最省钱，输入起点和终点  5、管理系统，可以选择用户输入或者文件输入  ## 六、测试结果 ### 0、交通图初始化 以火车为例，下图为根据附件 buildCity.txt 和 buildTrain.txt 所建立的交通图：  ### 1、最省钱查询  由之前构建的交通图可以看到，从北京出发到达昆明可以有三条不同的路径，其一是【北京-> 上海-> 昆明】，花费 900 元；其二是【北京-> 昆明】，花费 1000 元，其三是【北京-> 天津-> 重庆-> 昆明】，花费 450 元。但是事实上第三条途径不存在，因为重庆-> 昆明的发车时间比天津-> 重庆的到达时间还要早，故不可能走这条途径。因此在最省钱路径中我们选择了【北京-> 上海-> 昆明】，结果正确。 ### 2、最快查询  搜索北京到重庆的最快路径，得到的结果是【北京-> 天津-> 重庆】，表面上看似乎没有问题，因为【北京-> 天津】和【天津-> 重庆】分别耗时 40 和 400，比起另一条路径【北京-> 昆明】和【昆明-> 重庆】所耗时间 520+100 来说更短。但是在这次尝试中我们并没有考虑等待时间的问题，若选择第一条路径，旅客需要在天津等待 700 的时间！而选择【北京-> 昆明-> 重庆】的话只需要等待 300 的时间。 在意识到算法的缺陷之后，我们对原来的程序进行了修正。由于 dijkstra 算法并不能够直接计算等待时间，因�