武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用-全文預(yù)覽
【正文】 一個(gè)中綴表達(dá)式簡(jiǎn)單的多。根據(jù)以上分析，每個(gè)運(yùn)算符棧內(nèi)、棧外的級(jí)別如下：算符 棧內(nèi)級(jí)別 棧外級(jí)別^ 3 4*、/、% 2 2+、 1 1( 0 4） 1 1中綴表達(dá)式表達(dá)式 “3*2^（4+2*2１*3）5”。 乘方運(yùn)算的結(jié)合性是自右向左，所以，它的棧外級(jí)別高于棧內(nèi)。1． 中綴表達(dá)式求值：中綴表達(dá)式：每個(gè)二目運(yùn)算符在兩個(gè)運(yùn)算量的中間，假設(shè)所討論的算術(shù)運(yùn)算符包括：+ 、 、*、/、%、^（乘方）和括號(hào)（）。下面的算法是由算符優(yōu)先法對(duì)表達(dá)式求值。} /*while (d8)*/ } /*while */ return 0 。amp。 x=i 。while (d8) { i=x+move[d].x 。 while (! Empty_SeqStack (s ) ) { Pop_SeqStack (s,＆temp) 。 =1 。 item move[8] 。 if ( (x ,ｙ)= =(ｍ,n) ) 結(jié)束 。求出下一個(gè)要試探的方向d++ 。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í)就不能再走了。(3,6)0（下腳標(biāo)表示方向），當(dāng)從點(diǎn)(3,6)沿方向0到達(dá)點(diǎn)(3,7)之后，無(wú)路可走，則應(yīng)回溯，即退回到點(diǎn)(3,6)，對(duì)應(yīng)的操作是出棧，沿下一個(gè)方向即方向1繼續(xù)試探，方向１、２試探失敗，在方向３上試探成功，因此將(3,6,3)壓入棧中，即到達(dá)了（4,5）點(diǎn)。(2,2)1224。 j=y+move[v].y 。為了簡(jiǎn)化問(wèn)題，方便的求出新點(diǎn)的坐標(biāo)，將從正東開(kāi)始沿順時(shí)針進(jìn)行的這8個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組move [ 8 ]中，在move 數(shù)組中，每個(gè)元素有兩個(gè)域組成，x：橫坐標(biāo)增量，y：縱坐標(biāo)增量。 入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。 需要解決的四個(gè)問(wèn)題：1． 表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用maze[m][n]來(lái)表示一個(gè)迷宮，maze[i][j]=0或1。下面的求解過(guò)程采用回溯法?！纠?】 利用棧實(shí)現(xiàn)迷宮的求解。在后面的例子中，為了在算法中表現(xiàn)出問(wèn)題的層次，有關(guān)棧的操作調(diào)用了的相關(guān)函數(shù)，(a)那樣，對(duì)余數(shù)的入棧操作：Push_SeqStack ( amp。 printf(“%d”,x)。s ，amp。 /*余數(shù)入棧 */ N=N / r 。 top =1。 /*定義一個(gè)順序棧*/datetype x。若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。 教學(xué)難點(diǎn)：利用棧實(shí)現(xiàn)表達(dá)式求值216。第三章 棧和隊(duì)列第九講 棧的應(yīng)用 1．鞏固棧的定義及表示。 教學(xué)重點(diǎn)： 利用棧實(shí)現(xiàn)表達(dá)式求值216。算法思想如下：當(dāng)N0時(shí)重復(fù)1，21． 若 N≠0，則將N % r 壓入棧s中 ，執(zhí)行2。 { int s[L],top。s)。 { s[++top]=N%r。 s ) ) while (top!=1) { Pop_SeqStack (amp。 printf ( “ %d ”，x ) 。通常用順序棧較多，因?yàn)楹鼙憷?。在后面的例子中，為了算法的清楚易讀，在不至于混淆的情況下，不再加地址運(yùn)算符，請(qǐng)讀者注意。求解思想：回溯法是一種不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法。在求解過(guò)程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無(wú)路）時(shí)，能正確返回前一點(diǎn)以便繼續(xù)從下一個(gè)方向向前試探，則需要用一個(gè)棧保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向。 8的迷宮。因?yàn)槌隹谠冢╩，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|沿
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1