数据结构课程设计 —— 设计文档
〇、选题名称
《火车票务管理系统》
一、项目背景与意义
模拟一个小型火车票务平台，乘客可以查询车次、购票、退票、查看换乘方案；管理员可以维护车次信息。 目的是综合运用本学期学过的线性表、栈、队列、图、查找、排序这几类数据结构，做一个"看得见、能跑起来"的系统，而不是单独练习某一种数据结构。
二、需求分析
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 车次信息表 —— 顺序表（顺序存储结构）
作为本系统的主线性表，对应任务书"线性表若选顺序存储结构"的要求：
- 查找：顺序查找 + 二分查找（按车次号排序后二分）—— 满足"顺序查找 + 其他查找方式选一种"
- 排序：直接插入排序（按车次号初始化排序）、快速排序（按票价排序）、堆排序（按余票数排序）—— 满足"三种以上排序算法"
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）：实现"最优换乘路径推荐"——给定起点和终点，算出耗时最短或票价最低的换乘方案
- （可选加分）最小生成树：模拟"以最小总里程把所有站点连通"的线路规划场景
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时，乘客可加入候补队列；一旦有人退票释放余票，按先进先出原则自动给候补队列里排在最前面的乘客出票。
typedef struct {
OrderInfo data[MaxSize];
int front, rear;
} WaitQueue;
bool EnQueue(WaitQueue *&Q, OrderInfo e); // 进入候补
bool DeQueue(WaitQueue *&Q, OrderInfo &e); // 候补转正出票
4.4 操作撤销栈 —— 栈
记录最近若干次"购票/退票/改签"操作，支持"撤销上一步"，避免误操作（也是一个容易讲的创新点）。
typedef struct {
OperationLog data[MaxSize];
int top;
} OpStack;
bool Push(OpStack *&S, OperationLog op);
bool Pop(OpStack *&S, OperationLog &op); // 撤销最近一次操作
4.5 订单快速查找 —— 哈希表
按身份证号哈希定位订单，避免每次都要顺序扫描全部订单，对应"分块查找/哈希表查找选一种"的要求（这里选哈希表）。
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文件
八、创新点设计（用于答辩加分）
- 最优换乘路径推荐（图+Dijkstra）—— 力度最大的创新点
- 候补购票自动转正（队列）
- 操作撤销/回退功能（栈）
- 模糊查询/多条件组合查询（如同时按出发站+价格区间筛选）
- （可选）简单密码哈希存储，提升登录安全性
任务书规定：每个创新点加5分，一组总加分不超过60分。上面5个点选3-4个做扎实，比贪多但都做得浅更划算。
九、工作量自查清单
- 每人源码 ≥ 300行（建议人均400行留余量）
- 总代码量 ≥ 900行
- 录入 ≥ 30条相对真实的车次/乘客数据
- 顺序表满足：顺序查找 + 二分查找；三种以上排序算法
- 图结构满足：两种遍历 + 最短路径算法
- 报告正文（不含图、代码、运行截图）≥ 3000字
- 与参考书同类型选题代码重复率 < 50%（本选题与参考书的"通讯录系统"差异较大，基本不存在重复风险）
- 全程使用 C/C++（过程性语言），未使用Python等被禁止的语言