第三章習(xí)題1、

按圖3、1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度,回答:

⑴如進(jìn)站得車廂序列為123,則可能得到得出站車廂序列就是什么？⑵如進(jìn)站得車廂序列為123456,能否得到435612與135426得出站序列,并說(shuō)明原因。(即寫出以“S”表示進(jìn)棧、以“X”表示出棧得棧操作序列)。2、

設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素,其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作:(1)

輸出隊(duì)首元素;(2)

把隊(duì)首元素值插入到隊(duì)尾;(3)

刪除隊(duì)首元素;(4)

再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止,得到輸出序列:(1)

A、C、E、C、C

(2)A、C、E(3)

A、C、E、C、C、C

(4)A、C、E、C3、

給出棧得兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧得存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？4、

按照四則運(yùn)算加、減、乘、除與冪運(yùn)算(↑)優(yōu)先關(guān)系得慣例,畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧與運(yùn)算符棧得變化過(guò)程:

A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5、

試寫一個(gè)算法,判斷依次讀入得一個(gè)以為結(jié)束符得字母序列,就是否為形如‘序列1&序列2’模式得字符序列。其中序列1與序列2中都不含字符’&’,且序列2就是序列1得逆序列。例如,‘a(chǎn)+b&b+a’就是屬該模式得字符序列,而‘１+３&３－１’則不就是。6、

假設(shè)表達(dá)式由單字母變量與雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法,將一個(gè)通常書寫形式且書寫正確得表達(dá)式轉(zhuǎn)換為逆波蘭式。7、

假設(shè)以帶頭結(jié)點(diǎn)得循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫相應(yīng)得隊(duì)列初始化、入隊(duì)列與出隊(duì)列得算法。8、

要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用,設(shè)置一個(gè)標(biāo)志域tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)得隊(duì)列狀態(tài)得空與滿,請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)得入隊(duì)與出隊(duì)算法。9、

簡(jiǎn)述以下算法得功能(其中棧與隊(duì)列得元素類型均為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]);

}(2)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);

}}(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)

}

}實(shí)習(xí)題1.

回文判斷。稱正讀與反讀都相同得字符序列為“回文”序列。試寫一個(gè)算法,判斷依次讀入得一個(gè)以為結(jié)束符得字母序列,就是否為形如‘序列1&序列2’模式得字符序列。其中序列1與序列2中都不含字符‘&’,且序列2就是序列1得逆序列。例如,‘a(chǎn)+b&b+a’就是屬該模式得字符序列,而‘１+３&３－１’則不就是。2.

停車場(chǎng)管理。設(shè)停車場(chǎng)就是一個(gè)可停放n輛車得狹長(zhǎng)通道,且只有一個(gè)大門可供汽車進(jìn)出。在停車場(chǎng)內(nèi),汽車按到達(dá)得先后次序,由北向南依次排列(假設(shè)大門在最南端)。若車場(chǎng)內(nèi)已停滿n輛車,則后來(lái)得汽車需在門外得便道上等候,當(dāng)有車開(kāi)走時(shí),便道上得第一輛車即可開(kāi)入。當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí),在它之后進(jìn)入得車輛必須先退出車場(chǎng)為它讓路,待該輛車開(kāi)出大門后,其它車輛再按原次序返回車場(chǎng)。每輛車離開(kāi)停車場(chǎng)時(shí),應(yīng)按其停留時(shí)間得長(zhǎng)短交費(fèi)(在便道上停留得時(shí)間不收費(fèi))。試編寫程序,模擬上述管理過(guò)程。要求以順序棧模擬停車場(chǎng),以鏈隊(duì)列模擬便道。從終端讀入汽車到達(dá)或離去得數(shù)據(jù),每組數(shù)據(jù)包括三項(xiàng):①就是“到達(dá)”還就是“離去”;②汽車牌照號(hào)碼;③“到達(dá)”或“離去”得時(shí)刻。與每組輸入信息相應(yīng)得輸出信息為:如果就是到達(dá)得車輛,則輸出其在停車場(chǎng)中或便道上得位置;如果就是離去得車輛,則輸出其在停車場(chǎng)中停留得時(shí)間與應(yīng)交得費(fèi)用。(提示:需另設(shè)一個(gè)棧,臨時(shí)停放為讓路而從車場(chǎng)退出得車。)3.

商品貨架管理。商品貨架可以瞧成一個(gè)棧,棧頂商品得生產(chǎn)日期最早,棧底商品得生產(chǎn)日期最近。上貨時(shí),需要倒貨架,以保證生產(chǎn)日期較近得商品在較下得位置。用隊(duì)列與棧作為周轉(zhuǎn),實(shí)現(xiàn)上述管理過(guò)程。第三章答案3、1按3、1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度,回答:(1)

如進(jìn)站得車廂序列為123,則可能得到得出站車廂序列就是什么？(2)

如進(jìn)站得車廂序列為123456,能否得到435612與135426得出站序列,并說(shuō)明原因(即寫出以“S”表示進(jìn)棧、“X”表示出棧得棧序列操作)?！窘獯稹?1)可能得到得出站車廂序列就是:123、132、213、231、321。(2)不能得到435612得出站序列。因?yàn)橛蠸(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6),此時(shí)按照“后進(jìn)先出”得原則,出棧得順序必須為X(2)X(1)。能得到135426得出站序列。因?yàn)橛蠸(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。

3、3給出棧得兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧得存儲(chǔ)結(jié)構(gòu)中如何判別?？张c棧滿？【解答】(1)順序棧

(top用來(lái)存放棧頂元素得下標(biāo))判斷棧S空:如果S->top==-1表示?？?。判斷棧S滿:如果S->top==Stack_Size-1表示棧滿。(2)鏈棧(top為棧頂指針,指向當(dāng)前棧頂元素前面得頭結(jié)點(diǎn))判斷?？?如果top->next==NULL表示?？铡Ｅ袛鄺M:當(dāng)系統(tǒng)沒(méi)有可用空間時(shí),申請(qǐng)不到空間存放要進(jìn)棧得元素,此時(shí)棧滿。

3.4照四則運(yùn)算加、減、乘、除與冪運(yùn)算得優(yōu)先慣例,畫出對(duì)下列表達(dá)式求值時(shí)操作數(shù)棧與運(yùn)算符棧得變化過(guò)程:A-B*C/D+E↑F【解答】3.5寫一個(gè)算法,判斷依次讀入得一個(gè)以為結(jié)束符得字母序列,就是否形如‘序列1&序列2’得字符序列。序列1與序列2中都不含‘&’,且序列2就是序列1得逆序列。例如,’a+b&b+a’就是屬于該模式得字符序列,而’1+3&3-1’則不就是?！窘獯稹克惴ㄈ缦?

int

IsHuiWen()

{

Stack

*S;

Char

ch,temp;

InitStack(&S);

Printf(“\n請(qǐng)輸入字符序列:”);

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!=

&&

!IsEmpty(&S))if(ch==

&&

IsEmpty(&S))

{return(TRUE);

printf(“\nYES”);}

/*序列2就是序列1得逆序列*/else

{return(FALSE);

printf(“\nNO”);}

}/*IsHuiWen()*/

3、8要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用,設(shè)置一個(gè)標(biāo)志tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)得隊(duì)列狀態(tài)得空與滿,請(qǐng)編寫與此相應(yīng)得入隊(duì)與出隊(duì)算法。【解答】入隊(duì)算法:int

EnterQueue(SeqQueue

*Q,

QueueElementType

x){

/*將元素x入隊(duì)*/

if(Q->front==Q->front

&&

tag==1)

/*隊(duì)滿*/

return(FALSE);

if(Q->front==Q->front

&&

tag==0)

/*x入隊(duì)前隊(duì)空,x入隊(duì)后重新設(shè)置標(biāo)志*/

tag=1;Q->elememt[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;

/*設(shè)置隊(duì)尾指針*/Return(TRUE);

}

出隊(duì)算法:

int

DeleteQueue(SeqQueue

*Q,

QueueElementType

*x)

{/*刪除隊(duì)頭元素,用x返回其值*/if(Q->front==Q->rear

&&

tag==0)

/*隊(duì)空*/

return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE;

/*重新設(shè)置隊(duì)頭指針*/if(Q->front==Q->rear)

tag=0;

/*隊(duì)頭元素出隊(duì)后隊(duì)列為空,重新設(shè)置標(biāo)志域*/Return(TUUE);

}

編寫求解Hanoi問(wèn)題得算法,并給出三個(gè)盤子搬動(dòng)時(shí)得遞歸調(diào)用過(guò)程。【解答】算法:

void

hanoi(int

n,char

x,char

y,char

z)

{

/*將塔座X上按直徑由小到大且至上而下編號(hào)為1到n得n個(gè)圓盤按規(guī)則搬到塔座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)得遞歸調(diào)用過(guò)程:

Hanoi(2,A,C,B):

Hanoi(1,A,B,C)

move(A->C)

1號(hào)搬到C

Move(A->B)

2號(hào)搬到B

Hanoi(1,C,A,B)

move(C->B)

1號(hào)搬到B

Move(A->C)

3號(hào)搬到CHanoi(2,B,A,C)

Hanoi(1,B,C,A)

move(B->A)

1號(hào)搬到A

Move(B->C)

2號(hào)搬到C

Hanoi(1,A,B,C)

move(A->C)

1號(hào)搬到C

提示:第3章限定性線性表—棧與隊(duì)列習(xí)題1、

按圖3、1(b)所示鐵道(兩側(cè)鐵道均為單向行駛道)進(jìn)行車廂調(diào)度,回答:

⑴如進(jìn)站得車廂序列為123,則可能得到得出站車廂序列就是什么？

123、213、132、231、321(312)⑵如進(jìn)站得車廂序列為123456,能否得到435612與135426得出站序列,并說(shuō)明原因。(即寫出以“S”表示進(jìn)棧、以“X”表示出棧得棧操作序列)。SXSSXSSXXXSX

或

S1X1S2S3X3S4S5X5X4X2S6X62、

設(shè)隊(duì)列中有A、B、C、D、E這5個(gè)元素,其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作:(1)

輸出隊(duì)首元素;(2)

把隊(duì)首元素值插入到隊(duì)尾;(3)

刪除隊(duì)首元素;(4)

再次刪除隊(duì)首元素。直到隊(duì)列成為空隊(duì)列為止,則就是否可能得到輸出序列:(1)

A、C、E、C、C

(2)A、C、E(3)

A、C、E、C、C、C

(4)A、C、E、C[提示]:

A、B、C、D、E

(輸出隊(duì)首元素A)

A、B、C、D、E、A

(把隊(duì)首元素A插入到隊(duì)尾)

B、C、D、E、A

(刪除隊(duì)首元素A)

C、D、E、A

(再次刪除隊(duì)首元素B)

C、D、E、A(輸出隊(duì)首元素C)

C、D、E、A、C

(把隊(duì)首元素C插入到隊(duì)尾)

D、E、A、C

(刪除隊(duì)首元素C)

E、A、C

(再次刪除隊(duì)首元素D)

3、

給出棧得兩種存儲(chǔ)結(jié)構(gòu)形式名稱,在這兩種棧得存儲(chǔ)結(jié)構(gòu)中如何判別棧空與棧滿？4、

按照四則運(yùn)算加、減、乘、除與冪運(yùn)算(↑)優(yōu)先關(guān)系得慣例,畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧與運(yùn)算符棧得變化過(guò)程:

A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5、

試寫一個(gè)算法,判斷依次讀入得一個(gè)以為結(jié)束符得字母序列,就是否為形如‘序列1&序列2’模式得字符序列。其中序列1與序列2中都不含字符’&’,且序列2就是序列1得逆序列。例如,‘a(chǎn)+b&b+a’就是屬該模式得字符序列,而‘１+３&３－１’則不就是。[提示]:(1)

邊讀邊入棧,直到&(2)

邊讀邊出棧邊比較,直到……

6、

假設(shè)表達(dá)式由單字母變量與雙目四則運(yùn)算算符構(gòu)成。試寫一個(gè)算法,將一個(gè)通常書寫形式(中綴)且書寫正確得表達(dá)式轉(zhuǎn)換為逆波蘭式(后綴)。[提示]:例:中綴表達(dá)式:a+b

后綴表達(dá)式:

ab+中綴表達(dá)式:a+b×c

后綴表達(dá)式:

abc×+中綴表達(dá)式:a+b×c-d

后綴表達(dá)式:

abc×+d-中綴表達(dá)式:a+b×c-d/e

后綴表達(dá)式:

abc×+de/-中綴表達(dá)式:a+b×(c-d)-e/f

后綴表達(dá)式:

abcd-×+ef/-

后綴表達(dá)式得計(jì)算過(guò)程:(簡(jiǎn)便)順序掃描表達(dá)式,(1)

如果就是操作數(shù),直接入棧;(2)

如果就是操作符op,則連續(xù)退棧兩次,得操作數(shù)X,Y,計(jì)算XopY,并將結(jié)果入棧。

如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？順序掃描中綴表達(dá)式,(1)如果就是操作數(shù),直接輸出;(2)如果就是操作符op2,則與棧頂操作符op1比較:如果op2>op1,則op2入棧;如果op2=op1,則脫括號(hào);如果op2<op1,則輸出op1;

7、

假設(shè)以帶頭結(jié)點(diǎn)得循環(huán)鏈表表示隊(duì)列,并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針),試編寫相應(yīng)得隊(duì)列初始化、入隊(duì)列與出隊(duì)列得算法。[提示]:參P、56

P、70

先畫圖、typedef

LinkList

CLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intDeleteQueue(CLQueueQ,QueueElementType*x)

8、

要求循環(huán)隊(duì)列不損失一個(gè)空間全部都能得到利用,設(shè)置一個(gè)標(biāo)志域tag,以tag為0或1來(lái)區(qū)分頭尾指針相同時(shí)得隊(duì)列狀態(tài)得空與滿,請(qǐng)編寫與此結(jié)構(gòu)相應(yīng)得入隊(duì)與出隊(duì)算法。[提示]:

初始狀態(tài):front==0,

rear==0,

tag==0

隊(duì)空條件:front==rear,

tag==0

隊(duì)滿條件:front==rear,

tag==1

其它狀態(tài):front!=rear,

tag==0(或1、2)

入隊(duì)操作:…(入隊(duì))if(front==rear)

tag=1;(或直接tag=1)

出隊(duì)操作:…(出隊(duì))tag=0;

[問(wèn)題]:如何明確區(qū)分隊(duì)空、隊(duì)滿、非空非滿三種情況？

9、

簡(jiǎn)述以下算法得功能(其中棧與隊(duì)列得元素類型均為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;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)voidproc_3(Queue

*Q){StackS;

intd;InitStack(&S);

while(!EmptyQueue(*Q))

{Delet