第3章限定性線性表——棧和隊列(編輯修改稿)
2025-08-16 10:54 本頁面
【文章內(nèi)容簡介】 3+4*5 + */ ** ① 0 1 2 3 ② 置空棧 OVS、 OPTR 進 OVS 讀字符 W 退 OVS頂 、 次頂 ， OPTR頂 將 T(i)=OVS新頂 進 OPTR棧 W是操作符 N 結(jié)束 N Y N Y Y Y W=‘’’ OPTRZ?？? Y W優(yōu)先級 ≤OPTR棧頂優(yōu)先級 N 無括號算術(shù)表達式的 處理過程 如右圖 返回主目錄 2) 算術(shù)表達式處理規(guī)則 (1)規(guī)定優(yōu)先級表； (2) 設(shè)置兩個棧： OVS(運算數(shù)棧 )和 OPTR(運算符棧 )； (3) 自左向右掃描，遇操作符則與 OPTR棧頂優(yōu)先級比較：當前操作符 OPTR棧頂則進 OPTR棧；當前操作符 ≤ OPTR棧頂， OVS棧頂、次頂和OPTR棧頂，退棧形成運算 T（ i）， T（ i）進OVS棧。 返回主目錄 例：實現(xiàn) A/B↑C+D*E的運算過程時棧區(qū)變化情況 返回主目錄 3) 帶括號算術(shù)表達式 實現(xiàn)算符優(yōu)先算法時需要使用兩個工作棧：一個稱作 運算符棧 operator；另一個稱作 操作數(shù)棧 operand。 算法的基本過程如下： operand和運算符棧 operator， 并將表達式起始符 “ ”壓入運算符棧； ， 若是操作數(shù)則直接進入操作數(shù)棧 operand， 若是運算符 ， 則與運算符棧operator的棧頂運算符進行優(yōu)先權(quán)比較 ， 并做如下處理： 返回主目錄 (1) 若棧頂運算符的優(yōu)先級低于剛讀入的運算符 ， 則讓剛讀入的運算符進 operator棧； (2) 若棧頂運算符的優(yōu)先級高于剛讀入的運算符 ， 則將棧頂運算符退棧 ， 送入 θ， 同時將操作數(shù)棧 operand退棧兩次 ， 得到兩個操作數(shù) a、 b， 對 a、 b進行 θ運算后 ， 將運算結(jié)果作為中間結(jié)果推入 operand棧； (3) 若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同 ， 說明左右括號相遇 ， 只需將棧頂運算符 （ 左括號 ）退棧即可 。 當 operator棧的棧頂元素和當前讀入的字符均為 “ ”時 ，說明表達式起始符 “ ”與表達式結(jié)束符 “ ”相遇 ， 整個表達式求值完畢 。 返回主目錄 棧與遞歸的實現(xiàn) 遞歸 :在定義自身的同時又出現(xiàn)了對自身的調(diào)用。 直接遞歸函數(shù) :如果一個函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱直接遞歸函數(shù)。 間接遞歸函數(shù)： 如果一個函數(shù)經(jīng)過一系列的中間調(diào)用語句，通過其它函數(shù)間接調(diào)用自己，則稱間接遞歸函數(shù)。 返回主目錄 1） 遞歸定義的數(shù)學函數(shù) 如二階 Fibonacci數(shù)列： Ackerman函數(shù)： Fib(n)= 0 若 n=0 1 若 n=1 Fib(n1)+Fib(n2) 其它情況 Ack(m,n)= n+1 當 m=0時 Ack(m1,1) 當 m≠0, n=0時 Ack(m1,Ack(m,n1)) 當 m≠0, n≠0時 Ackerman函數(shù)可用一個簡單的 C語言函數(shù)描述 : int ack(int m,int n) { if(m==0) return n+1。 else if (n==0) return ack(m1,1)。 else return ack(m1, ack(m,n1))。 } 我們在后續(xù)章節(jié)將要學習的一些數(shù)據(jù)結(jié)構(gòu)，如廣義表、二叉樹、樹等結(jié)構(gòu)其本身均具有固有的遞歸特性，因此可以自然地采用遞歸法進行處理。 2） 遞歸數(shù)據(jù)結(jié)構(gòu)的處理 3）遞歸求解方法 許多問題的求解過程可以用遞歸分解的方法描述 ，一個典型的例子是著名的漢諾塔問題 （ hanoi） 問題 。 n階 Hanoi塔問題：假設(shè)有三個分別命名為 X,Y和Z的塔座，在塔座 X上插有 n個直徑大小各不相同、從小到大編號為 1， 2,... ， n的圓盤。現(xiàn)要求將塔座X上的 n個圓盤移至塔座 Z上，并仍按同樣順序疊排。 （ 1） 每次只能移動一個圓盤； （ 2） 圓盤可以插在 X,Y和 Z中的任何一個塔座上； （ 3） 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。 圓盤移動時必須遵循下列規(guī)則： 算法思想： 當 n=1時，問題比較簡單，只要將編號為 1的圓盤從座X直接移動到塔座 Z上即可；當 n1時，需利用塔座 Y作輔助塔座，若能設(shè)法將壓在編號為 n的圓盤上的 n1個圓盤從塔座 X(依照上述原則 )移至塔座 Y上，則可先將編號為 n的圓盤從塔座 X 移至塔座 Z上，然后再將塔座 Y上的 n1個圓盤 (依照上述原則 )移至塔座 Z上。而如何將 n1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小于 1，因此可以用同樣方法求解。 求解 n階 Hanoi塔問題的遞歸算法 void hanoi(int n, char x, char y, char z) /* 將塔座 X上從上到下編號為 1至 n， 且按直徑由小到大疊放的 n個圓盤 ， 按規(guī)則搬到塔座 Z上 ， Y用作輔助塔座 。 */ { if(n==1) move(x,1,z)。 /*將編號為 1的圓盤從 x移動 z*/ else { hanoi(n1,x,z,y)。 /* 將 X上編號為 1至 n1的圓盤移到 y,z作輔助塔 */ move(x,n,z)。 /* 將編號為 n的圓盤從 x移到 z */ hanoi(n1, y,x ,z)。 /* 將 y上編號為 1至 n1的圓盤移到 z， x作輔助塔 */ } } hanoi(3, A, B , C) hanoi(2, A, C, B): hanoi(1, A, B, C) move(AC) 1號搬到 C move(AB) 2號搬到 B hanoi(1, C, A, B) move(CB) 1號搬回到 B move(AC) 3號搬到 C hanoi(2,B,A,C): hanoi(1, B, C, A) move(BA)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1