/Travel-Consultation-System

Primary LanguageC++

交通咨询系统

需求分析

  1. 信息录入：需要从磁盘中读取大量的数据，包括火车与飞机两个时刻表，假设已获得格式化的时刻表数据，程 序需要从文本文件中把有效数据读入内存中。
  2. 城市编辑：这里由于编辑的数据量一般不大，直接在内存中对城市进行编辑，而不存入磁盘。城市增加仅在城 市列表中增加城市即可；城市删除不仅要删除城市列表中的特定城市，还要去掉其它城市与该城市之间的交通信 息。
  3. 交通线路编辑：由于编辑量不大，同样只在内存中编辑。要求能对城市间的交通信息进行增加或删除。
  4. 遍历显示：可以通过某种遍历算法显示所有的城市或者所有线路以供查询。
  5. 交通咨询：核心算法。提供两种策略，一种最为省钱，一种最省时间。要求用户提供起点与终点，提供出发时 间、出行方式和出行策略，由程序筛选最优路线。
  6. 简单可视化界面：为保证Project的实用性，简单提供可视化目录连接各个功能，方便用户查找。

概要设计

  • 最主要的数据结构为图，即源码中的Travel_Map，这里采用邻接表的形式进行存储，则需要辅助数据结构城市 City与线路Road，保存城市（City）列表，每个城市节点保存以该城市为起点，到其它城市的直接交通路线。每 种交通方式存入一幅图中，整个程序需要两幅图，一幅为铁路交通图Train_Map，一幅为航线交通图Plane_Map。 交通时刻表存储在每个城市到其它城市的路线中，包括车次号/航班号、出发时间、途径时间、到达时间、票 价。这两幅有向图只存储所有出度，不存储入度。
  • 辅助数据结构为时间Time，提供两个整型变量，一个记录小时，一个记录分钟。这个时间可以是某个时刻，也 可以是一个时间段。重载一些运算符，小于代表早于，大于代表晚于，其余与常规认识均相同。值得注意的有两 点，一个是时间加法不会在24小时进位，因为加法用于计算途径时间，给出小时更为直观，所以不进位到日；一 个是减法，大时间-小时间按常规时间减法，小时间-大时间要先+24小时再减，因为是次日到达，比如20：00出 发，8：00到达，相差12小时。
  • 辅助数据结构车站Station，作为计算最短路存储路径所用。Station存储某节点在最短路上的前一个节点到该节点 的最短路径信息，包括Road中提到的各种信息，额外附加一个是否为次日到达的信息，在输出中将利用Station分 别显示。

调试分析

  1. 城市增加功能
  • 时间复杂性分析：O(n)
  1. 城市删除功能

  • 时间复杂性分析：O(n*m)

  • 设计思路：删除城市是核心算法之外比较复杂的算法，要考虑三点，删除城市，删除其他城市指向该城市的出度，调整某些出度的城市序号。其中，删除城市可利vector库函数，删除出度可利用DestroyRoad函数，调整序号在本函数中需要完整给出实现。
    调整一半城市序号要遍历所有Road节点，n为城市数目，m为城市的出度完成这个模块曾经遇到过问题：我曾经先删除城市，后调整出度序号；还曾先让p指向城市的出路，然后删除路；这两种写法或导致数组越界，或导致指针指向不明，导致程序崩溃。这里解决问题时我在多处插入断点，观察程序运行到哪里会导致崩溃，然后仔细分析代码逻辑，发现逻辑问题，经过修正和重新测试，问题解决。

  1. 增加线路
  • 时间复杂性分析：O(n)
  • 定位出发点需要遍历Citylist。这里我曾经把新线路插入到出度链表末端，会导致时间增加，后思考改为插入前端，可以节省时间O(m)
  1. 删除线路
  • 时间复杂性分析：O(n+m)
  • 定位城市需要遍历Citylist，遍历该城市所有出度需要m，m为城市出度数目
  • 这里尤其应当注意空指针问题和删除所有满足条件的线路的区别，还要考虑删除头结点与删除其他节点的区别，这里处理得当，没有出现问题。
  1. 最短时间路径

  • 时间复杂性分析：O(n*max(n,m))

  • 设计思路：关于这个核心算法，在设计之初我就考虑应该尽可能详实地给出数据。无论何种策略，应给出总计费用与时间，换乘路线，换乘路线各站的详细信息都应该输出，所以一般的Dijkstra算法精巧的path数组处理部分应改换，思路不变但是存储的数据应当扩充。

  • Dijkstra算法要循环n-1次，每次会遍历一次城市列表，会遍历一次城市的出度列表。这里曾经遇到过许多问题，最主要的就是时间计算问题。早期的考虑方式很多，最终统一改成清晰的时间减法，避免误会，权重处理得当。这里的问题不仔细观察输出的数据很难发现，我也是偶尔发现某些线路的时间总计算的不正确，这才发现时间权重计算出现问题。

  • 还遇到的问题就是格式化输出问题，这不是很难的问题，但需要仔细，有耐心，处理好中英文占据字符的区 别，制表符\t的处理方式，慢慢测试各种情况，才能处理的美观。

  • 还出现的问题是我误以为整个图一定是连通的，所以没有设置捕捉异常。事实与想的正好相反，整个图只是 弱连通（忽略方向，退化成无向图，图是联通的），并不是任意两个节点互相可达，我碰巧试出了一些偏颇 城市的错误，启发了我这个问题，经过完善，这个异常被排除。

  1. 最省钱路径

  • 时间复杂性分析：O(n*max(n,m))

  • 理由同上

  • 这里算法基本框架同上，但是多了一个时间计算问题，开始这里的总计时间问题非常棘手，最后是将模块取出代入简单数据，逐步插入断点调试才找到初始代码的问题所在，经过进一步分析，找到了解决方案，最终总计时间计算总是正确的。