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

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

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

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

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

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

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

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

8、選擇航班，并需重新詢問客戶要求。若客戶需要，可預約登記排隊等候。新詢問客戶要求。若客戶需要，可預約登記排隊等候。(4)承辦退票：承辦退票： 根據(jù)客戶提供的根據(jù)客戶提供的訂單編號和姓名，訂單編號和姓名，核實客戶資料：訂核實客戶資料：訂單編號、姓名、證件號、訂票額，若無誤則辦理退票單編號、姓名、證件號、訂票額，若無誤則辦理退票手續(xù)；手續(xù)； 然后查詢該航班然后查詢該航班是否有人預約登記是否有人預約登記，首先詢問隊列中，首先詢問隊列中第一位客戶，若所退票額能滿足他的要求，則為他辦第一位客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其它排隊預約的客戶。理訂票手續(xù)，否則依次詢問其它排隊預

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