【文章內(nèi)容簡介】 ){ switch(ch){ case‘‘： Pop (S， c)； break； //僅當棧非空時退棧 case‘@‘： ClearStack(S)； break； //重置 S為空棧 default： Push (S， ch)； break； //有效字符進棧，未考慮棧滿情形 } ch=getchar( )； //從終端接收下一個字符 } ***** //將從棧底到棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū) ClearStack(S)； //重置 S為空棧 if (ch!=EOF) ch = getchar( )； } DestoryStack ( S )； } // LineEdit 算法 表達式求值問題 (用后綴表達式 ) ? Exp = S1 + OP + S2 ? 稱 OP + S1 + S2 為表達式的前綴表示法（簡稱前綴式） ? 稱 S1 + OP + S2 為表達式的中綴表示法（簡稱中綴式） ? 稱 S1 + S2 + OP 為表達式的后綴表示法（簡稱后綴式） ? 前綴、中綴、后綴表達式： ? 操作數(shù)次序一樣 ? 運算符次序發(fā)生變化 ? 中綴無意義，丟掉括號后運算次序可能發(fā)生改變 ? 前綴式運算規(guī)則：連續(xù)出現(xiàn)的 2個操作數(shù)和出現(xiàn)在他們之前的運算符構(gòu)成一個最小表達式 ? 后綴式運算符出現(xiàn)的次序恰好為表達式的運算次序，每個運算符和出現(xiàn)它之前的兩個操作數(shù)構(gòu)成一個最小表達式 ? 綜上，使用后綴式求值，是操作數(shù)進棧，遇到操作符，彈出 2個操作數(shù)，并將運算結(jié)果進棧。 ? 對后綴式從左向右“掃描”，遇見操作數(shù)則暫時保存，遇見運算符即可進行運算；此時參加運算的兩個操作數(shù)應該是在它之前剛剛碰到的兩個操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。 ? 如何從原表達式轉(zhuǎn)換為后綴式： ? 設立運算符棧 ? 設表達式結(jié)束符“ ”，并用來預設運算符棧底 ? 若當前字符是操作數(shù)則發(fā)送給后綴表達式 ? 若當前操作符優(yōu)先級高于棧頂操作符，則進棧；否則彈出棧頂送給表達式，并將該運算符進棧 ? “（”視為對出現(xiàn)在它之后的操作符起隔離作用，進棧，將左右括弧之內(nèi)的表達式看做一個單獨的表達式，“）”出現(xiàn)，將“（”之上的符號出棧。 ? 原表達式： a*b+(cd/e)*f ? 后綴表達式： abc*de/f*+ ? Void transform(char suffix[],char exp[]) ? {InitStack(S)。 Push(S, ‘’)； ? p=exp。 ch=*p。 ? while(!StackEmpty(S)) ? {if(!IN(ch,OP)) Pass(Suffix,ch)。 ? else {switch(ch) ? case 39。(39。 :Push(S, ch)。break。 ? case 39。)39。 :{Pop(S, c)。 ? while (c!=39。(39。) ? {Pass(Suffix, c)。 Pop(S, c)。} ? break。} ? defalt:{while(!Gettop(S,c) amp。amp。 preced(c, ch)) ? {Pass(Suffi,c)。pop(S,c)。} ? if(ch!=39。39。) Push(S, ch)。break。} ? }//switch ? }//while ? }//transform 棧與遞歸函數(shù)的實現(xiàn) ? 一、遞歸函數(shù) ? 二、函數(shù)調(diào)用的實現(xiàn)過程 ? 三、遞歸調(diào)用的實現(xiàn)過程 一、遞歸函數(shù) ? “ 從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山，山里有座廟，廟里有個老和尚，老和尚對小和尚說故事：從前有座山 …… ” 。 ? 在講述故事的過程中，又嵌套講述了故事本身 ? C語言程序由函數(shù)構(gòu)成。 ? 函數(shù)與函數(shù)之間是平行的，獨立的。 ? 不允許在一個函數(shù)內(nèi)部 嵌套定義 另一個函數(shù)；但允許在調(diào)用一個函數(shù)的過程中，又 調(diào)用 另一個函數(shù)。 ? 遞歸調(diào)用： 在調(diào)用一個函數(shù)的過程中又出現(xiàn)直接或間接的調(diào)用該函數(shù)本身，稱為函數(shù)的遞歸調(diào)用。 ? 何時應用遞歸 ？ ? 問題具有遞歸的數(shù)學定義 (fib數(shù) ) ? 使用了遞歸的數(shù)據(jù)結(jié)構(gòu) （ 二叉樹 ） ? 問題存在遞歸的解決方法（漢諾塔） ? 遞歸程序設計具有以下兩個特點： （ 1） 具備遞歸出口 。遞歸出口定義了遞歸的終止條件，當程序的執(zhí)行使它得到滿足時，遞歸執(zhí)行過程便終止。有些問題的遞歸程序可能存在幾個遞歸出口； （ 2）在不滿足遞歸出口的情況下，根據(jù)所求解問題的性質(zhì)，將 原問題分解成若干子問題 ，這些子問題的結(jié)構(gòu)與原問題的結(jié)構(gòu)相同，但規(guī)模較原問題小。子問題的求解通過以一定的方式 修改參數(shù) 進行函數(shù)自身調(diào)用加以實現(xiàn)，然后將子問題的解組合成原問題的解。遞歸調(diào)用時，參數(shù)的修改最終必須保證遞歸出口得以滿足。 ? 為了防止遞歸函數(shù)無休止的調(diào)用下去，就要 “ 打斷 ” 這個循環(huán)，我們只有一處 “ 要害 ” 可以下手：在調(diào)用會引起遞歸的函數(shù)之前，做一個條件分支判斷，如果條件不成立，則不調(diào)用該函數(shù)。調(diào)用的時候參數(shù)要發(fā)生改變。 ? 一個合理的遞歸函數(shù)，一定是一個邏輯上類似于這樣的函數(shù)定義： ? void F() ? { ? …… ? if(…… ) //先判斷某個條件是否成立 ? { ? F()。 //然后才調(diào)用自身 ? } ? …… ? } 遞歸函數(shù)設計舉例：求 n！ ? 算法描述： n!=1 2 3 …… (n－ 1) n ? 求積公式： f(n) ＝ 1 n=0 n (n1)! n0 5!的運算過程： ? 5！ 5 4！ 4 3！ 3 2！ 2 1！ 1 2 1 3 2 4 6 5 24 120 1 0！ 1 1 n！ 遞歸程序源程序 1/2 求 n！ 遞歸源程序如下： main( ) { int x。 long facto( )。 printf(Input a number:\n)。 scanf(%d,amp。x)。 printf(The result is %ld,facto(x))。 } long facto(n) int n。 { long int z。 if (n==1) z=1。 else z=n*facto(n1)。 return z。 } n！ 遞歸程序源程序 2/2 二、函數(shù)調(diào)用的實現(xiàn)過程 ? （ 1）函數(shù)調(diào)用 ? 當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三項任務： ? 將 返回地址 、 所有 實參 等信息傳遞給被調(diào)用函數(shù)保存； ? 為被調(diào)用函數(shù)的 局部變量 分配存儲區(qū)； ? 將 控制轉(zhuǎn)移 到被調(diào)用函數(shù)的入口。 ? （ 2）函數(shù)返回 從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應該完成下列三項任務： ? 保存被調(diào)函數(shù)的計算 結(jié)果 ； ? 釋放被調(diào)函數(shù)保存 局部變量 的數(shù)據(jù)區(qū)； ? 依照被調(diào)函數(shù)保存的 返回地址 將 控制轉(zhuǎn)移 到調(diào)用函數(shù)。 ? 函數(shù)嵌套調(diào)用時 ， 后調(diào)用的函數(shù)先返回 。 1. int main() 2. { 3. int n = 10。 4. int sn。 5. sn = sum(n)。 6. cout sn endl。 7. } 8. int sum ( int n ) 9. { 10. int i, s = 0。 11. for( i=1。 in。 i++) 12. s += i。 13. return s。 14. } m n() n = sn s smain:n=10 main:sn= sum:n=10 goto: 5 sum:i= sum:s=0 i=11sum:s=55 main:sn=55 main() sum() main函數(shù) 結(jié)束 調(diào)用函數(shù) a 調(diào)用函數(shù) b 函數(shù) b 函數(shù) a 函數(shù)的嵌套調(diào)用，后調(diào)用先返回的原則，上述函數(shù)信息傳遞過程需要設立一個棧，將程序運行時需要的數(shù)據(jù)安排在一個棧中，每調(diào)用一個函數(shù)，為它在棧頂分配一個存儲區(qū)，每當一個函數(shù)退出時，就釋放它的存儲區(qū)，當前運行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂 三、遞歸調(diào)用的實現(xiàn)過程 ? 一個遞歸函數(shù)的運行過程類似于多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)，因此，和每次調(diào)用相關(guān)的一個概念是遞歸函數(shù)運行的層次。假設調(diào)用該遞歸函數(shù)的主函數(shù)是第 0層，則從主函數(shù)調(diào)用遞歸函數(shù)為進入第一層；從第 I 層遞歸調(diào)用本函數(shù)為進入下一層，即第 I+1層。反之，退出第 I 層遞歸返回至第 I1層。 ? 為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設立一個“遞歸工作棧”作為整個函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有的實在參數(shù)、所有的局部變量以及上一層的