第三章棧與隊列(編輯修改稿)
2024-10-06 21:46 本頁面
【文章內(nèi)容簡介】 icp( ( ), 進(jìn)棧 + * ( AB 6 C 操作數(shù) + * ( ABC 7 操作符 isp( ( ) icp(), 進(jìn)棧 + * ( ABC 8 D 操作數(shù) + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退棧 + * ( ABCD– isp(( ) == icp( )), 退棧 + * ABCD 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( A C 后綴輸出： + top top 空棧 top * （ top top top B 棧的應(yīng)用：表達(dá)式求值 22 步 輸入 類型 動作 棧內(nèi)容 后綴輸出 0 進(jìn)棧 1 A 操作數(shù) A 2 + 操作符 isp() icp(+), 進(jìn)棧 + A 3 B 操作數(shù) + AB 4 * 操作符 isp(+) icp(*), 進(jìn)棧 + * AB 5 ( 操作符 isp(*) icp( ( ), 進(jìn)棧 + * ( AB 6 C 操作數(shù) + * ( ABC 7 操作符 isp( ( ) icp(), 進(jìn)棧 + * ( ABC 8 D 操作數(shù) + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退棧 + * ( ABCD– isp( ( ) == icp( ) ), 退棧 + * ABCD 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( A B C D 后綴輸出： + * （ top top top 棧的應(yīng)用：表達(dá)式求值 23 步 輸入 類型 動作 棧內(nèi)容 后綴輸出 10 操作符 isp(*) icp(), 退棧 + ABCD* isp(+) icp(), 退棧 ABCD*+ isp() icp(), 進(jìn)棧 ABCD*+ 11 E 操作數(shù) ABCD*+E 12 / 操作符 isp() icp(/), 進(jìn)棧 / ABCD*+E 13 F 操作數(shù) / ABCD*+EF 14 操作符 isp(/) icp(), 退棧 ABCD*+EF/ isp() icp(), 退棧 ABCD*+EF 結(jié)束 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( + top top * top A B C D * + 后綴輸出： 棧的應(yīng)用：表達(dá)式求值 24 步 輸入 類型 動作 棧內(nèi)容 后綴輸出 10 操作符 isp(*) icp(), 退棧 + ABCD* isp(+) icp(), 退棧 ABCD*+ isp() icp(), 進(jìn)棧 ABCD*+ 11 E 操作數(shù) ABCD*+E 12 / 操作符 isp() icp(/), 進(jìn)棧 / ABCD*+E 13 F 操作數(shù) / ABCD*+EF 14 操作符 isp(/) icp(), 退棧 ABCD*+EF/ isp() icp(), 退棧 ABCD*+EF 結(jié)束 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( top top / top A B C D * + E F / 后綴輸出： 作業(yè) ? 程序?qū)崿F(xiàn)簡單的中綴表達(dá)式求值 ? 數(shù)字均為一位數(shù)，即 09 ? 運(yùn)算符只有 + * / ( ) 25 棧與遞歸 ? 遞歸的定義 ? 若一個對象部分地包含它自己，或用它自己給自己定義，則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己，則稱這個過程是遞歸的過程。 ? 以下三種情況常常用到遞歸方法。 ? 定義是遞歸的 ? 數(shù)據(jù)結(jié)構(gòu)是遞歸的 ? 問題的解法是遞歸的 26 棧與遞歸 ? 定義是遞歸的 ? 例如 ，階乘函數(shù) (Factorial) ? 求解 階乘函數(shù)的遞歸算法 long Factorial ( long n ) { if (n == 0) return 1。 else return n*Factorial(n1)。 } 27 ????????時當(dāng)時當(dāng) 1 ,)!1( 0 ,1!nnnnn棧與遞歸 ? 定義是遞歸的 ? 例如，階乘函數(shù) (Factorial) 28 主程序 main : fact(4) 參數(shù) 4 計算 4*fact(3) 返回 24 參數(shù) 3 計算 3*fact(2) 返回 6 參數(shù) 2 計算 2*fact(1) 返回 2 參數(shù) 1 計算 1*fact(0) 返回 1 參數(shù) 0 直接定值 = 1 返回 1 參數(shù)傳遞 結(jié)果返回 遞歸調(diào)用 回歸求值 棧與遞歸 ? 數(shù)據(jù)結(jié)構(gòu)是遞歸的 ? 例如，單鏈表結(jié)構(gòu) ? 搜索單鏈表中值等于 x的結(jié)點(diǎn) 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根標(biāo)號為 A、 B、 C的柱子， A柱上又疊著 64個從小到大排放的盤子。目的是要將 A柱
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1