武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用-資料下載頁
2025-06-29 14:48本頁面
【正文】 ak 。 } Push_SeqStack (s, c) 。 } ch=*A++ 。 } Pop _SeqStack ( s , result ) 。return result 。}棧中狀態(tài)變化情況：當(dāng)前字符 棧中數(shù)據(jù) 說明３3３入棧２3，２２入棧４3，2，4４入棧２3，2，4，2２入棧２3，2，4，2，2２入棧＊3，2，4，4計算２＊２，將結(jié)果４入棧＋3，2，8計算４＋４，將結(jié)果８入棧１3，2，8，1１入棧３3，2，8，1，3３入棧＊3，2，8，3計算１＊３，將結(jié)果４入棧－3，2，5計算８－５，將結(jié)果５入棧^ 3，32計算2^5，將結(jié)果32入棧*96計算３＊32，將結(jié)果96入棧596，55入棧96計算965，結(jié)果入棧結(jié)束符空結(jié)果出棧圖 后綴表達(dá)式求值過程3． 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)示和前述對中綴表達(dá)式求值的方法完全類似，但只需要運(yùn)算符棧，遇到運(yùn)算對象時直接放后綴表達(dá)式的存儲區(qū)，假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組A中，轉(zhuǎn)換后的后綴表達(dá)式存儲在字符數(shù)組B中。具體做法：遇到運(yùn)算對象順序向存儲后綴表達(dá)式的B數(shù)組中存放，遇到運(yùn)算符時類似于中綴表達(dá)式求值時對運(yùn)算符的處理過程，但運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn)算，而是將其送入B中存放。讀者不難寫出算法，在此不在贅述?！尽? 棧與遞歸：棧的一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸過程?，F(xiàn)實中，有許多實際問題是遞歸定義的，這時用遞歸方法可以使許多問題的結(jié)果大大簡化，以 n!為例：n!的定義為：n! =1 n=0 /*遞歸終止條件*/n*(n1) n0 /*遞歸步驟*/根據(jù)定義可以很自然的寫出相應(yīng)的遞歸函數(shù)int fact (int n) { if (n= =0) return 1 。 else return (n* fact (n1) ) 。 }遞歸函數(shù)都有一個終止遞歸的條件，如上例n=0時，將不再繼續(xù)遞歸下去。遞歸函數(shù)的調(diào)用類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用單位和被調(diào)用單位是同一個函數(shù)而已。在每次調(diào)用時系統(tǒng)將屬于各個遞歸層次的信息組成一個活動記錄（ActivaTion Record），這個記錄中包含著本層調(diào)用的實參、返回地址、局部變量等信息，并將這個活動記錄保存在系統(tǒng)的“遞歸工作?！敝校慨?dāng)遞歸調(diào)用一次，就要在棧頂為過程建立一個新的活動記錄，一旦本次調(diào)用結(jié)束，則將棧頂活動記錄出棧，根據(jù)獲得的返回地址信息返回到本次的調(diào)用處。下面以求3!為例說明執(zhí)行調(diào)用時工作棧中的狀況。為了方便將求階乘程序修改如下： main () { int m，n=３ 。 m=fact (n) 。 R1： printf (“%d!=%d\n”，n，m) 。參數(shù) 返回地址fact(0)0R2fact(1)1R2 fact(2)2R2fact(3)3R１ } int fact (int n) { int f 。 if (n= =0) f=1 。 else f=n*fact (n1) 。 遞歸工作棧示意圖 R2: return f 。 }其中R1為主函數(shù)調(diào)用fact 時返回點地址，R2為fact函數(shù)中遞歸調(diào)用fact (n 1)時返回點地址。設(shè)主函數(shù)中n=3?。? n=3 n=2 n=1 n=0m=fact(n) f=3*fact(2) f=2*fact(1) f=1*fact(0) f=1 return f； return f return f return f f=3*2*1*1 f=2*1*1 f=1*1 f=1 圖 fact(3) 的執(zhí)行過程
公司管理相關(guān)推薦
鄂ICP備17016276號-1