基于線段樹(shù)的售票系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

王逸芳，張子牛，齊慶磊

(南陽(yáng)師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南陽(yáng) 453200)

0 引言

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

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

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

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

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

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

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

1 算法實(shí)現(xiàn)

1.1 算法描述

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

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

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

1.2 實(shí)現(xiàn)代碼

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

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

(2)購(gòu)票

(3)更新車票信息

2 程序運(yùn)行效果

購(gòu)票系統(tǒng)的運(yùn)行測(cè)試效果如圖1所示。測(cè)試用例選用的線路包括6個(gè)站點(diǎn)，依次為：BeiJing、ShiJiaZhuang、ZhengZhou、WuHan、ChangSha、GuangZhou。列車共提供1000張車票。共提出5次購(gòu)票請(qǐng)求，分別為(BeiJing ZhenZhou 100)、(ZhengZhou WuHan 500)、(ShiJiaZhuang WuHan 400)、(ZhengZhou WuHan 150)、(WuHan ShenZhen 10)。結(jié)果顯示，由于車票充足，系統(tǒng)為前3次請(qǐng)求成功分配了車票，并分別更新了線段樹(shù)中和請(qǐng)求線路有重合區(qū)間的節(jié)點(diǎn)的車票數(shù)量。由于第4次請(qǐng)求的車票數(shù)量多于相應(yīng)線路當(dāng)前剩余的車票數(shù)量，系統(tǒng)未能為本次請(qǐng)求分配車票。由于第5次請(qǐng)求的乘車區(qū)間不在線路內(nèi)，系統(tǒng)也未能為本次請(qǐng)求分配車票。

圖1 程序運(yùn)行效果

3 結(jié)語(yǔ)

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