# 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 给出最优换乘方案，哈希查找快速定位，统计数据准确