71 lines
3.0 KiB
Markdown
71 lines
3.0 KiB
Markdown
# TODO List — 组员C
|
||
|
||
**负责模块**: 线路网络图 + 订单哈希查找与统计
|
||
**核心数据结构**: 图 `StationGraph`（邻接表）、哈希表 `HashNode`（链地址法）
|
||
**文件**: `src/graph.h`、`src/graph.cpp`、`src/hash.h`、`src/hash.cpp`
|
||
**分支**: `feature/graph`
|
||
|
||
---
|
||
|
||
## 一、图基础操作（邻接表）
|
||
|
||
- [ ] `InitGraph` — 初始化图（`vertexCount = 0`，`firstEdge = nullptr`）
|
||
- [ ] `AddVertex` — 添加站点顶点（检查重复 / 越界）
|
||
- [ ] `AddEdge` — 添加线路边（无向图，需同时添加两条边）
|
||
- [ ] `FindVertex` — 按 `stationId` 查找顶点下标
|
||
|
||
## 二、图遍历算法
|
||
|
||
- [ ] `DFS` — 深度优先遍历（递归实现）
|
||
- 从 `startIdx` 出发，标记已访问，输出能到达的所有站点
|
||
- [ ] `BFS` — 广度优先遍历（队列辅助）
|
||
- 输出最少换乘次数的路径
|
||
|
||
## 三、最短路径算法（核心加分项）
|
||
|
||
- [ ] `Dijkstra` — Dijkstra 最短路径算法
|
||
- 初始化 `dist[] = INF`，`visited[] = false`，`dist[src] = 0`
|
||
- 循环选最小未访问顶点，遍历邻接表松弛
|
||
- [ ] `PrintPath` — 递归回溯 path[] 数组打印路径
|
||
- [ ] `RecommendTransfer` — 换乘推荐入口
|
||
- 输入起点/终点站名 → 调用 Dijkstra → 输出换乘方案
|
||
- 方案包含：经过站点、换乘次数、总时长/总票价
|
||
|
||
## 四、最小生成树（可选加分）
|
||
|
||
- [ ] `PrimMST` — Prim 算法，以最小总里程连通所有站点
|
||
|
||
## 五、站点文件读写
|
||
|
||
- [ ] `loadStationsFromFile` — 从 `data/stations.csv` 读取站点和边数据
|
||
- 解析顶点行和邻接边（格式: `相邻站点(车次号:边权);...`）
|
||
- 调用 `AddVertex` / `AddEdge` 构建图
|
||
|
||
## 六、哈希表操作（链地址法）
|
||
|
||
- [ ] `Hash` — 哈希函数（身份证号字符累加 % `HASH_SIZE`）
|
||
- [ ] `InitHashTable` — 初始化所有桶为 `nullptr`
|
||
- [ ] `HashInsert` — 插入订单（头插法）
|
||
- [ ] `HashSearch` — 按身份证号查找订单
|
||
- [ ] `HashSearchByOrderId` — 按订单号查找（遍历所有桶）
|
||
- [ ] `HashDelete` — 从哈希表中删除订单
|
||
- [ ] `DestroyHashTable` — 释放所有链表节点内存
|
||
|
||
## 七、统计功能
|
||
|
||
- [ ] `CountSalesByTrain` — 统计某车次已支付订单数
|
||
- [ ] `CountTrafficByRoute` — 统计某线路（始发站-终点站）客流量
|
||
- [ ] `CountRevenueByPeriod` — 统计某时间段总收入
|
||
- [ ] `HotTrainRanking` — 热门车次排行（按销量降序，取前 N）
|
||
|
||
## 八、乘客交互接口
|
||
|
||
- [ ] `passengerFindTransfer` — 换乘查询菜单交互
|
||
- 输入起点站名和终点站名 → 调用 `RecommendTransfer`
|
||
|
||
---
|
||
|
||
> **依赖关系**: `graph.cpp` 需 `#include <queue>`（BFS 辅助队列），`hash.cpp` 需 `#include "train.h"`（统计关联车次表）
|
||
> **算法重点**: Dijkstra 是最大加分项，务必写清注释便于答辩
|
||
> **验收标准**: 能正确构建线路图，DFS/BFS 遍历正确，Dijkstra 给出最优换乘方案，哈希查找快速定位，统计数据准确
|