數(shù)據(jù)結(jié)構(gòu)第三章棧和隊(duì)列(編輯修改稿)
2025-08-15 17:53 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 初始化棧將入口位置信息( x , y , 0 ) 入棧v = 4 ?否確定 ( x 1 , y 1 ) 在 v 方向上的下一個(gè)位置 ( x 2 , y 2 )?？諉崾菑棾鰲ｍ斘恢眯畔⒆鳛楫?dāng)前位置 ( x 1 , y 1 , v )v 增 1 ， 準(zhǔn)備換個(gè)方向探索是輸出一條路徑( x 2 , y 2 ) 是出口 ？是v 增 1( x 2 , y 2 ) 可走 ？否否將 ( x 1 , y 1 , v ) 入棧將 ( x 2 , y 2 ) 賦值給當(dāng)前位置 ( x 1 , y 1 )v = 1否是中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 313 棧的應(yīng)用舉例 =x0。 =y0。 =0。 Push(amp。s,e)。 //將入口入棧，探索方向是 0，準(zhǔn)備探索 maze[y0][x0]=2。//打上已走標(biāo)記 while(!IsSqstackEmpty(s)) { //如果棧未空，探索沒(méi)有結(jié)束 Pop(amp。s,amp。e)。 x=。 y=。 //彈出棧頂，作為當(dāng)前位置 v=+1。 //探索新的方向 if(0) //這次出棧是回退操作，清除原探索位置的‘已走’標(biāo)記 maze[y+movey[]][x+movex[]]=0。 while(v=4) /*按照順時(shí)針順序探索 4個(gè)方向 */ { x1=x+movex[v]。 y1=y+movey[v]。 //獲取當(dāng)前位置 (x,y)v方向的相鄰位置坐標(biāo) (x1,y1) if (x1==xxamp。amp。y1==yy) //遇到出口 { 輸出存放在 s中的路徑 /*這條指令不是 C語(yǔ)句 */ V++。 //換一個(gè)方向繼續(xù)探索 } while(v=4) //按照順時(shí)針順序探索 4個(gè)方向 {x1=x+movex[v]。 y1=y+movey[v]。 //獲取當(dāng)前位置 (x,y)v方向的相鄰位置坐標(biāo) (x1,y1) if (x1==xxamp。amp。y1==yy) //遇到出口 { 輸出存放在 s中的路徑 /*這條指令不是 C語(yǔ)句 */ V++。 //換一個(gè)方向繼續(xù)探索 } else if (x10amp。amp。x1N1amp。amp。y10amp。amp。y1M1amp。amp。!maze[y1][x1]) //(x1,y1)可走 { =x。 =y。 =v。 Push(amp。s,e)。 //將當(dāng)前位置 (x,y)以及探索方向 v入棧 x=x1。 y=y1。 v=1。 //將 (x1,y1)設(shè)置成當(dāng)前位置，開(kāi)始向上探索 maze[y][x]=2。 //打上“已走“標(biāo)記 } else v++。 //(x1,y1)不通，換一個(gè)方向探索 } //while循環(huán)結(jié)束時(shí)，說(shuō)明 (x,y)的 4個(gè)方向都探索過(guò)了，應(yīng)該回退一步 } //while stack } 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 314 棧的應(yīng)用舉例 斐波那契問(wèn)題 【 任務(wù)描述 】 斐波那契序列中第 n項(xiàng)的遞歸定義如下，設(shè)計(jì)算法求得第 n項(xiàng)斐波那契序列項(xiàng)的值。 【 遞歸算法 】 int Fibo(int n) { //斐波那契序列項(xiàng)求解的遞歸算法 int val。 if(n==1||n==2)return 1。 //到達(dá)遞歸終點(diǎn) val=Fibo(n1)+Fibo(n2)。//遞歸調(diào)用 return val。 } 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 315 棧的應(yīng)用舉例 ? 斐波那契問(wèn)題非遞歸算法 ? 首先將問(wèn)題 Fibo(n)入棧。 ? 接著進(jìn)入一個(gè)循環(huán)：彈出棧頂問(wèn)題，如果是遞歸終點(diǎn)，則求值累加； ? 否則將 Fibo(n)遞歸分解為 Fibo(n1)和 Fibo(n2)，并將它們分別入棧，直到?？諡橹?。 ? 適用條件 由 P(n)遞歸分解產(chǎn)生兩個(gè)問(wèn)題規(guī)模更小的問(wèn)題 P(n1)和 P(n2)，它們的求解相互獨(dú)立，相互之間不構(gòu)成求解條件。 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 316 棧的應(yīng)用舉例 ? 遞歸問(wèn)題的非遞歸算法設(shè)計(jì)中棧的作用 保存暫時(shí)不能求解的問(wèn)題，等待條件具備時(shí)，再將問(wèn)題出棧進(jìn)行求解。被保存的問(wèn)題，通常是遞歸分解的結(jié)果。 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 317 棧的應(yīng)用舉例 int Fibonacci(int
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1