基于线段树的售票系统的设计与实现

2021-08-09王逸芳张子牛齐庆磊

现代计算机 2021年17期

王逸芳，张子牛，齐庆磊

(南阳师范学院计算机科学与技术学院，南阳 453200)

0 引言

随着国家铁路运输事业的快速发展，列车已经成为人们生活中一种十分重要的出行方式。快速、准确的车票查询系统能够给人们带来良好的乘车体验。由于一条铁路线路上站点的数量，乘客从各站点上下车的时间，乘客购买车票的时间等因素都会成为影响车票查询结果的因素，设计和实现快速高效的车票查询系统面临着诸多挑战。

线段树[1-2]作为一种特殊的二叉树，目前已经得到广泛应用，有效解决了动态区间求最值[3]、范围查询[4]，高效内存划分[5]、求矩形面积[6]等问题。线段树的每个节点表示一个区间，存储区间信息。每个节点的孩子节点对该节点的区间进行分割。在线段树中，与叶子节点对应的区间为最小区间。最小区间是指不能再分或者无需再分的区间。线段树具有如下性质：

(1)线段树是一棵平衡二叉树，树的高度为logN，N为线段树中的节点数量。

(2)线段树把区间上的任意一条长度为N的线段都分为不大于2logN条线段的并。

(3)任两个节点可以是包含关系，也可以是没有相同结点关系，不可能有重叠的情况，每层节点的区间的并即为整个区间。

(4)给定一个叶子结点p，从根到p路径上全部节点代表的区间都包括点p，且其他节点代表的区间都不包括点p。

本文将线段树用于火车票管理系统中。每个节点表示某两个车站之间的区域。根节点表示始发站和终点站之间的区域。除叶子节点外，每个节点代表的区间由两个孩子节点分割为两个子区间。叶子节点表示相邻两个站点之间的区域。节点内记录车票剩余信息。本文设计实现的售票系统中主要包括创建线段树，购买车票，更新相应路段的车票信息。

1 算法实现

1.1 算法描述

假设某条线路上共有S个站点，依次存储在二维数组routeInf[S][]中，该线路上的某趟列车共设M个座位，并且该列车上仅售坐票。乘客购买票请求为(departure，arrival，ticketNum)，表示乘客需要购买ticketNum张车票，离开站为departure，到达站为arrival。线段树任一节点为(departure，arrival，ticketNum，lchild，rchild)，表示从站点departure到站点departure的余票数量为ticketNum，左孩子节点为lchild，右孩子节点为rchild。购票系统主要包括创建线段树，购买车票，更新相应路段的车票信息。创建线段树的函数为递归过程，从根节点开始，设置当前节点的离开站，到达站和车票数量，创建左子树和右子树。

购买车票的函数也是递归过程，从根节点开始，查看当前节点的车票数量是否能够满足乘客需求，如果满足，返回调用函数。否则分以下三种情况进行处理：①如果乘客的乘车区间在左孩子节点表示的区间内，查看左孩子节点的车票数量能否满足乘客的需求；②如果乘客的乘车区间在右孩子节点表示的区间内，查看右孩子节点的车票数量能否满足乘客的需求；③如果乘客的乘车区间跨越两个孩子节点表示的区间，分段查看左右孩子节点的车票数量能否满足乘客的需求。

更新车票的函数同样是递归过程，从根节点开始，查看当前节点的车票数量能否满足乘客的需求，如果可以，当前节点的车票数量减去乘客请求的车票数量，否则，当前节点的车票数量设置为0。然后分以下三种情况进行处理：①如果乘客的乘车区间在左孩子节点表示的区间内，更新左孩子节点的车票数量；②如果乘客的乘车区间在右孩子节点表示的区间内，更新右孩子节点的车票数量；③如果乘客的乘车区间跨越两个孩子节点表示的区间，更新左右孩子节点的车票数量。

1.2 实现代码

本节给出创建线段树，购票和更新车票三个模块的C语言实现代码。

(1)创建线段树

(2)购票

(3)更新车票信息

2 程序运行效果

购票系统的运行测试效果如图1所示。测试用例选用的线路包括6个站点，依次为：BeiJing、ShiJiaZhuang、ZhengZhou、WuHan、ChangSha、GuangZhou。列车共提供1000张车票。共提出5次购票请求，分别为(BeiJing ZhenZhou 100)、(ZhengZhou WuHan 500)、(ShiJiaZhuang WuHan 400)、(ZhengZhou WuHan 150)、(WuHan ShenZhen 10)。结果显示，由于车票充足，系统为前3次请求成功分配了车票，并分别更新了线段树中和请求线路有重合区间的节点的车票数量。由于第4次请求的车票数量多于相应线路当前剩余的车票数量，系统未能为本次请求分配车票。由于第5次请求的乘车区间不在线路内，系统也未能为本次请求分配车票。