武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用(參考版)
2025-07-02 14:48本頁面
【正文】 設(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í)行過程。 }其中R1為主函數(shù)調(diào)用fact 時返回點地址，R2為fact函數(shù)中遞歸調(diào)用fact (n 1)時返回點地址。 else f=n*fact (n1) 。參數(shù) 返回地址fact(0)0R2fact(1)1R2 fact(2)2R2fact(3)3R１ } int fact (int n) { int f 。 m=fact (n) 。下面以求3!為例說明執(zhí)行調(diào)用時工作棧中的狀況。遞歸函數(shù)的調(diào)用類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用單位和被調(diào)用單位是同一個函數(shù)而已。 else return (n* fact (n1) ) ?！尽? 棧與遞歸：棧的一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸過程。具體做法：遇到運算對象順序向存儲后綴表達式的B數(shù)組中存放，遇到運算符時類似于中綴表達式求值時對運算符的處理過程，但運算符出棧后不是進行相應(yīng)的運算，而是將其送入B中存放。return result 。 } ch=*A++ 。 break 。 break 。 break 。 break 。 break 。b) 。a) 。 while ( ch != ’’ ) {if (ch!=運算符) Push_SeqStack (s , ch) 。 ch=*A++ 。typedef char datetype 。具體做法：只使用一個對象棧，當(dāng)從左向右掃描表達式時，每遇到一個操作數(shù)就送入棧中保存，每遇到一個運算符就從棧中取出兩個操作數(shù)進行當(dāng)前的計算，然后把結(jié)果再入棧，直到整個表達式結(jié)束，這時送入棧頂?shù)闹稻褪墙Y(jié)果。2． 后綴表達式求值計算一個后綴表達式，算法上比計算一個中綴表達式簡單的多。在后綴表達式中，不在引入括號，所有的計算按運算符出現(xiàn)的順序，嚴格從左向右進行，而不用再考慮運算規(guī)則和級別。根據(jù)以上分析，每個運算符棧內(nèi)、棧外的級別如下：算符 棧內(nèi)級別 棧外級別^ 3 4*、/、% 2 2+、 1 1( 0 4） 1 1中綴表達式表達式 “3*2^（4+2*2１*3）5”。當(dāng)遇到右括號“）”時，一直需要對運算符棧出棧，并且做相應(yīng)的運算，直到遇到棧頂為左括號“(”時，將其出棧，因此右括號“）”級別最低但它是不入棧的。 乘方運算的結(jié)合性是自右向左，所以，它的棧外級別高于棧內(nèi)。當(dāng)自左至右掃描表達式的每一個字符時，若當(dāng)前字符是運算對象，入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧，繼續(xù)向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運算量，從算符棧出棧一個運算符進行運算，并將其運算結(jié)果入對象棧，繼續(xù)處理當(dāng)前字符，直到遇到結(jié)束符。1． 中綴表達式求值：中綴表達式：每個二目運算符在兩個運算量的中間，假設(shè)所討論的算術(shù)運算符包括：+ 、 、*、/、%、^（乘方）和括號（）。運算符從運算對象的個數(shù)上分，有單目運算符和雙目運算符；從運算類型上分，有算術(shù)運算、關(guān)系運算、邏輯運算。下面的算法是由算符優(yōu)先法對表達式求值?！尽? 表達式求值表達式求值是程序設(shè)計語言編譯中一個最基本的問題。} /*wh
公司管理相關(guān)推薦
鄂ICP備17016276號-1