第三章習題

1.按圖3.1(b)所示鐵道(兩側鐵道均為單向行駛道)進展車廂調度，答復：

(1)如進站的車廂序列為123,則可能得到的出站車廂序列是什么

⑵如進站的車廂序列為123456,能否得到435612和135426的出站序列，并說明原因。(即寫出

以“S”表示進棧、以“X〃表示出棧的棧操作序列)。

2.設隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復執行以下4步操作:

(1)輸出隊首元素；

(2)把隊首元素值插入到隊尾；

(3)刪除隊首元素；

(4)再次刪除隊首元素。

直到隊列成為空隊列為止，得到輸出序列：

⑴A、C、E、C,C(2)A、C、E

(3)A、C、E、C、C、C(4)A、C、E、C

3.給出棧的兩種存儲構造形式名稱，在這兩種棧的存儲構造中若何判別棧空與棧滿

4.按照四則運算加、減、乘、除和幕運算(t)優先關系的慣例，畫出對以下算術表達式求值時操作

數棧和運算符棧的變化過程：

A—B*C/D+EtF

5.試寫一個算法，判斷依次讀入的一個以@為完畢符的字母序列，是否為形如'序列1&序列2'模式

的字符序列。其中序列1和序列2中都不含字符',且序列2是序列1的逆序歹％例如，'a+b&b+a，

是屬該模式的字符序列，而41+3&3-1,則不是。

6.假設表達式由單字母變量和雙目四則運算算符構成。試寫一個算法，將一個通常書寫形式且書寫正

確的表達式轉換為逆波蘭式。

7.假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點(注意不設頭指針)，

試編寫相應的隊列初始化、入隊列和出隊列的算法。

8.要求循環隊列不損失一個空間全部都能得到利用，設置一個標志域tag,以tag為0或1來區分頭

尾指針一樣時的隊列狀態的空與滿，請編寫與此構造相應的入隊與出隊算法。

9.簡述以下算法的功能(其中棧和隊列的元素類型均為int)：

⑴voidproc_l(StackS)

{inti,n,A[255];

n=0;

while(!EmptyStack(S))

{n++;Pop(&S,&A[n]);}

for(i=l;i<=n;i++)

Push(&S,A[i]);

)

⑵voidproc_2(StackS,inte)

{StackT;intd;

InitStack(&T);

while(!EmptyStack(S))

{Pop(&S,&d);

if(d!=e)Push(&T,d);

)

while(!EmptyStack(T))

{Pop(&T,&d);

Push(&S,d);

)

i

(3)voidproc_3(Queue*Q)

{StackS;intd;

InitStack(&S);

while(!EmptyQueue(*Q))

DeleteQueue(Q,&d);

Push(&S,d);

while(!EmptyStack(S))

{Pop(&S,&d);

EnterQueue(Q,d)

）

實習題

1.回文判斷。稱正讀與反讀都一樣的字符序列為“回文”序列。

試寫一個算法，判斷依次讀入的一個以@為完畢符的字母序列，是否為形如'序列1&序列2，

模式的字符序列。其中序列1和序列2中都不含字符,且序列2是序列1的逆序列。例如，

<a+b&b+a;是屬該模式的字符序列，而'1+3&3—?1.'則不是。

2.停車場管理。

設停車場是一個可停放n輛車的狹長通道，且只有一個大門可供汽車進出。在停車場內，汽車

按到達的先后次序，由北向南依次排列（假設大門在最南端）。假設車場內已停滿n輛車，則后

來的汽車需在門外的便道上等候，當有車開走時，便道上的第一輛車即可開入。當停車場內某輛車

要離開時，在它之后進入的車輛必須先退出車場為它讓路，待該輛車開出大門后，其它車輛再按

原次序返回車場。每輛車離開停車場時,應按其停留時間的長短交費（在便道上停留的時間不收費）。

試編寫程序，模擬上述管理過程。要求以順序棧模擬停車場，以鏈隊列模擬便道。從終端讀入

汽車到達或離去的數據，每組數據包括三項：①是“到達”還是"離去"；②汽車牌照號碼；③“到

達〃或“離去”的時刻。與每組輸入信息相應的輸出信息為：如果是到達的車輛，則輸出其在停車

場中或便道上的位置；如果是離去的車輛，則輸出其在停車場中停留的時間和應交的費用。（提示:

需另設一個棧，臨時停放為讓路而從車場退出的車。）

3.商品貨架管理。

商品貨架可以看成一個棧，棧頂商品的生產日期最早，棧底商品的生產日期最近。上貨時，需要倒貨

架，以保證生產日期較近的商品在較下的位置。用隊列和棧作為周轉，實現上述管理過程。

第三章答案

3.1按3.1（b）所示鐵道（兩側鐵道均為單向行駛道）進展車廂調度，答復:

m如進站的車廂序列為123,則可能得到的出站車廂序列是什么

⑵如進站的車廂序列為123456,能否得至I435612和135426的出站序歹U,并說明原因(即寫

出以“S”表示進棧、“X”表示出棧的棧序列操作)。

【解答】

⑴可能得到的出站車廂序列是：123、132、213、231、321。

(2)不能得至I」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)o

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+EtF

【解答】

3.5寫一個算法，判斷依次讀入的一個以@為完畢符的字母序列，是否形如'序列1&序列2'的字符

序列。序列1和序列2中都不含,且序列2是序列1的逆序列。例如，'a+b&b+a'是屬于該

模式的字符序列，而'1+3&3-1’則不是。

【解答】算法如下：

intlsHuiWen()

Stack*S;

Charch,temp;

lnitStack(&S);

Printf("\n請輸入字符序列：”)

Ch=getchar();

While(ch!=&)/*序列1入棧*/

{Push(&S,ch);

ch=getchar();

)

do/*判斷序列2是否是序列1的逆序列*/

{ch=getchar();

Pop(&S,&temp);

if(ch!=temp)/*序列2不是序列1的逆序列*/

{return(FALSE);printf("\nNO");}

}while(ch!=@&&!lsEmpty(&S))

if(ch==@&&lsEmpty(&S))

{return(TRUE);printf("\n丫ES");}/*序列2是序列1的逆序列*/

else

{return(FALSE);printfCnNO");}

}/*lsHuiWen()7

3.8要求循環隊列不損失一個空間全部都能得到利用，設置一個標志tag,以tag為0或1來區分頭尾

指針一樣時的隊列狀態的空與滿，請編寫與此相應的入隊與出隊算法。

【解答】入隊算法：

intEnterQueue(SeqQueue*Q,QueueElementTypex)

{/*將元素x入隊*/

if(Q->front==Q->front&&tag==1)/*隊滿*/

return(FALSE);

if(Q->front==Q->front&&tag==O)/*x入隊前隊空，x入隊后重新設置標志*/

tag=1;

Q->elememt[Q->rear]=x;

Q->rear=(Q->rear+1)%MAXSIZE;/*設置隊尾指針*/

Return(TRUE);

)

出隊算法：

intDeleteQueue(SeqQueue*Q,QueueElementType*x)

{/*刪除隊頭元素，用x返回其值*/

if(Q->front==Q->rear&&tag==O)/*隊空*/

return(FALSE);

*x=Q->element[Q->front];

Q->front=(Q->front+1)%MAXSIZE;/*重新設置隊頭指針*/

if(Q->front==Q->rear)tag=O;/*隊頭元素出隊后隊列為空，重新設置標志域*/

Return(TUUE);

)

編寫求解Hanoi問題的算法，并給出三個盤子搬動時的遞歸調用過程。

【解答】算法：

voidhanoi(intn,charx,chary,charz)

{/*將塔座X上按直徑由小到大且至上而下編號為1到n的n個圓盤按規則搬到塔座Z上，丫可用

做輔助塔座*/

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(1,A,B,C)move(A->C)1號搬至UC

Move(A->B)2號搬到B

Hanoi(1,C,A,B)move(C->B)1號搬至B

Move(A->C)3號搬到C

Hanoi(2,B,A,C)

Hanoi。，B,GA)move(B->A)1號搬到A

Move(B->C)2號搬到C

Hanoi(1,A,B,C)move(A->C)1號搬至UC

提示:

第3章限定性線性表一棧和隊列

習題

1.按圖3.1(b)所示鐵道(兩側鐵道均為單向行駛道)進展車廂調度，答復:

⑴如進站的車廂序列為123,則可能得到的出站車廂序列是什么123、213、132、231、321(312)

⑵如進站的車廂序列為123456,能否得到435612和135426的出站序列，并說明原因。(即寫出以“S”表

示進棧、以“X”表示出棧的棧操作序列)。

SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6

2.設隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復執行以下4步操作:

(1)輸出隊首元素;

（2）把隊首元素值插入到隊尾;

（3）刪除隊首元素；

（4）再次刪除隊首元素。

直到隊列成為空隊列為止，則是否可能得到輸出序列:

（1）A、C、E、C、C（2）A、C、E

⑶A、C、(4)A、C、E、C

［提不］:

B、C、D、E（輸出隊首元素A）

B、C、D、E、A（把隊首元素A插入到隊尾）

B、C、D、EA（刪除隊首元素A）

D、E、A（再次刪除隊首元素B）

D、E、A（輸出隊首元素C）

D、E、AC（把隊首元素C插入到隊尾）

D、（刪除隊首元素C）

A、C（再次刪除隊首元素D）

3.給出棧的兩種存儲構造形式名稱，在這兩種棧的存儲構造中若何判別棧空與棧滿

4.按照四則運算加、減、乘、除和幕運算（t）優先關系的慣例，畫出對以下算術表達式求值時操作數棧和運算符棧

的變化過程：

A-B*C/D+EfF

5.試寫一個算法，判斷依次讀入的一個以@為完畢符的字母序列，是否為形如'序列1&序列2,模式的字符序列。

其中序列1和序列2中都不含字符，&，，且序列2是序列1的逆序列。例如，'a+b&b+a'是屬該模式的字符序

列，而'1+3&3一—貝!|不是。

［提示］:

（1）邊讀邊入棧，直到&

（2）邊讀邊出棧邊對比，直到……

6.假設表達式由單字母變量和雙目四則運算算符構成。試寫一個算法，將一個通常書寫形式（中綴）且書寫正確的表

達式轉換為逆波蘭式（后綴）。

【提示］:

例：

中綴表達式：a+b后綴表達式：ab+

中綴表達式：a+bxc后綴表達式：abcx+

中綴表達式：a+bxc-d后綴表達式：abcx+d-

中綴表達式：a+bxc-d/e后綴表達式：abcx+de/-

中綴表達式：a+b“c-d)-e/f后綴表達式：abcd-x+ef/-

?后綴表達式的計算過程：(簡便)

順序掃描表達式，

(1)如果是操作數，直接入棧；

(2)如果是操作符op,則連續退棧兩次，得操作數X,Y,計算XopY,并將結果入棧。

?若何將中綴表達式轉換為后綴表達式

順序掃描中綴表達式，

(1)如果是操作數，直接輸出；

(2)如果是操作符op2,則與棧頂操作符。pi對比：

如果OP2>OP1,則OP2入棧；

如果OP2=OP1,則脫括號；

如果OP2VOP1,則輸出Opi;

7.假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點(注意不設頭指針)，試編寫相應的

隊列初始化、入隊列和出隊列的算法。

［提示］:參P.56P.70先畫圖.

typedefLinkListCLQueue;

intlnitQueue(CLQueue*Q)

intEnterQueue(CLQueueQ,QueueElementTypex)

intDeleteQueue(CLQueueQ,QueueElementType*x)

8.要求循環隊列不損失一個空間全部都能得到利用，設置一個標志域tag,以tag為。或1來區分頭尾指針一樣時的

隊列狀態的空與滿，請編寫與此構造相應的入隊與出隊算法。

[提示]:

初始狀態：front==0,rear==O,tag==O

隊空條件：front==rear,tag==O

隊滿條件：front==rear,tag==1

其它狀態：front!=rear,tag==0(或1、2)

入隊操作：

…(入隊)

if(front==rear)tag=1；(或直接tag=1)

出隊操作：

…(出隊)

tag=0；

[問題]：若何明確區分隊空、隊滿、非空非滿三種情況

9.簡述以下算法的功能(其中棧和隊列的元素類型均為int)：

(1)voidproc_1(StackS)

{inti,n,A[255];

n=0;

while(!EmptyStack(S))

{n++;Pop(&S,&A[n]);}

for(i=1;i<=n;i++)

Push(&S,A[i]);

}

將棧S逆序。

(2)voidproc_2(StackS,inte)

{StackT;intd;

lnitStack(&T);

whiie(!EmptyStack(S))

{Pop(&S,&d);

if(d!=e)Push(&T,d);

}

while(!EmptyStack(T))

{Pop(&T,&d);

Push(&S,d);

}

}

刪除棧S中所有等于e的元素。

(3)voidproc_3(Queue*Q)

{StackS;intd;

lnitStack(&S);

while(!EmptyQueue(*Q))

(

DeleteQueue(Q,&d);

Push(&S,d);

}

while(!EmptyStack(S))

{Pop(&S,&d);

EnterQueue(Q,