棧的應(yīng)用舉例(編輯修改稿)
2025-09-01 08:28 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 Move[q].b N 1 0 NE 1 1 E 0 1 SE 1 1 S 1 0 SW 1 1 W 0 1 NW 1 1 Struct offsets { int a,b。 } offsets move[8] enum directions {N, NE, E, SE, S, SW, W, NW}。 迷宮問(wèn)題 ? 通常解決迷宮問(wèn)題時(shí)常用堆棧來(lái)儲(chǔ)存已走過(guò)之路徑的方向和坐標(biāo) . ? struct Items ? { int x, y。 //已經(jīng)走過(guò)的某位置 int dir。 //從該位置出發(fā) ,按順時(shí)針 //仍未走過(guò)的下一個(gè)方向 ? } 迷宮問(wèn)題 ? 使用另外一個(gè) mark[m+2][p+2] 維度的數(shù)組來(lái)記錄哪些位置已經(jīng)走訪過(guò) ,該數(shù)組初始化為 0,一旦某個(gè)位置被訪問(wèn) ,則相應(yīng)位置為 1. 求迷宮路徑算法的 基本思想 是： ? 若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn) 。 ? 若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索 。 ? 若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。 算法偽代碼與實(shí)現(xiàn) 見(jiàn)課本 114 程序 棧變化分析 1,1,2 i=0 j=0 d=0 g=0 h=0 i=1 j=1 d=2 g=1 h=2 i=1 j=1 d=3 g=2 h=2 1,1,4 i=2 j=2 d=0 g=2 h=2 1,1,4 i=2 j=2 d=0 g=1 h=2 1,1,4 i=2 j=2 d=1 g=1 h=3 說(shuō)明 : ,以及從該位置出發(fā) ,還未試探的下一個(gè)方向 2. 變量 (i, j)代表當(dāng)前到達(dá)的位置 ,d代表從當(dāng)前位置出發(fā)試探的方向 3. 變量 (g, h)代表從當(dāng)前位置 (i, j)出發(fā) ,向 d方向探索的下一個(gè)位置 4. 內(nèi)層 while循環(huán)不斷地試探前進(jìn) ,跳出內(nèi)層 while循環(huán)意味著當(dāng)前位置的四周均無(wú)法前進(jìn) (墻壁或已經(jīng)走過(guò) ). 若運(yùn)行到內(nèi)循環(huán)的 return語(yǔ)句 ,意味找到路徑 5. 外層 while循環(huán)取出棧頂位置 ,作為新的當(dāng)前位置 ,代表著探索路徑的回退 , 跳出外層循環(huán)意味著沒(méi)有可以走通的路徑 . 表達(dá)式計(jì)算問(wèn)題 表達(dá)式 ::= (操作數(shù) ) + (運(yùn)算符 ) + (操作數(shù) ) 操作數(shù) ::= 簡(jiǎn)單變量 | 表達(dá)式 簡(jiǎn)單變量 :: = 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù) 假設(shè)限于二元運(yùn)算符的表達(dá)式的定義為 : 算術(shù)運(yùn)算的規(guī)則為 : 先乘除后加減 。 先左后右 。 先括弧內(nèi)后括弧外 。 4+68/(2?4+54/6) = 8 ? 33 表達(dá)式的三種標(biāo)識(shí)方法： 設(shè) Exp = S1 + OP + S2 則稱 OP + S1 + S2 為 前綴 表示法 S1 + OP + S2 為 中綴 表示法 S1 + S2 + OP 為 后綴 表示法 例如 : Exp = a ? b + (c ? d / e) ? f 前綴式 : + ? a b ? ? c / d e f 中綴式 : a ? b + c ? d / e ? f 后綴式 :
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1