第章棧和隊(duì)列答案

1、第三章棧和隊(duì)列答案、選擇題1.B2.1B2.2A2.3B2.4D3.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、判斷題12.3.4. V5. X6. V7. V8. V9. V10. x11. V/ 12. X13. x14. X15. v16. X17. V18. x19. V20. v/部分答案解釋如下。1、尾遞歸的消除就不需

2、用棧2、這個(gè)數(shù)是前序序列為 1,2,3,n所能得到的不相似的二叉樹的數(shù)目。三、填空題1、 操作受限(或限定僅在表尾進(jìn)行插入和刪除操作)后進(jìn)先出2、棧3、3 1 24、23100CH5、0n+1top1+1=top26、兩棧頂指針值相減的絕對值為1 (或兩棧頂指針相鄰)。7、 (1)滿(2)空(3)n (4) 棧底(5)兩棧頂指針相鄰(即值之差的絕對值為1)8、 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)9、Sx SSX Sxx 10、data+top=x ;11、 23.12.3*2-4/34.5*7/+108.9/+(注：表達(dá)式中的點(diǎn) ()表示將數(shù)隔開，如是三個(gè)數(shù))12、假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素。13、 (M+1) MO

3、D N (M+1)% N ;14 、隊(duì)列 15、先進(jìn)先出16、先進(jìn)先出17、 s=(LinkedList)malloc(sizeof (LNode) ; s-data=x;s-next=r-next; r-next=s ;r=s ;18、 犧牲一個(gè)存儲(chǔ)單元設(shè)標(biāo)記19、 (TAIL+1 ) MOD M=FRONT數(shù)組下標(biāo)0到M-1，若一定使用1到M則取模為0者，值 改取M20、sq.front=(sq.front+1)%(M+1); return (sq.data(sq.front);(sq.rear+1)%(M+1)=sq.fro nt;21、棧 22、(rear-front+m ) % m

4、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) T0 (2) i0 ( 4) topn (5) top+1 (6) true (7) i-1 ( 8) top-1 (9) T+wi (10) false四、應(yīng)用題1、 棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出(L IF O)表。2、隊(duì)列是允許在一端插入而在另一

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

6、，S的個(gè)數(shù)要大于或等于 X的個(gè)數(shù)。(2) 可以得到相同的輸出元素序列。例如，輸入元素為A，B，C,則兩個(gè)輸入的合法序列ABC和BAC均可得到輸出元素序列 ABC。對于合法序列 ABC，我們使用本題約定 的SX SX SX操作序列；對于合法序列 BAC我們使用SSXX SX操作序列。5、三個(gè)：CDEBA CDBEA CDBAE6、 輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是 12,前面 4個(gè)元素(4356)得到后，棧中元素剩 12,且2在棧頂，不可能棧底元素 1在棧頂元素2 之前出棧。得到135426的過程如下：1入棧并出棧，得到部分輸出序列 1;然后2和3入棧

7、，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,三個(gè)元素中 C是棧頂元素，B 和A不可能早于C出棧，故不可能得到 D B A C、E出棧序列。8、 借助棧結(jié)構(gòu)，n個(gè)入棧元素可得到 1/(n+1)(2n )! / (n!*n!)種出棧序列。本題 4 個(gè)元素，可有14種出棧序列，abed和deba就是其中兩種。但 dabc和adbc是不可能得到 的兩

8、種。9、 不能得到序列2, 5, 3, 4, 6。?？梢杂脝捂湵韺?shí)現(xiàn)，這就是鏈棧。由于棧只在棧頂 操作，所以鏈棧通常不設(shè)頭結(jié)點(diǎn)。10、 如果i pj的情況，則 說明要將口壓到pi之上，也就是在 pj出棧之后pi才能出棧。這就說明，對于 ijk,不可 能出現(xiàn)pjpkpi的輸出序列。換句話說，對于輸入序列 1, 2, 3,不可能出現(xiàn)3, 1, 2的輸 出序列。11、 ( 1)能得到325641。在123依次進(jìn)棧后，3和2出棧，得部分輸出序列 32;然后4, 5入棧，5出棧，得部分出棧序列 325; 6入棧并出棧，得部分輸出序列3256;最后退棧， 直到?？铡５幂敵鲂蛄?325641。其操作序列為

9、AAADDAADADDD(2)不能得到輸出順序?yàn)?54623的序列。部分合法操作序列為ADAAAADDADI到部分輸出序列1546后，棧中元素為23,3在棧頂，故不可能2先出棧，得不到輸出序列154623。12、(1) 一個(gè)函數(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,這稱為間接遞歸。在實(shí)際應(yīng)用中，多為直接遞歸，也常簡稱為 遞歸。(2) 遞歸程序的優(yōu)點(diǎn)是程序結(jié)構(gòu)簡單、清晰，易證明其正確性。缺點(diǎn)是執(zhí)行中占內(nèi) 存空間較多，運(yùn)行效率低。(3) 遞歸程序執(zhí)行中需借助棧這種數(shù)

10、據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。(4) 遞歸程序的入口語句和出口語句一般用條件判斷語句來實(shí)現(xiàn)。遞歸程序由基本項(xiàng)和歸納項(xiàng)組成。 基本項(xiàng)是遞歸程序出口， 即不再遞歸即可求出結(jié)果的部分； 歸納項(xiàng)是將原 來問題化成簡單的且與原來形式一樣的問題，即向著“基本項(xiàng)”發(fā)展，最終“到達(dá)”基本項(xiàng)。13、函數(shù)調(diào)用結(jié)束時(shí) vol=14。執(zhí)行過程圖示如下：vol(4)=vol(3)+5 =vol(2)+3+5 =vol(1)+4+3+5vol (3) +5=vol(0)+2+4+3+5=0+2+4+3+5=1414、過程p遞歸調(diào)用自身時(shí)，過程 p由內(nèi)部定義的局部變量在 p的2次調(diào)用期間，不占 同一數(shù)據(jù)區(qū)。每次調(diào)用都保留其數(shù)據(jù)區(qū)，這是遞歸

11、定義所決定，用“遞歸工作?！眮韺?shí)現(xiàn)。15、設(shè)Hn為n個(gè)盤子的Hanoi塔的移動(dòng)次數(shù)。(假定n個(gè)盤子從鋼針X移到鋼針乙可借助鋼針Y)則Hn=2Hn-1+1/先將n-1個(gè)盤子從X移到Y(jié),第n個(gè)盤子移到Z,再將那n-1個(gè)移到Z=2(2H-2+1) +1=22Hn-2+2+1=22(2Hn-3+1 ) +2+1=232Hn-3+2 +2+1ckk-1 ck-2J=2 H n-k+2+2+ +2 +2n-1n-2 n-31 0=2 H1+2 +2 + +2 +2因?yàn)?H1=1，所以原式 Hn=2n-1+2n-2+21+20=2n-1故總盤數(shù)為n的Hanoi塔的移動(dòng)次數(shù)是 2n-1。16、 運(yùn)行結(jié)果為：1

12、2 13 12 1(注：運(yùn)行結(jié)果是每行一個(gè)數(shù)，為節(jié)省篇幅，放 到一行。)17、 兩棧共享一向量空間(一維數(shù)組)，棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時(shí)為棧滿。設(shè)共享數(shù)組為SMAX，則一個(gè)棧頂指針為-1，另一個(gè)棧頂指針為MAX寸，棧為空。用C寫的入棧操作push (i, x)如下：con st MAX=共享?xiàng)？赡苓_(dá)到的最大容量typedef struct nodeelemtype sMAX ;int top2;anode ;anode ds;int push( int i,elemtype x)/ds為容量有MAX個(gè)類型為elemtype的元素的一維數(shù)組，由兩個(gè)棧共享其空間。i的值為0或1, x為類型

13、為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）; / 入棧成功。18、 本程序段查找棧S中有無整數(shù)為k的元素，如有，則刪除。采用的辦法使用另一個(gè)棧T。在S棧元素退棧時(shí)，若退棧元素不是整數(shù)k，則壓入T棧。遇整數(shù)k， k不入T棧，然后將T棧元素全部退棧，并依次壓入棧 S中，實(shí)現(xiàn)了在 S中刪除整數(shù)k的目的。若S

14、中 無整數(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á)式 設(shè)操作符棧 掃描，遇操作數(shù)， 掃描完畢。（1）w 為 級高于棧頂操作符（1） 8 3 5 （ 2）8 3 5 + 5 6 2 （ 3）8 3 5 + 5 6 2 / - （ 4）8 3 5 + 5 6 2 / - * 轉(zhuǎn)為后綴表達(dá)式exp2的規(guī)則如下：初始為空棧力后壓入優(yōu)先級最低的操作符#寫入exp： 2；e

15、xp1s，直接 工 般操是操作符（記為#。對中綴表達(dá) 分如下情況處理，式從左向右 直至表達(dá)式 exp1般操作符（一，J則入棧；否則J棧頂運(yùn)算符退棧到比較處理，直至w入棧。（2）w為左括號（），w入棧。（3）w為右括號（），操作符棧退棧并進(jìn)入w優(yōu)先戔頂操作符比較優(yōu)先級，exp2，w再與新棧頂操作符作上述exp2，直到碰到左括號為止，左括號退 棧（不能進(jìn)入exp2），右括號也丟掉，達(dá)到 exp2中消除括號的目的。（4）w為#表示中綴表達(dá)式 exp1結(jié)束，操作符棧退棧到exp2，直至碰到#退棧，整個(gè)操作結(jié)束。這里，再介紹一種簡單方法。中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式有二步：首先，將中綴表達(dá) 式中所有的子表達(dá)

16、式按計(jì)算規(guī)則用嵌套括號括起來；接著，順序?qū)⒚繉ㄌ栔械倪\(yùn)算符移到 相應(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í)行完上面第三步后為：835 + 5 6 2 / - * -?？捎妙愃品椒▽⒅芯Y表達(dá)式轉(zhuǎn)為前綴表達(dá)式。20、中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式的規(guī)則基本上與上面19題相同，不同之處是對運(yùn)算符*優(yōu)先級的規(guī)定。在算術(shù)運(yùn)算中，先乘除后加減，先括號內(nèi)后括號外， 相同級別的運(yùn)算符按從左到右的規(guī)則運(yùn)算。 而對*運(yùn)算符

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

18、*級別高于棧頂?shù)?，因此*入棧。接著讀 入C，直接到結(jié)果表達(dá)式。現(xiàn)在的結(jié)果（后綴）表達(dá)式是ABC。最后讀入#，表示輸入表達(dá)式，結(jié)果表達(dá)式變?yōu)锳BC*。運(yùn)算符棧中只剩#退棧，運(yùn)算結(jié)束。sum( 0)+221、( 1)sum=21。當(dāng)x為局部變量時(shí)，每次遞歸調(diào)用，都要給局部變量分配存儲(chǔ)單元，故 數(shù)值4，9, 6和2均保留，其遞歸過程示意圖如下：(x=4)(x=9)(x=6)(x=2)(2) sum=8,當(dāng)x為全局變量時(shí)，在程序的整個(gè)執(zhí)行期間，x只占一個(gè)存儲(chǔ)單元，先后讀入的4個(gè)數(shù)(4,9,6,2),僅最后一個(gè)起作用。當(dāng)遞歸調(diào)用結(jié)束，逐層返回時(shí)sum:=sum(n-1)+x表達(dá)式中，x就是2，所以結(jié)果

19、為sum=8。22、設(shè)操作數(shù)棧是 opnd,操作符棧是optr，對算術(shù)表達(dá)式 A-B*C/D-E f F求值，過程如下：步 驟opnd 棧optr棧輸入字符主要操作初始#A-B*C/D-E fF#PUSHQPTR, #)1A#A-B*C/D-E fF#PUSH(OPND,A)2A# -B*C/D-E fF#PUSHQPTR,-)3AB# -B*C/D-E fF#PUSH(OPND,B)4AB# - *C/D-E fF#PUSHQPTR, * )5ABC# - *C/D-E fF#PUSH(OPND,C)6AT(T=B*C)# - /D-E fF#PUSH(OPND,POP(OPND)*POP(

20、OPND)PUSHQPTR, / )7ATD# - /D-E fF#PUSH(OPND,D)8AT(T=T/D)T(T=A-T)# -# -E fF#x=POP(OPND);y=POP(OPND) PUSH(OPND,y/x); x=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,-)9TE# -E fF#PUSH(OPND,E)10TE# - fF#fPUSHQPTR, f)11TEF# - f#FPUSH(OPND)12TETS(S=Ef F)R(R=T-S)#-#X=POP(OPND) Y=POP(OPND) POP(OPTR) PUSHQ

21、PNDf x) 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?-*9D+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 (

22、注：T5= T3+ T4)?+?24、XSXXXSSSXXSXXSXXSSSS25、S1和S2共享內(nèi)存中一片連續(xù)空間（地址 1到m）,可以將S1和S2的棧底設(shè)在兩端，兩棧頂向共享空間的中心延伸，僅當(dāng)兩棧頂指針相鄰（兩棧頂指針值之差的絕對值等于1）時(shí)，判斷為棧滿，當(dāng)一個(gè)棧頂指針為0,另一個(gè)棧頂指針 m+1時(shí)為兩棧均空。26、 設(shè)棧S1和棧S2共享向量V1.m，初始時(shí)，棧 S1的棧頂指針top0=0，棧S2的棧頂 指針 top1=m+1，當(dāng) top0=0 為左棧空，top1=m+1 為右棧空；當(dāng) top0=0 并且 top1=m+1 時(shí)為全?？?。當(dāng)top1-top0=1時(shí)為棧滿。27、 （ 1）每

23、個(gè)棧僅用一個(gè)順序存儲(chǔ)空間時(shí)，操作簡便，但分配存儲(chǔ)空間小了， 容易產(chǎn)生溢出， 分配空間大了，容易造成浪費(fèi)，各棧不能共享空間。（2）多個(gè)棧共享一個(gè)順序存儲(chǔ)空間，充分利用了存儲(chǔ)空間，只有在整個(gè)存儲(chǔ)空間都用完時(shí)才能產(chǎn)生溢出，其缺點(diǎn)是當(dāng)一個(gè)棧滿時(shí)要向左、右棧查詢有無空閑單元。如果有，則要移動(dòng)元素和修改相關(guān)的棧底和棧頂指針。當(dāng)接近棧滿時(shí)，查詢空閑單元、移動(dòng)元素和修改棧底棧頂指針的操作頻繁，計(jì)算復(fù)雜并且耗費(fèi)時(shí)間。（3 ）多個(gè)鏈棧一般不考慮棧的溢出（僅受用戶內(nèi)存空間限制），缺點(diǎn)是棧中元素要以指針相鏈接，比順序存儲(chǔ)多占用了存儲(chǔ)空間。28、設(shè)topi和top2分別為棧1和2的棧頂指針（1）入棧主要語句if （to

24、p2-top1=1） printf（棧滿 n ” ）; exit（0）;case 1:top1+ ； SPACEtop1=x; / 設(shè) x 為入棧元素。case 2:top2- ； SPACEtop2=x;出棧主要語句case 1：if （ top1= -1 ） printf （“棧空 n ”）； exit （0）；top1-； return （ SPACEtop1+1 ）； /返回出棧元素。case 2：if （ top2= N） printf （“?？?n ”）； exit （0）； top2+；return （ SPACEtop2-1 ）； /返回出棧元素。（ 2）棧滿條件： top2-

25、top1=1棧空條件：top1=-1并且top2= N /top仁 -1為左?？?，top2=N為右?？?9、 設(shè)順序存儲(chǔ)隊(duì)列用一維數(shù)組qm表示，其中 m為隊(duì)列中元素個(gè)數(shù)，隊(duì)列中元素在向量 中的下標(biāo)從0到m-1。設(shè)隊(duì)頭指針為front ，隊(duì)尾指針是rear，約定front指向隊(duì)頭元素的 前一位置， rear 指向隊(duì)尾元素。當(dāng) front 等于 -1 時(shí)隊(duì)空， rear 等于 m-1 時(shí)為隊(duì)滿。由于隊(duì) 列的性質(zhì)（“刪除”在隊(duì)頭而“插入”在隊(duì)尾），所以當(dāng)隊(duì)尾指針rear等于m-1時(shí)，若front 不等于 -1 ，則隊(duì)列中仍有空閑單元， 所以隊(duì)列并不是真滿。這時(shí)若再有入隊(duì)操作， 會(huì)造成假“溢出”。其解

26、決辦法有二，一是將隊(duì)列元素向前“平移”（占用 0至 rear-front-1 ）；二是將隊(duì)列看成首尾相連， 即循環(huán)隊(duì)列 （0.m-1 ）。在循環(huán)隊(duì)列下， 仍定義 front=rear 時(shí)為隊(duì)空， 而判斷隊(duì)滿則用兩種辦法，一是用“犧牲一個(gè)單元”，即 rear+1=front （準(zhǔn)確記是（rear+1 ）%m=front，m是隊(duì)列容量）時(shí)為隊(duì)滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記 tag ， tag 等于 0 情況下，若刪除時(shí)導(dǎo)致 front=rear 為隊(duì)空； tag=1 情況下，若因插入導(dǎo)致 front=rear 則為隊(duì)滿。30、見上題 29 的解答。 31 、參見上面 29 題。32、ty

27、pedef struct nodeelemtype elemcqm; /m 為隊(duì)列最大可能的容量。int front ,rear; /front和 rear 分別為隊(duì)頭和隊(duì)尾指針。cqnode;cqnode cq;（1） 初始狀態(tài)cq.front=cq.rear=0;（2）隊(duì)列空cq.front=cq.rear;（3）隊(duì)列滿（cq.rear+1）%m=cq.front;33、 棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。初始時(shí)設(shè)棧s1 和棧 s2 均為空。（1）用棧si和s2模擬一個(gè)隊(duì)列的輸入：設(shè)si和s2容量相等。分以下三種情況討論：若si未滿，則元素入si棧；若si滿，s2空，則將si全部元

28、素退棧，再壓棧入s2,之后元素入 s1 棧；若 s1 滿， s2 不空（已有出隊(duì)列元素） ，則不能入隊(duì)。（ 2）用棧 si 和 s2 模擬隊(duì)列出隊(duì)（刪除） ：若棧 s2 不空，退棧，即是隊(duì)列的出隊(duì)；若 s2 為空且si不空，則將si棧中全部元素退棧，并依次壓入s2中，s2棧頂元素退棧，這就是相當(dāng)于隊(duì)列的出隊(duì)。若棧 si 為空并且 s2 也為空，隊(duì)列空，不能出隊(duì)。（ 3）判隊(duì)空 若棧 si 為空并且 s2 也為空，才是隊(duì)列空。討論： si 和 s2 容量之和是隊(duì)列的最大容量。其操作是， si 棧滿后，全部退棧并壓棧入 s2 （設(shè)si和s2容量相等）。再入棧si直至si滿。這相當(dāng)隊(duì)列元素“入隊(duì)”完

29、畢。出隊(duì)時(shí)， s2退棧完畢后，si棧中元素依次退棧到 s2，s2退棧完畢，相當(dāng)于隊(duì)列中全部元素出隊(duì)。在棧 s2 不空情況下，若要求入隊(duì)操作，只要 si 不滿，就可壓入 si 中。若 si 滿和 s2不空狀態(tài)下要求隊(duì)列的入隊(duì)時(shí)，按出錯(cuò)處理。34、( 1)隊(duì)空 s.front=s.rear ； / 設(shè) s 是 sequeuetp 類型變量(2)隊(duì)滿：(s.rear+1 ) MOD MAXSIZE=s.front / 數(shù)組下標(biāo)為 0. MAXSIZE-1 具體參見本章應(yīng)用題第 29 題35、typedef structelemtp qm;int front,count; /front是隊(duì)首指針， c

30、ount 是隊(duì)列中元素個(gè)數(shù)。cqnode; /定義類型標(biāo)識(shí)符。(1) 判空： int Empty(cqnode cq)/cq是 cqnode 類型的變量if (cq.count=0) return (1) ；else return (0); / 空隊(duì)列 入隊(duì) : int EnQueue(cqnode cq ， elemtp x)if (count=m)printf(“隊(duì)滿 n ”； exit(0); cq.q(cq.front+count)%m=x; /x入隊(duì)count+;出隊(duì) : intifreturn (1);/隊(duì)列中元素個(gè)數(shù)增加 1, 入隊(duì)成功。DelQueue(cqnode cq) (

31、count=0)printf(“隊(duì)空 n ”) ； return (0);printf(“出隊(duì)元素” ，cq.qcq.front);x=cq.qcq.front;cq.front=(cq.front+1)%m; /計(jì)算新的隊(duì)頭指針。return (x)(2)隊(duì)列中能容納的元素的個(gè)數(shù)為m。隊(duì)頭指針front指向隊(duì)頭元素。36、 循環(huán)隊(duì)列中元素個(gè)數(shù)為(REAR-FRONT+N%N其中FRONTS隊(duì)首指針，指向隊(duì)首元素的 前一位置；REAR是隊(duì)尾指針，指向隊(duì)尾元素；N是隊(duì)列最大長度。37、 循環(huán)隊(duì)列解決了用向量表示隊(duì)列所出現(xiàn)的“假溢出” 問題，但同時(shí)又出現(xiàn)了如何判斷隊(duì) 列的滿與空問題。例如：在隊(duì)列長

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

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

34、操作 D2 后，f=r=0 ；r=3 ； / A 3表示三次入隊(duì)操作 f=1 ； /D 1表示一次出隊(duì)操作r=0 ；f=3 ；執(zhí)行操作執(zhí)行操作 執(zhí)行操作 則出錯(cuò)。A后，D2 后，f=5 ;A后，r=1 ；按溢出處理。因?yàn)閳?zhí)行 A后，r=4，這時(shí)隊(duì)滿,若再執(zhí)行 A 操作，41一般說，高級語言的變量名是以字母開頭的字母數(shù)字序列。故本題答案是 AP321,PA321,P3A21,P32A1,P321A 。五、算法設(shè)計(jì)題1、 題目分析 兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時(shí)， 兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向， 迎面增長，s2 棧頂為 maxsize 。 元素。#define maxsiz

35、e #define elemtp typedef structs1 棧頂指針為 -1 ，棧頂指針指向棧頂int兩棧共享順序存儲(chǔ)空間所能達(dá)到的最多元素?cái)?shù)/假設(shè)元素類型為整型elemtp stackmaxsize; /int top2;stk; stk s;(1) 入棧操作： int push( int / 入棧操作。 入棧成功返回/top?？臻g為兩個(gè)棧頂指針/s是如上定義的結(jié)構(gòu)類型變量，為全局變量。i, int x) i 為棧號， 1，否則返回 0。棧號輸入不對” );exit(0); 棧已滿 n ” ); return (0);i=0表示左邊的棧 s1， i=1 表示右邊的棧 s2，x 是入棧

36、元素。if (i1)printf( if (s.top1-s.top0=1) printf( switch (i) case 0: s.stack+s.top0=x;case 1: s.stack-s.top1=x;/push(2) 退棧操作elemtp pop(/returnreturn(1);(1);break ;int i) 退棧算法。 i 代表?xiàng)Ｌ枺?i=0 否則返回 -1 。 if (i1)printf( switch (i)case 0:時(shí)為 s1 棧，棧號輸入錯(cuò)誤i=1n”case 1:時(shí)為 s2 棧。退棧成功返回退棧元素，) ； exit(0);?？?n ”)；return (

37、-1 )；if (s.top0=-1) printf( else return (s.stacks.top0-);if (s.top1=maxsize printf( “?？?n ” ); return (-1); else return (s.stacks.top1+); 算法討論 請注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。兩棧共享空間示意圖算法結(jié)束略， s1 棧是通常意義下的棧，而 s2 棧入棧操作時(shí)，其棧頂指針左移(減1)，退棧時(shí)，棧頂指針右移(加 1)。2、 #define maxsize?？臻g容量void InOutS( int smaxsize)/s是元素為整數(shù)的棧，本算法進(jìn)行

38、入棧和退棧操作。 int top=0; /topfor (i=1; i=n; i+) /nscanf(“ %d”,&x); /if (x!=-1) /為棧頂指針，定義 top=0 時(shí)為棧空。個(gè)整數(shù)序列作處理。 從鍵盤讀入整數(shù)序列。 讀入的整數(shù)不等于 -1 時(shí)入棧。if (top=maxsize-1)printf(“棧滿 n ” );exit(0);else s+top=x; /x入棧。else / 讀入的整數(shù)等于 -1 時(shí)退棧。 if (top=0)printf( “ 棧 空 n ” );exit(0); 是 dn ”，stop-); else printf( “ 出 棧 元 素/ 算法結(jié)束。

39、3、 題目分析 判斷表達(dá)式中括號是否匹配，可通過棧，簡單說是左括號時(shí)進(jìn)棧，右括號時(shí) 退棧。退棧時(shí)， 若棧頂元素是左括號， 則新讀入的右括號與棧頂左括號就可消去。 如此下去，輸入表達(dá)式結(jié)束時(shí)，棧為空則正確，否則括號不匹配。int EXYX（char E， int n）/E 是有 n 字符的字符數(shù)組，存放字符串表達(dá)式，以#結(jié)束。本算法判斷表達(dá)式中圓括號是否匹配。 char s30;/sint top=0;/topstop= #; /int i=0;/while (Ei!= # ) /switch (Ei)是一維數(shù)組，容量足夠大，用作存放括號的棧。 用作棧頂指針。 #先入棧，用于和表達(dá)式結(jié)束符號 #

40、匹配。 字符數(shù)組 E 的工作指針。 逐字符處理字符表達(dá)式的數(shù)組。case ) : if (stop= (top-; i+;break ;else printf( “括號不配對” );exit(0);case#: if (stop= # )printf(“括號配對 n ”); return(1);else printf( “ 括號不配對 n ” ); return(0); /括號不配對defaulti+; /讀入其它字符，不作處理。 case( : s+top=(; i+ ;break ;/ 算法結(jié)束。 算法討論 本題是用棧判斷括號匹配的特例： 只檢查圓括號的配對。 一般情況是檢查花括號（ ，

41、）、方括號（ ， ）和圓括號（ （，）的配對問題。編寫算法中如遇左括號（ ， ，或（）就壓入棧中，如遇右括號（ ， ，或），則與棧頂 元素比較，如是與其配對的括號（左花括號，左方括號或左圓括號） ，則彈出棧頂元素；否 則，就結(jié)論括號不配對。在讀入表達(dá)式結(jié)束符#時(shí)，棧中若應(yīng)只剩 #，表示括號全部配對成功；否則表示括號不匹配。另外，由于本題只是檢查括號是否匹配，故對從表達(dá)式中讀入的不是括號的那些字符， 一律未作處理。再有，假設(shè)棧容量足夠大，因此入棧時(shí)未判斷溢出。4、題目分析逆波蘭表達(dá)式（即后綴表達(dá)式）求值規(guī)則如下：設(shè)立運(yùn)算數(shù)棧OPND對表達(dá)式從左到右掃描（讀入），當(dāng)表達(dá)式中掃描到數(shù)時(shí)，壓入 OPN

42、弱。當(dāng)掃描到運(yùn)算符時(shí)，從 OPND 退出兩個(gè)數(shù)，進(jìn)行相應(yīng)運(yùn)算，結(jié)果再壓入OPND棧。這個(gè)過程一直進(jìn)行到讀出表達(dá)式結(jié)束符$，這時(shí)OPN戯中只有一個(gè)數(shù)，就是結(jié)果。float expr( )/ 從鍵盤輸入逆波蘭表達(dá)式，以 $表示輸入結(jié)束，本算法求逆波蘭式表達(dá)式的值。 float OPND30; / OPND 是操作數(shù)棧。兩棧初始化。 數(shù)字初始化。是字符型變量。init(OPND); / float num=0.0;/scanf (while (x!= switch%c” ,&x);/x$)case0=x= 0&x= num=num+(ord(x)-ord(scale=scale*10; scanf(

43、/elsepush(OPND,num); num=0.0;/scanf( “ %c” ,&x);0&xj）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 的個(gè)數(shù)）都必須大于等于出棧次數(shù)（即 O的個(gè)數(shù)），否則視作非法序列，立即 給出信息，退出算法。整個(gè)序列（即讀到字符數(shù)組中字符

44、串的結(jié)束標(biāo)記0） ，入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序列。6、題目分析 表達(dá)式中的括號有以下三對： （、）、 、，使用棧，當(dāng) 為左括號時(shí)入棧，右括號時(shí)，若棧頂是其對應(yīng)的左括號，則退棧，若不是其對應(yīng)的左括號， 則結(jié)論為括號不配對。當(dāng)表達(dá)式結(jié)束，若棧為空，則結(jié)論表達(dá)式括號配對，否則，結(jié)論表達(dá) 式括號不配對。int Match(LinkedList la)/ 算術(shù)表達(dá)式存儲(chǔ)在以char s; p=la-link; StackInit(s); while (p!=la)switch case case/s/p/(p-ch) ( ) la為頭結(jié)點(diǎn)的單循環(huán)鏈表中，本

45、算法判斷括號是否正確配對為字符棧，容量足夠大為工作指針，指向待處理結(jié)點(diǎn)初始化棧 s循環(huán)到頭結(jié)點(diǎn)為止case:push(s,p-ch); break ;:if (StackEmpty(s)|StackGetTop(s)!= printf( “括號不配對 n ”); return :push(s,p-ch); break ; ( )(0); elsepop(s);break ;casecase : if (StackEmpty(s)|StackGetTop(s)!= 括號不配對 n ” ); return break ;caseprintf( :push(s,p-ch); )(0); elsepo

46、p(s);break ;: if (StackEmpty(s)|StackGetTop(s)!= printf( “括號不配對 n ” 后移指針); return )(0); elsepop(s);break ; p=p-link;/ whileif （StackEmpty（s） printf（ “括號配對 else printf（ “括號不配對 n ”）; return/ 算法 match 結(jié)束n ”); return (1);(0); 算法討論 算法中對非括號的字符未加討論。 遇到右括號時(shí)， 若?？栈驐ｍ斣夭皇瞧?對應(yīng)的左圓（方、花）括號，則結(jié)論括號不配對，退出運(yùn)行。最后，若棧不空，仍結(jié)

47、論括號 不配對。7、題目分析 棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。所以，用兩個(gè)棧s1 和 s2 模擬一個(gè)隊(duì)列時(shí)， s1 作輸入棧，逐個(gè)元素壓棧，以此模擬隊(duì)列元素的入隊(duì)。當(dāng)需要出隊(duì)時(shí)， 將棧 s1 退棧并逐個(gè)壓入棧 s2 中， s1 中最先入棧的元素， 在 s2 中處于棧頂。 s2 退棧，相當(dāng)s2 為空且 s1 也為空，才算是隊(duì)列空。于隊(duì)列的出隊(duì)，實(shí)現(xiàn)了先進(jìn)先出。顯然，只有棧(1) int enqueue(stack s1,elemtp x)/s1 是容量為 n 的棧，棧中元素類型是 elemtp 。本算法將 x 入棧，若入棧成功返回 1， 否則返回 0。 if (top1=n & !Se

48、mpty(s2) /top1 是棧 s1 的棧頂指針，是全局變量。printf( “棧滿” ); return (0); /s1 滿 s2 非空 , 這時(shí) s1 不能再入棧。if (top1=n &Sempty(s2) /若 s2 為空， 先將 s1 退棧 , 元素再壓棧到 s2 。 while (!Sempty(s1) POP(s1,x);PUSH(s2,x);PUSH(s1,x); return (1); /x 入棧，實(shí)現(xiàn)了隊(duì)列元素的入隊(duì)。(2) void dequeue(stack s2,s1)/s2 是輸出棧，本算法將 s2 棧頂元素退棧，實(shí)現(xiàn)隊(duì)列元素的出隊(duì)。if (!Sempty(s2)/P0P(s2,x); printf( else/if (Sempty(si) printf(棧 s2 不空，則直接出隊(duì)?！俺鲫?duì)元素為” ,x); 處理