第三章棧與隊列(編輯修改稿)

　

【文章內容簡介】 icp( ( ), 進棧 + * ( AB 6 C 操作數 + * ( ABC 7 操作符 isp( ( ) icp(), 進棧 + * ( ABC 8 D 操作數 + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退棧 + * ( ABCD– isp(( ) == icp( )), 退棧 + * ABCD 中綴表示轉換為后綴表示過程： A B C D * + E F / ) ( A C 后綴輸出： + top top 空棧 top * （ top top top B 棧的應用：表達式求值 22 步 輸入 類型 動作 棧內容 后綴輸出 0 進棧 1 A 操作數 A 2 + 操作符 isp() icp(+), 進棧 + A 3 B 操作數 + AB 4 * 操作符 isp(+) icp(*), 進棧 + * AB 5 ( 操作符 isp(*) icp( ( ), 進棧 + * ( AB 6 C 操作數 + * ( ABC 7 操作符 isp( ( ) icp(), 進棧 + * ( ABC 8 D 操作數 + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退棧 + * ( ABCD– isp( ( ) == icp( ) ), 退棧 + * ABCD 中綴表示轉換為后綴表示過程： A B C D * + E F / ) ( A B C D 后綴輸出： + * （ top top top 棧的應用：表達式求值 23 步 輸入 類型 動作 棧內容 后綴輸出 10 操作符 isp(*) icp(), 退棧 + ABCD* isp(+) icp(), 退棧 ABCD*+ isp() icp(), 進棧 ABCD*+ 11 E 操作數 ABCD*+E 12 / 操作符 isp() icp(/), 進棧 / ABCD*+E 13 F 操作數 / ABCD*+EF 14 操作符 isp(/) icp(), 退棧 ABCD*+EF/ isp() icp(), 退棧 ABCD*+EF 結束 中綴表示轉換為后綴表示過程： A B C D * + E F / ) ( + top top * top A B C D * + 后綴輸出： 棧的應用：表達式求值 24 步 輸入 類型 動作 棧內容 后綴輸出 10 操作符 isp(*) icp(), 退棧 + ABCD* isp(+) icp(), 退棧 ABCD*+ isp() icp(), 進棧 ABCD*+ 11 E 操作數 ABCD*+E 12 / 操作符 isp() icp(/), 進棧 / ABCD*+E 13 F 操作數 / ABCD*+EF 14 操作符 isp(/) icp(), 退棧 ABCD*+EF/ isp() icp(), 退棧 ABCD*+EF 結束 中綴表示轉換為后綴表示過程： A B C D * + E F / ) ( top top / top A B C D * + E F / 后綴輸出： 作業 ? 程序實現簡單的中綴表達式求值 ? 數字均為一位數，即 09 ? 運算符只有 + * / ( ) 25 棧與遞歸 ? 遞歸的定義 ? 若一個對象部分地包含它自己，或用它自己給自己定義，則稱這個對象是遞歸的；若一個過程直接地或間接地調用自己，則稱這個過程是遞歸的過程。 ? 以下三種情況常常用到遞歸方法。 ? 定義是遞歸的 ? 數據結構是遞歸的 ? 問題的解法是遞歸的 26 棧與遞歸 ? 定義是遞歸的 ? 例如 ，階乘函數 (Factorial) ? 求解 階乘函數的遞歸算法 long Factorial ( long n ) { if (n == 0) return 1。 else return n*Factorial(n1)。 } 27 ????????時當時當 1 ,)!1( 0 ,1!nnnnn棧與遞歸 ? 定義是遞歸的 ? 例如，階乘函數 (Factorial) 28 主程序 main : fact(4) 參數 4 計算 4*fact(3) 返回 24 參數 3 計算 3*fact(2) 返回 6 參數 2 計算 2*fact(1) 返回 2 參數 1 計算 1*fact(0) 返回 1 參數 0 直接定值 = 1 返回 1 參數傳遞 結果返回 遞歸調用 回歸求值 棧與遞歸 ? 數據結構是遞歸的 ? 例如，單鏈表結構 ? 搜索單鏈表中值等于 x的結點 LinkNode*Search(LinkNode *f, Type x) { if(f == null) return null。 else if(fdata == x) return f。 else Search(flink, x)。 } 29 a1 first a2 a3 an null ??? struct LinkNode { Type data。 LinkNode *link。 }。 棧與遞歸 ? 問題解法是遞歸的 ? 例如，漢諾塔 (Tower of Hanoi) 問題的解法 ?有 3根標號為 A、 B、 C的柱子， A柱上又疊著 64個從小到大排放的盤子。目的是要將 A柱