數(shù)據(jù)結(jié)構(gòu)第06講-棧的應(yīng)用2與遞歸c

1、第3章 棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.2.2 括號(hào)匹配的檢驗(yàn) 3.2.3 行編輯程序 3.2.4 迷宮求解 3.2.5 表達(dá)式求值3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列 通常用“窮舉求解”方法。3.2.4 迷宮求解求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。1 1 11 2 22 2 23 2 13 3 13 4 42 4 12 5 12 6 41 6 31 5 31 4 43$設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通， 則將當(dāng)前

2、位置插入棧頂； 若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置； 否則 求迷宮中一條從入口到出口的路徑的算法： 若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置； / 從路徑中刪去該通道塊 若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)有可通相鄰塊的位置 或出棧至?？眨?while (棧不空)；若?？?，則表明迷宮沒有通路。第3章 棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.2.2 括號(hào)匹配的檢驗(yàn) 3.2.3 行編輯程序 3.2.4

3、迷宮求解 3.2.5 表達(dá)式求值3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列 3.2.5 表達(dá)式求值以表達(dá)式 A*B + CD 為例說明利用棧的求值過程： 操作數(shù)：常數(shù)、變量或常量標(biāo)識(shí)符 運(yùn)算符：* / * + - 界限符： ( ) # 優(yōu)先級(jí)：運(yùn)算符和界限符統(tǒng)稱算符。思想：從左到右掃描表達(dá)式，若當(dāng)前讀入的是操作數(shù)，則進(jìn)操作數(shù)（NS）棧，若讀入的符號(hào)是算符，應(yīng)進(jìn)行判斷：若是“（”，進(jìn)運(yùn)算符棧；若是“）”，當(dāng)運(yùn)算符棧頂是“（”，則彈出棧頂元素，繼續(xù)掃描下一符號(hào)。否則當(dāng)前讀入符號(hào)暫不處理，從操作數(shù)棧彈出兩個(gè)操作數(shù)，從運(yùn)算符棧彈出一個(gè)運(yùn)算符，生成運(yùn)算指令，結(jié)果送入操作數(shù)棧，繼續(xù)處理當(dāng)前讀入符號(hào)。2. 若讀入的

4、運(yùn)算符的優(yōu)先級(jí)大于運(yùn)算符棧頂?shù)膬?yōu)先級(jí)，則進(jìn)運(yùn)算符棧，繼續(xù)掃描下一符號(hào)；否則從操作數(shù)棧頂彈出兩個(gè)操作數(shù)，從運(yùn)算符棧彈出一個(gè)運(yùn)算符，生成運(yùn)算指令，把結(jié)果送入操作數(shù)棧。繼續(xù)處理剛才讀入的符號(hào)。3. 若讀入的是“#”，且算符棧頂?shù)姆?hào)也是“#”時(shí)，則表達(dá)式處理結(jié)束。從操作數(shù)棧彈出表達(dá)式結(jié)果。A*B + C/Dtop2top1初態(tài)#(a)OSNSBA*#(b)NSOST1#(c)T1=A*BNSOSDCT1/+#(d)NSOS(g)NSOST2=C/DT2T1+#(e)NSOST3#(f)T3=T2+T1NSOS算術(shù)表達(dá)式求值的算符優(yōu)先算法。OperandType EvaluateExpressiOn

5、( ) /設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧。OP為運(yùn)算符集合。 InitStack(OPTR)； InitStack(OPND)； Push(OPTR，#)； c=getchar()；while (c !=#| GetTop(OPTR)!=#)if(!In(c,OP) /不是運(yùn)算符則進(jìn)棧 Push(OPND,c); c=getchar( ); elseswitch ( Precede ( GetTop (OPTR)，c)case ： /退棧并將運(yùn)算結(jié)果入棧Pop(OPTR，theta)； Pop(OPND，b)； Pop(OPND，a)； Push(OPND，Operate(a，t

6、heta，b)；break ；/注意這里無c=getchar() /swith/whilereturn GetTop(OPND)； /end of EvaluateExpression 由于棧結(jié)構(gòu)具有的后進(jìn)先出的特性，致使棧成為程序設(shè)計(jì)中的有用工具。在系統(tǒng)軟件設(shè)計(jì)以及應(yīng)用軟件中解決實(shí)際問題都有廣泛的應(yīng)用。 棧的其他應(yīng)用還有：子程序的調(diào)用、處理遞歸調(diào)用、二叉樹的遍歷、圖的深度優(yōu)先搜索法等。第3章 棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用舉例3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列 3.3 棧與遞歸的實(shí)現(xiàn) 當(dāng)求解一個(gè)問題時(shí)，是通過求解與它同樣解法的子問題而得到的，這就是遞歸。 或理解為子程序或函數(shù)反復(fù)的調(diào)用自

7、己，并傳入不同的變量來執(zhí)行的一種程序設(shè)計(jì)技巧。 是程序設(shè)計(jì)及解題的一種有力的、重要的工具，幫助程序設(shè)計(jì)者解決復(fù)雜問題，并精簡(jiǎn)程序結(jié)構(gòu)。例：設(shè)計(jì)一個(gè)乘法器，可以計(jì)算出兩個(gè)數(shù)相乘的乘積。但是此時(shí)計(jì)算機(jī)不能提供乘法運(yùn)算（僅知道任何數(shù)乘 1，其值不變），則唯一可以使用的運(yùn)算方式就是加法運(yùn)算。即： 11 * 3是 11 連加 3 次 (11 * 3) = 11 + （11 * 2） = 11 + （11 + （11 * 1）) = 11 + （11 + 11） = 11 + 22 = 33使用遞歸的一個(gè)重要問題 一個(gè)遞歸的求解問題必然包含有終止遞歸的條件，當(dāng)滿足一定條件時(shí)就終止向下遞歸，從而使問題得以解

8、決。 解決遞歸問題的算法稱遞歸算法，在遞歸算法中需要根據(jù)遞歸條件直接或間接地調(diào)用算法本身，當(dāng)滿足某種條件時(shí)結(jié)束遞歸調(diào)用。當(dāng)然對(duì)于一些簡(jiǎn)單的遞歸問題，很容易把它轉(zhuǎn)換為循環(huán)問題解決，從而使編寫出的算法更為有效。將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。 當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項(xiàng)任務(wù)：保存被調(diào)函數(shù)的計(jì)算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。 從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:此時(shí)的內(nèi)存管理實(shí)行

9、“棧式管理”后調(diào)用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)遞歸工作棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。 遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，例如：例1：采用遞歸算法求解正整數(shù)n的階乘（n!） 用C語言編寫出求解n!的遞歸函數(shù)為： long f（int n） if （n = = 0） return 1; else return n

10、 * f（n 1）; f(n) = 1 (n=0) nf(n-1) (n0)4r13r24r12r33r24r1進(jìn)行f(4)調(diào)用的系統(tǒng)棧的變化狀態(tài)0r41r42r33r24r11r42r33r24r14r13r24r12r33r24r1進(jìn)行f(4)調(diào)用的系統(tǒng)棧的變化狀態(tài)1r42r33r24r1例2：最大公因子問題 數(shù)學(xué)上利用輾轉(zhuǎn)相除法解決。同時(shí)此種方法也稱為歐幾理德定理，其定義為：GCD(M，N) =GCD（N，M % N） （N0）M （N=0）寫出求解最大公因子的遞歸函數(shù)為： long GCD（int M，int N） / 前提條件：MN if （N = = 0） /遞歸結(jié)束條件 retu

11、rn M ； else return GCD（N，M % N）； 假設(shè)有三個(gè)分別命名為X、Y、Z的塔座，在塔座X上插有n個(gè)直徑大小各不相同、依小到大編號(hào)為1、2、n的圓盤。現(xiàn)要求將X軸上的n個(gè)圓盤移到塔座Z上并仍按同樣的順序疊排，圓盤移動(dòng)時(shí)必須遵循下列規(guī)則： 1）每次只能移動(dòng)一個(gè)圓盤； 2）圓盤可以插在X、Y、Z的任一塔座上； 3）任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤上。例3：漢諾（hanoi)塔問題void hanoi (int n, char x, char y, char z)/ 將塔座x上按直徑由小到大且至上而下編號(hào)為1至n/ 的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1

12、 2 if (n=1)3 move(x, 1, z); / 將編號(hào)為的圓盤從x移到z4 else 5 hanoi(n-1, x, z, y); / 將x上編號(hào)為至n-1的 /圓盤移到y(tǒng), z作輔助塔6 move(x, n, z); / 將編號(hào)為n的圓盤從x移到z7 hanoi(n-1, y, x, z); / 將y上編號(hào)為至n-1的 /圓盤移到z, x作輔助塔8 9 遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc主函數(shù)： 執(zhí)行調(diào)用語句hanoi (3,a,b,c) ，入棧。層1： 執(zhí)行1,2,4,5語句，產(chǎn)生向下調(diào)用，進(jìn)層2。遞歸工作棧狀態(tài)(返址,

13、n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b層2 入棧，記錄層1的返回地址6等信息； 執(zhí)行2層的1,2,4,5語句，執(zhí)行到語句再向下調(diào)用，進(jìn)入層3。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b6, 1, a, b, c層3 入棧，記錄層2的返回地址6等信息； 執(zhí)行1,2,3,9語句，過程執(zhí)行完。層 第層調(diào)用結(jié)束，出棧，返回第2層； 從第2層的斷點(diǎn)語句執(zhí)行； 執(zhí)行到語句，又開始向下遞歸調(diào)用到第3層。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a

14、, b, cabc6, 2, a, c, b6, 1, a, b, c層3 入棧,記錄層2的返回地址8等信息； 執(zhí)行語句1,2,3,9,過程執(zhí)行完。 出棧，返回第2層斷點(diǎn)語句8。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b8, 1, c, a, b層 從第3層返回后，從斷點(diǎn)開始執(zhí)行，執(zhí)行語句8,9，過程執(zhí)行完，出棧，返回第1層。層 從第2層返回后，從斷點(diǎn)開始執(zhí)行；執(zhí)行到語句，又開始向下遞歸調(diào)用到層2，入棧，記錄第1層的返回地址8等信息。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc6, 2, a, c, b8, 2, b, a, c層 執(zhí)行到語句，向下遞歸調(diào)用。層 執(zhí)行語句,2,3,9，結(jié)束，返回第2層。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0, 3, a, b, cabc8, 2, b, a, c6, 1, b, c, a層 從斷點(diǎn)語句6開始執(zhí)行，執(zhí)行到語句7，向下遞歸調(diào)用，到層