數(shù)據(jù)結(jié)構(gòu) 第3章棧和隊列答案

1、第三章 棧和隊列答案一、選擇題 1.B2.1B2.2A2.3B2.4D2.5.C3.B4.D5.D6.C7.D8.B9.D10.D11.D12.C13.B14.C15.B16.D17.B18.B19.B20.D21.D22.D23.D24.C25.A26.A27.D28.B29.BD30.C31.B32.C33.1B33.2A33.3C33.4C33.5F34.C35.C36.A37.AD二、判斷題1.2.3. 4. 5.×6.7.8. 9. 10.×11. 12.×13. ×14.×15. 16.×17.18.×19.20

2、. 部分答案解釋如下。1、 尾遞歸的消除就不需用棧2、 這個數(shù)是前序序列為1,2,3,n，所能得到的不相似的二叉樹的數(shù)目。三、填空題 1、操作受限（或限定僅在表尾進行插入和刪除操作） 后進先出 2、棧 3、3 1 2 4、23 100CH 5、0 n+1 top1+1=top2 6、兩棧頂指針值相減的絕對值為1（或兩棧頂指針相鄰）。7、(1)滿 (2)空 (3)n (4)棧底 (5)兩棧頂指針相鄰（即值之差的絕對值為1）8、鏈?zhǔn)酱鎯Y(jié)構(gòu) 9、S×SS×S×× 10、data+top=x； 11、23.12.3*2-4/34.5*7/+108.9/+（注：

3、表達(dá)式中的點(.)表示將數(shù)隔開，如23.12.3是三個數(shù)）12、假溢出時大量移動數(shù)據(jù)元素。 13、(M+1) MOD N (M+1)% N； 14、隊列 15、先進先出 16、先進先出 17、s=(LinkedList)malloc(sizeof(LNode)； s->data=x;s->next=r->next；r->next=s；r=s； 18、犧牲一個存儲單元 設(shè)標(biāo)記 19、（TAIL+1）MOD M=FRONT (數(shù)組下標(biāo)0到M-1，若一定使用1到M，則取模為0者，值改取M 20、sq.front=(sq.front+1)%(M+1)；return(sq.dat

4、a(sq.front)；(sq.rear+1)%(M+1)=sq.front； 21、棧 22、（rear-front+m）% m； 23、（R-P+N）% N；24、（1）ai或a1 （2）ai （3）pop（s）或s1； 25、（1）PUSH（OPTR，w）（2）POP（OPTR）（3）PUSH（OPND，operate（a，theta，b） 26、（1）T>0（2）i<n（3）T>0（4）top<n（5）top+1（6）true（7）i-1（8）top-1（9）T+wi（10）false四、應(yīng)用題 1、棧是只準(zhǔn)在一端進行插入和刪除操作的線性表，允許插入和刪除的一端

5、叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進先出（LIFO）表。2、隊列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的一端叫隊頭。最先插入隊的元素最先離開（刪除），故隊列也常稱先進先出（FIFO）表。3、用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊列，由于隊列的性質(zhì)（隊尾插入和隊頭刪除），容易造成“假溢出”現(xiàn)象，即隊尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊中元素個數(shù)小于隊列的長度（容量）。循環(huán)隊列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊列下，通常采用“犧牲一個存儲單元”或“作標(biāo)記”的方法解決“隊滿”和“隊空”的判定問題。4、（1）

6、通常有兩條規(guī)則。第一是給定序列中S的個數(shù)和X的個數(shù)相等；第二是從給定序列的開始，到給定序列中的任一位置，S的個數(shù)要大于或等于X的個數(shù)。 （2）可以得到相同的輸出元素序列。例如，輸入元素為A，B，C，則兩個輸入的合法序列ABC和BAC均可得到輸出元素序列ABC。對于合法序列ABC，我們使用本題約定的S×S×S×操作序列；對于合法序列BAC，我們使用SS××S×操作序列。5、三個：CDEBA，CDBEA，CDBAE6、輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素

7、剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。 得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)椋?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。7、能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。8、借助棧結(jié)構(gòu)，n個入棧元素可得到1/(n+1)(2n）！/（n!*n!）)種出棧序列。本題4個

8、元素，可有14種出棧序列，abcd和dcba就是其中兩種。但dabc和adbc是不可能得到的兩種。9、不能得到序列2，5，3，4，6。?？梢杂脝捂湵韺崿F(xiàn)，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設(shè)頭結(jié)點。10、如果i<j，則對于pi<pj情況，說明pi在pj入棧前先出棧。而對于pi>pj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對于i<j<k，不可能出現(xiàn)pj<pk<pi的輸出序列。換句話說，對于輸入序列1，2，3，不可能出現(xiàn)3，1，2的輸出序列。11、（1）能得到325641。在123依次進棧后，3和2出棧，

9、得部分輸出序列32；然后4，5入棧，5出棧，得部分出棧序列325；6入棧并出棧，得部分輸出序列3256；最后退棧，直到?？铡５幂敵鲂蛄?25641。其操作序列為AAADDAADADDD。 （2）不能得到輸出順序為154623的序列。部分合法操作序列為ADAAAADDAD，得到部分輸出序列1546后，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列154623。12、（1）一個函數(shù)在結(jié)束本函數(shù)之前，直接或間接調(diào)用函數(shù)自身，稱為遞歸。例如，函數(shù)f在執(zhí)行中，又調(diào)用函數(shù)f自身，這稱為直接遞歸；若函數(shù)f在執(zhí)行中，調(diào)用函數(shù)g，而g在執(zhí)行中，又調(diào)用函數(shù)f，這稱為間接遞歸。在實際應(yīng)用中，多為直接遞歸

10、，也常簡稱為遞歸。 （2）遞歸程序的優(yōu)點是程序結(jié)構(gòu)簡單、清晰，易證明其正確性。缺點是執(zhí)行中占內(nèi)存空間較多，運行效率低。 （3）遞歸程序執(zhí)行中需借助棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。 （4）遞歸程序的入口語句和出口語句一般用條件判斷語句來實現(xiàn)。遞歸程序由基本項和歸納項組成。基本項是遞歸程序出口，即不再遞歸即可求出結(jié)果的部分；歸納項是將原來問題化成簡單的且與原來形式一樣的問題，即向著“基本項”發(fā)展，最終“到達(dá)”基本項。13、函數(shù)調(diào)用結(jié)束時vol=14。執(zhí)行過程圖示如下： vol（4） vol(4)=vol(3)+5 14 =vol(2)+3+5 =vol(1)+4+3+5vol（3）+5 =vol(0)+2+

11、4+3+5 9 =0+2+4+3+5 =14vol（2）+3 6vol（1）+4 2vol（0）+2 014、過程p遞歸調(diào)用自身時，過程p由內(nèi)部定義的局部變量在p的2次調(diào)用期間，不占同一數(shù)據(jù)區(qū)。每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是遞歸定義所決定，用“遞歸工作?！眮韺崿F(xiàn)。15、設(shè)Hn為n個盤子的Hanoi塔的移動次數(shù)。(假定n個盤子從鋼針X移到鋼針Z，可借助鋼針Y) 則 Hn =2Hn-1+1 /先將n-1個盤子從X移到Y(jié)，第n個盤子移到Z，再將那n-1個移到Z =2（2Hn-2+1）+1 =22 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 · 

12、3; · = 2k Hn-k+2k-1 +2k-2 +21 +20 =2n-1 H1+2n-2+2n-3+21+20 因為H1=1，所以原式Hn=2n-1+2n-2+21+20=2n-1故總盤數(shù)為n的Hanoi塔的移動次數(shù)是2n-1。16、運行結(jié)果為：1 2 1 3 1 2 1（注：運行結(jié)果是每行一個數(shù)，為節(jié)省篇幅，放到一行。）17、兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設(shè)共享數(shù)組為SMAX，則一個棧頂指針為-1，另一個棧頂指針為MAX時，棧為空。 用C寫的入棧操作push（i，x）如下： const MAX=共享棧可能達(dá)到的最大容量 typedef

13、 struct node elemtype sMAX； int top2； anode； anode ds; int push(int i,elemtype x)/ds為容量有MAX個類型為elemtype的元素的一維數(shù)組，由兩個棧共享其空間。i的值為0或1，x為類型為elemtype的元素。本算法將x壓入棧中。如壓棧成功，返回1；否則，返回0。 if（ds.top1-ds.top0=1）printf（“棧滿n”）；return（0）； switch（i） case 0：ds.s+ds.topi=x；break； case 1：ds.s-ds.topi=x； return（1）；/入棧成功。

14、18、本程序段查找棧S中有無整數(shù)為k的元素，如有，則刪除。采用的辦法使用另一個棧T。在S棧元素退棧時，若退棧元素不是整數(shù)k，則壓入T棧。遇整數(shù)k，k不入T棧，然后將T棧元素全部退棧，并依次壓入棧S中，實現(xiàn)了在S中刪除整數(shù)k的目的。若S中無整數(shù)k，則在S退成空棧后，再將T棧元素退棧，并依次壓入S棧。直至T?？?。這后一種情況下S棧內(nèi)容操作前后不變。19、中綴表達(dá)式8-(3+5)*(5-6/2）的后綴表達(dá)式是： 8 3 5 + 5 6 2 / - * - 棧的變化過程圖略（請參見22題），表達(dá)式生成過程為：中綴表達(dá)式exp1轉(zhuǎn)為后綴表達(dá)式exp2的規(guī)則如下：設(shè)操作符棧s，初始為空棧后，壓入優(yōu)先級最低

15、的操作符#。對中綴表達(dá)式從左向右掃描，遇操作數(shù)，直接寫入exp2；若是操作符（記為w），分如下情況處理，直至表達(dá)式exp1掃描完畢。（1）w為一般操作符（+，-，*，/等），要與棧頂操作符比較優(yōu)先級，若w優(yōu)先級高于棧頂操作符，則入棧；否則，棧頂運算符退棧到exp2，w再與新棧頂操作符作上述比較處理，直至w入棧。（2）w為左括號（），w入棧。（3）w為右括號（），操作符棧退棧并進入exp2，直到碰到左括號為止，左括號退棧（不能進入exp2），右括號也丟掉，達(dá)到exp2中消除括號的目的。（4）w為#，表示中綴表達(dá)式exp1結(jié)束，操作符棧退棧到exp2，直至碰到#，退棧，整個操作結(jié)束。這里，再介紹一

16、種簡單方法。中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式有三步：首先，將中綴表達(dá)式中所有的子表達(dá)式按計算規(guī)則用嵌套括號括起來；接著，順序?qū)⒚繉ㄌ栔械倪\算符移到相應(yīng)括號的后面；最后，刪除所有括號。例如，將中綴表達(dá)式8-(3+5)*(5-6/2）轉(zhuǎn)為后綴表達(dá)式。按如上步驟：執(zhí)行完上面第一步后為：(8-(3+5)*(5-(6/2)；執(zhí)行完上面第二步后為：(8(35)+(5(62)/)-)*)- ；執(zhí)行完上面第三步后為：8 3 5 + 5 6 2 / - * - 。可用類似方法將中綴表達(dá)式轉(zhuǎn)為前綴表達(dá)式。20、中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式的規(guī)則基本上與上面19題相同，不同之處是對運算符*優(yōu)先級的規(guī)定。在算術(shù)運算中，先乘除后

17、加減，先括號內(nèi)后括號外，相同級別的運算符按從左到右的規(guī)則運算。而對*運算符，其優(yōu)先級同常規(guī)理解，即高于加減乘除而小于左括號。為了適應(yīng)本題中“從右到左計算”的要求，規(guī)定棧頂運算符*的級別小于正從表達(dá)式中讀出的運算符*，即剛讀出的運算符*級別高于棧頂運算符*，因此也入棧。 下面以A*B*C為例說明實現(xiàn)過程。 讀入A，不是操作符，直接寫入結(jié)果表達(dá)式。再讀入*，這里規(guī)定在讀入*后，不能立即當(dāng)乘號處理，要看下一個符號，若下個符號不是*，則前個*是乘號。這里因為下一個待讀的符號也是*，故認(rèn)為*是一個運算符，與運算符棧頂比較（運算符棧頂初始化后，首先壓入#作為開始標(biāo)志），其級別高于#，入棧。再讀入B，直接進

18、入結(jié)果表達(dá)式。接著讀入*，與棧頂比較，均為*，我們規(guī)定，后讀入的*級別高于棧頂?shù)?，因此*入棧。接著讀入C，直接到結(jié)果表達(dá)式?，F(xiàn)在的結(jié)果（后綴）表達(dá)式是ABC。最后讀入#，表示輸入表達(dá)式結(jié)束，這時運算符棧中從棧頂?shù)綏５子袃蓚€*和一個#。兩個運算符*退棧至結(jié)果表達(dá)式，結(jié)果表達(dá)式變?yōu)锳BC*。運算符棧中只剩#，退棧，運算結(jié)束。21、（1）sum=21。當(dāng)x為局部變量時，每次遞歸調(diào)用，都要給局部變量分配存儲單元，故x數(shù)值4，9，6和2均保留，其遞歸過程示意圖如下： sum（4） 21 sum（3）+4 （x=4） 17 sum（2）+9 （x=9）8 sum（1）+6 （x=6）2 sum（0）+2

19、 （x=2）0(2) sum=8,當(dāng)x為全局變量時，在程序的整個執(zhí)行期間，x只占一個存儲單元，先后讀入的4個數(shù)(4,9,6,2),僅最后一個起作用。當(dāng)遞歸調(diào)用結(jié)束，逐層返回時sum:=sum(n-1)+x表達(dá)式中，x就是2，所以結(jié)果為sum=8。22、設(shè)操作數(shù)棧是opnd，操作符棧是optr，對算術(shù)表達(dá)式A-B*C/D-EF求值，過程如下：步驟opnd棧optr棧輸入字符主要操作初始#A-B*C/D-EF#PUSH(OPTR,#)1A#A-B*C/D-EF#PUSH(OPND,A)2A# -B*C/D-EF#PUSH(OPTR,-)3AB# -B*C/D-EF#PUSH(OPND,B)4AB#

20、 - *C/D-EF#PUSH(OPTR,*)5ABC# - *C/D-EF#PUSH(OPND,C)6AT(T=B*C)# - /D-EF#PUSH(OPND,POP(OPND)*POP(OPND)PUSH(OPTR,/)7ATD# - /D-EF#PUSH(OPND,D)8AT(T=T/D)T(T=A-T)# - # - -EF#x=POP(OPND);y=POP(OPND)PUSH(OPND,y/x);x=POP(OPND);y=POP(OPND);PUSH(OPND,y-x)PUSH(OPTR,-)9TE# -EF#PUSH(OPND,E)10TE# -F#PUSH(OPTR, )11

21、TEF# -F#PUSH(OPND,F)12 TETS(S=EF) R(R=T-S) #- # # X=POP(OPND) Y=POP(OPND)POP(OPTR) PUSH(OPND,yx)x=POP(OPND) y=POP(OPND)POP(OPTR) PUSH(OPND,y-x) 23、 步驟棧S1棧S2輸入的算術(shù)表達(dá)式（按字符讀入）初始®A-B*C/D+E/F®1A®A-B*C/D+E/F®2A®-B*C/D+E/F®3AB®-B*C/D+E/F®4AB®-*C/D+E/F®5ABC&#

22、174;-*C/D+E/F®6AT1（注：T1=B*C）®-/D+E/F®7AT1D®-/D+E/F®8AT2（注：T2=T1/D）T3 （注：T3=A-T2）®-®+E/F®9T3E®+E/F®10T3E®+/F®11T3EF®+/F®12T3T4（注：T4=E/F）T5（注：T5= T3+ T4）®+®®24、XSXXXSSSXXSXXSXXSSSS25、S1和S2共享內(nèi)存中一片連續(xù)空間（地址1到m），可以將S1和S2的棧

23、底設(shè)在兩端，兩棧頂向共享空間的中心延伸，僅當(dāng)兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時，判斷為棧滿，當(dāng)一個棧頂指針為0，另一個棧頂指針m+1時為兩棧均空。26、設(shè)棧S1和棧S2共享向量V1.m，初始時，棧S1的棧頂指針top0=0，棧S2的棧頂指針top1=m+1，當(dāng)top0=0為左棧空，top1=m+1為右?？?；當(dāng)top0=0并且top1=m+1時為全?？?。當(dāng)top1-top0=1時為棧滿。27、（1）每個棧僅用一個順序存儲空間時，操作簡便，但分配存儲空間小了，容易產(chǎn)生溢出，分配空間大了，容易造成浪費，各棧不能共享空間。 （2）多個棧共享一個順序存儲空間，充分利用了存儲空間，只有在整

24、個存儲空間都用完時才能產(chǎn)生溢出，其缺點是當(dāng)一個棧滿時要向左、右棧查詢有無空閑單元。如果有，則要移動元素和修改相關(guān)的棧底和棧頂指針。當(dāng)接近棧滿時，查詢空閑單元、移動元素和修改棧底棧頂指針的操作頻繁，計算復(fù)雜并且耗費時間。 （3）多個鏈棧一般不考慮棧的溢出（僅受用戶內(nèi)存空間限制），缺點是棧中元素要以指針相鏈接，比順序存儲多占用了存儲空間。28、設(shè)top1和top2分別為棧1和2的棧頂指針（1）入棧主要語句if(top2-top1=1) printf(“棧滿n”); exit(0);case1:top1+；SPACEtop1=x; /設(shè)x為入棧元素。case2:top2-；SPACEtop2=x;出

25、棧主要語句case1：if（top1=-1） printf（“?？課”）；exit（0）； top1-；return（SPACEtop1+1）； /返回出棧元素。case2：if（top2=N）printf（“棧空n”）；exit（0）； top2+；return（SPACEtop2-1）； /返回出棧元素。 （2）棧滿條件：top2-top1=1?？諚l件：top1=-1并且top2=N /top1=-1為左棧空，top2=N為右?？?9、設(shè)順序存儲隊列用一維數(shù)組qm表示，其中m為隊列中元素個數(shù)，隊列中元素在向量中的下標(biāo)從0到m-1。設(shè)隊頭指針為front，隊尾指針是rear，約定front指

26、向隊頭元素的前一位置，rear指向隊尾元素。當(dāng)front等于-1時隊空，rear等于m-1時為隊滿。由于隊列的性質(zhì)（“刪除”在隊頭而“插入”在隊尾），所以當(dāng)隊尾指針rear等于m-1時，若front不等于-1，則隊列中仍有空閑單元，所以隊列并不是真滿。這時若再有入隊操作，會造成假“溢出”。其解決辦法有二，一是將隊列元素向前“平移”（占用0至rear-front-1）；二是將隊列看成首尾相連，即循環(huán)隊列（0.m-1）。在循環(huán)隊列下，仍定義front=rear時為隊空，而判斷隊滿則用兩種辦法，一是用“犧牲一個單元”，即rear+1=front（準(zhǔn)確記是（rear+1）%m=front，m是隊列容量

27、）時為隊滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記tag，tag等于0情況下，若刪除時導(dǎo)致front=rear為隊空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊滿。30、見上題29的解答。 31、參見上面29題。32、typedef struct nodeelemtype elemcqm; /m為隊列最大可能的容量。 int front ,rear; /front和rear分別為隊頭和隊尾指針。cqnode;cqnode cq;(1) 初始狀態(tài)cq.front=cq.rear=0;(2) 隊列空cq.front=cq.rear;(3) 隊列滿(cq.rear+1)%m=cq.fro

28、nt;33、棧的特點是后進先出，隊列的特點是先進先出。初始時設(shè)棧s1和棧s2均為空。（1）用棧s1和s2模擬一個隊列的輸入：設(shè)s1和s2容量相等。分以下三種情況討論：若s1未滿，則元素入s1棧；若s1滿，s2空，則將s1全部元素退棧，再壓棧入s2，之后元素入s1棧；若s1滿，s2不空（已有出隊列元素），則不能入隊。（2）用棧s1和s2模擬隊列出隊（刪除）：若棧s2不空，退棧，即是隊列的出隊；若s2為空且s1不空，則將s1棧中全部元素退棧，并依次壓入s2中，s2棧頂元素退棧，這就是相當(dāng)于隊列的出隊。若棧s1為空并且s2也為空，隊列空，不能出隊。（3）判隊空 若棧s1為空并且s2也為空，才是隊列空

29、。討論：s1和s2容量之和是隊列的最大容量。其操作是，s1棧滿后，全部退棧并壓棧入s2（設(shè)s1和s2容量相等）。再入棧s1直至s1滿。這相當(dāng)隊列元素“入隊”完畢。出隊時，s2退棧完畢后，s1棧中元素依次退棧到s2，s2退棧完畢，相當(dāng)于隊列中全部元素出隊。 在棧s2不空情況下，若要求入隊操作，只要s1不滿，就可壓入s1中。若s1滿和s2不空狀態(tài)下要求隊列的入隊時，按出錯處理。34、（1）隊空s.front=s.rear； /設(shè)s是sequeuetp類型變量 （2）隊滿：（s.rear+1）MOD MAXSIZE=s.front /數(shù)組下標(biāo)為0. MAXSIZE-1具體參見本章應(yīng)用題第29題35、

30、typedef structelemtp qm; int front,count; /front是隊首指針，count是隊列中元素個數(shù)。cqnode; /定義類型標(biāo)識符。(1)判空：int Empty(cqnode cq) /cq是cqnode類型的變量 if(cq.count=0) return(1)；else return(0); /空隊列入隊: int EnQueue(cqnode cq，elemtp x)if(count=m)printf(“隊滿n”)；exit(0); cq.q(cq.front+count)%m=x; /x入隊 count+; return(1); /隊列中元素個數(shù)

31、增加1,入隊成功。出隊: int DelQueue(cqnode cq)if (count=0)printf(“隊空n”)；return(0); printf(“出隊元素”，cq.qcq.front); x=cq.qcq.front;cq.front=(cq.front+1)%m; /計算新的隊頭指針。return(x)(2) 隊列中能容納的元素的個數(shù)為m。隊頭指針front指向隊頭元素。36、循環(huán)隊列中元素個數(shù)為（REAR-FRONT+N）%N。其中FRONT是隊首指針，指向隊首元素的前一位置；REAR是隊尾指針，指向隊尾元素；N是隊列最大長度。37、循環(huán)隊列解決了用向量表示隊列所出現(xiàn)的“假

32、溢出”問題，但同時又出現(xiàn)了如何判斷隊列的滿與空問題。例如：在隊列長10的循環(huán)隊列中，若假定隊頭指針front指向隊頭元素的前一位置，而隊尾指針指向隊尾元素，則front=3，rear=7的情況下，連續(xù)出隊4個元素，則front=rear為隊空；如果連續(xù)入隊6個元素，則front=rear為隊滿。如何判斷這種情況下的隊滿與隊空，一般采取犧牲一個單元的做法或設(shè)標(biāo)記法。即假設(shè)front=rear為隊空，而（rear+1）%表長=front為隊滿，或通過設(shè)標(biāo)記tag。若tag=0，front=rear則為隊空；若tag=1，因入隊而使得front=rear，則為隊滿。本題中隊列尾指針rear，指向隊尾

33、元素的下一位置,listarrayrear表示下一個入隊的元素。在這種情況下，我們可規(guī)定，隊頭指針front指向隊首元素。當(dāng)front=rear時為隊空，當(dāng)（rear+1）%n=front時為隊滿。出隊操作（在隊列不空情況下）隊頭指針是front=（front+1）%n，38、既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是dbca。39、（1）4132 （2）4213 （3）423140、（1）隊空的初始條件：f=r=0； （2）執(zhí)行操作A3后，r=3；/ A3表示三次入隊操作 執(zhí)行操作D1后，f=1；/D1表示一次出隊操作 執(zhí)行操作A5后，r=0； 執(zhí)行操作D2后

34、，f=3； 執(zhí)行操作A1后，r=1； 執(zhí)行操作D2后，f=5； 執(zhí)行操作A4后，按溢出處理。因為執(zhí)行A3后，r=4，這時隊滿，若再執(zhí)行A操作，則出錯。41一般說，高級語言的變量名是以字母開頭的字母數(shù)字序列。故本題答案是:AP321,PA321,P3A21,P32A1,P321A。五、算法設(shè)計題1、題目分析兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時，s1棧頂指針為-1，s2棧頂為maxsize。兩棧頂指針相鄰時為棧滿。兩棧頂相向，迎面增長，棧頂指針指向棧頂元素。#define maxsize 兩棧共享順序存儲空間所能達(dá)到的最多元素數(shù)#define elemtp int /假設(shè)元素類型為整型

35、typedef structelemtp stackmaxsize; /?？臻g int top2; /top為兩個棧頂指針stk;stk s; /s是如上定義的結(jié)構(gòu)類型變量，為全局變量。(1)入棧操作：int push(int i,int x)/入棧操作。i為棧號，i=0表示左邊的棧s1，i=1表示右邊的棧s2，x是入棧元素。入棧成功返回1，否則返回0。if(i<0|i>1)printf(“棧號輸入不對”);exit(0);if(s.top1-s.top0=1) printf(“棧已滿n”);return(0);switch(i) case 0: s.stack+s.top0=x;

36、 return(1); break; case 1: s.stack-s.top1=x; return(1); /push（2） 退棧操作 elemtp pop(int i) /退棧算法。i代表棧號，i=0時為s1棧，i=1時為s2棧。退棧成功返回退棧元素，否則返回-1。 if(i<0 | i>1)printf(“棧號輸入錯誤n”)；exit(0); switch(i) case 0: if(s.top0=-1) printf(“?？課”)；return（-1）； else return(s.stacks.top0-); case 1: if(s.top1=maxsize prin

37、tf(“?？課”); return(-1); else return(s.stacks.top1+); /算法結(jié)束 算法討論 請注意算法中兩棧入棧和退棧時的棧頂指針的計算。兩棧共享空間示意圖略，s1棧是通常意義下的棧，而s2棧入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。2、#define maxsize 棧空間容量 void InOutS(int smaxsize) /s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。 int top=0; /top為棧頂指針，定義top=0時為?？?。 for(i=1; i<=n; i+) /n個整數(shù)序列作處理。 scanf(“%d”,

38、&x); /從鍵盤讀入整數(shù)序列。 if(x!=-1) / 讀入的整數(shù)不等于-1時入棧。 if(top=maxsize-1)printf(“棧滿n”);exit(0);else s+top=x; /x入棧。 else /讀入的整數(shù)等于-1時退棧。 if(top=0)printf(“?？課”);exit(0); else printf(“出棧元素是%dn”,stop-)； /算法結(jié)束。3、題目分析判斷表達(dá)式中括號是否匹配，可通過棧，簡單說是左括號時進棧，右括號時退棧。退棧時，若棧頂元素是左括號，則新讀入的右括號與棧頂左括號就可消去。如此下去，輸入表達(dá)式結(jié)束時，棧為空則正確，否則括號不匹配。

39、 int EXYX(char E,int n) /E是有n字符的字符數(shù)組，存放字符串表達(dá)式，以#結(jié)束。本算法判斷表達(dá)式中圓括號是否匹配。char s30; /s是一維數(shù)組，容量足夠大，用作存放括號的棧。 int top=0; /top用作棧頂指針。 stop= #; /#先入棧，用于和表達(dá)式結(jié)束符號#匹配。 int i=0; /字符數(shù)組E的工作指針。 while(Ei!= #) /逐字符處理字符表達(dá)式的數(shù)組。 switch(Ei) case(: s+top=(; i+ ; break ;case): if(stop=(top-; i+; break;elseprintf(“括號不配對”);ex

40、it(0);case#: if(stop=#)printf(“括號配對n”);return (1);else printf(“ 括號不配對n”);return (0); /括號不配對 default : i+; /讀入其它字符，不作處理。 /算法結(jié)束。算法討論本題是用棧判斷括號匹配的特例：只檢查圓括號的配對。一般情況是檢查花括號（，）、方括號（，）和圓括號（，）的配對問題。編寫算法中如遇左括號（，或（）就壓入棧中，如遇右括號（，或），則與棧頂元素比較，如是與其配對的括號（左花括號，左方括號或左圓括號），則彈出棧頂元素；否則，就結(jié)論括號不配對。在讀入表達(dá)式結(jié)束符#時，棧中若應(yīng)只剩#，表示括號全部

41、配對成功；否則表示括號不匹配。 另外，由于本題只是檢查括號是否匹配，故對從表達(dá)式中讀入的不是括號的那些字符，一律未作處理。再有，假設(shè)棧容量足夠大，因此入棧時未判斷溢出。4、題目分析逆波蘭表達(dá)式(即后綴表達(dá)式)求值規(guī)則如下：設(shè)立運算數(shù)棧OPND,對表達(dá)式從左到右掃描(讀入)，當(dāng)表達(dá)式中掃描到數(shù)時，壓入OPND棧。當(dāng)掃描到運算符時，從OPND退出兩個數(shù)，進行相應(yīng)運算，結(jié)果再壓入OPND棧。這個過程一直進行到讀出表達(dá)式結(jié)束符$，這時OPND棧中只有一個數(shù)，就是結(jié)果。 float expr( )/從鍵盤輸入逆波蘭表達(dá)式，以$表示輸入結(jié)束，本算法求逆波蘭式表達(dá)式的值。float OPND30; / OP

42、ND是操作數(shù)棧。init(OPND); /兩棧初始化。 float num=0.0; /數(shù)字初始化。 scanf (“%c”,&x);/x是字符型變量。 while(x!=$) switch case0<=x<=9:while(x>=0&&x<=9)|x=.) /拼數(shù) if(x!=.) /處理整數(shù)num=num*10+（ord(x)-ord(0)）; scanf(“%c”,&x); else /處理小數(shù)部分。 scale=10.0; scanf(“%c”,&x); while(x>=0&&x<=9) n

43、um=num+(ord(x)-ord(0)/scale; scale=scale*10; scanf(“%c”,&x); /else push(OPND,num); num=0.0;/數(shù)壓入棧，下個數(shù)初始化 case x= :break; /遇空格，繼續(xù)讀下一個字符。 case x=+:push(OPND,pop(OPND)+pop(OPND);break; case x=-:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=*:push(OPND,pop(OPND)*pop(OPND);break; case x=/:x

44、1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: /其它符號不作處理。 /結(jié)束switch scanf(“%c”,&x);/讀入表達(dá)式中下一個字符。 /結(jié)束while（x！=$） printf(“后綴表達(dá)式的值為%f”,pop(OPND);/算法結(jié)束。算法討論假設(shè)輸入的后綴表達(dá)式是正確的，未作錯誤檢查。算法中拼數(shù)部分是核心。若遇到大于等于0且小于等于9的字符，認(rèn)為是數(shù)。這種字符的序號減去字符0的序號得出數(shù)。對于整數(shù)，每讀入一個數(shù)字字符，前面得到的部分?jǐn)?shù)要乘上10再加新讀入的數(shù)得到新的部分?jǐn)?shù)。當(dāng)讀到小數(shù)點，認(rèn)為數(shù)的整數(shù)部分

45、已完，要接著處理小數(shù)部分。小數(shù)部分的數(shù)要除以10（或10的冪數(shù)）變成十分位，百分位，千分位數(shù)等等，與前面部分?jǐn)?shù)相加。在拼數(shù)過程中，若遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復(fù)為0，準(zhǔn)備下一個數(shù)。這時對新讀入的字符進入+、-、*、/及空格的判斷，因此在結(jié)束處理數(shù)字字符的case后，不能加入break語句。5、（1）A和D是合法序列，B和C 是非法序列。 （2）設(shè)被判定的操作序列已存入一維數(shù)組A中。 int Judge(char A) /判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。 i=0; /i為下標(biāo)。 j=k=0; /j和k分別為I

46、和字母O的的個數(shù)。 while(Ai!=0) /當(dāng)未到字符數(shù)組尾就作。 switch(Ai) caseI: j+; break; /入棧次數(shù)增1。 caseO: k+; if(k>j)printf(“序列非法n”)；exit(0); i+; /不論Ai是I或O，指針i均后移。 if(j!=k) printf(“序列非法n”)；return(false); else printf(“序列合法n”)；return(true); /算法結(jié)束。 算法討論在入棧出棧序列（即由I和O組成的字符串）的任一位置，入棧次數(shù)（I的個數(shù)）都必須大于等于出棧次數(shù)（即O的個數(shù)），否則視作非法序列，立即給出信息，退

47、出算法。整個序列（即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記0），入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序列。6、題目分析表達(dá)式中的括號有以下三對：（、）、，使用棧，當(dāng)為左括號時入棧，右括號時，若棧頂是其對應(yīng)的左括號，則退棧，若不是其對應(yīng)的左括號，則結(jié)論為括號不配對。當(dāng)表達(dá)式結(jié)束，若棧為空，則結(jié)論表達(dá)式括號配對，否則，結(jié)論表達(dá)式括號不配對。int Match(LinkedList la)/算術(shù)表達(dá)式存儲在以la為頭結(jié)點的單循環(huán)鏈表中，本算法判斷括號是否正確配對char s; /s為字符棧，容量足夠大p=la->link; /p為工作指針，指向待處理結(jié)點StackI

48、nit(s); /初始化棧s while (p!=la) /循環(huán)到頭結(jié)點為止 switch (p->ch) case (:push(s,p->ch); break; case ):if(StackEmpty(s)|StackGetTop(s)!=()printf(“括號不配對n”); return(0); else pop(s);break;case :push(s,p->ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括號不配對n”); return(0); else pop(s);break;cas

49、e :push(s,p->ch); break; case : if(StackEmpty(s)|StackGetTop(s)!=)printf(“括號不配對n”); return(0); else pop(s);break; p=p->link; 后移指針/whileif (StackEmpty(s) printf(“括號配對n”); return(1); elseprintf(“括號不配對n”); return(0); /算法match結(jié)束 算法討論算法中對非括號的字符未加討論。遇到右括號時，若棧空或棧頂元素不是其對應(yīng)的左圓（方、花）括號，則結(jié)論括號不配對，退出運行。最后，若棧不空，仍結(jié)論括號不配對。7、題目分析棧的特點是后進先出，隊列的特點是先進先出。所以，用兩個棧s1和s2模擬一個隊列時，s1作輸入棧，逐個元素壓棧，以此模擬隊列元素的入隊。當(dāng)需要出隊時，將棧s1退棧并逐個壓入棧s2中，s1中最先入棧的元素，在s2中處于棧頂。s2退棧，相當(dāng)于隊列的出隊，實現(xiàn)了先進先出。顯然，只有棧s2為空且s1也為空，才算是隊列空。(1) int enqueue(stack s1,elemtp x)/s1是容量為n的棧，棧中元素類型是elemtp。本算法將x入棧，若入棧成功返回1，否則返回0。if(top1=n &