城市交通路网分析系统

数据结构课程设计 控制台 + Qt GUI

开发环境： VSCode | 语言：C/C++ | 构建：CMake + MinGW | 版本管理：Git

---

项目概述

• 将城市抽象为顶点，道路抽象为带权边
• 同时使用邻接矩阵 + 邻接表两套存储结构
• 集成 DFS、BFS、Dijkstra、Floyd、Prim、Kruskal、拓扑排序 七大经典图算法
• 手写实现 队列、栈、并查集、最小堆优先队列 四种基础数据结构
• 支持路网编辑、最短路径规划、最小生成树、拥堵仿真、性能对比、数据持久化
• 23 个自动化测试用例（合法/非法/边界/交叉验证全覆盖）
• JSON 路网数据文件化管理：程序启动自动加载，支持多路网切换、新建有向/无向路网
• 非连续城市 ID 支持：算法内部使用 ID→数组下标映射，城市编号无需从 0 或 1 连续递增

---

目录结构

course-design/
├── docs/                            # 文档目录
│   ├── design_topic.md              # 选题说明
│   ├── general_requipment.md        # 课程设计总体要求
│   ├── coding_standard.md           # 代码编写规范
│   ├── todo.md                      # 开发任务清单
│   ├── cli_commands.md              # CLI 命令速查手册
│   └── prg/                         # 流程图目录
├── src/                             # 源代码
│   ├── main.cpp                     # 程序入口（菜单/CLI/Qt/批处理）
│   ├── common/                      # types.h  defines.h
│   ├── graph/                       # graph_base.h  adj_matrix.*  adj_list.*
│   ├── algorithms/                  # 8 个模块：4 数据结构 + 4 算法
│   ├── services/                    # 4 个模块：路网/拥堵/对比/文件
│   ├── ui/                          # 3 个模块：菜单/格式化/校验
│   ├── cli/                         # 2 个模块：命令行交互
│   ├── qt/                          # 7 个模块：Qt GUI 界面（未完成）
│   └── test/                        # test_cases.* (23 个测试用例)
├── bin/                             # 二进制程序文件
│   └── network_console.exe          # g++编译产物
├── data/                            # 路网数据文件（.json）
│   ├── default.json                 # 默认路网
│   └── *.json                       # 其他城市/区域路网
├── CMakeLists.txt                   # CMake 构建文件（支持 Qt5/Qt6 + 纯控制台）
├── .gitignore
├── CHANGELOG.md                     # 更新日志
└── README.md

---

功能与使用说明

1. 路网编辑（主菜单 1）

 1. 新增城市     → 输入编号 + 名称
 2. 删除城市     → 输入编号（同步删除关联道路）
 3. 新增道路     → 输入起点、终点、权值
 4. 删除道路     → 输入起点、终点
 5. 修改道路权值 → 输入起点、终点、新权值
 6. 查看路网总览 → 图类型、城市数、道路数
 7. 查看全部节点和路径 → 列出所有城市和道路的详细信息

删除城市会自动清理所有关联道路。所有修改在邻接矩阵和邻接表上同步执行。

2. 图遍历（主菜单 2）

 1. DFS 深度优先遍历 → 输入起点，输出访问序列
 2. BFS 广度优先遍历 → 输入起点，输出访问序列

3. 最短路径（主菜单 3）

 1. Dijkstra 单源最短路径 → 输入起点，输出到所有城市的最短距离
 2. Floyd 多源最短路径   → 输出任意两城间的最短距离对照表

4. 最小生成树（主菜单 4）

 1. Prim 算法   → 构建最小生成树，输出边集和总造价
 2. Kruskal 算法 → 同上（两种算法结果一致，验证正确性）

仅适用于无向图。有向图会自动提示。

5. 拓扑排序（主菜单 5）

仅适用于有向图。无向图会提示"无法执行"。

6. 拥堵模拟（主菜单 6）

 1. 修改道路权值       → 指定道路 + 新权值（模拟拥堵）
 2. 恢复全部修改       → 撤销所有拥堵修改
 3. 查看修改记录       → 显示当前拥堵的道路和权值变化
 4. 拥堵前后对比分析   → 自动对比最优路径变化

7. 结构性能对比（主菜单 7）

自动统计邻接矩阵 vs 邻接表在四项指标上的差异：

• 内存占用
• 遍历速度
• 顶点查找效率
• 边查询效率

8. 数据文件管理（主菜单 8）

 1. 保存路网到文件        → 输入文件名，保存为 data/xxx.json
 2. 从文件加载路网        → 输入文件名，替换当前路网
 3. 切换路网（从 data/ 选择） → 列出所有可用文件，选择后加载
 4. 设置默认文件路径      → 修改自动加载的默认文件
 5. 新建路网              → 选择有向/无向并生成空 JSON 文件

9. 帮助 / 关于（主菜单 9）

显示功能概览。

10. 命令行模式（主菜单 10 / --cli 启动）

菜单中选 10 或启动时加 --cli 进入。menu 切回菜单，exit 退出。

命令	参数	说明
new_network	<type> <file>	新建空路网，type 支持0/1/undirected/directed
new_city	<id> <name>	添加城市
del_city	<id>	删除城市
new_road	<from> <to> <w>	添加道路
del_road	<from> <to>	删除道路
update_road	<from> <to> <w>	修改权值
show_network	—	路网详情
dfs	<start>	深度优先遍历
bfs	<start>	广度优先遍历
dijkstra	<start> [end]	最短路径
floyd	—	全源最短路径表
prim	—	Prim 最小生成树
kruskal	—	Kruskal 最小生成树
topo	—	拓扑排序
congest	<from> <to> <w>	设置拥堵
restore	—	恢复拥堵
congest_list	—	查看拥堵记录
congest_report	<start>	拥堵对比报告
compare	—	结构性能对比
save	[filename]	保存路网
load	[filename]	加载路网
list	—	列出可用路网文件
help	—	命令帮助
menu	—	切回菜单模式
exit	—	退出

文件名自动补全 data/ 前缀和 .json 后缀。程序从项目根目录、bin/、build/bin/ 启动时都会自动定位 data/ 目录。

0. 退出系统

退出时自动保存到当前路网文件。

---

数据文件格式（JSON）

字段说明：graph_type 中 0=无向图、1=有向图；cities 保存城市；roads 保存道路。加载时程序会先读取 graph_type，再自动切换为有向图或无向图。

示例（data/default.json）：

{
  "graph_type": 0,
  "cities": [
    {"id": 1, "name": "City1"},
    {"id": 2, "name": "City2"}
  ],
  "roads": [
    {"from": 1, "to": 2, "weight": 10}
  ]
}

---

快速开始

CMake 构建（支持 Qt GUI，可选）

GUI 版本需要 MSYS2（约 200MB，无需 8GB 的 Qt 在线安装器）。

1. 安装 MSYS2 + Qt6 库 + CMake

winget install MSYS2.MSYS2

装完后运行一次 MSYS2 终端更新，然后再装 Qt 和编译工具：

C:\msys64\usr\bin\bash.exe -lc "pacman -Syu --noconfirm"
C:\msys64\usr\bin\bash.exe -lc "pacman -S --noconfirm mingw-w64-ucrt-x86_64-qt6-base mingw-w64-ucrt-x86_64-cmake mingw-w64-ucrt-x86_64-gcc mingw-w64-ucrt-x86_64-make"

2. 编译

# 纯控制台版（不依赖 Qt）
& "C:\msys64\usr\bin\bash.exe" -lc "export PATH=/ucrt64/bin:`$PATH && cd /e/vscode\ project/course-design && cmake --build build --target traffic_console"

# Qt GUI 版
& "C:\msys64\usr\bin\bash.exe" -lc "export PATH=/ucrt64/bin:`$PATH && cd /e/vscode\ project/course-design && cmake -S . -B build -G 'MinGW Makefiles' -DCMAKE_PREFIX_PATH=/ucrt64 && cmake --build build --target traffic_network"

3. 运行

编译产物在 build/bin/：

.\build\bin\traffic_console.exe              # 菜单模式（默认）
.\build\bin\traffic_console.exe --cli        # CLI 交互模式
.\build\bin\traffic_network.exe --gui        # Qt GUI 模式（需先编译 GUI 版）

首次运行 GUI 版需要 DLL：把 C:\msys64\ucrt64\bin 加到系统 PATH，或复制 DLL 到 exe 同目录。详见 MSYS2 文档。

---

直接运行控制台

从项目根目录直接编译

g++ -std=c++11 -Wall -g3 src/main.cpp src/graph/adj_matrix.cpp src/graph/adj_list.cpp src/algorithms/queue.cpp src/algorithms/stack.cpp src/algorithms/union_find.cpp src/algorithms/priority_queue.cpp src/algorithms/traversal.cpp src/algorithms/shortest_path.cpp src/algorithms/spanning_tree.cpp src/algorithms/topological.cpp src/services/road_network.cpp src/services/congestion.cpp src/services/comparator.cpp src/services/file_io.cpp src/ui/menu.cpp src/ui/formatter.cpp src/ui/validator.cpp src/test/test_cases.cpp src/cli/cli_app.cpp src/cli/command_parser.cpp -o bin/network_console.exe

VSCode 中按 Ctrl+Shift+B → 选"编译全部（21个cpp）"即可。

运行

# 菜单模式（无参数，默认）
bin/network_console.exe

# 命令行交互模式
bin/network_console.exe --cli

# 单条命令批处理
bin/network_console.exe dijkstra 1 5

也可以直接进入 bin/ 后双击或运行 network_console.exe。程序会自动向上查找项目根目录下的 data/ 文件夹。

运行测试

编辑 main.cpp，把 // run_all_tests(); 和 // return 0; 前面的 // 去掉，重新编译运行。

调试模式

src/common/defines.h 第 12 行，去掉 // 开启：

#define DEBUG_MODE    // 开启 → 算法每一步求解过程全打印

新建路网

1. 菜单方式：主菜单 8 → 5 新建路网 → 选择 0=无向图 或 1=有向图 → 输入文件名
2. CLI 方式：new_network 0 my_network 或 new_network 1 directed_network
3. 新建后在“路网编辑”中添加城市/道路，退出或手动保存时写回当前 JSON 文件

---

编码规范速查

类别	规则	示例
局部变量	snake_case	city_count, start_city
成员变量	snake_case	vertex_count, max_vertices
常量	UPPER_CASE	MAX_CITY_COUNT, INF_WEIGHT
公共函数	snake_case	add_city(), run_dijkstra()
私有函数	snake_case	init_matrix(), find_index()
结构体	PascalCase + _t	City_t, Edge_t
类	PascalCase	GraphBase, AdjMatrix
文件	snake_case	graph_base.h, adj_matrix.cpp
缩进	4 空格，禁止 Tab	—

详见 docs/coding_standard.md

---

Git 协作

git pull
git checkout dev/member-{a,b,c}
git add -A
git commit -m "完成 xxx 功能"
git checkout main
git pull
git merge dev/member-{a,b,c}
git push