AdeiTech-star/dsa_group_20
GitHub: AdeiTech-star/dsa_group_20
基于七种自研数据结构的城市应急调度模拟系统，用于道路网络建模、事故分级和最优路径规划。
Stars: 1 | Forks: 0
# 城市突发事件响应系统
一个为卢旺达基加利市构建的紧急调度模拟系统，完全使用 C++ 及自定义数据结构（无 STL 容器）开发。该系统将城市道路网络建模为动态加权图，并实时管理救护车、消防车和警车向事故现场的调度。
## 概述
基加利的应急基础设施负责在拥有 170 万以上居民、地势多山且快速发展的城市中，协调警察 (112)、SAMU 救护车 (912) 和消防队 (111) 服务。本项目使用七个从零开始构建的数据结构来模拟这种协调机制——加权图、最小堆、哈希表、AVL 树、线段树、Union-Find 和字典树。
### 核心功能
- **动态城市地图** — 在运行时添加/移除道路，并实时跟踪连通性
- **事故分流** — 优先队列确保始终优先调度最紧急的事故
- **最优路径规划** — Dijkstra 算法计算最短路径；Union-Find 用于拦截无法到达的调度
- **时间分析** — 针对事故日志的 AVL 树范围查询和线段树区间计数
- **前缀搜索** — 基于字典树的自动补全，用于单位名称和路口名称搜索
## 项目结构
```
.
urban-irs/
├── include/
│ ├── hash_table.h
│ ├── graph.h
│ ├── union_find.h
│ ├── min_heap.h
│ ├── avl_tree.h
│ ├── segment_tree.h
│ ├── trie.h
│ └── dispatcher.h
├── src/
│ ├── hash_table.cpp
│ ├── graph.cpp
│ ├── union_find.cpp
│ ├── min_heap.cpp
│ ├── avl_tree.cpp
│ ├── segment_tree.cpp
│ ├── trie.cpp
│ ├── dispatcher.cpp
│ └── main.cpp
├── tests/
│ ├── test_hash_table.cpp
│ ├── test_graph.cpp
│ ├── test_union_find.cpp
│ ├── test_min_heap.cpp
│ ├── test_avl_tree.cpp
│ ├── test_segment_tree.cpp
│ ├── test_trie.cpp
│ └── test_dispatcher.cpp
├── data/
│ └── kigali_map.txt
├── docs/
│ └── proposal.pdf
├── .github/
│ └── workflows/
│ └── ci.yml
├── Makefile
└── README.md
```
## 构建
```
mkdir build && cd build
cmake ..
cmake --build .
```
## 运行测试
一次性运行所有测试，并将单独的日志保存到 `build/test_results/`：
```
bash run_tests.sh
```
或者运行特定的测试：
```
./build/test_graph
./build/test_hash_table
./build/test_min_heap
./build/test_union_find
./build/test_avl_tree
./build/test_segment_tree
./build/test_trie
./build/test_dijkstra
./build/test_dispatcher
```
## 运行基准测试
```
./build/benchmark
```
基准测试运行三个计时场景（总计约 80,000+ 次操作）：
1. **大规模伤亡** — 10,000 次 `reportIncident` 调用 + autoDispatch 排空 + 10,000 次 `resolveIncident` 调用。测试 MinHeap、HashTable、AVLTree、SegmentTree、UnionFind 和 Dijkstra。
2. **道路封闭重路由** — 10,000 次 `closeRoad`+`reopenRoad` 循环（每次 UnionFind 完全重建）+ 每次封闭后进行 500 次调度+重路由迭代。
3. **时间分析** — 针对 SegmentTree（更新 + 范围查询）、AVLTree（插入 + collectRange）、HashTable（插入 + 查找）和 Trie（插入 + 前缀搜索）各进行 10,000 次操作。每个结构均独立测量。
## 内存管理
已通过 Valgrind 验证——零内存泄漏，零错误（参见 `build/valgrind.log`）。
## 团队
| 姓名 | Andrew ID |
|------|-----------|
| Kavini Nzau | knzau |
| Nthabiseng Thema | nthema |
| Christian Abiyingoma | cabiying |
| Regis Ndahiro Ngoga | rndahiro |
标签：AVL树, Bash脚本, C++, 事件分诊, 优先队列, 前缀搜索, 动态加权图, 区间查询, 卢旺达基加利, 图论算法, 城市应急响应, 字典树, 并查集, 应急调度模拟, 救护车调度, 散列表, 数据擦除, 无STL, 时间序列分析, 智能交通系统, 最小堆, 最短路径, 模拟系统, 消防车, 算法与数据结构, 紧急救援, 线段树, 自动补全, 自定义数据结构, 警车, 迪杰斯特拉算法