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

1、3.3 3.3 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號匹配的檢驗括號匹配的檢驗例三、例三、 行編輯程序問題行編輯程序問題例四、例四、 迷宮求解迷宮求解例五、例五、 表達式求值表達式求值例七、例七、 實現(xiàn)遞歸實現(xiàn)遞歸例六、例六、 二元運算符的表達式的標(biāo)識二元運算符的表達式的標(biāo)識 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ，其運算過程如下：其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算

2、順序計算順序輸出順序輸出順序void conversion ( ) InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion例二、例二、 括號匹配的檢驗括號匹配的檢驗 假設(shè)在表達式中假設(shè)在表達式中 （）或（）或（ ） 等為正確的格式，等為正確的格式， （ ）或（）或（ ）或）或 （）（）) ) 均為不正確的格式。均為不正確的格式。則則 檢驗括號是否匹配檢驗括號是否匹配的方法可用的方法可用“期待的急迫程度

3、期待的急迫程度”這個概念來描述。這個概念來描述。分析可能出現(xiàn)的分析可能出現(xiàn)的不匹配不匹配的情況的情況: 到來的右括弧到來的右括弧并非是所并非是所“期待期待”的；的；例如：考慮下列括號序列：例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 到來的是到來的是“不速之客不速之客”； 直到結(jié)束，也沒有到來直到結(jié)束，也沒有到來所所“期待期待”的括的括弧。弧。算法的設(shè)計思想：算法的設(shè)計思想：1 1)凡出現(xiàn)左括弧左括弧，則進棧進棧；2 2)凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若棧空?？?，則表明該“右括弧右括弧”多余多余， 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧

4、出?！?” ， 否則表明不匹配不匹配。3 3)表達式表達式檢驗結(jié)束結(jié)束時， 若?？諚？?，則表明表達式中匹配正確匹配正確， 否則表明“左括弧左括弧”有余有余。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch of expi case “(”:“(”:Push(S,expi); i+; break; case”)”: if(NOT StackEmpty(S)&GetTop(S)=“(“ Pop(S,e); i+; else state = 0; break; if (StackEmpty

5、(S)&state) return OK; .例三、行編輯程序問題例三、行編輯程序問題 一個簡單的行編輯程序的功能是：接收用戶從一個簡單的行編輯程序的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。 由于用戶在終端上進行輸入時，不能保證不出由于用戶在終端上進行輸入時，不能保證不出差錯，因此，若在編輯程序中，差錯，因此，若在編輯程序中，“每接收一個字符每接收一個字符即存入用戶數(shù)據(jù)區(qū)即存入用戶數(shù)據(jù)區(qū)”的做法顯然不是最恰當(dāng)?shù)?。的做法顯然不是最恰當(dāng)?shù)摹?設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入

6、用戶數(shù)據(jù)區(qū)，并假的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)設(shè)“#”為退格符，為退格符，“”為退行符。為退行符。合理的作法是：合理的作法是：假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實際有效的是下列兩行：則實際有效的是下列兩行： while (*s) putchar(*s+); 為此，可設(shè)這個輸入緩沖區(qū)為一個棧結(jié)構(gòu)，為此，可設(shè)這個輸入緩沖區(qū)為一個棧結(jié)構(gòu)，每當(dāng)從終端接收了一個字符之后先作如下判別：每當(dāng)從終端接收了一個字符之后先作如下判別： 如果它既不是退格符也不是退行符，則將如果它既不是退格符也不是退

7、行符，則將 該字符壓入棧頂；該字符壓入棧頂； 如是一個退格符，則從棧頂刪去一個字符；如是一個退格符，則從棧頂刪去一個字符； 如果他是一個退行符，則將字符棧清為空棧。如果他是一個退行符，則將字符棧清為空棧?？捎孟率鏊惴▉砻枋觯嚎捎孟率鏊惴▉砻枋觯?while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break; / 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); / 從終端接收下一個字符從終端接收下一個字

8、符 ClearStack(S); / 重置重置S為空棧為空棧 if (ch != EOF) ch = getchar();while (ch != EOF) / EOF為全文結(jié)束符為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；void LineEdit( ) InitStack(S); /構(gòu)造空棧構(gòu)造空棧 ch=getchar( ); /從終端接收第一個字符從終端接收第一個字符 while (ch!=EOF) /EOFEOF是全文結(jié)束符是全文結(jié)束符 while (ch!=EOF & ch!=n) switch (ch) case #: Pop

9、(S,c); break; case :ClearStack(S);break; /重置重置S S為空棧為空棧 default: Push(S,ch); break; ch=getchar( ); /從終端接收下一個字符從終端接收下一個字符 將從棧底至棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；將從棧底至棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)； ClearStack (S); /重置重置S S為空棧為空棧 if (ch!=EOF) ch=getchar( ); DestroyStack(S); /棧棧S S被銷毀被銷毀 /LineEdit例四、例四、 迷宮求解迷宮求解通常用的是“窮舉求解窮舉求解”的方

10、法# # # # # # # # # # # # $ $ $ # # # # $ $ $ # # # $ $ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 求迷宮路徑算法的基本思想基本思想是： 若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼，則納入路徑，繼續(xù)前進續(xù)前進; 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方，則后退，換方向繼續(xù)探索向繼續(xù)探索; 若四周若四周“均無通路均無通路”，則將當(dāng)前位置從，則將當(dāng)前位置從路徑中刪除出去。路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置； do 若

11、當(dāng)前位置可通若當(dāng)前位置可通， 則則將當(dāng)前位置插入棧頂插入棧頂； 若若該位置是出口位置，則則算法結(jié)束； 否則切換否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； 否則否則 while (棧不空）棧不空）；求迷宮中一條從入口到出口的路徑的算法：求迷宮中一條從入口到出口的路徑的算法： 若若棧不空且棧頂位置尚有其他方向未被探索棧不空且棧頂位置尚有其他方向未被探索，則則設(shè)定新的當(dāng)前位置為: 沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊棧頂位置的下一相鄰塊；若若棧不空但棧頂位置的四周均不可通棧不空但棧頂位置的四周均不可通，則則刪去棧頂位置；/ 從路徑中刪去該通道塊 若若棧不空，則則重新測試新的棧頂位置， 直至

12、直至找到一個可通的相鄰塊或出棧至?？?； 若若?？諚？?，則則表明迷宮沒有通路。 表達式求值是程序設(shè)計語言編譯中的一個基本表達式求值是程序設(shè)計語言編譯中的一個基本問題，它的實現(xiàn)是棧應(yīng)用的又一個典型例子。這里介問題，它的實現(xiàn)是棧應(yīng)用的又一個典型例子。這里介紹一種簡單直觀，廣為使用的算法，叫紹一種簡單直觀，廣為使用的算法，叫“算符優(yōu)先算符優(yōu)先法法”。它是根據(jù)運算優(yōu)先關(guān)系的規(guī)定來實現(xiàn)對表達式。它是根據(jù)運算優(yōu)先關(guān)系的規(guī)定來實現(xiàn)對表達式的編譯或解釋執(zhí)行的。的編譯或解釋執(zhí)行的。例如：要對算術(shù)表達式例如：要對算術(shù)表達式 4+2*3-10/5 求值。求值。算術(shù)四則運算規(guī)則：算術(shù)四則運算規(guī)則： 先乘除，后加減；先乘

13、除，后加減； 同級運算從左算到右；同級運算從左算到右； 先括號內(nèi)，后括號外。先括號內(nèi)，后括號外。 “算符優(yōu)先法算符優(yōu)先法”就是根據(jù)這個運算優(yōu)先關(guān)系的規(guī)就是根據(jù)這個運算優(yōu)先關(guān)系的規(guī)定來實現(xiàn)對表達式的編譯或解釋執(zhí)行的。定來實現(xiàn)對表達式的編譯或解釋執(zhí)行的。例五、例五、 表達式求值表達式求值表達式表達式操作數(shù)操作數(shù)(operand)：常數(shù)、變量或常量標(biāo)識符：常數(shù)、變量或常量標(biāo)識符運算符運算符(operator)：算術(shù)運算符、關(guān)系運算符、：算術(shù)運算符、關(guān)系運算符、 邏輯運算符等邏輯運算符等界限符界限符(delimiter)：（ 、）、表達式結(jié)束符等、）、表達式結(jié)束符等 為了敘述的簡潔，我們僅討論為了敘述

14、的簡潔，我們僅討論簡單算術(shù)表達式簡單算術(shù)表達式的求值問題的求值問題，這種表達式僅包含加、減、乘、除、，這種表達式僅包含加、減、乘、除、括號等四種運算。不難將它推廣到更一般的表達式括號等四種運算。不難將它推廣到更一般的表達式上。上。 我們把運算符和界限符統(tǒng)稱為算符，它們構(gòu)成的我們把運算符和界限符統(tǒng)稱為算符，它們構(gòu)成的集合命名為集合命名為op，在運算的每一步中，任意兩個相繼出，在運算的每一步中，任意兩個相繼出現(xiàn)的運算符現(xiàn)的運算符1和和2之間的優(yōu)先關(guān)系至多是下面三種關(guān)之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一：系之一： 1 2 : 1的優(yōu)先權(quán)高于的優(yōu)先權(quán)高于2；下表定義了算符之間的這種優(yōu)先關(guān)系。下表定義了

15、算符之間的這種優(yōu)先關(guān)系。算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表 + - * / （ ） # =+-*/()# 為實現(xiàn)算符優(yōu)先算法可使用兩個工作棧：為實現(xiàn)算符優(yōu)先算法可使用兩個工作棧： OPTROPTR棧：用以寄存運算符；棧：用以寄存運算符； OPNDOPND棧：用以寄存操作數(shù)或運算結(jié)果；棧：用以寄存操作數(shù)或運算結(jié)果；算法基本思想：算法基本思想： 首先置操作數(shù)棧為空棧，表達式起始符首先置操作數(shù)棧為空棧，表達式起始符“#”#”為運算符棧的棧底元素；為運算符棧的棧底元素； 依次讀入表達式中的每個字符，若是操作依次讀入表達式中的每個字符，若是操作數(shù)，則進數(shù)，則進OPNDOPND棧；若是運算符，則和棧；若是運算符

16、，則和OPTROPTR棧的棧頂棧的棧頂運算符比較優(yōu)先數(shù)后作相應(yīng)操作，直至整個表達式運算符比較優(yōu)先數(shù)后作相應(yīng)操作，直至整個表達式求值完畢（即求值完畢（即OPTROPTR棧的棧頂元素和當(dāng)前讀入的字符棧的棧頂元素和當(dāng)前讀入的字符均為均為“#”)#”)。OperandType EvaluateExpression( ) InitStack(OPTR); Push (OPTR,#); InitStack(OPND); c=getchar( ); while (c!=# | GetTop(OPTR)!=#) if (!In(c,OP) Push (OPND,c);c=getchar( ); /操作數(shù)進棧操

17、作數(shù)進棧 else switch (Precede(GetTop(OPTR),c) case : theta =Pop(OPTR); b= Pop(OPND); a=Pop(OPND); Push(OPND,Operate(a,theta,b); break; /退棧并將運算結(jié)果入棧退棧并將運算結(jié)果入棧 /switch /while return GetTop(OPND); / EvaluateExpression 表達式表達式 := (操作數(shù)操作數(shù)) + (運算符運算符) + (操作數(shù)操作數(shù)) 操作數(shù)操作數(shù) := 簡單變量簡單變量 | 表達式表達式 簡單變量簡單變量 :=標(biāo)識符標(biāo)識符 | 無

18、符號整數(shù)無符號整數(shù)例六、例六、二元運算符的表達式的標(biāo)識二元運算符的表達式的標(biāo)識 表達式的三種標(biāo)識方法：表達式的三種標(biāo)識方法：設(shè)設(shè) Exp = S1 + OP + S2則稱則稱 OP + S1 + S2 為前綴表示法前綴表示法 S1 + OP + S2 為中綴表示法中綴表示法 S1 + S2 + OP 為后綴表示法后綴表示法 例如: Exp = a b + (c d / e) f前綴式: + a b c / d e f中綴式: a b + c d / e f后綴式: a b c d e / f + 結(jié)論結(jié)論:1）操作數(shù)之間的相對次序不變）操作數(shù)之間的相對次序不變;2）運算符的相對次序不同）運算符

19、的相對次序不同;3）中綴式丟失了括弧信息， 致使運算的次序不確定;4)前綴式的運算規(guī)則前綴式的運算規(guī)則為:連續(xù)出現(xiàn)的兩個操作數(shù)和在它們連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構(gòu)成一之前且緊靠它們的運算符構(gòu)成一個最小表達式個最小表達式; 5)后綴式的運算規(guī)則后綴式的運算規(guī)則為: 運算符在式中出現(xiàn)的順序恰為運算符在式中出現(xiàn)的順序恰為 表達式的運算順序表達式的運算順序; 每個運算符和在它之前出現(xiàn)每個運算符和在它之前出現(xiàn) 且且 緊靠它的兩個操作數(shù)構(gòu)成一個最小緊靠它的兩個操作數(shù)構(gòu)成一個最小 表達式。表達式。如何從后綴式求值？如何從后綴式求值？先找運算符，先找運算符， 再找操作數(shù)再找操作數(shù)例如：

20、例如： a b c d e / f +a bd/ec-d/e(c-d/e) fl如何從原表達式求得后綴式？如何從原表達式求得后綴式？ 每個運算符的運算次序要由它之后的每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先數(shù)一個運算符來定，在后綴式中，優(yōu)先數(shù)高的運算符領(lǐng)先于優(yōu)先數(shù)低的運算符。高的運算符領(lǐng)先于優(yōu)先數(shù)低的運算符。分析分析 “原表達式原表達式” 和和 “后綴式后綴式”中的運算符中的運算符:原表達式原表達式: a + b c d / e f后綴式后綴式: a b c + d e / f 從原表達式求得后綴式的規(guī)律為：從原表達式求得后綴式的規(guī)律為：1) 設(shè)立設(shè)立操作數(shù)棧；操作數(shù)棧

21、；2) 設(shè)表達式的結(jié)束符為設(shè)表達式的結(jié)束符為“#”， 預(yù)設(shè)預(yù)設(shè)運算符棧的運算符棧的棧底為棧底為“#”；3) 若若當(dāng)前字符當(dāng)前字符是操作數(shù)是操作數(shù)， 則則直接發(fā)送給后綴式直接發(fā)送給后綴式。4) 若若當(dāng)前當(dāng)前運算符的運算符的優(yōu)先數(shù)高優(yōu)先數(shù)高于棧頂運算于棧頂運算符，則符，則進棧進棧；5) 否則，退出棧頂運算符發(fā)送給后綴式否則，退出棧頂運算符發(fā)送給后綴式； 6) “(” 對它之前后的運算符對它之前后的運算符起隔離作起隔離作用用，“)”可視為自相應(yīng)左括弧開始的可視為自相應(yīng)左括弧開始的表達式的結(jié)束符。表達式的結(jié)束符。從原表達式求得后綴式的規(guī)律為從原表達式求得后綴式的規(guī)律為：例七、實現(xiàn)遞歸例七、實現(xiàn)遞歸 將

22、所有的實在參數(shù)、返回地址等將所有的實在參數(shù)、返回地址等信息信息傳傳遞給被調(diào)用函數(shù)遞給被調(diào)用函數(shù)保存保存； 為被調(diào)用函數(shù)的局部變量為被調(diào)用函數(shù)的局部變量分配存儲區(qū)分配存儲區(qū)； 將將控制轉(zhuǎn)移控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。到被調(diào)用函數(shù)的入口。 當(dāng)在一個函數(shù)的運行期間當(dāng)在一個函數(shù)的運行期間調(diào)用另一個函調(diào)用另一個函數(shù)數(shù)時，在時，在運行該被調(diào)用函數(shù)之前運行該被調(diào)用函數(shù)之前，需先完成三項任務(wù)：需先完成三項任務(wù)： 保存保存被調(diào)函數(shù)的被調(diào)函數(shù)的計算結(jié)果計算結(jié)果； 釋放釋放被調(diào)函數(shù)的被調(diào)函數(shù)的數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)； 依照被調(diào)函數(shù)保存的返回地址將依照被調(diào)函數(shù)保存的返回地址將控控制轉(zhuǎn)移制轉(zhuǎn)移到調(diào)用函數(shù)。到調(diào)用函數(shù)。從被調(diào)用函數(shù)從被調(diào)用函數(shù)返回返回調(diào)用函數(shù)調(diào)用函數(shù)之前之前，應(yīng)該