【文章內(nèi)容簡介】 3 4 5 6 7 1 0 0 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 1 2 2 3 4 1 4 33 2 3 1 紫色 2 黃色 3 紅色 4 綠色 已知 n件物品各自的體積，背包容積為 T，要求從 n件中找出若干物物品，其體積之各恰好等于背包容積，看是否有解。 解決思路： 順序棧 S用來存放放入背包內(nèi)的物品序號（最多有 n個元素）； 參數(shù) T動態(tài)計算背包還可裝入的重量； 依次裝入試驗，不滿足時從后往前回溯。 初始容量 T=10， 6件物品重分別為 (4,7,3,5,4,2) 4 7 3 5 4 2 W S T=10 top 4 7 3 5 4 2 1 W S T=6 top 4 7 3 5 4 2 1 3 W S T=3 top 4 7 3 5 4 2 1 W S T=6 top 4 7 3 5 4 2 1 4 W S T=1 top 4 7 3 5 4 2 1 W S T=6 top 4 7 3 5 4 2 1 5 W S T=2 top 4 7 3 5 4 2 1 5 6 W S T=6 top ? 一個表達式由 操作數(shù) (亦稱運算對象 )、操作符 (亦稱運算符 ) 和 分界符 組成 。 ? 算術(shù)表達式有三種表示： ? 中綴 (infix)表示 操作數(shù) 操作符 操作數(shù) ， 如 A+B； ? 前綴 (prefix)表示 操作符 操作數(shù) 操作數(shù) ， 如 +AB； ? 后綴 (postfix)表示 操作數(shù) 操作數(shù) 操作符 ， 如 AB+； 表達式的中綴表示 a + b * ( c d ) e ^ f / g ? 表達式中相鄰兩個操作符的計算次序為： ? 優(yōu)先級高的先計算 ； ? 優(yōu)先級相同的自左向右計算 ； ? 當使用括號時從最內(nèi)層括號開始計算 。 rst1 rst2 rst3 rst4 rst5 rst6 應用后綴表示計算表達式的值 ? 從左向右順序地掃描表達式 ， 并用一個棧 暫存掃描到的 操作數(shù) 或 計算結(jié)果 。 ? 在后綴表達式的計算順序中已 隱含了加括號的優(yōu)先次序 ， 括號在后綴表達式中不出現(xiàn) 。 ? 計算例 a b c d * + e f ^ g / rst1 rst2 rst3 rst4 rst5 rst6 通過后綴表示計算表達式值的過程 ? 順序掃描表達式的每一項，根據(jù)它的類型做如下相應操作： ? 若該項是 操作數(shù) ，則將其 壓棧 ； ? 若該項是 操作符 op，則 連續(xù)從棧中退出兩個操作數(shù) Y和 X， 形成運算指令 XopY，并將計算結(jié)果重新 壓棧 。 ? 當表達式的所有項都掃描并處理完后，棧頂存放的就是最后的計算結(jié)果。 后綴表達式的處理過程 操作順序 后綴表達式 ABCD/－ E + T1 ← C/D ABT1－ E + T2 ← B – T1 AT 2E + T3 ← T 2 E AT 3+ T4 ← A + T 3 T4 中綴表達式： A + ( B – C / D) E 后綴表達式： ABCD/－ E + 本節(jié)結(jié)束 第十三講 數(shù)據(jù)結(jié)構(gòu) 棧的應用 (3)與遞歸函數(shù) 主講：劉立嘉 利用棧將中綴表示轉(zhuǎn)換為后綴表示 ? 使用?？蓪⒈磉_式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示 。 ? 為了實現(xiàn)這種轉(zhuǎn)換 ， 需要考慮各操作符的優(yōu)先級 。 棧的應用舉例 中綴表達式轉(zhuǎn)換為后綴表達式 ＋ － ／ ( ) ＋ － ／ ( = ) = 當前運算符 棧頂運算符 中綴表達式轉(zhuǎn)換為后綴表達式的處理規(guī)則 如為操作數(shù)，直接輸出到隊列； 如當前運算符高于棧頂運算符，入棧； 如當前運算符低于棧頂運算符，棧頂運算符退棧， 并輸出到隊列，當前運算符再與棧頂運算符比較； 如當前運算符等于棧頂運算符，且棧頂運算符為 “ （ ” ，當前運算符為 “ ） ” ，則棧頂運算符退棧， 繼續(xù)讀下一符號； 如當前運算符等于棧頂運算符，且棧頂運算符為 “ ” ，當前運算符也為 “ ” ，則棧頂運算符退棧， 繼續(xù)讀下一符號； 各個算術(shù)操作符的優(yōu)先級 ? isp叫做棧內(nèi) (in stack priority)優(yōu)先數(shù) ? icp叫做棧外 (in ing priority)優(yōu)先數(shù) 。 ? 操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在 括號配對 或 棧底的 “ ?！碧柵c輸入流最后的 “ ?！碧柵鋵?時 。 操作符 ch 。 ( ^ * , / , % + , )i s p ( 棧內(nèi) ) 0 1 7 5 3 8i c p ( 棧外 ) 0 8 6 4 2 1中綴表達式轉(zhuǎn)換為后綴表達式的算法 ? 操作符棧初始化 ， 將結(jié)束符 ‘ 。?進棧 。然后讀入中綴表達式字符流的首字符 ch。 ? 重復執(zhí)行以下步驟 ， 直到 ch = ?。?， 同時棧頂?shù)牟僮鞣彩?‘ 。?， 停止循環(huán) 。 ? 若 ch是 操作數(shù) 直接輸出 ， 讀入下一個字符 ch。 ? 若 ch是 操作符 ， 判斷 ch的優(yōu)先級 icp和 位于棧頂 的 操作符 op的優(yōu)先級 isp： ? 若 icp (ch) isp (op)， 令 ch進棧 ， 讀入下一個字符 ch。 ? 若 icp (ch) isp (op)， 退棧并輸出 。 ? 若 icp (ch) == isp (op)， 退棧但不輸出 ， 若退出的是 “ (”號讀入下一個字符 ch。 ? 算法結(jié)束，輸出序列即為所需的后綴表達式。 步驟 中綴表達式 STACK 輸出 1 A＋ (B－ C／ D) E 2 ＋ (B－ C／ D) E A 3 (B－ C／ D) E ＋ A 4 B－ C／ D) E ＋ ( A 5 － C／ D) E ＋ ( AB 6 C／ D) E =(－ AB 7 ／ D) E ＋ (－ ABC 8 D) E ＋ (－ / ABC 9 ) E ＋ (－ / ABCD 步驟 中綴表達式 STACK 輸出 10 E ＋ (－ ABCD/ 11 E ＋ ( ABCD/ － 12 E ＋ ABCD/ － 13 E ＋ ABCD/ － 14 ＋ ABCD/ － E 15 = ABCD/ － E 16 ABCD/ － E ＋ 中綴算術(shù)表達式求值 ? 使用兩個棧 ， 操作符棧 OPTR (operator)，操作數(shù)棧 OPND(operand)， ? 對中綴表達式求值的一般規(guī)則： (1) 建立并初始化 OPTR棧和 OPND棧 ，然后 在 OPTR棧中壓入一個 “ ?！?(2) 從頭掃描中綴表達式 ， 取一字符送入 ch。 (3) 當 ch != “。” 時 , 執(zhí)行以下工作 , 否則結(jié)束算法 。 此時在 OPND棧 的棧頂?shù)玫竭\算結(jié)果 。 ① 若 ch是 操作數(shù) ， 進 OPND棧 ， 從中綴表達式取下一字符送入 ch； ② 若 ch是 操作符 ， 比較 icp(ch)的優(yōu)先級和 isp(OPTR)的優(yōu)先級： ? 若 icp(ch) isp(OPTR)， 則 ch進 OPTR棧 ， 從中綴表達式取下一字符送入 ch； ? 若 icp(ch) isp(OPTR)， 則從 OPND棧退出 a2和 a1， 從 OPTR棧 退出 θ, 形成運算指令 (a1)θ(a2)， 結(jié)果進 OPND棧 ； ? 若 icp(ch) == isp(OPTR) 且 ch == “)”，則從 OPTR棧 退出棧頂?shù)?“ (”， 對消括號 ， 然后從中綴表達式取下一字符送入ch； 以表達式 ＃ A*B + C/D＃ 為例說明利用棧的求值過程。 操作數(shù)： A B C D 算符（運算符和界限符）： * + / 優(yōu)先級： * +* + /+ / + = 表達式為 A*B + C/D top2 top1 初態(tài) (a) OS NS B A * (b) NS OS T1 (c) T1=A*B NS OS D C T1 / + (d) NS OS (g) NS OS T2=C/D T2 T1 + (e) NS OS T3 (f) T3=T2+T1 NS OS NS運算數(shù)棧， OS運算符棧 InitStack(OPTR)。Push(OPTR,??)。 //OPTR運算符棧， OPND運算數(shù)棧 InitStack(OPND)。 c=getchar()。 While(c!=??||GetTop(OPTR)!=??){ If(!In(c,OP)){Push(OPND,c)。c=getchar()。}不是運算符則進棧 Else Switch(Precede(GetTop(OPTR),c)){ Case ??: //棧頂元素優(yōu)先級低 Push(OPTR,c)。c=getchar()。Break。 Case ?=?: //脫括號接收下一字符 Pop(OPTR,x)。c=getchar()。break。 OperandType EvaluateExpression( ){ Case ??: //退棧并將運算結(jié)果入棧 Pop(OPTR,theta)。 Pop(OPND,b)。Pop(OPND,a)。 Push(OPND,Operate(a,theta,b))。 Break。 } } return GetTop(OPND)。 } OPTR運算符棧， OPND運算數(shù)棧 ? 將所有的 實在參數(shù)、返回地址 等信息傳遞給被調(diào)用函數(shù)保存； ? 為被調(diào)用函數(shù)的 局部變量 分配存儲區(qū)； ? 將 控制 轉(zhuǎn)移到被調(diào)用函數(shù)的入口。 當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三項任務： 棧與函數(shù)調(diào)用機制 ? 保存 被調(diào)函數(shù)的 計算結(jié)果 ； ? 釋放 被調(diào)函數(shù)的 數(shù)據(jù)區(qū) ； ? 依照被調(diào)函數(shù)保存的返回地址將 控制轉(zhuǎn)移 到 調(diào)用函數(shù) 。 從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應該完成下列三項任務： 多個函數(shù)嵌套調(diào)用的規(guī)則是： 此時的內(nèi)存管理實行“棧式管理” 后調(diào)用先返回 ！ 例如： void main( ){ … a( )。 … }//main Main的數(shù)據(jù)區(qū) 函數(shù) a的數(shù)據(jù)區(qū) 函數(shù) b的數(shù)據(jù)區(qū) void a( ){ … b( )。 … }// a void b( ){ … }// b r 主程序 s r r r s 子程序1 r s t 子程序2 r s t 子程序3 函數(shù)的嵌套 ?遞歸函數(shù)： 一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)。 ?遞歸算法： 描述遞歸定義的函數(shù)或求解遞歸問題的過程稱為遞歸算法。 遞歸算法的實質(zhì)，是將較復雜的處理歸結(jié)為較簡單的處理，直到最簡單的處理。 棧結(jié)構(gòu)與遞歸函數(shù) 遞歸算法優(yōu)缺點： ?優(yōu)點：結(jié)構(gòu)清晰，易讀，在高級語言中，由系統(tǒng)管理堆棧，用戶編程調(diào)試方便。 ?缺點：運行效率低，執(zhí)行過程中反復入棧、出棧，時間、空間開銷大，算法優(yōu)化困難。 遞歸工作棧： 整個遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。 遞歸函數(shù)運行過程類似于多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)