第三章習題
1. 按圖3.1(b)所示鐵道（兩側鐵道均為單向行駛道）進行車廂排程，回答：
⑴ 如進站的車廂序列為123，則可能得到的出站車廂序列是什麼？
⑵如進站的車廂序列為123456，能否得到435612和135426的出站序列，並說明原因。（即寫出以「s」表示進棧、以「x」表示出棧的棧操作序列）。
2. 設佇列中有a、b、c、d、e這5個元素，其中隊首元素為a。如果對這個佇列重複執行下列4步操作：
（1） 輸出隊首元素；
（2） 把隊首元素值插入到隊尾；
（3） 刪除隊首元素；
（4） 再次刪除隊首元素。
直到佇列成為空佇列為止，得到輸出序列：
（1） a、c、e、c、c （2） a、c、e
（3） a、c、e、c、c、c （4） a、c、e、c
3. 給出棧的兩種儲存結構形式名稱，在這兩種棧的儲存結構中如何判別棧空與棧滿？
4. 按照四則運算加、減、乘、除和冪運算（↑）優先關係的慣例，畫出對下列算術表示式求值時運算元棧和運算子棧的變化過程：
a－b＊ｃ／ｄ＋ｅ↑ｆ
5. 試寫乙個演算法，判斷依次讀入的乙個以@為結束符的字母序列，是否為形如『序列1 & 序列2』模式的字串行。其中序列1和序列2 中都不含字元』&』，且序列2 是序列1的逆序列。
例如，『a+b&b+a』是屬該模式的字串行，而『１+３&３－１』則不是。
6. 假設表示式由單字母變數和雙目四則運算算符構成。試寫乙個演算法，將乙個通常書寫形式且書寫正確的表示式轉換為逆波蘭式。
7. 假設以帶頭結點的迴圈鍊錶表示佇列，並且只設乙個指標指向隊尾元素結點（注意不設頭指標），試編寫相應的佇列初始化、入佇列和出佇列的演算法。
8. 要求迴圈佇列不損失乙個空間全部都能得到利用, 設定乙個標誌域tag , 以tag為0或1來區分頭尾指標相同時的佇列狀態的空與滿，請編寫與此結構相應的入隊與出隊演算法。
9. 簡述以下演算法的功能（其中棧和佇列的元素型別均為int）：
（1）void proc_1(stack s)
for(i=1; i<=n; i++)
push(&s, a[i]);
}（2）void proc_2(stack s, int e)
while(!emptystack(t)) }
（3）void proc_3(queue *q)
while(!emptystack(s)) }
實習題1． 回文判斷。稱正讀與反讀都相同的字串行為「回文」序列。
試寫乙個演算法，判斷依次讀入的乙個以@為結束符的字母序列，是否為形如『序列1 &序列2』模式的字串行。其中序列1和序列2 中都不含字元『&』，且序列2 是序列1的逆序列。例如，『a+b&b+a』是屬該模式的字串行，而『１+３&３－１』則不是。
2． 停車場管理。
設停車場是乙個可停放n輛車的狹長通道，且只有乙個大門可供汽車進出。在停車場內，汽車按到達的先後次序，由北向南依次排列（假設大門在最南端）。若車場內已停滿n輛車，則後來的汽車需在門外的便道上等候，當有車開走時，便道上的第一輛車即可開入。
當停車場內某輛車要離開時，在它之後進入的車輛必須先退出車場為它讓路，待該輛車開出大門後，其它車輛再按原次序返回車場。每輛車離開停車場時，應按其停留時間的長短交費（在便道上停留的時間不收費）。
試編寫程式，模擬上述管理過程。要求以順序棧模擬停車場，以鏈佇列模擬便道。從終端讀入汽車到達或離去的資料，每組資料報括三項：
①是「到達」還是「離去」；②汽車牌照號碼；③「到達」或「離去」的時刻。與每組輸入資訊相應的輸出資訊為：如果是到達的車輛，則輸出其在停車場中或便道上的位置；如果是離去的車輛，則輸出其在停車場中停留的時間和應交的費用。
（提示：需另設乙個棧，臨時停放為讓路而從車場退出的車。）
3． 商品貨架管理。
商品貨架可以看成乙個棧，棧頂商品的生產日期最早，棧底商品的生產日期最近。上貨時，需要倒貨架，以保證生產日期較近的商品在較下的位置。用佇列和棧作為周轉，實現上述管理過程。
第三章答案
3.1按3.1(b)所示鐵道（兩側鐵道均為單向行駛道）進行車廂排程，回答：
（1） 如進站的車廂序列為123，則可能得到的出站車廂序列是什麼？
（2） 如進站的車廂序列為123456，能否得到435612和135426的出站序列，並說明原因（即寫出以「s」表示進棧、「x」表示出棧的棧序列操作）。
【解答】
（1）可能得到的出站車廂序列是：123、132、213、231、321。
(2)不能得到435612的出站序列。
因為有s(1)s(2)s(3)s(4)x(4)x(3)s(5)x(5)s(6)s(6)，此時按照「後進先出」的原則，出棧的順序必須為x(2)x(1)。
能得到135426的出站序列。
因為有s(1)x(1)s(2)s(3)x(3)s(4)s(5)x(5)x(4)x(2)x(1)。
3.3給出棧的兩種儲存結構形式名稱，在這兩種棧的儲存結構中如何判別棧空與棧滿？
【解答】（1）順序棧 （top用來存放棧頂元素的下標）
判斷棧s空：如果s->top==-1表示棧空。
判斷棧s滿：如果s->top==stack_size-1表示棧滿。
(2) 鏈棧（top為棧頂指標，指向當前棧頂元素前面的頭結點）
判斷棧空：如果top->next==null表示棧空。
判斷棧滿：當系統沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。
3． 4照四則運算加、減、乘、除和冪運算的優先慣例，畫出對下列表示式求值時運算元棧和運算子棧的變化過程：a-b*c/d+e↑f
【解答】
3． 5寫乙個演算法，判斷依次讀入的乙個以@為結束符的字母序列，是否形如『序列1&序列2』的字串行。序列1和序列2中都不含『&』，且序列2是序列1 的逆序列。例如，』a+b&b+a』是屬於該模式的字串行，而』1+3&3-1』則不是。
【解答】演算法如下：
int ishuiwen()
do /*判斷序列2是否是序列1的逆序列*/
} while(ch!=@ && !isempty(&s))
if(chisempty(&s))
/*序列2是序列1的逆序列*/
else
}/*ishuiwen()*/
3.8 要求迴圈佇列不損失乙個空間全部都能得到利用，設定乙個標誌tag,以tag為0或1來區分頭尾指標相同時的佇列狀態的空與滿，請編寫與此相應的入隊與出隊演算法。
【解答】入隊演算法：
int enterqueue(se**ueue *q, queueelementtype x)
出隊演算法：
int deletequeue( se**ueue *q , queueelementtype *x)
{ /*刪除隊頭元素，用x返回其值*/
if(q->front==q->rear && tag==0) /*隊空*/
return(false);
*x=q->element[q->front];
q->front=(q->front+1)%maxsize; /*重新設定隊頭指標*/
資料結構課後習題第三章
1.對於棧，運算元據的原則是 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.一般情況下，將遞迴演算法轉換成非遞迴應通過設定 實現。a.陣列 b.線性表 c.佇列d.棧 3.棧和佇列的共同點是 a.都是先進後出b.都是先進先出 c.只允許在端點處插入和刪除元素 d.沒有共同點 4.若元素...
資料結構第三章課後習題及總結
資料結構第三章 t1223 3 28朱俊傑 1 原理討論題 1 順序儲存的三個優點 1思路和實現都比較簡單，容易理解。2不用為表示結點間的邏輯關係而增加額外的儲存空間。3順序表具有按元素序號隨機訪問的特點。順序比鏈式節約空間。是因為鏈式結構每乙個節點都有乙個指標儲存域。順序支援隨機訪問，方便操作 鏈...
資料結構1800題第三章
第3章棧和佇列 一選擇題 1.對於棧運算元據的原則是 青島大學 2001 五 2 2分 a.先進先出 b.後進先出 c.後進後出 d.不分順序 2.在作進棧運算時,應先判別棧是否 在作退棧運算時應先判別棧是否 當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為 為了增加記憶體空間的利用率...