[理學]數(shù)據(jù)結構3第三章：棧和隊列-資料下載頁
2024-10-16 21:14本頁面
【正文】 回 ERROR if(==) // 隊列空 return ERROR。 e=[]。 =(+1)%MAXQSIZE。 return OK。 } 循環(huán)隊列出隊操作 循環(huán)隊列的基本操作 Status DestroyQueue(SqQueue amp。Q) { // 銷毀隊列 Q,Q不再存在 if() free()。 =NULL。 ==0。 return OK。 } 銷毀隊列圖例 實習題（一） ? 棧、隊列的算法設計 本次實習的目的在于深入了解棧和隊列的特性 ， 以便在實際問題背景下靈活運用它們 。 [基本描述 ] 設停車場內只有一個可停放 n輛汽車的狹長通道 ， 且只有一個大門可供汽車進出 。 汽車在停車場內按車輛到達時間的先后順序 ， 依次由北向南排列 （ 大門在最南端 ， 最先到達的第一輛車停放在車場的最北端 ） ，若車場內已停滿 n輛汽車 ， 則后來的汽車只能在門外的便道上等候 ， 一旦有車開走 ， 則排在便道上的第一輛車即可開入；當停車場內某車開出大門外 ， 其它車輛再按原次序進入車場 ， 每輛停放在車場的車在它離開停車場時 ， 必須按它停留的時間長短繳納費用 ， 試為停車場編制按上述要求進行管理的模擬程序 。 [基本要求 ] 以棧模擬停車場 ， 以隊列模擬車場外的通道 ， 按照從終端讀八的輸入數(shù)據(jù)序列進行模擬管理 。 每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項的汽車 ? 到達 ? 或 ? 離去 ? 信息 ，汽車牌照碼及到達或離去的時刻 ， 對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛離去 ， 則輸出汽車在停車場內停留的時間和應交納的費用 （ 在便道上停留時間不收費 ） 。 棧以順序結構實現(xiàn) ， 隊列以鏈表結構實現(xiàn) 。 [測試數(shù)據(jù) ] 設 n=2， 輸入數(shù)據(jù)為： (?A?,1,5), (?A?,2,10), (?D?,1,15), (?A?,3,20), (?A?,4,25), (?A?,5,30), (?D?,2,35),（ ‘ D?,4,10） ,(?E?,0,0), 其中 ， ’ A?表示到達 ， ‘ D?表示 ，‘ E’ 表示輸入結束 。 實習題（二） [問題描述 ] 假設停在鐵路調度站 ， （ 如課本 ） ， 入 D處車廂序列的編號依次為 1,2,3,… , n。 設計一個程序 ， 求出所有可能由此輸出的長度為 n的車廂序列 。 [基本要求 ] 首先在課本第 實現(xiàn)的五種基本運算 。 除了棧初始化操作之外 ， 都要按函數(shù)實現(xiàn) 。 Push(s,x)是一個布爾函數(shù) ， 當且僅當棧 S上溢時返回 ? 假 ? 值 ， 再說明一個 date型的常量是datetype操作 。 pop(s)和 top(s)遇到 S為空的情況時 ， 返回值為空元素 NLLL。 程序對棧的任何存取 （ 即更改 ， 讀取和狀態(tài)判別等操作 ） 必須借助于基本運算進行 。 [測試數(shù)據(jù) ] 分別取 n=1,2,3,和 4 復習思考題 ? 棧 ? ？ 什么叫 ? 出棧 ? 和 ? 進棧 ? ？ ， 元素進棧的次序為 A， B， C。 試問能否得到下列操作序列 ？ 若不能 ， 請說明原因 。 （ 1） A， B， C （ 2） A， C， B （ 3） B， A， C （ 4） B， C， A （ 5） C， B， A （ 6） C， A， B ， 畫出對下列算術表達式求值時 ， 操作數(shù)棧和運算符棧的變化過程 。 AB*C/D+E^E C（ 1： m） ,它們的棧底分別設在向量的兩端且進棧的每個元素只占一個分量 ，試寫出這兩個棧公用的棧操作算法 push(I,x),pop(i)和top(i)， 其中 i為 o或 1， 并討論過程或函數(shù)設計這些操作算法各有什么優(yōu)缺點 。 ？ 順序存儲的隊列為什么要采用循環(huán)隊列 ？ 1,2,3,4,則隊列的輸出序列是什么 ？ Sepu(1： m)存入循環(huán)隊列的元素 ， 同時改變量 rear和 quelen分別指示循環(huán)隊列中隊尾無素的位置和內含元素的個數(shù) ， 試給出循環(huán)隊列的隊滿條件 ， 并寫出相應的入隊列和出隊列的算法 。
教學課件相關推薦
鄂ICP備17016276號-1