武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用-文庫(kù)吧資料
2025-07-05 14:48本頁(yè)面
【正文】 ile (d8)*/ } /*while */ return 0 。 /*迷宮有路*/ else d=0 。amp。 maze[x][y]= 1 。 x=i 。if ( maze[i][j]= =0 ) { temp={x, y, d} 。while (d8) { i=x+move[d].x 。 y= 。 while (! Empty_SeqStack (s ) ) { Pop_SeqStack (s,＆temp) 。 =1 。 =1 。 datetype temp 。 item move[8] 。 } else d++ 。 if ( (x ,ｙ)= =(ｍ,n) ) 結(jié)束 。 求新點(diǎn)坐標(biāo) (i, j ) 。求出下一個(gè)要試探的方向d++ 。迷宮求解算法思想如下：1． 棧初始化。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í)就不能再走了。/* 橫縱坐標(biāo)及方向*/}datatype 。(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)。(3,4)0224。(2,2)1224。因此，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向。 j=y+move[v].y 。 item move[8] 。為了簡(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)增量。2．試探方向：在上述表示迷宮的情況下，每個(gè)點(diǎn)有8個(gè)方向去試探，如當(dāng)前點(diǎn)的坐標(biāo)(x,y)，與其相鄰的8個(gè)點(diǎn)的坐標(biāo)都可根據(jù)與該點(diǎn)的相鄰方位而得到。 入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。這樣做使問(wèn)題簡(jiǎn)單了，每個(gè)點(diǎn)的試探方向全部為8，不用再判斷當(dāng)前點(diǎn)的試探方向有幾個(gè)，同時(shí)與迷宮周圍是墻壁這一實(shí)際問(wèn)題相一致。 需要解決的四個(gè)問(wèn)題：1． 表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用maze[m][n]來(lái)表示一個(gè)迷宮，maze[i][j]=0或1。 若所有的方向均沒(méi)有通路，則沿原路返回前一點(diǎn)，換下一個(gè)方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無(wú)路可走又返回到入口點(diǎn)。下面的求解過(guò)程采用回溯法。迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口?！纠?】 利用棧實(shí)現(xiàn)迷宮的求解。 因?yàn)槭怯胏語(yǔ)言描述，第一個(gè)參數(shù)是棧的地址才能對(duì)棧進(jìn)行加工。在后面的例子中，為了在算法中表現(xiàn)出問(wèn)題的層次，有關(guān)棧的操作調(diào)用了的相關(guān)函數(shù)，(a)那樣，對(duì)余數(shù)的入棧操作：Push_SeqStack ( amp。(b)中的直接用int向量S和int 變量top作為一個(gè)棧來(lái)使用，往往初學(xué)者將棧視為一個(gè)很復(fù)雜的東西，不知道如何使用，通過(guò)這個(gè)例子可以消除棧的“神秘”，當(dāng)應(yīng)用程序中需要一個(gè)與數(shù)據(jù)保存時(shí)相反順序使用數(shù)據(jù)時(shí)，就要想到棧。 printf(“%d”,x)。 { x=s[top]。s ，amp。 /* 商作為被除數(shù)繼續(xù) */ } }while ( Empty_SeqStack(amp。 /*余數(shù)入棧 */ N=N / r 。s ，N % r )。 top =1。Init_SeqStack(amp。 /*定義一個(gè)順序棧*/datetype x。 define L 10void conversion(int N，int r) void conversion(int N，int r){ SeqStack s。若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束?！纠?】簡(jiǎn)單應(yīng)用：數(shù)制轉(zhuǎn)換問(wèn)題將十進(jìn)制數(shù)N轉(zhuǎn)換為r進(jìn)制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3456，r=8為例轉(zhuǎn)換方法如下： N N / 8 （整除）
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1