武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用(更新版)
【正文】 =1*1 f=1 圖 fact(3) 的執(zhí)行過程。參數(shù) 返回地址fact(0)0R2fact(1)1R2 fact(2)2R2fact(3)3R１ } int fact (int n) { int f 。 else return (n* fact (n1) ) 。 } ch=*A++ 。 break 。 while ( ch != ’’ ) {if (ch!=運算符) Push_SeqStack (s , ch) 。2． 后綴表達式求值計算一個后綴表達式，算法上比計算一個中綴表達式簡單的多。 乘方運算的結(jié)合性是自右向左，所以，它的棧外級別高于棧內(nèi)。下面的算法是由算符優(yōu)先法對表達式求值。amp。while (d8) { i=x+move[d].x 。 =1 。 if ( (x ,ｙ)= =(ｍ,n) ) 結(jié)束 。4． 如何防止重復(fù)到達某點，以避免發(fā)生死循環(huán)： 一種方法是另外設(shè)置一個標志數(shù)組mark[m][n]，它的所有元素都初始化為0，一旦到達了某一點 ( i , j )之后，使mark[i][j] 置1，下次再試探這個位置時就不能再走了。(2,2)1224。為了簡化問題，方便的求出新點的坐標，將從正東開始沿順時針進行的這8個方向的坐標增量放在一個結(jié)構(gòu)數(shù)組move [ 8 ]中，在move 數(shù)組中，每個元素有兩個域組成，x：橫坐標增量，y：縱坐標增量。 需要解決的四個問題：1． 表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用maze[m][n]來表示一個迷宮，maze[i][j]=0或1?！纠?】 利用棧實現(xiàn)迷宮的求解。 printf(“%d”,x)。 /*余數(shù)入棧 */ N=N / r 。 /*定義一個順序棧*/datetype x。 教學(xué)難點：利用棧實現(xiàn)表達式求值216。 教學(xué)重點： 利用棧實現(xiàn)表達式求值216。 { int s[L],top。 { s[++top]=N%r。 printf ( “ %d ”，x ) 。在后面的例子中，為了算法的清楚易讀，在不至于混淆的情況下，不再加地址運算符，請讀者注意。在求解過程中，為了保證在到達某一點后不能向前繼續(xù)行走（無路）時，能正確返回前一點以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能夠到達的每一點的下標及從該點前進的方向。因為出口在（m，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進行。依次入棧為：top —5,8,2 5,7,05,6,04,5,1top —3,6,03,6,3 3,5,03,5,0 3,4,03,4,0 3,3,03,3,0 2,2,12,2,1 1,1,11,1,1棧中每一組數(shù)據(jù)是所到達的每點的坐標及從該點沿哪個方向向下走的，走的路線為：(1,1)1224。棧的定義仍然為： SeqStack s 。將新點（i , j）切換為當(dāng)前點（x , y） 。 int x, y, d, i, j 。 d=+1 。 if (x==mamp。它的實現(xiàn)也是需要棧的加入。根據(jù)運算規(guī)則，左括號“（”在棧外時它的級別最高，而進棧后它的級別則最低了。中綴表達式“3*2^（4+2*21*3）5 ”的后綴表達式為：“32422*+13*^*5”。 Init_SeqStack(s) 。 case ch= =’’： c=ab 。 } Push_SeqStack (s, c) 。現(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 。 R1： printf (“%d!=%d\n”，n
公司管理相關(guān)推薦
鄂ICP備17016276號-1