# 数据结构课程设计 —— 设计文档

## 〇、选题名称

**《火车票务管理系统》**

---

## 一、项目背景与意义

模拟一个小型火车票务平台，乘客可以查询车次、购票、退票、查看换乘方案；管理员可以维护车次信息。
目的是综合运用本学期学过的**线性表、栈、队列、图、查找、排序**这几类数据结构，做一个"看得见、能跑起来"的系统，而不是单独练习某一种数据结构。

---

## 二、需求分析

### 2.1 用户角色

| 角色 | 权限 |
|---|---|
| 管理员 | 增/删/改车次信息，查看销售统计 |
| 普通乘客 | 查询车次、购票、退票、查看自己的订单、查询换乘方案 |

### 2.2 功能需求（对应任务书"增删改查排序统计"要求）

- **增**：新增车次（管理员）；生成购票订单（乘客）
- **删**：删除/停运车次（管理员）；退票/取消订单（乘客）
- **改**：修改车次信息（票价、时间、余票）；改签订单
- **查**：按车次号/出发站/到达站/日期查询车次；按身份证号/订单号查询订单；模糊查询
- **排序**：按出发时间、票价、剩余票数排序展示
- **统计**：统计某车次销售量、某线路客流量、某时间段总收入

### 2.3 非功能需求

- 界面采用菜单驱动（一级菜单 + 二级菜单），文字交互即可，不强制图形界面
- 数据用文件持久化（`.csv`），程序启动时加载，操作后及时写回
- 输入要做基本合法性校验（如车次号不能重复、余票不能为负）

---

## 三、个体数据描述（数据项设计）

### 3.1 车次信息 TrainInfo

| 字段 | 说明 | 类型示例 |
|---|---|---|
| trainNo | 车次号（唯一，如 G1234） | char[8] |
| startStation | 始发站 | char[20] |
| endStation | 终点站 | char[20] |
| departTime | 出发时间 | char[10] |
| arriveTime | 到达时间 | char[10] |
| price | 票价 | float |
| totalSeats | 总票数 | int |
| remainSeats | 余票 | int |

### 3.2 订单信息 OrderInfo

| 字段 | 说明 |
|---|---|
| orderId | 订单号（唯一） |
| trainNo | 关联车次号 |
| passengerName | 乘客姓名 |
| idCard | 身份证号（唯一标识乘客，可作哈希查找键） |
| seatNo | 座位号 |
| orderTime | 购票时间 |
| status | 状态：已支付 / 候补中 / 已退票 |

### 3.3 站点/线路信息 Station（供图结构使用）

| 字段 | 说明 |
|---|---|
| stationId | 站点编号 |
| stationName | 站点名称 |
| adjList | 相邻站点及边权（时长或票价）—— 即图的邻接表 |

---

## 四、数据结构设计（核心部分）

这是整个课程设计评分的重点，下面把"用在哪、为什么用、要实现哪些算法"都列清楚，方便写报告时直接展开。

### 4.1 车次信息表 —— 顺序表（顺序存储结构）

作为本系统的**主线性表**，对应任务书"线性表若选顺序存储结构"的要求：

- 查找：**顺序查找** + **二分查找**（按车次号排序后二分）—— 满足"顺序查找 + 其他查找方式选一种"
- 排序：**直接插入排序**（按车次号初始化排序）、**快速排序**（按票价排序）、**堆排序**（按余票数排序）—— 满足"三种以上排序算法"

```c
typedef struct {
    TrainInfo data[MaxSize];
    int length;
} TrainList;

bool ListInsert(TrainList *&L, int i, TrainInfo e);
bool ListDelete(TrainList *&L, int i, TrainInfo &e);
int  SeqSearch(TrainList *L, char trainNo[]);      // 顺序查找
int  BinSearch(TrainList *L, char trainNo[]);      // 二分查找（要求按trainNo有序）
void QuickSort(TrainList *&L, int low, int high);  // 按票价快排
void HeapSort(TrainList *&L);                      // 按余票堆排序
```

### 4.2 线路网络 —— 图（邻接表存储）

这是本系统的**创新亮点**，对应任务书"图存储结构"的加分项：

- 顶点 = 车站，边 = 两站之间存在的车次（边权可设为"时长"或"票价"）
- **图的两种遍历**：DFS（深度优先，找某站出发能到达的所有站点）、BFS（广度优先，找最少换乘次数的路径）
- **最短路径算法（Dijkstra）**：实现"最优换乘路径推荐"——给定起点和终点，算出耗时最短或票价最低的换乘方案
- （可选加分）**最小生成树**：模拟"以最小总里程把所有站点连通"的线路规划场景

```c
typedef struct {
    int stationId;
    char stationName[20];
    EdgeNode *firstEdge;   // 邻接表头指针
} VertexNode;

typedef struct EdgeNode {
    int toStationId;
    float weight;          // 时长或票价
    struct EdgeNode *next;
} EdgeNode;

void DFS(Graph G, int v);
void BFS(Graph G, int v);
void Dijkstra(Graph G, int src, float dist[], int path[]); // 最优换乘路径
```

### 4.3 候补购票队列 —— 队列

当某车次余票为0时，乘客可加入候补队列；一旦有人退票释放余票，按**先进先出**原则自动给候补队列里排在最前面的乘客出票。

```c
typedef struct {
    OrderInfo data[MaxSize];
    int front, rear;
} WaitQueue;

bool EnQueue(WaitQueue *&Q, OrderInfo e);  // 进入候补
bool DeQueue(WaitQueue *&Q, OrderInfo &e); // 候补转正出票
```

### 4.4 操作撤销栈 —— 栈

记录最近若干次"购票/退票/改签"操作，支持"撤销上一步"，避免误操作（也是一个容易讲的创新点）。

```c
typedef struct {
    OperationLog data[MaxSize];
    int top;
} OpStack;

bool Push(OpStack *&S, OperationLog op);
bool Pop(OpStack *&S, OperationLog &op);  // 撤销最近一次操作
```

### 4.5 订单快速查找 —— 哈希表

按身份证号哈希定位订单，避免每次都要顺序扫描全部订单，对应"分块查找/哈希表查找选一种"的要求（这里选哈希表）。

```c
int Hash(char idCard[]);                  // 简单除留余数法或字符累加法
bool HashInsert(OrderInfo orders[], OrderInfo e);
OrderInfo* HashSearch(OrderInfo orders[], char idCard[]);
```

> 小结：本系统用到 **顺序表 + 图 + 队列 + 栈 + 哈希表** 五种数据结构，覆盖面广，五个模块分给3人小组刚好可以人均2类结构、4个以上核心函数模块，工作量和创新点都比较容易达标。

---

## 五、系统功能模块划分（建议3人分工）

| 负责人 | 模块 | 核心数据结构 |
|---|---|---|
| 组员A — 李 | ① 车次信息增删改 ② 顺序/二分查找 ③ 三种排序 ④ 文件读写(trains.csv) | 顺序表 |
| 组员B — 刘 | ① 购票下单 ② 退票/改签 ③ 候补排队 ④ 操作撤销栈 | 队列、栈 |
| 组员C — 朱 | ① 线路图构建 ② 图的遍历(DFS/BFS) ③ 最短路径换乘推荐 ④ 订单哈希查找与销量统计 | 图、哈希表 |
| 共同 | 菜单系统、登录权限、主程序整合 | — |

每人独立完成的模块均≥4个，预计人均代码量400行以上，总代码量轻松超过900行（任务书最低要求）。

---

## 六、文件存储格式设计

**trains.csv**
```
车次号,始发站,终点站,出发时间,到达时间,票价,总票数,余票
G1907,北京,上海,08:00,13:28,553.0,800,800
```

**orders.csv**
```
订单号,车次号,乘客姓名,身份证号,座位号,购票时间,状态
O00001,G1907,张三,1101**********1234,03A,2026-07-08 09:12,已支付
```

**stations.csv**（辅助构建图）
```
站点编号,站点名称,相邻站点(车次号:边权)
1,北京,2:553.0
2,上海,1:553.0;3:120.0
```

> 建议至少录入30条以上"看起来真实"的车次/乘客数据，可以参考12306的真实城市和车次号编一套，满足"30条以上相对真实个体信息"的要求。

---

## 七、业务流程（文字版，写报告时可画成流程图）

**购票流程**：
登录 → 查询车次（条件查询+排序展示）→ 选择车次 → 判断余票
　　├ 有余票 → 生成订单、扣减余票、写回文件
　　└ 无余票 → 询问是否进入候补队列 → 进入WaitQueue
退票时若有候补，自动从队首取出一人补票。

**换乘查询流程**：
输入起点/终点 → 在图中用Dijkstra计算最短路径（按时长或票价）→ 输出换乘方案（经过哪些站、换乘几次）

**数据流向**：
用户输入 → 内存数据结构（顺序表/图/队列/栈/哈希表）→ 算法处理（查找/排序/最短路径）→ 显示结果 → 写回csv文件

---

## 八、创新点设计（用于答辩加分）

1. **最优换乘路径推荐**（图+Dijkstra）—— 力度最大的创新点
2. **候补购票自动转正**（队列）
3. **操作撤销/回退功能**（栈）
4. **模糊查询/多条件组合查询**（如同时按出发站+价格区间筛选）
5. （可选）简单密码哈希存储，提升登录安全性

> 任务书规定：每个创新点加5分，一组总加分不超过60分。上面5个点选3-4个做扎实，比贪多但都做得浅更划算。

---

## 九、工作量自查清单

- [ ] 每人源码 ≥ 300行（建议人均400行留余量）
- [ ] 总代码量 ≥ 900行
- [ ] 录入 ≥ 30条相对真实的车次/乘客数据
- [ ] 顺序表满足：顺序查找 + 二分查找；三种以上排序算法
- [ ] 图结构满足：两种遍历 + 最短路径算法
- [ ] 报告正文（不含图、代码、运行截图）≥ 3000字
- [ ] 与参考书同类型选题代码重复率 < 50%（本选题与参考书的"通讯录系统"差异较大，基本不存在重复风险）
- [ ] 全程使用 C/C++（过程性语言），未使用Python等被禁止的语言

---