書面作業(yè)一：棧隊(duì)列應(yīng)用題2014-10-10

1、“單鏈表和隊(duì)列單鏈表和隊(duì)列”、“棧和隊(duì)列的應(yīng)用棧和隊(duì)列的應(yīng)用” 二選一二選一【選題提示】【選題提示】棧和隊(duì)的應(yīng)用棧和隊(duì)的應(yīng)用-停車場(chǎng)管理停車場(chǎng)管理n停車場(chǎng)停車場(chǎng)大門大門便道便道臨時(shí)臨時(shí)停放停放為給為給要離要離去的去的汽車汽車讓路讓路而從而從停車停車場(chǎng)退場(chǎng)退出來出來的汽的汽車車停車場(chǎng)內(nèi)只有一個(gè)可停放停車場(chǎng)內(nèi)只有一個(gè)可停放n n汽車的狹長(zhǎng)通道，汽車的狹長(zhǎng)通道，只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的

2、最北端）。車停放在車場(chǎng)的最北端）。若車場(chǎng)內(nèi)已停滿若車場(chǎng)內(nèi)已停滿n n輛汽車，則后來的汽車只能輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入。便道上的第一輛車即可開入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門外，其它車輛按原次序進(jìn)入車場(chǎng)，每輛停大門外，其它車輛按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。的時(shí)間長(zhǎng)短交

3、納費(fèi)用?！締栴}描述】【問題描述】 模擬停車場(chǎng)管理。模擬停車場(chǎng)管理?！净疽蟆俊净疽蟆客＼噲?chǎng)停車場(chǎng)park：停車場(chǎng)。用棧模擬，容量為：停車場(chǎng)。用棧模擬，容量為n，棧中每個(gè)元素表，棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼（示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號(hào)碼（ id ）和進(jìn)入停車場(chǎng)的時(shí)刻（和進(jìn)入停車場(chǎng)的時(shí)刻（ oclock ）。）。1.數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)臨時(shí)停放道臨時(shí)停放道parktemp：臨時(shí)停放道，臨時(shí)停放道，為給要離去的汽車讓路而從為給要離去的汽車讓路而從停車場(chǎng)退出來的汽車。用棧模擬，容量足夠大，不會(huì)停車場(chǎng)退出來的汽車。用棧模擬，容量足夠大，不會(huì)

4、發(fā)生發(fā)生“上溢上溢”。停車場(chǎng)外便道停車場(chǎng)外便道pavement：停車場(chǎng)外的便道，用隊(duì)列模擬。：停車場(chǎng)外的便道，用隊(duì)列模擬。rearrearfrontfrontevtype：事件類型：事件類型 1-表示汽車表示汽車“到達(dá)到達(dá)”，2-表示汽車表示汽車“離開離開”，3-表示輸入結(jié)束。表示輸入結(jié)束。time：事件發(fā)生時(shí)間：事件發(fā)生時(shí)間【設(shè)計(jì)提示】【設(shè)計(jì)提示】1.1.初始化。初始化。置隊(duì)列和兩個(gè)棧為空置隊(duì)列和兩個(gè)棧為空2.2.輸入數(shù)據(jù)。輸入數(shù)據(jù)?！暗竭_(dá)到達(dá)”或或“離去離去”信息、汽車牌照信息、汽車牌照號(hào)號(hào) 碼、到達(dá)或離去的時(shí)刻碼、到達(dá)或離去的時(shí)刻3.3.循環(huán)循環(huán)。當(dāng)當(dāng)evtypeevtype不為不為3時(shí)

5、執(zhí)行時(shí)執(zhí)行 記錄當(dāng)前事件發(fā)生時(shí)間記錄當(dāng)前事件發(fā)生時(shí)間 oclockoclock 若若 evtype evtype 1 則則 處理汽車到達(dá)事件處理汽車到達(dá)事件 若若 evtype evtype 2 則則 處理汽車離去事件處理汽車離去事件 2.算法設(shè)計(jì)算法設(shè)計(jì)單鏈表和隊(duì)的應(yīng)用單鏈表和隊(duì)的應(yīng)用-航空訂票系統(tǒng)航空訂票系統(tǒng) 航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢航空客運(yùn)訂票的業(yè)務(wù)活動(dòng)包括：查詢航線、客票預(yù)訂和承辦退票等。航線、客票預(yù)訂和承辦退票等。 查詢航線查詢航線 客票預(yù)訂客票預(yù)訂 承辦退票承辦退票 【問題描述】【問題描述】【基本要求】【基本要求】構(gòu)建的航空訂票系統(tǒng)應(yīng)具有如下功能：構(gòu)建的航空訂票系統(tǒng)應(yīng)具有如

6、下功能： (1)數(shù)據(jù)錄入數(shù)據(jù)錄入 (2)查詢航線查詢航線 (3)客票預(yù)訂客票預(yù)訂 (4)承辦退票承辦退票 (5)修改航班信息修改航班信息(1)航班數(shù)據(jù)錄入和維護(hù)：航班數(shù)據(jù)錄入和維護(hù)： 每條航線所涉及的信息有：終點(diǎn)站名、航班號(hào)、每條航線所涉及的信息有：終點(diǎn)站名、航班號(hào)、飛機(jī)號(hào)、飛行周日（星期幾飛行）、起飛時(shí)間、飛機(jī)號(hào)、飛行周日（星期幾飛行）、起飛時(shí)間、航班票價(jià)、票價(jià)折扣、乘員定額、余票量、已訂航班票價(jià)、票價(jià)折扣、乘員定額、余票量、已訂票的乘客名單以及等候替補(bǔ)的客戶名單。票的乘客名單以及等候替補(bǔ)的客戶名單。(2)查詢航線：查詢航線： 根據(jù)旅客提出的根據(jù)旅客提出的終點(diǎn)站名終點(diǎn)站名，輸出下列信息：航班

7、，輸出下列信息：航班號(hào)、飛機(jī)號(hào)、星期幾飛行、起飛時(shí)間、最近一天號(hào)、飛機(jī)號(hào)、星期幾飛行、起飛時(shí)間、最近一天航班的日期，航班票價(jià)、票價(jià)折扣，確定航班是航班的日期，航班票價(jià)、票價(jià)折扣，確定航班是否滿倉(cāng)、余票額。否滿倉(cāng)、余票額。(3)客票預(yù)訂：客票預(yù)訂： 根據(jù)客戶提出的要求：根據(jù)客戶提出的要求：終點(diǎn)站、航班號(hào)、飛機(jī)號(hào)、日終點(diǎn)站、航班號(hào)、飛機(jī)號(hào)、日期期，查詢?cè)摵桨嗥鳖~情況，若尚有余票，則為客戶辦，查詢?cè)摵桨嗥鳖~情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出訂單編號(hào)和座位號(hào)；若已滿員或余理訂票手續(xù)，輸出訂單編號(hào)和座位號(hào)；若已滿員或余票少于訂票額，則可以提供相關(guān)可選擇航班，并需重票少于訂票額，則可以提供相關(guān)可

8、選擇航班，并需重新詢問客戶要求。若客戶需要，可預(yù)約登記排隊(duì)等候。新詢問客戶要求。若客戶需要，可預(yù)約登記排隊(duì)等候。(4)承辦退票：承辦退票： 根據(jù)客戶提供的根據(jù)客戶提供的訂單編號(hào)和姓名，訂單編號(hào)和姓名，核實(shí)客戶資料：訂核實(shí)客戶資料：訂單編號(hào)、姓名、證件號(hào)、訂票額，若無誤則辦理退票單編號(hào)、姓名、證件號(hào)、訂票額，若無誤則辦理退票手續(xù)；手續(xù)； 然后查詢?cè)摵桨嗳缓蟛樵冊(cè)摵桨嗍欠裼腥祟A(yù)約登記是否有人預(yù)約登記，首先詢問隊(duì)列中，首先詢問隊(duì)列中第一位客戶，若所退票額能滿足他的要求，則為他辦第一位客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其它排隊(duì)預(yù)約的客戶。理訂票手續(xù)，否則依次詢問其它排隊(duì)預(yù)

9、約的客戶。stype：服務(wù)類型：服務(wù)類型（1查詢航線，查詢航線，2客票預(yù)訂，客票預(yù)訂，3承辦退票）承辦退票）數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)linelist：為航線表，：為航線表，采用順序存儲(chǔ)結(jié)構(gòu)，采用順序存儲(chǔ)結(jié)構(gòu)，并并按航班號(hào)有序按航班號(hào)有序。 該表包含兩項(xiàng)：該表包含兩項(xiàng)： (1)序號(hào)序號(hào)(No.)， (2)指向各航線的指指向各航線的指針針(line)。line：為指向航線的指針。：為指向航線的指針。booed：指向已訂票的客：指向已訂票的客戶名單戶名單booked_liner，用線性鏈表表示用線性鏈表表示booking：指向預(yù)約登記：指向預(yù)約登記客戶名單客戶名單book_chain，用隊(duì)列表示用隊(duì)列表示【設(shè)計(jì)提示