王逸芳，張子牛，齊慶磊

(南陽師范學(xué)院計算機科學(xué)與技術(shù)學(xué)院，南陽 453200)

0 引言

隨著國家鐵路運輸事業(yè)的快速發(fā)展，列車已經(jīng)成為人們生活中一種十分重要的出行方式?？焖?、準(zhǔn)確的車票查詢系統(tǒng)能夠給人們帶來良好的乘車體驗。由于一條鐵路線路上站點的數(shù)量，乘客從各站點上下車的時間，乘客購買車票的時間等因素都會成為影響車票查詢結(jié)果的因素，設(shè)計和實現(xiàn)快速高效的車票查詢系統(tǒng)面臨著諸多挑戰(zhàn)。

線段樹[1-2]作為一種特殊的二叉樹，目前已經(jīng)得到廣泛應(yīng)用，有效解決了動態(tài)區(qū)間求最值[3]、范圍查詢[4]，高效內(nèi)存劃分[5]、求矩形面積[6]等問題。線段樹的每個節(jié)點表示一個區(qū)間，存儲區(qū)間信息。每個節(jié)點的孩子節(jié)點對該節(jié)點的區(qū)間進(jìn)行分割。在線段樹中，與葉子節(jié)點對應(yīng)的區(qū)間為最小區(qū)間。最小區(qū)間是指不能再分或者無需再分的區(qū)間。線段樹具有如下性質(zhì)：

(1)線段樹是一棵平衡二叉樹，樹的高度為logN，N為線段樹中的節(jié)點數(shù)量。

(2)線段樹把區(qū)間上的任意一條長度為N的線段都分為不大于2logN條線段的并。

(3)任兩個節(jié)點可以是包含關(guān)系，也可以是沒有相同結(jié)點關(guān)系，不可能有重疊的情況，每層節(jié)點的區(qū)間的并即為整個區(qū)間。

(4)給定一個葉子結(jié)點p，從根到p路徑上全部節(jié)點代表的區(qū)間都包括點p，且其他節(jié)點代表的區(qū)間都不包括點p。

本文將線段樹用于火車票管理系統(tǒng)中。每個節(jié)點表示某兩個車站之間的區(qū)域。根節(jié)點表示始發(fā)站和終點站之間的區(qū)域。除葉子節(jié)點外，每個節(jié)點代表的區(qū)間由兩個孩子節(jié)點分割為兩個子區(qū)間。葉子節(jié)點表示相鄰兩個站點之間的區(qū)域。節(jié)點內(nèi)記錄車票剩余信息。本文設(shè)計實現(xiàn)的售票系統(tǒng)中主要包括創(chuàng)建線段樹，購買車票，更新相應(yīng)路段的車票信息。

1 算法實現(xiàn)

1.1 算法描述

假設(shè)某條線路上共有S個站點，依次存儲在二維數(shù)組routeInf[S][]中，該線路上的某趟列車共設(shè)M個座位，并且該列車上僅售坐票。乘客購買票請求為(departure，arrival，ticketNum)，表示乘客需要購買ticketNum張車票，離開站為departure，到達(dá)站為arrival。線段樹任一節(jié)點為(departure，arrival，ticketNum，lchild，rchild)，表示從站點departure到站點departure的余票數(shù)量為ticketNum，左孩子節(jié)點為lchild，右孩子節(jié)點為rchild。購票系統(tǒng)主要包括創(chuàng)建線段樹，購買車票，更新相應(yīng)路段的車票信息。創(chuàng)建線段樹的函數(shù)為遞歸過程，從根節(jié)點開始，設(shè)置當(dāng)前節(jié)點的離開站，到達(dá)站和車票數(shù)量，創(chuàng)建左子樹和右子樹。

購買車票的函數(shù)也是遞歸過程，從根節(jié)點開始，查看當(dāng)前節(jié)點的車票數(shù)量是否能夠滿足乘客需求，如果滿足，返回調(diào)用函數(shù)。否則分以下三種情況進(jìn)行處理：①如果乘客的乘車區(qū)間在左孩子節(jié)點表示的區(qū)間內(nèi)，查看左孩子節(jié)點的車票數(shù)量能否滿足乘客的需求；②如果乘客的乘車區(qū)間在右孩子節(jié)點表示的區(qū)間內(nèi)，查看右孩子節(jié)點的車票數(shù)量能否滿足乘客的需求；③如果乘客的乘車區(qū)間跨越兩個孩子節(jié)點表示的區(qū)間，分段查看左右孩子節(jié)點的車票數(shù)量能否滿足乘客的需求。

更新車票的函數(shù)同樣是遞歸過程，從根節(jié)點開始，查看當(dāng)前節(jié)點的車票數(shù)量能否滿足乘客的需求，如果可以，當(dāng)前節(jié)點的車票數(shù)量減去乘客請求的車票數(shù)量，否則，當(dāng)前節(jié)點的車票數(shù)量設(shè)置為0。然后分以下三種情況進(jìn)行處理：①如果乘客的乘車區(qū)間在左孩子節(jié)點表示的區(qū)間內(nèi)，更新左孩子節(jié)點的車票數(shù)量；②如果乘客的乘車區(qū)間在右孩子節(jié)點表示的區(qū)間內(nèi)，更新右孩子節(jié)點的車票數(shù)量；③如果乘客的乘車區(qū)間跨越兩個孩子節(jié)點表示的區(qū)間，更新左右孩子節(jié)點的車票數(shù)量。

1.2 實現(xiàn)代碼

本節(jié)給出創(chuàng)建線段樹，購票和更新車票三個模塊的C語言實現(xiàn)代碼。

(1)創(chuàng)建線段樹

(2)購票

(3)更新車票信息

2 程序運行效果

購票系統(tǒng)的運行測試效果如圖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)。結(jié)果顯示，由于車票充足，系統(tǒng)為前3次請求成功分配了車票，并分別更新了線段樹中和請求線路有重合區(qū)間的節(jié)點的車票數(shù)量。由于第4次請求的車票數(shù)量多于相應(yīng)線路當(dāng)前剩余的車票數(shù)量，系統(tǒng)未能為本次請求分配車票。由于第5次請求的乘車區(qū)間不在線路內(nèi)，系統(tǒng)也未能為本次請求分配車票。

圖1 程序運行效果

3 結(jié)語

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