數(shù)據(jù)結(jié)構(gòu)第3-1章

1、 實(shí)驗(yàn)安排實(shí)驗(yàn)安排 時(shí)間：時(shí)間：8-158-15周周 單周：周四單周：周四 5 5、6 6節(jié)節(jié) 雙周：周二雙周：周二 5 5、6 6節(jié)節(jié) 地點(diǎn)：地點(diǎn)：1 1、2 2班班 軟軟419419 3 3、4 4班班 軟軟420420 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 棧和隊(duì)列是兩種常用的線性結(jié)構(gòu)棧和隊(duì)列是兩種常用的線性結(jié)構(gòu) 【學(xué)習(xí)目標(biāo)】【學(xué)習(xí)目標(biāo)】 1. 1. 掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在 相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。 2. 2. 熟練掌握棧類型的兩種實(shí)現(xiàn)方法。熟練掌握棧類型的兩種實(shí)現(xiàn)方法。 3. 3. 熟練掌

2、握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。 【重點(diǎn)和難點(diǎn)】【重點(diǎn)和難點(diǎn)】 棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù) 結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)， 以便能在應(yīng)用問(wèn)題中正確使用。以便能在應(yīng)用問(wèn)題中正確使用。 線性表線性表 棧棧 隊(duì)列隊(duì)列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in

3、棧和隊(duì)列是限定插入和刪除只能在表?xiàng)：完?duì)列是限定插入和刪除只能在表 的的“端點(diǎn)端點(diǎn)”進(jìn)行的進(jìn)行的線性表線性表限定性數(shù)據(jù)限定性數(shù)據(jù) 結(jié)構(gòu)。結(jié)構(gòu)。 3.1 3.1 棧棧 3.2 3.2 隊(duì)列隊(duì)列 3.1 棧 3.1 3.1 棧棧 定義：定義：限定僅在限定僅在表尾表尾進(jìn)行插入或刪除操作的線性表進(jìn)行插入或刪除操作的線性表。 表尾表尾( (允許插入和刪除允許插入和刪除) )棧頂，表頭棧頂，表頭棧底棧底 特點(diǎn)：特點(diǎn)：后進(jìn)先出（后進(jìn)先出（LIFO） an a1 a2 . 棧底棧底 棧頂棧頂 . 出棧出棧 進(jìn)棧進(jìn)棧 棧棧s=(a1,a2,an) 3.1.1 3.1.1 棧的定義棧的定義 3.1 3.1 棧棧 棧

4、的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型 ADT Stack 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 基本操作基本操作： ADT Stack 建棧、入棧、出棧、建棧、入棧、出棧、 讀棧頂元素、判斷讀棧頂元素、判斷 棧滿或?？盏?。棧滿或?？盏?。 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 順序棧順序棧：( (棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)) )利用一組利用一組地址連續(xù)地址連續(xù)的的 存儲(chǔ)單元依次存放自

5、棧底到棧頂?shù)臄?shù)據(jù)元素。存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。 /- 棧的順序存儲(chǔ)表示棧的順序存儲(chǔ)表示 - typedef struct SElemType *base; /棧底指針即棧的基址棧底指針即棧的基址 SElemType *top; /指向棧頂元素的上一個(gè)位置指向棧頂元素的上一個(gè)位置 int stacksize; /棧的容量棧的容量( (已分配的存儲(chǔ)空間已分配的存儲(chǔ)空間) ) SqStack; 棧頂元素的說(shuō)明棧頂元素的說(shuō)明 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 如：如：SqStack s; s為一個(gè)順序棧的變量。為一個(gè)順序棧的變量。s的存儲(chǔ)空間為

6、：的存儲(chǔ)空間為： s.base s.top s. stacksize s.base0 s.basestacksize-1 該空間的申請(qǐng)由該空間的申請(qǐng)由 初始化初始化操作實(shí)現(xiàn)操作實(shí)現(xiàn) 3.1 3.1 棧棧 ?？粘鰲?，則?？粘鰲＃瑒t下溢下溢(underflow) 棧滿入棧，則棧滿入棧，則上溢上溢(overflow) 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) base 1 2 3 4 5 0 棧空?？?top 棧頂指針棧頂指針top初值指向初值指向 棧底：棧底：top=base 1 2 3 4 5 0 進(jìn)棧進(jìn)棧 baseA top B topC topD topE topF top 出棧

7、出棧 1 2 3 4 5 0A B C D E F base top top top top top top top top top top top top 棧滿棧滿:top- base = stacksize ?？諚？?top top top top top toptop *S.top+ = ee = *- S.top 3.1 3.1 棧棧 思考思考：如果進(jìn)棧順序?yàn)椋喝绻M(jìn)棧順序?yàn)?，2，3，4。不限制出棧。不限制出棧 的時(shí)間，則下面哪一種出棧順序不可能。的時(shí)間，則下面哪一種出棧順序不可能。 (1) 1, 2, 3, 4 (2) 2, 1, 4, 3 (3) 3, 1, 2, 4 (4) 4

8、, 3, 2, 1 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 棧的基本操作在棧的基本操作在順序棧順序棧中的實(shí)現(xiàn)中的實(shí)現(xiàn) InitStack( if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top = S.base; S.stacksize = STACK_INI_SIZE ; return OK; / InitStack 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 入棧入棧 算法描述：算法描述： Status Push (SqSt

9、ack return OK; /Push/Push e e插入后棧頂指針加插入后棧頂指針加1 1 if (S.top - S.base = S.stacksize) /棧滿棧滿, ,追加存儲(chǔ)空間追加存儲(chǔ)空間 S.base = (SElemType *)relloc(S.base , (STACK_INI_SIZE+STACKINCREMENT)* sizeof (SElemType); If(!S.base) exit(OVERFLOWOVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT；

10、3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 出棧出棧 算法描述：算法描述： Status Pop (SqStack /?？諚？?e = *-S.top; return OK; /Pop 棧頂指針減棧頂指針減1 1，取所指元素，取所指元素 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 取棧頂元素取棧頂元素 算法描述：算法描述： Status GetTop(SqStack S，SElemType /否則，返回否則，返回ERROR If(S.top=S.base) return Error; e= * (S.top-1) Return O

11、K; /GetPop 3.1 3.1 棧棧 鏈棧鏈棧(補(bǔ)充補(bǔ)充): 用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示的棧就是用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示的棧就是鏈棧鏈棧 (1)(1)鏈棧的構(gòu)造方式鏈棧的構(gòu)造方式: : 以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除 nextdata an an-1 a1 a2 棧頂元素棧頂元素 棧底元素棧底元素 注意注意 指針指針 方向方向 通常鏈棧不設(shè)通常鏈棧不設(shè)頭結(jié)頭結(jié) 點(diǎn)點(diǎn)，因?yàn)闂ｍ?，因?yàn)闂ｍ? (表表 頭）操作頻繁頭）操作頻繁 基本操作基本操作：p-data=e; p-next=top; top=p; 3.1 3.1 棧棧 鏈棧鏈棧(補(bǔ)充補(bǔ)充): v入棧：入棧： . 棧

12、底棧底 top e p top v出棧：出棧： 棧底棧底 . top q top 基本操作：基本操作：e=top-data; q=top; top=top-next; free(q); return(e); 3.1 3.1 棧棧 3.1.3 3.1.3 棧的應(yīng)用舉例棧的應(yīng)用舉例 例一：數(shù)制轉(zhuǎn)換例一：數(shù)制轉(zhuǎn)換 例二：括號(hào)匹配的檢驗(yàn)例二：括號(hào)匹配的檢驗(yàn) 例三：行編輯程序例三：行編輯程序 例四：迷宮求解例四：迷宮求解 例五：表達(dá)式求值例五：表達(dá)式求值 例六：漢諾塔問(wèn)題例六：漢諾塔問(wèn)題* 設(shè)計(jì)思路：設(shè)計(jì)思路： 用棧暫存低位值用棧暫存低位值 3.1 3.1 棧棧 例一：數(shù)制轉(zhuǎn)換例一：數(shù)制轉(zhuǎn)換 算法基于原

13、理：算法基于原理： N = (N div d)d + N mod d 求商求商 求余求余進(jìn)制進(jìn)制 例如：例如：（1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下，其運(yùn)算過(guò)程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計(jì)算順序計(jì)算順序 輸出順序輸出順序 3.1 3.1 棧棧 算法描述：算法描述： void conversion () /對(duì)于輸入的十進(jìn)制非負(fù)整數(shù)，輸出對(duì)應(yīng)的八進(jìn)制數(shù)對(duì)于輸入的十進(jìn)制非負(fù)整數(shù)，輸出對(duì)應(yīng)的八進(jìn)制數(shù) InitStack(S); /構(gòu)造空棧構(gòu)造空棧S scanf (%d,N); while (N) Pus

14、h(S, N % 8); /入棧入棧 N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( “%d”, e ); /出棧出棧 / conversion 例一：數(shù)制轉(zhuǎn)換例一：數(shù)制轉(zhuǎn)換 3.1 3.1 棧棧 例二：括號(hào)匹配的檢驗(yàn)例二：括號(hào)匹配的檢驗(yàn) 假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中 （）或（）或（ ） 等為等為正確正確的格式，的格式， （ ）或（）或（ ）或）或 ( ) 均為均為不正確不正確的格式。的格式。 則則 檢驗(yàn)括號(hào)是否匹配檢驗(yàn)括號(hào)是否匹配的方法可用的方法可用“期待的期待的 急迫程度急迫程度”這個(gè)概念來(lái)描述。這個(gè)概念來(lái)描述。 “期待的急迫程度期待的急

15、迫程度” :” :即后出現(xiàn)的即后出現(xiàn)的“左括弧左括弧”， 它等待與其匹配的它等待與其匹配的“右括弧右括弧”出現(xiàn)的出現(xiàn)的“急迫急迫” 心情要比先出現(xiàn)的左括弧高。換句話說(shuō)，對(duì)心情要比先出現(xiàn)的左括弧高。換句話說(shuō)，對(duì) “左括弧左括弧”來(lái)說(shuō)，后出現(xiàn)的比先出現(xiàn)的來(lái)說(shuō)，后出現(xiàn)的比先出現(xiàn)的“優(yōu)先優(yōu)先” 等待檢驗(yàn)，對(duì)等待檢驗(yàn)，對(duì)“右括弧右括弧”來(lái)說(shuō)，每個(gè)出現(xiàn)的右來(lái)說(shuō)，每個(gè)出現(xiàn)的右 括弧要去找在它之前括弧要去找在它之前“最后最后”出現(xiàn)的那個(gè)左括出現(xiàn)的那個(gè)左括 弧去匹配?；∪テヅ洹?顯然，必須將先后出現(xiàn)的左括弧依次保存，為顯然，必須將先后出現(xiàn)的左括弧依次保存，為 了了反映這個(gè)優(yōu)先程度反映這個(gè)優(yōu)先程度，保存左括弧的結(jié)

16、構(gòu)用棧，保存左括弧的結(jié)構(gòu)用棧 最合適。這樣對(duì)出現(xiàn)的右括弧來(lái)說(shuō)，只要最合適。這樣對(duì)出現(xiàn)的右括弧來(lái)說(shuō)，只要“棧棧 頂元素頂元素”相匹配即可。如果在棧頂?shù)哪莻€(gè)左括相匹配即可。如果在棧頂?shù)哪莻€(gè)左括 弧正好和它匹配，就可將它從棧頂刪除?；≌煤退ヅ?，就可將它從棧頂刪除。 3.1 3.1 棧棧 3.1 3.1 棧棧 例二：括號(hào)匹配的檢驗(yàn)例二：括號(hào)匹配的檢驗(yàn) 例如：考慮下列括號(hào)序列：例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8 分析：分析：當(dāng)接受了第一個(gè)括號(hào)當(dāng)接受了第一個(gè)括號(hào)“”“”后，期待與其匹配的第八后，期待與其匹配的第八 個(gè)個(gè) 出現(xiàn)，而等來(lái)的確是第二個(gè)出現(xiàn)，而等來(lái)的確是第二個(gè)“（

17、”，此時(shí)，第二個(gè)括號(hào)期待，此時(shí)，第二個(gè)括號(hào)期待 匹匹 配的程度高于第一個(gè)，第一個(gè)配的程度高于第一個(gè)，第一個(gè)“”“”只能放一邊；而迫切等只能放一邊；而迫切等 待待 與第二個(gè)括號(hào)相匹配的、第七個(gè)括號(hào)與第二個(gè)括號(hào)相匹配的、第七個(gè)括號(hào)“）”的出現(xiàn)，可等來(lái)的出現(xiàn)，可等來(lái) 的的 是第三個(gè)括是號(hào)是第三個(gè)括是號(hào)“”“”，因而，其期待匹配程度高于第二個(gè)，因而，其期待匹配程度高于第二個(gè) ， 第二個(gè)括號(hào)讓位于第三個(gè)；直到第四個(gè)括號(hào)第二個(gè)括號(hào)讓位于第三個(gè)；直到第四個(gè)括號(hào)“”“”出現(xiàn)，第出現(xiàn)，第 三三 個(gè)括號(hào)期待得到滿足，消解之后，第二個(gè)括號(hào)期待匹配成個(gè)括號(hào)期待得到滿足，消解之后，第二個(gè)括號(hào)期待匹配成 了最急迫的任務(wù)了

18、最急迫的任務(wù) 設(shè)計(jì)思路：設(shè)計(jì)思路： 用棧暫存左括號(hào)用棧暫存左括號(hào) 3.1 3.1 棧棧 例二：括號(hào)匹配的檢驗(yàn)例二：括號(hào)匹配的檢驗(yàn) 算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想： 1. 1. 出現(xiàn)的凡是出現(xiàn)的凡是“左括號(hào)左括號(hào)”，則，則進(jìn)棧進(jìn)棧； 2. 2. 出現(xiàn)的是出現(xiàn)的是“右括號(hào)右括號(hào)”， 首先檢查棧是否空？首先檢查棧是否空？ 若若棧空棧空，則表明該，則表明該“右括右括號(hào)號(hào)”多余多余 否則否則和棧頂元素和棧頂元素比較？比較？ 若若相匹配相匹配，則棧頂則棧頂“左括號(hào)出棧左括號(hào)出?！?否則表明否則表明不匹配不匹配 3.3.表達(dá)式表達(dá)式檢驗(yàn)結(jié)束檢驗(yàn)結(jié)束時(shí)，時(shí)， 若若?？諚？?，則表明表達(dá)式中，則表明表達(dá)式中匹配正

19、確匹配正確 否則表明否則表明“左括號(hào)左括號(hào)”有余有余 3.1 3.1 棧棧 例二：括號(hào)匹配的檢驗(yàn)例二：括號(hào)匹配的檢驗(yàn) 算法描述算法描述 （作（作 業(yè)）業(yè)） 3.1 3.1 棧棧 例三：行編輯程序例三：行編輯程序 “每接受一個(gè)字符即存入存儲(chǔ)器每接受一個(gè)字符即存入存儲(chǔ)器” ” ? ? 并不恰當(dāng)！并不恰當(dāng)！ 在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)，在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)， 并在發(fā)現(xiàn)有誤時(shí)可以并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正及時(shí)更正。 合理的作法是：合理的作法是： 設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一一 行行字符，然后逐行存入用戶數(shù)據(jù)區(qū)字符，

20、然后逐行存入用戶數(shù)據(jù)區(qū); 并假設(shè)并假設(shè)“#”為為 退格符，退格符，“”為退行符為退行符。 3.1 3.1 棧棧 例三：行編輯程序例三：行編輯程序 假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+); 則實(shí)際有效的是下列兩行：則實(shí)際有效的是下列兩行： while (*s) putchar(*s+); 3.1 3.1 棧棧 例三：行編輯程序例三：行編輯程序 while (ch != EOF) /EOF為全文結(jié)束符為全文結(jié)束符 while (ch != n) /判斷是否換行判斷是否換行 switch (ch) ca

21、se # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); / 從終端接收下一個(gè)字符從終端接收下一個(gè)字符 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)； ClearStack(S); / 重置重置S為空棧為空棧 if (ch != EOF) ch = getchar(); 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解(窮舉求解窮舉求解) # # #$# # #$# # $ $# #

22、# # # # # # # # # # 出口出口 入口入口 1-東 2-南 3-西 4-北 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 1 1 1 1 2 2 2 2 2 3 2 1 3 3 1 3 4 4 2 4 1 2 5 1 2 6 4 1 6 3 1 5 3 1 4 4 3 $ $ $ 藍(lán)-坐標(biāo)，紅-方向 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解 算法的基本思想是：算法的基本思想是： 若當(dāng)前位置若當(dāng)

23、前位置“可通可通”，則納入路徑，繼，則納入路徑，繼 續(xù)前進(jìn)續(xù)前進(jìn); 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方，則后退，換方 向繼續(xù)探索向繼續(xù)探索; 若四周若四周“均無(wú)通路均無(wú)通路”，則將當(dāng)前位置從，則將當(dāng)前位置從 路徑中刪除出去。路徑中刪除出去。 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解 設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若若當(dāng)前位置可通當(dāng)前位置可通， 則則將當(dāng)前位置將當(dāng)前位置插入棧頂插入棧頂； 若若該位置是出口位置，該位置是出口位置，則則算法結(jié)束；算法結(jié)束； 否則切換否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；當(dāng)前位置的東鄰方塊為新的當(dāng)前位

24、置； 否則否則 while (棧不空）棧不空）； 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解 若若棧不空且棧頂位置尚有其他方向未被探索，棧不空且棧頂位置尚有其他方向未被探索， 則則設(shè)定新的當(dāng)前位置為設(shè)定新的當(dāng)前位置為: 沿順時(shí)針?lè)较蛐D(zhuǎn)沿順時(shí)針?lè)较蛐D(zhuǎn) 找到的找到的棧頂位置的下一相鄰塊；棧頂位置的下一相鄰塊； 若若棧不空但棧頂位置的四周均不可通，棧不空但棧頂位置的四周均不可通， 則則刪去棧頂位置；刪去棧頂位置；/ / 從路徑中刪去該通道塊從路徑中刪去該通道塊 若若棧不空，棧不空，則則重新測(cè)試新的棧頂位置，重新測(cè)試新的棧頂位置， 直至直至找到一個(gè)可通的相鄰塊或出棧至?？?；找到一個(gè)可通的相

25、鄰塊或出棧至?？眨?若若棧空?？?，則表明迷宮沒(méi)有通路。，則表明迷宮沒(méi)有通路。 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 表達(dá)式求值表達(dá)式求值是棧應(yīng)用的典型例子是棧應(yīng)用的典型例子 (1)(1)表達(dá)式求值必須滿足算術(shù)四則運(yùn)算規(guī)則：表達(dá)式求值必須滿足算術(shù)四則運(yùn)算規(guī)則： a. a. 先乘除，后加減先乘除，后加減 b. b. 從左算到右從左算到右 c. c. 先括號(hào)內(nèi)，后括號(hào)外先括號(hào)內(nèi)，后括號(hào)外 (2)(2)任何一個(gè)表達(dá)式由：任何一個(gè)表達(dá)式由：操作數(shù)、運(yùn)算符、界限符操作數(shù)、運(yùn)算符、界限符 組成組成 (3)(3)運(yùn)算符和界限符統(tǒng)稱運(yùn)算符和界限符統(tǒng)稱算符算符。 根據(jù)上面的運(yùn)算規(guī)則，在運(yùn)算的每一

26、步中，任意兩個(gè)根據(jù)上面的運(yùn)算規(guī)則，在運(yùn)算的每一步中，任意兩個(gè) 相繼出現(xiàn)的算符相繼出現(xiàn)的算符 1 1和和 2 2之間的優(yōu)先關(guān)系至多是下面之間的優(yōu)先關(guān)系至多是下面三三 種關(guān)系種關(guān)系之一：之一： 1 1 1 2 : 2 : 1 1的優(yōu)先權(quán)高于的優(yōu)先權(quán)高于 2 2 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值（下表給出了算符之間的優(yōu)先級(jí)）（下表給出了算符之間的優(yōu)先級(jí)） v 由上表可看出，右括號(hào)由上表可看出，右括號(hào) ) 和井號(hào)和井號(hào) # 作為作為 2時(shí)時(shí)級(jí)別最級(jí)別最 低；低； v 由由c 規(guī)則規(guī)則得出：得出： * ，/， + ，-為為 1時(shí)的優(yōu)先權(quán)低于時(shí)的優(yōu)先權(quán)低于，高，高 于于 v 由由b

27、規(guī)則規(guī)則得出：得出： = 表明括號(hào)內(nèi)的運(yùn)算已完成；表明括號(hào)內(nèi)的運(yùn)算已完成； = 表明表達(dá)式求值完畢。表明表達(dá)式求值完畢。 + 2 1 - - * * / / ( ( ) ) # # + - + - * * / ( ) # / ( ) # = = = 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 為了實(shí)現(xiàn)為了實(shí)現(xiàn)算符優(yōu)先算法算符優(yōu)先算法，可以設(shè)定兩個(gè)工作棧：，可以設(shè)定兩個(gè)工作棧： 存放操作數(shù)或運(yùn)算結(jié)果，存放操作數(shù)或運(yùn)算結(jié)果， OPTR存放運(yùn)算符號(hào)。存放運(yùn)算符號(hào)。 算法思想：算法思想： 1 1）首先置）首先置為空棧，表達(dá)式的起始符為空棧，表達(dá)式的起始符# #為運(yùn)算符棧為運(yùn)算符棧 OPTR

28、的棧底元素；的棧底元素； 2 2）依次讀入表達(dá)式中的每個(gè)字符，）依次讀入表達(dá)式中的每個(gè)字符， 若運(yùn)算符是若運(yùn)算符是#或棧頂是或棧頂是#，結(jié)束計(jì)算，返回，結(jié)束計(jì)算，返回OPNDOPND棧頂值。棧頂值。 ifif（是操作數(shù)）是操作數(shù)） 則則PUSH（ ，操作數(shù)操作數(shù)）； ifif（是運(yùn)算符）是運(yùn)算符） 則與則與OPTR棧頂元素棧頂元素 1進(jìn)行比較，按優(yōu)先級(jí)進(jìn)行比較，按優(yōu)先級(jí)( (規(guī)定規(guī)定 詳見詳見P53P53表表3.13.1）進(jìn)行操作；）進(jìn)行操作； ifif棧頂元素棧頂元素 運(yùn)算符運(yùn)算符，則退棧、按棧頂計(jì)算，將結(jié)果壓入，則退棧、按棧頂計(jì)算，將結(jié)果壓入棧棧。 判判C C是否是否 操作符操作符 3.1

29、 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 算法描述：算法描述： Status EvaluateExpression( OperandType InitStack(OPTR);Push(OPTR ,#); =getchar(); while(c!=#) c=getchar(); else switch(precede(GetTop(OPTR) , c) case : Pop(OPTR ,theta); Pop(OPND,b);a=Pop(); thetabreak; /switch /while result=GetTop(OPND); /EvaluateExpression 運(yùn)算符與棧

30、頂比運(yùn)算符與棧頂比 較并查較并查3.13.1表表 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 例：對(duì)表達(dá)式例：對(duì)表達(dá)式3*（7 2 ）求值）求值 OPTROPNDINPUTOPERATE 3*(7-2)#Push(opnd,3) # *(7-2)#3#Push(optr,*) #,*3(7-2)#Push(optr,() #,*,(37-2)#Push(opnd,7) #,*,(3,7-2)#Push(optr,-) #,*,(,3,72)#Push(opnd,2) #,*,(,3,7,2)#Operate(7-2) #,*,(3,5)#Pop(optr) #,*3,5#Opera

31、te(3*5) #15#GetTop(opnd) 練習(xí)：練習(xí)： 3+4-(6-9/2)+7*5# (參照例參照例3-1) 3.1 3.1 棧棧 例六：漢諾塔問(wèn)題例六：漢諾塔問(wèn)題* 漢諾漢諾（ Hanoi）塔塔 傳說(shuō)在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫傳說(shuō)在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫Brahma的寺廟里，有三的寺廟里，有三 個(gè)柱子，其中一柱上有個(gè)柱子，其中一柱上有6464個(gè)盤子從小到大依次疊放，僧個(gè)盤子從小到大依次疊放，僧 侶的工作是將這侶的工作是將這6464個(gè)盤子從一根柱子移到另一個(gè)柱子上。個(gè)盤子從一根柱子移到另一個(gè)柱子上。 移動(dòng)時(shí)的規(guī)則：移動(dòng)時(shí)的規(guī)則： v 每次只能移動(dòng)一個(gè)盤子；每次只能移動(dòng)一個(gè)盤子； v 只能小盤

32、子在大盤子上面；只能小盤子在大盤子上面； v 可以使用任一柱子?？梢允褂萌我恢印?當(dāng)工作做完之后，就標(biāo)志著世界末日到來(lái)。當(dāng)工作做完之后，就標(biāo)志著世界末日到來(lái)。 x y zx y z n 1 n 3.1 3.1 棧棧 例六：漢諾塔問(wèn)題例六：漢諾塔問(wèn)題* 分析：分析： 設(shè)三根柱子分別為設(shè)三根柱子分別為 x, y, z , x, y, z , 盤子在盤子在 x x 柱上，要移柱上，要移 到到z z 柱上。柱上。 1 1、當(dāng)、當(dāng) n=1 n=1 時(shí)，盤子直接從時(shí)，盤子直接從 x x 柱移到柱移到 z z 柱上；柱上； 2 2、當(dāng)、當(dāng) n1 n1 時(shí)時(shí), , 則則: : 設(shè)法將前設(shè)法將前 n 1 n

33、1 個(gè)盤子個(gè)盤子 從從 x x 移到移到 y y 柱上（借助柱上（借助z z），）， 則則 盤子盤子 n n 就能從就能從 x x 移到移到 z z 柱上；柱上； 再設(shè)法把再設(shè)法把n 1 n 1 個(gè)盤子個(gè)盤子 從從 y y 移到移到 z z 柱上柱上( (這又是一這又是一 個(gè)與原來(lái)相同的問(wèn)題，只是規(guī)模少了）個(gè)與原來(lái)相同的問(wèn)題，只是規(guī)模少了） 。 x y zx y z n 1 n 遞歸函數(shù)遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過(guò)一系列：一個(gè)直接調(diào)用自己或通過(guò)一系列 的調(diào)用語(yǔ)句間接調(diào)用自己的函數(shù)的調(diào)用語(yǔ)句間接調(diào)用自己的函數(shù) 3.1 3.1 棧棧 例六：漢諾塔問(wèn)題例六：漢諾塔問(wèn)題* 算法描述：算法描述： Void Hanoi ( int n, char x, char y, char z ) 1 /將將n n個(gè)編號(hào)從上到下為個(gè)編號(hào)從上到下為1 1n n的盤子從的盤子從x x柱，借助柱，借助y y柱移到柱移到z z柱柱 2 if ( n = = 1 ) 3 move ( x , 1 , z ) ; /將編號(hào)為將編號(hào)為1 1的盤子從的盤子從x x柱移到柱移到