下载掌阅APP，畅读海量书库
立即打开
大型应用实现：总览
本书将以1.1节介绍的火车票管理系统作为大型应用，贯穿全书所有章节，每章首先介绍数据结构的基本概念，然后讲解该大型应用中与该章数据结构内容相关的具体实现。
针对火车票管理系统的数据特点及管理要求，为每一类数据选择合适的数据结构，并采用面向对象的程序设计方法，把对每一类数据的管理封装成一个类，供应用系统使用。
根据1.1节火车票管理系统的需求分析（如图1-1所示）与系统构成（如图1-2所示），下面将以数据为中心描述火车票管理系统的类及其对应的数据结构与所属章节，按照数据的生成、使用与消亡过程依次介绍其管理类。
列车运行图类RailwayGraph管理整个列车运行计划所包含的运行线路图，提供站点可达性查询、途经站点查询和最优路线查询功能，这3种查询统称路线查询。列车运行图信息与列车运行计划的添加有关，如图1-4所示。该类涉及的并查集、图的存储与搜索、最短路径等内容将分别在第5章、第9章、第10章中介绍。
图1-4 列车运行图类RailwayGraph
列车运行计划管理类TrainScheduler管理所有列车的运行计划，包括车次号、额定乘员、途经站点、历时、票价等车次基本信息，提供列车运行计划的添加与查询功能。列车运行计划信息也与车票的发售与停售有关，如图1-5所示。该类涉及的线性表等内容将在第2章中介绍。
图1-5 列车运行计划管理类TrainScheduler
余票管理类TicketManager管理每一段线路的余票信息，提供车票发售与停售、购票、退票、余票查询功能，如图1-6所示。该类涉及的B+树等内容将在第8章中介绍。
行程管理类TripManager管理所有旅客的行程，行程信息受到旅客购票和退票交易的影响。该类为每个旅客提供已购车票查询功能，如图1-7所示。该类涉及的B+树等内容也将在第8章中介绍。
图1-6 余票管理类TicketManager
排队交易类WaitingList与PrioritizedWaitingList管理所有待交易车票的信息，处理普通或特殊旅客的排队购票及退票请求，如图1-8所示。该类涉及的队列与优先级队列等内容将分别在第3章、第4章中介绍。
图1-7 行程管理类TripManager
图1-8 排队交易类WaitingList与PrioritizedWaitingList
旅客管理类UserManager管理所有旅客的信息，提供旅客信息的查询、添加与修改功能，该类在旅客的购票和退票交易时将被用到，如图1-9所示。该类涉及的红黑树等内容将在第6章中介绍。
图1-9 旅客管理类UserManager
本节概述了火车票管理系统中列车运行图、列车运行计划管理、余票管理、行程管理、排队交易、旅客管理等6个类，后续章节将逐一详细讲解并用C++语言实现。在学习过程中，读者可以尝试编译和运行书中的示例代码，以进一步探索和练习。有关环境配置和项目构建的更多信息详见附录B。