1、第三章習題 1. 按圖3.1(b)所示鐵道(兩側鐵道均為單向行駛道)進行車廂調度，回答： 如進站的車廂序歹 0 為123,則可能得到的出站車廂序歹 0 是什么？ 如進站的車廂序列為123456,能否得到435612和135426的出站序列，并說明原因。(即寫出 以“S”表示進棧、以“ X”表示出棧的棧操作序列)。 2. 設隊列中有A、B、C、E這5個元素，其中隊首元素為 A。如果對這個隊列重復執行下列 4步 操作： (1) 輸出隊首元素； (2) 把隊首元素值插入到隊尾； (3) 刪除隊首元素； (4) 再次刪除隊首元素。 直到隊列成為空隊列為止，得到輸出序列： (1) A G E、G C (

2、2) A、C、E (3) A、C、E、C、C、C (4) A、C、E、C 3. 給出棧的兩種存儲結構形式名稱，在這兩種棧的存儲結構中如何判別棧空與棧滿？ 4. 按照四則運算加、減、乘、除和籍運算(f)優先關系的慣例，畫出對下列算術表達式求值時操 作數棧和運算符棧的變化過程： A B* C/D+ E f F 5. 試寫一個算法，判斷依次讀入的一個以遂結束符的字母序列，是否為形如序列 1 &序列2 模式的字符序歹 0。其中序列1和序列2中都不含字符&,且序列2是序列1的逆序歹 0。例如， a+b&b+a是屆該模式的字符序歹 0,而1 +3 &3 1 則不是。 6.

3、假設表達式由單字母變量和雙目四則運算算符構成。試寫一個算法，將一個通常書寫形式且書寫 正確的表達式轉換為逆波蘭式。 7. 假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點(注意不設頭指針)， 試編寫相應的隊列初始化、入隊列和出隊列的算法。 8. 要求循環隊列不損失一個空間全部都能得到利用，設置一個標志域tag ,以tag為0或1來區分 頭尾指針相同時的隊列狀態的空與滿，請編寫與此結構相應的入隊與出隊算法。 9. 簡述以下算法的功能(其中棧和隊列的元素類型均為 int ): (1) void proc_1(Stack S) ( int i, n, A255; n=0; whil

4、e(!EmptyStack(S) (n+; Pop(&S, &An); for(i=1; itop=-1表示棧空。 判斷棧S滿：如果S-top=Stack_Size-1 表示棧滿。 (2)鏈棧(top為棧頂指針，指向當前棧頂元素前面的頭結點) 判斷棧空：如果top-next=NULL表示棧空。 判斷棧滿：當系統沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。 3. 4照四則運算加、減、乘、除和籍運算的優先慣例，畫出對下列表達式求值時操作數棧和運算符棧 的變化過程：A-B*C/D+E f F 【解答】OVS OPTR OVS OPTR OVS OPTR,+ OPTR7,

5、生成 T(1)/D T(2) A OVS CPTR OVS OPTR 右邊界* T(4) front=Q-front & tag=1) /* 隊滿 */ return(FALSE); if(Q-front=Q-front & tag=0) /*x入隊前隊空，x入隊后重新設置標志*/ tag=1; Q-elememtQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /*設置隊尾指針 */ Return(TRUE); 出隊算法： int DeleteQueue( SeqQueue *Q , QueueElementType *x) ( /*刪除隊頭元素，用x

6、返回其值*/ if(Q-front=Q-rear & tag=0) /* 隊空 */ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新設置隊頭指針 */ if(Q-front=Q-rear) tag=0; /*隊頭元素出隊后隊歹0為空，重新設置標志域 */ Return(TUUE); 編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調用過程。 【解答】算法： void hanoi (int n ,char x, char y, char z) ( /*將塔座X上按直徑由小到大且至上而下編號

7、為 1到n的n個圓盤按規則搬到塔座Z上，Y可用 做輔助塔座*/ if(n = =1) move(x,1,z); else ( Hanoi(n-1,x,z,y); move(x, n, z); Hanoi(n-1, y,x,z); Hanoi(3,A,B,C)的遞歸調用過程: Hanoi(2,A,C,B): Hanoi(2,B,A,C) 提示: 習題 1. 按圖3.1(b)所示鐵道(兩側鐵道均為單向行駛道)進行車廂調度，回答: 如進站的車廂序列為 123,則可能得到的出站車廂序列是什么? 如進站的車廂序列為 123456，能否得到435612和135426的出站序列，并說明原因。(即寫出以“ S

8、”表 示進棧、以“ X”表示出棧的棧操作序列)。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6 A、B、C、D、E這5個元素，其中隊首元素為 A。如果對這個隊列重復執行下列 4步操作: (1) 輸出隊首兀素； 2) 把隊首兀素值插入到隊尾; 3) 刪除隊首兀素； 4) 再次刪除隊首兀:素。 Hanoi(1,A,B,C) move(A-C) 1 號搬到 C Move(A-B) 2號搬到B Hanoi(1,C,A,B) move(C-B) 1 號搬到 B Move(A-C) 3號搬到C Hanoi(1,B,C,A) move(B-A) 1 號搬到 A Move

9、(B-C) 2號搬到C Hanoi(1,A,B,C) move(A-C) 1 號搬到 C 第3章 限定性線性表 棧和隊列 123、213、132、231、321 (312) 2. 設隊列中有 直到隊列成為空隊列為止，則是否可能得到輸出序列: 提示： A、B、C、D、E （輸出隊首元素A） A、 B、C、D、E、A （把隊首元素 A插入到隊尾） B、 C、D、E、A （刪除隊首元素A） C、 D、E、A （再次刪除隊首元素B） C、D、E、A （輸出隊首元素C） C、 D、E、A、C （把隊首元素 C插入到隊尾） D、 E、A、C （刪除隊首元素C） E、 A、C （再次刪除隊首元素D） 3.

10、給出棧的兩種存儲結構形式名稱，在這兩種棧的存儲結構中如何判別棧空與棧滿？ 4. 按照四則運算加、減、乘、除和藉運算（f）優先關系的慣例，畫出對下列算術表達式求值時操作數棧和運算 符棧的變化過程： A B * C/D+ E f F 5. 試寫一個算法，判斷依次讀入的一個以 為結束符的字母序列，是否為形如序列 1 & 序列2模式的字符 序列。其中序列1和序列2中都不含字符&且序列2是序列1的逆序列。例如，a+b&b+a 是屬該模式 的字符序列，而1 + 3 & 3 1則不是。 提示： 邊讀邊入棧，直到& 6. 假設表達式由單字母變量和雙目四則運算算符構成。試

11、寫一個算法，將一個 通常書寫形式（中綴） 且書寫正確 的表達式轉換為逆波蘭式（后綴）。 提示： 例: 中綴表達式：a+b 后綴表達式：ab + 中綴表達式：a+b xc 后綴表達式：abc x+ 中綴表達式：a+bXc-d 后綴表達式：abc d- (3) A、 A、 C、 E、 C、 C (2) A、 C、 E C、E、 C、C、C (4) A、 C、 E、 C (2) 邊讀邊出棧邊比較，直到, 中綴 表達式：a+b Xc-d/e 后綴 表達式：abc x+de/- 中綴表達式：a+b Xc-d)-e/f 后綴 表達式：abcd - +ef/- 后綴表達式的計算過程：(簡便) 順序掃描表達式

12、， (1) 如果是操作數，直接入棧； (2) 如果是操作符op,則連續退棧兩次，得操作數 X, Y ,計算X op Y ,并將結果入棧。 * 如何將中綴表達式轉換為后綴表達式？ 順序掃描中綴表達式， (1) 如果是操作數，直接輸出； (2) 如果是操作符op 2,則與棧頂操作符op 1比較： 如果op 2 op 1,則op 2入棧； 如果op 2 = op 1,則脫括號； 如果op 2 op 1,則輸出op 1 ； 7. 假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點(注意不設頭指針)，試編寫相應 的隊列初始化、入隊列和出隊列的算法。 提示: 參P.56 P.70 先畫圖.

13、 typedef LinkList CLQueue ; int InitQueue( CLQueue * Q) int EnterQueue( CLQueue Q, QueueElementType x) int DeleteQueue( CLQueue Q, QueueElementType *x) 8. 要求循環隊列不損失一個空間全部都能得到利用 ，設置一個標志域tag ,以tag為0或1來區分頭尾指針相同 時的隊列狀態的空與滿，請編寫與此結構相應的入隊與出隊算法。 提示: 初始狀態： front=0, rear=0, tag=0 隊空條件： front=rear, tag= 0 隊滿條件

14、: front=rear, tag= 1 其它狀態： front !=rear, tag= 0 （或 1、2） 入隊操作： ,(入隊) if (front=rear) tag= 1;(或直接 tag= 1) 出隊操作： ,(出隊) tag= 0; 問題:如何明確區分 隊空、隊滿、非空非滿三種情況？ 9. 簡述以下算法的功能(其中棧和隊列的元素類型均為 int) (1) void proc_1(Stack S) ( int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i=n; i+) Push(

15、&S, Ai); 將棧S逆序。 ( Stack T; int d; InitStack(&T); while(!EmptyStack(S) ( Pop(&S, &d); if (d!=e) Push( &T, d); while(!EmptyStack(T) ( Pop(&T, &d); Push( &S, d); 刪除棧S中所有等于e的元素。 (3) void proc_3(Queue *Q) ( Stack S; int d; InitStack(&S); while(!EmptyQueue(*Q) ( DeleteQ

16、ueue(Q, &d); Push( &S, d); while(!EmptyStack(S) ( Pop(&S, &d); EnterQueue(Q , d) 將隊列Q逆序。 實習題 1. 回文判斷。稱正讀與反讀都相同的字符序列為“回文”序列。 試寫一個算法，判斷依次讀入的一個以 為結束符的字母序列，是否為形如序列 1 &序列2模式的 字符序列。其中序列 1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a 是屬 該模式的字符序列，而1 +3 & 3 1則不是。 2. 停車場管理。 設停車場是一個可停放 n輛車的狹長通道，且只有一個大門可供汽車進出。在停車場內，汽車按到達的 先后次序，由北向南依次排列（假設大門在最南端）。若車場內已停滿 n輛車，則后來的汽車需在門外的便道 上等候，當有車開走時，便道上的第一輛車即可開入。當停車場內某輛車要離開時，在它之后進入的車輛必須 先退出車場為它讓路，待該輛車開出大門后，其它車輛再按原次序返回車場。每輛車離開停車場時，應按其停 留時間的長短交費（在便道上停留的時間不收費）。 試編寫程序，模擬上述管理過程。要求以順序棧模 擬停車場，以鏈隊列模擬便道。從終端讀入汽車到達 或離去的數據，每組數據包括三項：是“到達