基于線段樹的售票系統的設計與實現

王逸芳，張子牛，齊慶磊

(南陽師范學院計算機科學與技術學院，南陽 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次請求的乘車區間不在線路內，系統也未能為本次請求分配車票。

圖1 程序運行效果

3 結語

本文給出基于線段樹的售票系統的設計思路和實現過程，主要包括構建線段樹，購買車票和更新車票信息三部分。測試結果顯示該系統能夠有效完成車票購買和車票更新功能，具有一定的應用價值，能夠幫助讀者理解和掌握線段樹的基本思想和應用方法。