1. 项目概述与核心价值最近在整理个人项目库翻到了一个几年前做的“地铁线路查询系统”用C和Qt框架实现的。当时做这个项目一方面是觉得市面上的查询工具要么是网页版要么是手机App想试试用桌面端实现一个体验一下本地计算的流畅感另一方面也是想系统地练练手把C的面向对象、数据结构算法和Qt的GUI、网络、文件操作这些知识点串起来。没想到这个项目后来成了我面试和带新人时经常提到的案例因为它麻雀虽小五脏俱全覆盖了从需求分析、数据结构设计、核心算法实现到最终界面交互和部署的完整流程。这个系统核心就干一件事给你一个起点站和一个终点站它能帮你找出所有可能的乘车路线并且按照你指定的策略比如换乘次数最少、途经站点最少、时间最短进行排序推荐。听起来简单但背后涉及到图论算法的应用、高效数据结构的组织、以及如何把冰冷的算法结果用友好直观的界面呈现出来。对于正在学习C和Qt想找一个有实际应用场景、又不至于太复杂的综合项目来练手的同学来说这个地铁查询系统是个非常不错的选择。它不要求你有多高深的图形学或并发编程知识但能扎实地锻炼你的工程思维和代码能力。2. 整体架构设计与技术选型2.1 为什么选择C和Qt首先聊聊技术栈。选择C核心诉求是性能和控制力。地铁网络数据一旦规模上去比如包含几十条线路、上千个站点最短路径查询是个高频且要求实时响应的操作。Dijkstra、Floyd这些经典算法用C来实现可以精细地管理内存选择最合适的数据结构如邻接表效率上有保障。而且用C写核心算法模块逻辑清晰便于后续优化和移植。而选择Qt则完美弥补了C在快速开发图形界面方面的短板。Qt不仅仅是一个GUI库它更是一个成熟的应用程序框架提供了信号与槽Signals Slots这一强大的对象间通信机制、丰富的UI控件、便捷的文件与网络IO、甚至数据库访问支持。用Qt Designer拖拽式设计界面再用C代码实现业务逻辑开发效率很高。更重要的是Qt是跨平台的写一套代码稍微调整一下编译配置就能在Windows、macOS、Linux上运行这对于一个工具类软件来说非常友好。2.2 系统核心模块划分基于上述考量我将系统分成了几个松耦合的模块这也是一个良好软件设计的起点数据层负责地铁线路数据的加载、解析和存储。数据通常来自一份结构化的文本文件如JSON或自定义格式里面包含了线路名、站点名、站点间的连接关系和权重如距离或时间。核心算法层这是系统的“大脑”。它基于数据层构建的图模型实现路径查询算法。这里至少要实现一个最短路径算法如Dijkstra算法用于查询最少站点或最短时间和一个考虑换乘惩罚的算法用于查询换乘最少。业务逻辑层作为UI和算法层之间的桥梁。它接收用户从界面输入的查询请求起点、终点、策略调用对应的算法然后将算法返回的原始路径数据可能是一堆节点ID转换成对用户友好的信息如线路名、站名、换乘提示。表示层UI层基于Qt Widgets构建的用户界面。主要包括线路图展示区、查询条件输入区、结果列表展示区。理想情况下线路图应该是可交互的点击站点能高亮或直接作为查询输入。这几个模块之间通过清晰的接口进行通信比如业务逻辑层向算法层请求路径算法层只返回std::vectorint节点ID序列业务逻辑层再将其与数据层结合生成std::vectorRouteSegment包含线路、站名等信息的路径段。这样的设计使得单元测试、模块替换比如换一个更快的算法变得非常容易。注意在项目初期不要过度设计。我的建议是先让核心功能查询跑起来哪怕所有代码都写在MainWindow.cpp里。功能稳定后再着手进行上述模块化重构你会对“高内聚、低耦合”有更深刻的理解。3. 数据结构设计与数据建模3.1 如何用图来建模地铁网络这是整个项目的基石。地铁网络天然就是一个图Graph。每个地铁站是图中的一个顶点Vertex相邻两站之间的轨道是连接顶点的一条边Edge。但地铁图有它的特殊性换乘。同一个物理地点如“人民广场”可能是多条线路的换乘站。在图中我们不能简单地将它建模为一个顶点否则“1号线的人民广场站”和“2号线的人民广场站”之间就没有边相连算法就无法发现换乘。因此常见的建模方式有两种顶点为“站点-线路”对将“1号线-人民广场”和“2号线-人民广场”视为两个不同的顶点。它们之间通过一条权重很小的边代表换乘步行时间比如2分钟连接。同一线路上的相邻站点的边权重可以用站间距离或运行时间来设定。顶点为物理站点边带线路属性每个物理站点是一个顶点。如果两个站点被某条线路直接连接就在它们之间添加一条边并在这条边上记录所属的线路ID。换乘站则是一个单独的顶点所有经过它的线路都连接到这个顶点上。我采用的是第一种方法因为它更直观在后续生成换乘提示时更方便。我们定义顶点的数据结构如下// 地铁网络图中的顶点 struct StationNode { int id; // 顶点唯一ID std::string name; // 站点名如“人民广场” std::string line; // 所属线路如“Line1” // 经纬度坐标用于界面绘图 double longitude; double latitude; // ... 其他信息如是否换乘站 };边则相对简单// 地铁网络图中的边 struct TrackEdge { int fromNodeId; int toNodeId; double weight; // 权重可以是距离(km)或时间(分钟) // 如果是站内换乘边可以加一个类型标识 bool isTransfer; };3.2 图的存储邻接表有了顶点和边的定义接下来要考虑如何存储这个图。对于地铁网络这种稀疏图每个站点只和很少的邻居相连邻接表Adjacency List是空间和时间效率最高的选择。在C中我们可以用std::vectorstd::vectorstd::pairint, double来表示邻接表其中外层vector的索引是顶点ID内层vector存储的是邻居顶点ID 边权重对。但为了存储更多边的信息如是否为换乘边我通常会定义一个AdjacencyInfo结构体然后使用std::vectorstd::vectorAdjacencyInfo。struct AdjacencyInfo { int neighborId; double weight; bool isTransfer; // 如果是运行边还可以存储所属线路用于结果展示 std::string lineId; }; class SubwayGraph { private: std::vectorStationNode nodes; // 顶点集 std::vectorstd::vectorAdjacencyInfo adjacencyList; // 邻接表 std::unordered_mapstd::string, int stationNameToNodeId; // 站名到顶点ID的快速映射 public: // ... 添加顶点、添加边、查询邻居等方法 bool addStation(const StationNode node); bool addTrack(int fromId, int toId, double weight, const std::string lineId); bool addTransfer(int nodeId1, int nodeId2, double transferTime); const std::vectorAdjacencyInfo getNeighbors(int nodeId) const; int findNodeIdByNameAndLine(const std::string name, const std::string line) const; };这个SubwayGraph类就是数据层和算法层共用的核心数据结构。stationNameToNodeId这个哈希表非常重要它使得我们能够通过“站名线路”快速定位到图中的顶点ID这是处理用户输入用户通常只输入站名的第一步。4. 核心路径查询算法实现4.1 算法选型Dijkstra 还是 Floyd路径查询的核心是图的最短路径算法。常见的有Dijkstra算法单源最短路径适合每次查询时实时计算。给定一个起点它能算出到网络中所有其他点的最短路径。对于我们的查询系统一次查一个起点-终点对Dijkstra是首选。Floyd算法多源最短路径通过动态规划一次性计算出所有点对之间的最短路径并存储起来。查询时直接查表速度是O(1)。但它的空间复杂度是O(V²)对于大型网络V是顶点数内存消耗巨大且初始化计算的时间复杂度是O(V³)在数据更新时如新线路开通需要重新全量计算。因此对于交互式、数据更新不频繁的地铁查询系统Dijkstra算法是更实用和资源友好的选择。我们甚至可以实现一个“双向Dijkstra”优化从起点和终点同时开始搜索相遇时停止在大型网络上能显著减少搜索范围。4.2 Dijkstra算法的C实现与优化标准的Dijkstra算法使用优先队列最小堆来选取当前距离起点最近的未访问顶点。这里的关键是“距离”的定义在我们的系统中它可以根据查询策略变化最少站点每条边的权重设为1。最短时间边的权重是站间运行时间换乘时间换乘边的权重。最少换乘这是一个 trick。我们不能简单地将换乘边的权重设得很大因为Dijkstra是基于累加权重工作的。一种方法是分层图将不同线路视为不同的层层内移动坐车权重为0或很小跨层移动换乘权重为1。另一种更简单实用的方法是先按“最少站点”找到路径然后对路径进行后处理计算换乘次数作为排序依据之一。下面是一个支持自定义权重策略的Dijkstra算法实现框架#include queue #include vector #include limits #include functional struct DijkstraResult { std::vectordouble dist; // 从起点到各点的最短距离 std::vectorint prev; // 路径前驱节点用于回溯路径 }; DijkstraResult dijkstra(const SubwayGraph graph, int startId, std::functiondouble(const AdjacencyInfo) weightFunc) { int n graph.getNodeCount(); DijkstraResult res; res.dist.assign(n, std::numeric_limitsdouble::max()); res.prev.assign(n, -1); res.dist[startId] 0.0; // 使用优先队列pair当前距离, 顶点ID using P std::pairdouble, int; std::priority_queueP, std::vectorP, std::greaterP pq; pq.emplace(0.0, startId); std::vectorbool visited(n, false); while (!pq.empty()) { auto [currentDist, u] pq.top(); pq.pop(); if (visited[u]) continue; visited[u] true; for (const auto edge : graph.getNeighbors(u)) { int v edge.neighborId; // 通过weightFunc回调动态计算边权重 double weight weightFunc(edge); if (currentDist weight res.dist[v]) { res.dist[v] currentDist weight; res.prev[v] u; pq.emplace(res.dist[v], v); } } } return res; }这个实现的关键在于weightFunc这个回调函数。对于“最少站点”查询我们传入一个返回常量1的函数对于“最短时间”我们传入一个返回edge.weight的函数对于“最少换乘”我们可以传入一个函数对普通运行边返回0对换乘边返回一个很大的惩罚值但这并非完美只是近似。4.3 路径回溯与结果组装Dijkstra算法结束后我们得到了prev数组。要获取从起点startId到终点endId的路径需要从终点反向回溯到起点std::vectorint getPath(const DijkstraResult res, int endId) { std::vectorint path; for (int at endId; at ! -1; at res.prev[at]) { path.push_back(at); } std::reverse(path.begin(), path.end()); return path; // 返回的是顶点ID的序列 }拿到顶点ID序列后业务逻辑层需要将其“翻译”成用户能看懂的路线描述。这需要查询SubwayGraph获取每个顶点对应的StationNode然后判断连续两个顶点是否属于同一条线路。如果属于同一条线就是“乘坐X号线经过A、B、C站”如果属于不同线路就在前一个顶点处提示“在X站换乘Y号线”。std::vectorRouteSegment convertToRouteSegments(const SubwayGraph graph, const std::vectorint nodePath) { std::vectorRouteSegment segments; if (nodePath.empty()) return segments; RouteSegment currentSeg; currentSeg.lineName graph.getNode(nodePath[0]).line; currentSeg.stations.push_back(graph.getNode(nodePath[0]).name); for (size_t i 1; i nodePath.size(); i) { const auto prevNode graph.getNode(nodePath[i-1]); const auto currNode graph.getNode(nodePath[i]); // 判断是否为换乘站名相同但线路不同 bool isTransfer (prevNode.name currNode.name) (prevNode.line ! currNode.line); if (isTransfer) { // 结束当前段开始新段 segments.push_back(currentSeg); currentSeg RouteSegment(); currentSeg.lineName currNode.line; currentSeg.stations.push_back(currNode.name); } else { // 同一线路继续添加站点 currentSeg.stations.push_back(currNode.name); } } // 添加最后一段 if (!currentSeg.stations.empty()) { segments.push_back(currentSeg); } return segments; }5. Qt图形界面设计与交互实现5.1 主界面布局与控件选择Qt提供了多种界面布局方式水平、垂直、网格、表单等。对于这个系统我采用一个经典的左右分栏布局。左侧使用QGraphicsView和QGraphicsScene来绘制交互式地铁线路图。这是界面的视觉核心。右侧使用QWidget组合各种控件垂直布局。查询输入区两个QComboBox用于选择起点和终点可以输入拼音或汉字进行过滤一个QButtonGroup包含多个QRadioButton让用户选择查询策略最少换乘/最短时间/最少站点一个QPushButton触发查询。结果展示区一个QTextBrowser或QListWidget用来清晰、分条地展示查询出的路线详情包括每段乘坐的线路、经过的站点、总站数、估计时间、换乘次数等。地图控制区一些按钮或滑块用于控制地图的缩放、平移或者高亮显示某条线路。在Qt Creator中使用Designer可以很方便地拖拽出这个界面并为其各个控件设置好对象名如startComboBox,queryButton然后通过“提升为...”功能将左侧的QGraphicsView提升为我们自定义的MapWidget类以便实现自定义绘图和交互。5.2 自定义绘图绘制地铁线路图在MapWidget类继承自QGraphicsView中我们需要在QGraphicsScene上绘制所有站点和线路。数据映射首先需要将SubwayGraph中每个StationNode的经纬度或模拟坐标映射到场景的像素坐标。可以遍历所有节点找到经纬度的最大最小值然后线性映射到视图大小。绘制线路对于每条地铁线收集属于该线的所有站点按照线路走向可能需要额外数据或排序用QPainterPath连接起来并设置不同的颜色和线宽。绘制站点在每个站点坐标处画一个圆QGraphicsEllipseItem。对于换乘站可以用一个更大的圆或者不同的颜色如带圆环来标记。添加交互让站点图形项可点击。可以为每个站点的圆图元设置setFlag(QGraphicsItem::ItemIsSelectable)并连接其clicked()信号到槽函数用于选中站点作为查询的起点或终点。// MapWidget 中的关键绘制函数简化 void MapWidget::drawLine(const QString lineId, const QColor color) { auto stations graph.getStationsByLine(lineId); QPainterPath path; bool first true; for (const auto station : stations) { QPointF pos geoToPixel(station.longitude, station.latitude); if (first) { path.moveTo(pos); first false; } else { path.lineTo(pos); } // 绘制站点 auto* stationItem scene()-addEllipse(pos.x()-3, pos.y()-3, 6, 6, QPen(Qt::black), QBrush(color)); stationItem-setData(StationNodeIdRole, station.id); // 存储ID stationItem-setFlag(QGraphicsItem::ItemIsSelectable); connect(stationItem, QGraphicsEllipseItem::clicked, this, MapWidget::onStationClicked); } auto* lineItem scene()-addPath(path, QPen(color, 2)); lineItem-setZValue(-1); // 线路在站点下层 }5.3 信号与槽连接界面与逻辑Qt的信号与槽机制是连接用户操作与后台逻辑的桥梁。查询按钮点击当用户点击“查询”按钮时发出clicked()信号。我们将其连接到一个槽函数在这个函数里从startComboBox和endComboBox获取当前选中的站名。从QButtonGroup获取当前选中的查询策略。调用业务逻辑层的查询接口例如RoutePlanner::findRoutes。将返回的std::vectorRouteSegment结果格式化成字符串显示在右侧的QTextBrowser中。站点图元点击当用户在地图上点击某个站点时MapWidget::onStationClicked槽函数被触发。我们可以通过sender()或事件参数获取被点击的图元进而得到其存储的站点ID和名称。然后我们可以将这个站名设置到起点或终点的QComboBox中通过一个标志位记录当前是在设置起点还是终点。结果高亮当一条查询结果被选中时我们可以遍历该结果路径上的所有站点ID在地图场景中找到对应的图元并高亮显示例如改变颜色、放大。// MainWindow 构造函数中的连接 connect(ui-queryButton, QPushButton::clicked, this, MainWindow::onQueryButtonClicked); connect(ui-mapWidget, MapWidget::stationSelected, this, MainWindow::onStationSelected); // 槽函数示例 void MainWindow::onQueryButtonClicked() { QString start ui-startComboBox-currentText(); QString end ui-endComboBox-currentText(); int strategy getSelectedStrategy(); // 获取策略枚举值 auto routes routePlanner.findRoutes(start, end, strategy); displayRoutes(routes); // 在UI上展示结果 highlightRouteOnMap(routes); // 在地图上高亮路径 }6. 数据持久化与程序配置6.1 线路数据格式设计与解析程序不能硬编码地铁数据必须从外部文件加载。我选择使用JSON格式因为它结构清晰、可读性好且Qt原生支持通过QJsonDocument,QJsonObject,QJsonArray。一个简化的数据文件subway_data.json可能长这样{ lines: [ { id: 1, name: 1号线, color: #FF0000, stations: [ {id: 101, name: 苹果园, lng: 116.18, lat: 39.92}, {id: 102, name: 古城, lng: 116.19, lat: 39.91}, // ... 更多站点 ] }, // ... 更多线路 ], transfers: [ {stationName: 西直门, lineIds: [2, 4, 13]}, // ... 更多换乘站信息 ] }在程序启动时我们需要编写一个DataLoader类来解析这个JSON文件遍历lines数组为每条线路的每个站点创建StationNode注意ID的生成要唯一可以结合线路ID和站序。在创建站点的同时为同一线路内相邻的站点添加“运行边”TrackEdge权重可以预设或根据坐标计算距离。遍历transfers数组对于同一个换乘站名下的所有线路找到它们对应的站点顶点ID然后两两之间添加“换乘边”TransferEdge并赋予一个固定的换乘时间权重如5分钟。6.2 使用QSettings管理用户偏好一个友好的桌面应用应该能记住用户的一些设置比如窗口大小、位置、最近使用的起点终点、默认的查询策略等。Qt提供了QSettings类可以非常方便地将这些信息以键值对的形式保存到系统注册表Windows或plist文件macOS或ini文件Linux中。// 保存设置 void MainWindow::writeSettings() { QSettings settings(MyCompany, SubwayQuery); settings.setValue(geometry, saveGeometry()); settings.setValue(windowState, saveState()); settings.setValue(defaultStrategy, currentStrategy); settings.setValue(recentStarts, recentStartStations); } // 读取设置 void MainWindow::readSettings() { QSettings settings(MyCompany, SubwayQuery); restoreGeometry(settings.value(geometry).toByteArray()); restoreState(settings.value(windowState).toByteArray()); int strategy settings.value(defaultStrategy, 0).toInt(); setCurrentStrategy(strategy); recentStartStations settings.value(recentStarts).toStringList(); updateComboBoxHistory(); }在MainWindow的closeEvent中调用writeSettings()在构造函数末尾调用readSettings()就能实现用户偏好的持久化。7. 项目构建、打包与部署7.1 使用CMake管理项目对于C/Qt项目我强烈推荐使用CMake作为构建系统而不是Qt自带的qmake。CMake更现代、更强大也更容易集成第三方库。一个基本的CMakeLists.txt如下cmake_minimum_required(VERSION 3.16) project(SubwayQuerySystem VERSION 1.0.0 LANGUAGES CXX) # 设置C标准 set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) # 自动查找Qt6组件如果使用Qt6 find_package(Qt6 REQUIRED COMPONENTS Core Widgets) # 对于Qt5使用 find_package(Qt5 REQUIRED COMPONENTS Core Widgets) # 启用Qt的MOC、UIC、RCC自动处理 set(CMAKE_AUTOMOC ON) set(CMAKE_AUTOUIC ON) set(CMAKE_AUTORCC ON) # 添加可执行文件 add_executable(SubwayQuery src/main.cpp src/mainwindow.cpp src/mainwindow.ui src/mapwidget.cpp src/subwaygraph.cpp src/routeplanner.cpp src/dataloader.cpp # ... 其他源文件 ) # 链接Qt库 target_link_libraries(SubwayQuery Qt6::Core Qt6::Widgets # 如果用了其他模块如 Qt6::Network, Qt6::Charts ) # 在macOS上设置应用程序Bundle信息可选 if(APPLE) set_target_properties(SubwayQuery PROPERTIES MACOSX_BUNDLE TRUE MACOSX_BUNDLE_GUI_IDENTIFIER com.mycompany.subwayquery MACOSX_BUNDLE_BUNDLE_NAME Subway Query ) endif()在项目根目录下执行cmake -B build -S .生成构建文件然后cmake --build build进行编译整个过程非常清晰。7.2 解决Windows下的DLL依赖问题在Windows上发布Qt程序最让人头疼的就是那一堆运行时DLL。你不能指望用户电脑上恰好有对应版本的Qt运行库。手动复制DLL容易遗漏尤其是Qt5Core.dll,Qt5Widgets.dll,Qt5Gui.dll以及平台插件platforms/qwindows.dll还有C运行时msvcp140.dll,vcruntime140.dll等。推荐方法使用windeployqt工具。这是Qt官方提供的部署工具能自动扫描你的exe文件找出所有依赖的Qt库并复制到你的发布目录。操作步骤在Release模式下编译你的程序生成SubwayQuery.exe。新建一个发布文件夹如SubwayQuery_Release。将SubwayQuery.exe复制到这个文件夹。打开Qt命令行如Qt 5.15.2 (MSVC 2019 64-bit)切换到发布文件夹。执行命令windeployqt SubwayQuery.exe。工具会自动将所需的Qt DLL、插件、翻译文件等复制到当前目录及子目录如platforms。你还需要手动将项目依赖的数据文件如subway_data.json和可能用到的C运行时库如果静态链接了可以忽略复制过来。实操心得windeployqt有时会漏掉一些间接依赖的库比如如果你用了QtCharts模块它可能不会自动包含。一个检查方法是在干净的虚拟机或另一台电脑上运行你打包好的程序如果报错缺少某个DLL就回到开发机在Qt安装目录的bin文件夹里找到它手动复制过来。7.3 生成安装包对于更专业的发布可以使用安装包制作工具如Inno Setup(Windows) 或macOS PackageMaker。以Inno Setup为例你可以编写一个.iss脚本指定要打包的文件、创建开始菜单快捷方式、设置安装目录、写入注册表信息如果需要等。这样生成一个单一的.exe安装文件用户双击即可安装体验更好。8. 性能优化与扩展思考8.1 查询性能优化实践当网络规模很大时每次查询都运行一次完整的Dijkstra算法可能会成为瓶颈。以下是一些优化思路双向搜索如前所述从起点和终点同时运行Dijkstra当两个搜索的“前沿”相遇时停止。这通常能将搜索空间减半。A算法*如果每个站点有地理坐标可以将其作为启发式信息。A*算法在Dijkstra的基础上优先搜索“看起来”更接近终点的方向能进一步加快搜索速度。启发函数可以用欧几里得距离或曼哈顿距离。预计算与缓存对于热门站点对比如城市核心枢纽站之间的路径可以将查询结果缓存起来。下次查询时先查缓存。可以使用std::unordered_map键是(startId, endId, strategy)的组合值是路径结果。注意设置合理的缓存大小和过期策略。分层图或收缩层次这是高级优化技术。将网络中的主要换乘站或大站作为“枢纽”预先计算枢纽之间的最短路径。查询时先快速从起点走到最近的枢纽然后走预计算的枢纽路径再从枢纽走到终点。这能极大减少搜索的节点数。在我的实现中首先应用了双向Dijkstra对于拥有300个节点站点的网络查询时间从毫秒级降低到了亚毫秒级用户体验已经非常流畅。A*算法需要额外的坐标数据来估算代价实现起来也不复杂是下一步优化的好选择。8.2 功能扩展方向一个基础的地铁查询系统完成后可以考虑很多有趣的扩展实时信息集成通过网络请求使用QNetworkAccessManager获取地铁的实时运营状态如某条线路是否延误、某站是否临时关闭并在查询结果和地图上进行标注。票价计算根据当地的票价规则如分段计价、累计折扣在路径规划后计算出票价。多模态交通不仅限于地铁加入公交、步行、共享单车等。这需要更复杂的图模型和算法如考虑不同交通工具的速度、等待时间、换乘便利性。可视化动画在展示路径时不是静态高亮而是用一个移动的小点模拟列车行进增强趣味性。离线地图将线路图作为背景图片加载到QGraphicsScene中然后将站点绘制在上面比纯矢量绘图更美观。跨平台与移动端利用Qt的跨平台特性尝试将代码移植到Android或iOS上。这涉及到界面布局的适配和触摸交互的处理。这个项目就像一棵树的根基把这些核心功能做扎实了任何方向的扩展都是顺理成章、水到渠成的事情。它带给你的不仅仅是一个可以写在简历上的项目更是一套解决复杂问题的完整方法论——从抽象建模、算法选型、代码实现到最终的产品化。
C++与Qt实现地铁线路查询系统：图论算法与桌面应用开发实践
1. 项目概述与核心价值最近在整理个人项目库翻到了一个几年前做的“地铁线路查询系统”用C和Qt框架实现的。当时做这个项目一方面是觉得市面上的查询工具要么是网页版要么是手机App想试试用桌面端实现一个体验一下本地计算的流畅感另一方面也是想系统地练练手把C的面向对象、数据结构算法和Qt的GUI、网络、文件操作这些知识点串起来。没想到这个项目后来成了我面试和带新人时经常提到的案例因为它麻雀虽小五脏俱全覆盖了从需求分析、数据结构设计、核心算法实现到最终界面交互和部署的完整流程。这个系统核心就干一件事给你一个起点站和一个终点站它能帮你找出所有可能的乘车路线并且按照你指定的策略比如换乘次数最少、途经站点最少、时间最短进行排序推荐。听起来简单但背后涉及到图论算法的应用、高效数据结构的组织、以及如何把冰冷的算法结果用友好直观的界面呈现出来。对于正在学习C和Qt想找一个有实际应用场景、又不至于太复杂的综合项目来练手的同学来说这个地铁查询系统是个非常不错的选择。它不要求你有多高深的图形学或并发编程知识但能扎实地锻炼你的工程思维和代码能力。2. 整体架构设计与技术选型2.1 为什么选择C和Qt首先聊聊技术栈。选择C核心诉求是性能和控制力。地铁网络数据一旦规模上去比如包含几十条线路、上千个站点最短路径查询是个高频且要求实时响应的操作。Dijkstra、Floyd这些经典算法用C来实现可以精细地管理内存选择最合适的数据结构如邻接表效率上有保障。而且用C写核心算法模块逻辑清晰便于后续优化和移植。而选择Qt则完美弥补了C在快速开发图形界面方面的短板。Qt不仅仅是一个GUI库它更是一个成熟的应用程序框架提供了信号与槽Signals Slots这一强大的对象间通信机制、丰富的UI控件、便捷的文件与网络IO、甚至数据库访问支持。用Qt Designer拖拽式设计界面再用C代码实现业务逻辑开发效率很高。更重要的是Qt是跨平台的写一套代码稍微调整一下编译配置就能在Windows、macOS、Linux上运行这对于一个工具类软件来说非常友好。2.2 系统核心模块划分基于上述考量我将系统分成了几个松耦合的模块这也是一个良好软件设计的起点数据层负责地铁线路数据的加载、解析和存储。数据通常来自一份结构化的文本文件如JSON或自定义格式里面包含了线路名、站点名、站点间的连接关系和权重如距离或时间。核心算法层这是系统的“大脑”。它基于数据层构建的图模型实现路径查询算法。这里至少要实现一个最短路径算法如Dijkstra算法用于查询最少站点或最短时间和一个考虑换乘惩罚的算法用于查询换乘最少。业务逻辑层作为UI和算法层之间的桥梁。它接收用户从界面输入的查询请求起点、终点、策略调用对应的算法然后将算法返回的原始路径数据可能是一堆节点ID转换成对用户友好的信息如线路名、站名、换乘提示。表示层UI层基于Qt Widgets构建的用户界面。主要包括线路图展示区、查询条件输入区、结果列表展示区。理想情况下线路图应该是可交互的点击站点能高亮或直接作为查询输入。这几个模块之间通过清晰的接口进行通信比如业务逻辑层向算法层请求路径算法层只返回std::vectorint节点ID序列业务逻辑层再将其与数据层结合生成std::vectorRouteSegment包含线路、站名等信息的路径段。这样的设计使得单元测试、模块替换比如换一个更快的算法变得非常容易。注意在项目初期不要过度设计。我的建议是先让核心功能查询跑起来哪怕所有代码都写在MainWindow.cpp里。功能稳定后再着手进行上述模块化重构你会对“高内聚、低耦合”有更深刻的理解。3. 数据结构设计与数据建模3.1 如何用图来建模地铁网络这是整个项目的基石。地铁网络天然就是一个图Graph。每个地铁站是图中的一个顶点Vertex相邻两站之间的轨道是连接顶点的一条边Edge。但地铁图有它的特殊性换乘。同一个物理地点如“人民广场”可能是多条线路的换乘站。在图中我们不能简单地将它建模为一个顶点否则“1号线的人民广场站”和“2号线的人民广场站”之间就没有边相连算法就无法发现换乘。因此常见的建模方式有两种顶点为“站点-线路”对将“1号线-人民广场”和“2号线-人民广场”视为两个不同的顶点。它们之间通过一条权重很小的边代表换乘步行时间比如2分钟连接。同一线路上的相邻站点的边权重可以用站间距离或运行时间来设定。顶点为物理站点边带线路属性每个物理站点是一个顶点。如果两个站点被某条线路直接连接就在它们之间添加一条边并在这条边上记录所属的线路ID。换乘站则是一个单独的顶点所有经过它的线路都连接到这个顶点上。我采用的是第一种方法因为它更直观在后续生成换乘提示时更方便。我们定义顶点的数据结构如下// 地铁网络图中的顶点 struct StationNode { int id; // 顶点唯一ID std::string name; // 站点名如“人民广场” std::string line; // 所属线路如“Line1” // 经纬度坐标用于界面绘图 double longitude; double latitude; // ... 其他信息如是否换乘站 };边则相对简单// 地铁网络图中的边 struct TrackEdge { int fromNodeId; int toNodeId; double weight; // 权重可以是距离(km)或时间(分钟) // 如果是站内换乘边可以加一个类型标识 bool isTransfer; };3.2 图的存储邻接表有了顶点和边的定义接下来要考虑如何存储这个图。对于地铁网络这种稀疏图每个站点只和很少的邻居相连邻接表Adjacency List是空间和时间效率最高的选择。在C中我们可以用std::vectorstd::vectorstd::pairint, double来表示邻接表其中外层vector的索引是顶点ID内层vector存储的是邻居顶点ID 边权重对。但为了存储更多边的信息如是否为换乘边我通常会定义一个AdjacencyInfo结构体然后使用std::vectorstd::vectorAdjacencyInfo。struct AdjacencyInfo { int neighborId; double weight; bool isTransfer; // 如果是运行边还可以存储所属线路用于结果展示 std::string lineId; }; class SubwayGraph { private: std::vectorStationNode nodes; // 顶点集 std::vectorstd::vectorAdjacencyInfo adjacencyList; // 邻接表 std::unordered_mapstd::string, int stationNameToNodeId; // 站名到顶点ID的快速映射 public: // ... 添加顶点、添加边、查询邻居等方法 bool addStation(const StationNode node); bool addTrack(int fromId, int toId, double weight, const std::string lineId); bool addTransfer(int nodeId1, int nodeId2, double transferTime); const std::vectorAdjacencyInfo getNeighbors(int nodeId) const; int findNodeIdByNameAndLine(const std::string name, const std::string line) const; };这个SubwayGraph类就是数据层和算法层共用的核心数据结构。stationNameToNodeId这个哈希表非常重要它使得我们能够通过“站名线路”快速定位到图中的顶点ID这是处理用户输入用户通常只输入站名的第一步。4. 核心路径查询算法实现4.1 算法选型Dijkstra 还是 Floyd路径查询的核心是图的最短路径算法。常见的有Dijkstra算法单源最短路径适合每次查询时实时计算。给定一个起点它能算出到网络中所有其他点的最短路径。对于我们的查询系统一次查一个起点-终点对Dijkstra是首选。Floyd算法多源最短路径通过动态规划一次性计算出所有点对之间的最短路径并存储起来。查询时直接查表速度是O(1)。但它的空间复杂度是O(V²)对于大型网络V是顶点数内存消耗巨大且初始化计算的时间复杂度是O(V³)在数据更新时如新线路开通需要重新全量计算。因此对于交互式、数据更新不频繁的地铁查询系统Dijkstra算法是更实用和资源友好的选择。我们甚至可以实现一个“双向Dijkstra”优化从起点和终点同时开始搜索相遇时停止在大型网络上能显著减少搜索范围。4.2 Dijkstra算法的C实现与优化标准的Dijkstra算法使用优先队列最小堆来选取当前距离起点最近的未访问顶点。这里的关键是“距离”的定义在我们的系统中它可以根据查询策略变化最少站点每条边的权重设为1。最短时间边的权重是站间运行时间换乘时间换乘边的权重。最少换乘这是一个 trick。我们不能简单地将换乘边的权重设得很大因为Dijkstra是基于累加权重工作的。一种方法是分层图将不同线路视为不同的层层内移动坐车权重为0或很小跨层移动换乘权重为1。另一种更简单实用的方法是先按“最少站点”找到路径然后对路径进行后处理计算换乘次数作为排序依据之一。下面是一个支持自定义权重策略的Dijkstra算法实现框架#include queue #include vector #include limits #include functional struct DijkstraResult { std::vectordouble dist; // 从起点到各点的最短距离 std::vectorint prev; // 路径前驱节点用于回溯路径 }; DijkstraResult dijkstra(const SubwayGraph graph, int startId, std::functiondouble(const AdjacencyInfo) weightFunc) { int n graph.getNodeCount(); DijkstraResult res; res.dist.assign(n, std::numeric_limitsdouble::max()); res.prev.assign(n, -1); res.dist[startId] 0.0; // 使用优先队列pair当前距离, 顶点ID using P std::pairdouble, int; std::priority_queueP, std::vectorP, std::greaterP pq; pq.emplace(0.0, startId); std::vectorbool visited(n, false); while (!pq.empty()) { auto [currentDist, u] pq.top(); pq.pop(); if (visited[u]) continue; visited[u] true; for (const auto edge : graph.getNeighbors(u)) { int v edge.neighborId; // 通过weightFunc回调动态计算边权重 double weight weightFunc(edge); if (currentDist weight res.dist[v]) { res.dist[v] currentDist weight; res.prev[v] u; pq.emplace(res.dist[v], v); } } } return res; }这个实现的关键在于weightFunc这个回调函数。对于“最少站点”查询我们传入一个返回常量1的函数对于“最短时间”我们传入一个返回edge.weight的函数对于“最少换乘”我们可以传入一个函数对普通运行边返回0对换乘边返回一个很大的惩罚值但这并非完美只是近似。4.3 路径回溯与结果组装Dijkstra算法结束后我们得到了prev数组。要获取从起点startId到终点endId的路径需要从终点反向回溯到起点std::vectorint getPath(const DijkstraResult res, int endId) { std::vectorint path; for (int at endId; at ! -1; at res.prev[at]) { path.push_back(at); } std::reverse(path.begin(), path.end()); return path; // 返回的是顶点ID的序列 }拿到顶点ID序列后业务逻辑层需要将其“翻译”成用户能看懂的路线描述。这需要查询SubwayGraph获取每个顶点对应的StationNode然后判断连续两个顶点是否属于同一条线路。如果属于同一条线就是“乘坐X号线经过A、B、C站”如果属于不同线路就在前一个顶点处提示“在X站换乘Y号线”。std::vectorRouteSegment convertToRouteSegments(const SubwayGraph graph, const std::vectorint nodePath) { std::vectorRouteSegment segments; if (nodePath.empty()) return segments; RouteSegment currentSeg; currentSeg.lineName graph.getNode(nodePath[0]).line; currentSeg.stations.push_back(graph.getNode(nodePath[0]).name); for (size_t i 1; i nodePath.size(); i) { const auto prevNode graph.getNode(nodePath[i-1]); const auto currNode graph.getNode(nodePath[i]); // 判断是否为换乘站名相同但线路不同 bool isTransfer (prevNode.name currNode.name) (prevNode.line ! currNode.line); if (isTransfer) { // 结束当前段开始新段 segments.push_back(currentSeg); currentSeg RouteSegment(); currentSeg.lineName currNode.line; currentSeg.stations.push_back(currNode.name); } else { // 同一线路继续添加站点 currentSeg.stations.push_back(currNode.name); } } // 添加最后一段 if (!currentSeg.stations.empty()) { segments.push_back(currentSeg); } return segments; }5. Qt图形界面设计与交互实现5.1 主界面布局与控件选择Qt提供了多种界面布局方式水平、垂直、网格、表单等。对于这个系统我采用一个经典的左右分栏布局。左侧使用QGraphicsView和QGraphicsScene来绘制交互式地铁线路图。这是界面的视觉核心。右侧使用QWidget组合各种控件垂直布局。查询输入区两个QComboBox用于选择起点和终点可以输入拼音或汉字进行过滤一个QButtonGroup包含多个QRadioButton让用户选择查询策略最少换乘/最短时间/最少站点一个QPushButton触发查询。结果展示区一个QTextBrowser或QListWidget用来清晰、分条地展示查询出的路线详情包括每段乘坐的线路、经过的站点、总站数、估计时间、换乘次数等。地图控制区一些按钮或滑块用于控制地图的缩放、平移或者高亮显示某条线路。在Qt Creator中使用Designer可以很方便地拖拽出这个界面并为其各个控件设置好对象名如startComboBox,queryButton然后通过“提升为...”功能将左侧的QGraphicsView提升为我们自定义的MapWidget类以便实现自定义绘图和交互。5.2 自定义绘图绘制地铁线路图在MapWidget类继承自QGraphicsView中我们需要在QGraphicsScene上绘制所有站点和线路。数据映射首先需要将SubwayGraph中每个StationNode的经纬度或模拟坐标映射到场景的像素坐标。可以遍历所有节点找到经纬度的最大最小值然后线性映射到视图大小。绘制线路对于每条地铁线收集属于该线的所有站点按照线路走向可能需要额外数据或排序用QPainterPath连接起来并设置不同的颜色和线宽。绘制站点在每个站点坐标处画一个圆QGraphicsEllipseItem。对于换乘站可以用一个更大的圆或者不同的颜色如带圆环来标记。添加交互让站点图形项可点击。可以为每个站点的圆图元设置setFlag(QGraphicsItem::ItemIsSelectable)并连接其clicked()信号到槽函数用于选中站点作为查询的起点或终点。// MapWidget 中的关键绘制函数简化 void MapWidget::drawLine(const QString lineId, const QColor color) { auto stations graph.getStationsByLine(lineId); QPainterPath path; bool first true; for (const auto station : stations) { QPointF pos geoToPixel(station.longitude, station.latitude); if (first) { path.moveTo(pos); first false; } else { path.lineTo(pos); } // 绘制站点 auto* stationItem scene()-addEllipse(pos.x()-3, pos.y()-3, 6, 6, QPen(Qt::black), QBrush(color)); stationItem-setData(StationNodeIdRole, station.id); // 存储ID stationItem-setFlag(QGraphicsItem::ItemIsSelectable); connect(stationItem, QGraphicsEllipseItem::clicked, this, MapWidget::onStationClicked); } auto* lineItem scene()-addPath(path, QPen(color, 2)); lineItem-setZValue(-1); // 线路在站点下层 }5.3 信号与槽连接界面与逻辑Qt的信号与槽机制是连接用户操作与后台逻辑的桥梁。查询按钮点击当用户点击“查询”按钮时发出clicked()信号。我们将其连接到一个槽函数在这个函数里从startComboBox和endComboBox获取当前选中的站名。从QButtonGroup获取当前选中的查询策略。调用业务逻辑层的查询接口例如RoutePlanner::findRoutes。将返回的std::vectorRouteSegment结果格式化成字符串显示在右侧的QTextBrowser中。站点图元点击当用户在地图上点击某个站点时MapWidget::onStationClicked槽函数被触发。我们可以通过sender()或事件参数获取被点击的图元进而得到其存储的站点ID和名称。然后我们可以将这个站名设置到起点或终点的QComboBox中通过一个标志位记录当前是在设置起点还是终点。结果高亮当一条查询结果被选中时我们可以遍历该结果路径上的所有站点ID在地图场景中找到对应的图元并高亮显示例如改变颜色、放大。// MainWindow 构造函数中的连接 connect(ui-queryButton, QPushButton::clicked, this, MainWindow::onQueryButtonClicked); connect(ui-mapWidget, MapWidget::stationSelected, this, MainWindow::onStationSelected); // 槽函数示例 void MainWindow::onQueryButtonClicked() { QString start ui-startComboBox-currentText(); QString end ui-endComboBox-currentText(); int strategy getSelectedStrategy(); // 获取策略枚举值 auto routes routePlanner.findRoutes(start, end, strategy); displayRoutes(routes); // 在UI上展示结果 highlightRouteOnMap(routes); // 在地图上高亮路径 }6. 数据持久化与程序配置6.1 线路数据格式设计与解析程序不能硬编码地铁数据必须从外部文件加载。我选择使用JSON格式因为它结构清晰、可读性好且Qt原生支持通过QJsonDocument,QJsonObject,QJsonArray。一个简化的数据文件subway_data.json可能长这样{ lines: [ { id: 1, name: 1号线, color: #FF0000, stations: [ {id: 101, name: 苹果园, lng: 116.18, lat: 39.92}, {id: 102, name: 古城, lng: 116.19, lat: 39.91}, // ... 更多站点 ] }, // ... 更多线路 ], transfers: [ {stationName: 西直门, lineIds: [2, 4, 13]}, // ... 更多换乘站信息 ] }在程序启动时我们需要编写一个DataLoader类来解析这个JSON文件遍历lines数组为每条线路的每个站点创建StationNode注意ID的生成要唯一可以结合线路ID和站序。在创建站点的同时为同一线路内相邻的站点添加“运行边”TrackEdge权重可以预设或根据坐标计算距离。遍历transfers数组对于同一个换乘站名下的所有线路找到它们对应的站点顶点ID然后两两之间添加“换乘边”TransferEdge并赋予一个固定的换乘时间权重如5分钟。6.2 使用QSettings管理用户偏好一个友好的桌面应用应该能记住用户的一些设置比如窗口大小、位置、最近使用的起点终点、默认的查询策略等。Qt提供了QSettings类可以非常方便地将这些信息以键值对的形式保存到系统注册表Windows或plist文件macOS或ini文件Linux中。// 保存设置 void MainWindow::writeSettings() { QSettings settings(MyCompany, SubwayQuery); settings.setValue(geometry, saveGeometry()); settings.setValue(windowState, saveState()); settings.setValue(defaultStrategy, currentStrategy); settings.setValue(recentStarts, recentStartStations); } // 读取设置 void MainWindow::readSettings() { QSettings settings(MyCompany, SubwayQuery); restoreGeometry(settings.value(geometry).toByteArray()); restoreState(settings.value(windowState).toByteArray()); int strategy settings.value(defaultStrategy, 0).toInt(); setCurrentStrategy(strategy); recentStartStations settings.value(recentStarts).toStringList(); updateComboBoxHistory(); }在MainWindow的closeEvent中调用writeSettings()在构造函数末尾调用readSettings()就能实现用户偏好的持久化。7. 项目构建、打包与部署7.1 使用CMake管理项目对于C/Qt项目我强烈推荐使用CMake作为构建系统而不是Qt自带的qmake。CMake更现代、更强大也更容易集成第三方库。一个基本的CMakeLists.txt如下cmake_minimum_required(VERSION 3.16) project(SubwayQuerySystem VERSION 1.0.0 LANGUAGES CXX) # 设置C标准 set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) # 自动查找Qt6组件如果使用Qt6 find_package(Qt6 REQUIRED COMPONENTS Core Widgets) # 对于Qt5使用 find_package(Qt5 REQUIRED COMPONENTS Core Widgets) # 启用Qt的MOC、UIC、RCC自动处理 set(CMAKE_AUTOMOC ON) set(CMAKE_AUTOUIC ON) set(CMAKE_AUTORCC ON) # 添加可执行文件 add_executable(SubwayQuery src/main.cpp src/mainwindow.cpp src/mainwindow.ui src/mapwidget.cpp src/subwaygraph.cpp src/routeplanner.cpp src/dataloader.cpp # ... 其他源文件 ) # 链接Qt库 target_link_libraries(SubwayQuery Qt6::Core Qt6::Widgets # 如果用了其他模块如 Qt6::Network, Qt6::Charts ) # 在macOS上设置应用程序Bundle信息可选 if(APPLE) set_target_properties(SubwayQuery PROPERTIES MACOSX_BUNDLE TRUE MACOSX_BUNDLE_GUI_IDENTIFIER com.mycompany.subwayquery MACOSX_BUNDLE_BUNDLE_NAME Subway Query ) endif()在项目根目录下执行cmake -B build -S .生成构建文件然后cmake --build build进行编译整个过程非常清晰。7.2 解决Windows下的DLL依赖问题在Windows上发布Qt程序最让人头疼的就是那一堆运行时DLL。你不能指望用户电脑上恰好有对应版本的Qt运行库。手动复制DLL容易遗漏尤其是Qt5Core.dll,Qt5Widgets.dll,Qt5Gui.dll以及平台插件platforms/qwindows.dll还有C运行时msvcp140.dll,vcruntime140.dll等。推荐方法使用windeployqt工具。这是Qt官方提供的部署工具能自动扫描你的exe文件找出所有依赖的Qt库并复制到你的发布目录。操作步骤在Release模式下编译你的程序生成SubwayQuery.exe。新建一个发布文件夹如SubwayQuery_Release。将SubwayQuery.exe复制到这个文件夹。打开Qt命令行如Qt 5.15.2 (MSVC 2019 64-bit)切换到发布文件夹。执行命令windeployqt SubwayQuery.exe。工具会自动将所需的Qt DLL、插件、翻译文件等复制到当前目录及子目录如platforms。你还需要手动将项目依赖的数据文件如subway_data.json和可能用到的C运行时库如果静态链接了可以忽略复制过来。实操心得windeployqt有时会漏掉一些间接依赖的库比如如果你用了QtCharts模块它可能不会自动包含。一个检查方法是在干净的虚拟机或另一台电脑上运行你打包好的程序如果报错缺少某个DLL就回到开发机在Qt安装目录的bin文件夹里找到它手动复制过来。7.3 生成安装包对于更专业的发布可以使用安装包制作工具如Inno Setup(Windows) 或macOS PackageMaker。以Inno Setup为例你可以编写一个.iss脚本指定要打包的文件、创建开始菜单快捷方式、设置安装目录、写入注册表信息如果需要等。这样生成一个单一的.exe安装文件用户双击即可安装体验更好。8. 性能优化与扩展思考8.1 查询性能优化实践当网络规模很大时每次查询都运行一次完整的Dijkstra算法可能会成为瓶颈。以下是一些优化思路双向搜索如前所述从起点和终点同时运行Dijkstra当两个搜索的“前沿”相遇时停止。这通常能将搜索空间减半。A算法*如果每个站点有地理坐标可以将其作为启发式信息。A*算法在Dijkstra的基础上优先搜索“看起来”更接近终点的方向能进一步加快搜索速度。启发函数可以用欧几里得距离或曼哈顿距离。预计算与缓存对于热门站点对比如城市核心枢纽站之间的路径可以将查询结果缓存起来。下次查询时先查缓存。可以使用std::unordered_map键是(startId, endId, strategy)的组合值是路径结果。注意设置合理的缓存大小和过期策略。分层图或收缩层次这是高级优化技术。将网络中的主要换乘站或大站作为“枢纽”预先计算枢纽之间的最短路径。查询时先快速从起点走到最近的枢纽然后走预计算的枢纽路径再从枢纽走到终点。这能极大减少搜索的节点数。在我的实现中首先应用了双向Dijkstra对于拥有300个节点站点的网络查询时间从毫秒级降低到了亚毫秒级用户体验已经非常流畅。A*算法需要额外的坐标数据来估算代价实现起来也不复杂是下一步优化的好选择。8.2 功能扩展方向一个基础的地铁查询系统完成后可以考虑很多有趣的扩展实时信息集成通过网络请求使用QNetworkAccessManager获取地铁的实时运营状态如某条线路是否延误、某站是否临时关闭并在查询结果和地图上进行标注。票价计算根据当地的票价规则如分段计价、累计折扣在路径规划后计算出票价。多模态交通不仅限于地铁加入公交、步行、共享单车等。这需要更复杂的图模型和算法如考虑不同交通工具的速度、等待时间、换乘便利性。可视化动画在展示路径时不是静态高亮而是用一个移动的小点模拟列车行进增强趣味性。离线地图将线路图作为背景图片加载到QGraphicsScene中然后将站点绘制在上面比纯矢量绘图更美观。跨平台与移动端利用Qt的跨平台特性尝试将代码移植到Android或iOS上。这涉及到界面布局的适配和触摸交互的处理。这个项目就像一棵树的根基把这些核心功能做扎实了任何方向的扩展都是顺理成章、水到渠成的事情。它带给你的不仅仅是一个可以写在简历上的项目更是一套解决复杂问题的完整方法论——从抽象建模、算法选型、代码实现到最终的产品化。
