2025年数据结构期末课程设计，其中包括飞机票管理系统，Trie 树和后缀树的应用，交通咨询系统设计，简单搜索引擎.zip

# 交通咨询系统项目架构文档 ## 1. 项目概述 交通咨询系统是一个基于Qt的图形界面应用程序，用于城市间交通路径规划和分析。系统通过加载城市距离矩阵和邻接矩阵，提供最短路径查询、多路径查询、避开特定城市的路径规划以及中心城市验证等功能。 ## 2. 项目结构 ## 3. 类设计与功能 ### 3.1 City 类 **功能**: 表示城市节点 - **属性**: - `name`: 城市名称 - `isProvincialCapital`: 是否为省会城市 - **方法**: - 构造函数：`City(const QString &name, bool isProvincialCapital)` - 获取城市名称：`getName()` - 获取是否为省会城市：`getIsProvincialCapital()` ### 3.2 Graph 类 **功能**: 管理城市网络图结构 - **属性**: - `cities`: 城市列表 - `cityNameToIndex`: 城市名称到索引的映射 - `distanceMatrix`: 城市间距离矩阵 - `adjacencyMatrix`: 城市间邻接矩阵 - `originalAdjacencyMatrix`: 原始邻接矩阵（用于恢复） - `avoidCityIndex`: 当前避开的城市索引 - **方法**: - 加载距离矩阵：`loadDistanceMatrix(const QString &filePath)` - 加载邻接矩阵：`loadAdjacencyMatrix(const QString &filePath)` - 获取城市数量：`getCityCount()` - 获取城市索引：`getCityIndex(const QString &cityName)` - 获取城市名称：`getCityName(int index)` - 获取城市间距离：`getDistance(int from, int to)` - 判断城市是否相邻：`isAdjacent(int from, int to)` - 获取所有城市名称：`getAllCityNames()` - 设置避开城市：`setAvoidCity(int cityIndex)` - 重置避开城市：`resetAvoidCity()` ### 3.3 PathFinder 类 **功能**: 实现各种路径查找算法 - **属性**: - `graph`: 图引用 - `floydDist`/`floydNext`: Floyd算法存储 - `floydComputed`: Floyd算法是否已计算 - **方法**: - **基础算法**: - Dijkstra算法：`dijkstra(int start, int end)` - Floyd-Warshall算法：`floydWarshall()` 和 `getFloydPath(int start, int end)` - **路径查询功能**: - 最短路径查询：`findShortestPath(int start, int end)` 和 `findShortestPathFloyd(int start, int end)` - 所有可行路径查询：`findAllPaths(int start, int end, int maxNodes)` - 绕过特定城市的路径查询：`findPathAvoidingCity(int start, int end, int avoidCity, bool useDijkstra)` - 第K短路径查询：`findKthShortestPath(int start, int end, int k, int maxNodes)` - **辅助方法**: - 验证武汉中心性：`validateWuhanCentrality(QStringList &counterExamples)` - 计算路径长度：`calculatePathLength(const Path &path)` - 路径转换为字符串：`pathToString(const Path &path)` - 深度优先搜索：`dfs(int current, int target, QVector<bool> &visited, Path &currentPath, QVector<Path> &allPaths, int maxNodes, int depth)` - 导出路径到文件：`exportPathsToFile(const QVector<QPair<Path, int>> &paths, const QString &filePath)` ### 3.4 QuickSort 类 **功能**: 提供路径排序功能 - **方法**: - 快速排序：`sort(QVector<PathLengthPair> &paths)` - 分区操作：`partition(QVector<PathLengthPair> &paths, int low, int high)` - 递归排序：`quickSortRecursive(QVector<PathLengthPair> &paths, int low, int high)` ### 3.5 MainWindow 类 **功能**: 管理UI界面和用户交互 - **属性**: - `ui`: UI界面 - `graph`: 图实例 - `pathFinder`: 路径查找器实例 - `currentPaths`: 当前查询的路径结果 - **方法**: - 加载数据文件：`loadDataFiles()` - 更新城市下拉框：`updateCityComboBoxes()` - 按钮响应函数： - 验证武汉中心性：`on_validateWuhanButton_clicked()` - 最短路径查询：`on_shortestPathButton_clicked()` - 所有路径查询：`on_allPathsButton_clicked()` - 第K短路径查询：`on_kthPathButton_clicked()` - 导出结果：`on_exportButton_clicked()` - 显示路径结果：`displayPath()` 和 `displayAllPaths()` - 清除结果：`clearResults()` ## 4. UI界面设计 ### 4.1 主窗口组件 - **城市选择区域**: - 出发城市下拉框：`sourceComboBox` - 目的城市下拉框：`destComboBox` - 避开城市下拉框：`avoidComboBox` - **算法选择区域**: - Dijkstra算法单选按钮：`dijkstraRadioButton` - Floyd算法单选按钮：`floydRadioButton` - 最大节点数微调框：`maxNodesSpinBox` - K值微调框：`kValueSpinBox` - **功能按钮区域**: - 验证武汉中心性按钮：`validateWuhanButton` - 最短路径查询按钮：`shortestPathButton` - 所有路径查询按钮：`allPathsButton` - 第K短路径查询按钮：`kthPathButton` - 导出结果按钮：`exportButton` - **结果显示区域**: - 标签页控件：`tabWidget` - 表格结果页：包含`pathsTableWidget` - 文本结果页：包含`resultTextEdit` - 状态栏：`statusbar` ## 5. 数据文件结构 ### 5.1 距离矩阵文件 (距离矩阵.CSV) - 第一行：城市名称列表 - 其余行：各城市之间的距离数据 - 格式：CSV格式，逗号分隔 ### 5.2 邻接矩阵文件 (邻接矩阵.csv) - 第一行：城市名称列表 - 其余行：各城市之间的连通性（0或1） - 格式：CSV格式，逗号分隔 ## 6. 主要算法实现 ### 6.1 最短路径算法 - **Dijkstra算法**: 用于计算单源最短路径 - **Floyd-Warshall算法**: 用于计算所有点对间的最短路径 ### 6.2 深度优先搜索 - 用于查找两城市间的所有可行路径 - 支持限制最大节点数以控制搜索深度 ### 6.3 K短路径算法 - 基于所有路径查询结果 - 使用QuickSort对路径按距离排序 - 返回第K短的路径 ## 7. 后续开发计划 1. 完善各个算法的具体实现 2. 添加更多的用户交互功能 3. 优化数据加载和处理逻辑 4. 改进UI界面，提升用户体验 5. 添加路径可视化功能 6. 实现更多的路径规划策略