基于 QT（C++）开发的地铁换乘系统【100010886】

# 上海地铁换乘系统 - 使用 Qt 实现的一个图形化上海地铁换乘系统，支持查询两地铁站之间的最短路径和最少换乘路径，支持自主添加线路、站点等等。 ## 文件目录： - exe：该目录存储可执行文件，直接双击目录下的 5_2_subway.exe 文件即可运行。不需要预先安装 Qt 环境。 - source：该目录存储 Qt 项目，包括项目文件、源代码、资源文件等等。 - 设计说明.pdf：详细解释了本程序的设计方法、运行方法等等。 ## 效果：   ## 软件功能 本程序为一个较为完备的地铁网络线路展示系统，功能主要包括以下几个方面：1、图形化显示上海地铁网络结构，并支持放大、缩小等功能，可以显示某一站点的详细信息等等； 2、查询两站点之间的路线，支持最短路线查询和换乘最少路线查询两种模式，并将查询结果显示在文字界面和图形化界面上； 3、支持添加线路和站点，添加完成后可以进行图形化显示，并可以用于 1 和 2 的所有功能中 ## 设计思想 ### 1 总体设计思想 本题相较于上一题而言是一道综合性强、涵盖范围广、实用性强的题目。对于这种大型工程，不可能一次设计出完全适合的数据结构和算法。为此，我采用了敏捷开发的思想，结合在软件开发中学习到的 UML 建模思想，先从整个系统的功能需求大致推导出需要的各个类和数据结构，按照完整的功能链需求列出各个类之间的关系，快速开发出一个基础版本。然后，再对该版本逐步进行完善，得到更加完善的版本。 由于本题没有涉及到动画播放、延迟等等方面的内容，故算法和图形界面的代码可以实现完全分离。这对于面向对象设计是一件很好的事情。在代码结构的设计中，我充分利用了面向对象的开发思想，为每个可以抽象出来并且具有一些类似操作的部分都设计了相应的类，如站点类、线路类、地铁系统类、图形界面管理类等等。各类之间的关系也非常明确，比如线路类中含有多个站点类成员，地铁系统类中含有多个线路类成员等等。在开发过程中，首先大致设计出后端的各种类和数据结构，并且加以实现。然后再逐步实现前端的界面，过程中将后端操作与前端的按钮等进行连接，实现前后端相连。 ## 2 各模块具体设计思想 本题的数据结构设计以及类的划分大多是按照实际情况来的。每个站点都有自己的信息，故我建立了一个 Station 类表示站点，包含名称、经纬度、所属线路等等相关信息。而站点又是通过线路进行组合的，故我建立了一个 Line 类表示线路，该类中存储了线路的名称、颜色、包含站点、总站点数等等信息。此外，整个地铁线路图是一个整体，故我建立了一个 SubwaySystem 类，用于表示一整个地铁系统，包含多个线路和站点的信息。这种类设计也体现了一种自顶向下、自下而上的思想。 在数据结构方面，由于站点、线路是名称和实体对象之间进行一一对应，故我在很多地方使用了 Qt 中的 QMap 这一数据结构。QMap 类似 c++ 中的 map，是基于红黑树实现的一种键值相对应的类型，使用效果非常类似于哈希表，但是其查找的复杂度为 O(logn)，稍慢于哈希表。程序中由于地铁站点和线路数目有限，故使用 QMap 也可以达到很高的效率。 在如地铁站点所属线路等方面，我还使用了集合这一数据结构。Qt 中的集合类是 QSet，集合的特性使得元素不能重复插入集合中，非常适合某些特殊场合的要求。 在本题的算法设计部分，最关键的部分是如何查询最短路径以及最少换乘路径。这两个问题我采用了两种不同的实现方法。 最短路径问题是典型的使用 Dijkstra 算法进行求解的问题。同时，通过查阅各种资料，我了解到还有一种 SPFA 算法也可以很好地求解单源最短路径问题。 SPFA 算法要对所有的边去进行一次松弛操作，进行了 n-1 次更新，先初始化距离数组，起点赋值为 0，其余赋值为无穷大，先起点入队列，入了队列的被标记，当队列不为空时循环，队首元素出队，松弛与队首元素相连的边，这些被更新的点如果不在队列中就加入队列，队首元素继续出队，松弛与队首元素相连的边，是不需要去找离原点最近的点的，所以 Dijkstra 算法用的是小根堆优化，SPFA 直接用的队列优化。 此外，SPFA 算法可以处理边权值为负的情况。由于地铁站点之间的距离一定是正数，因此这一点利用不到。在程序中，我使用了 Dijkstra 求解最短路径问题。算法的主要流程如下（为简化算法流程图，没有标出不存在任何路径的情况）：  最少换乘路径问题无法使用上述算法进行求解，因为无法定义距离。如果以换乘的次数作为某站点的距离，那么将会出现某站点到另一站点换乘次数反而减少的情况，而且这种情况是很不好判断的，需要记录前面经过的所有站点，因此也不适用 SPFA 算法。程序中，我使用了广度优先遍历思想进行了算法设计。从起始站点开始，依次遍历所有不需要换乘、需要换乘 1 次、需要换成 2 次，……的站点，直到找到了终点站。算法流程如下：  ### 逻辑结构与物理结构 本题考察的知识点较为综合，故数据结构使用的也非常丰富。逻辑结构方面，集合结构、线性结构、树形结构、图形结构均有涉及。集合结构用于记 录站点所属线路等等不可重复、对顺序无要求的信息。线性结构的使用非常广泛，许多地方使用了 QVector、QList 等线性结构，如线路包含的站点、返回查询的线路结果等等。树形结构没有显式进行使用，但是 Qt 的图形对象都设置了 parent，整个图形界面实际上在逻辑上反映为一颗很大的对象树，MainWindow 是根节点。最后，地铁网络图的表示显然使用了图形结构，Dijkstra、SPFA 等算法也是基于图形结构实现的。 物理结构方面，也是顺序存储、链式存储、散列存储、索引存储均有涉及。前面两项分别对应 QVector 和 QList 的使用，较为普遍。对于需要经常随机访问而很少插入、删除的数据列表而言，使用顺序存储结构；对于需要经常插入。删除的数据而言，使用链式存储结构。由于站点、线路的名称与其本身一一对应，故在地铁系统类中，使用名称到内容的 Hash 表来进行存储。这里用到了散列存储方法，使用了 Qt 中的 QMap 结构。关于线路中包含的所有站点，使用了索引存储结构进行存储。由于地铁系统类中已经存储了站点信息，故线路中不再重复存储，仅记录了其在地铁系统类的 Hash 表中的相应索引，减少了重复存储，提高了效率。 类定义如下：站点类，记录一个站点的基本信息，如名称、经纬度等等 ``` structEdge { QSet<QString>line_list; intdist = 0; }; class Station { protected: QString name; double longi, lati; /* 站点经纬度 */ QPointF coord; /* 站点在图上的坐标位置 QMap<QString,Edge> edges; //边 */ QSet<QSt