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