【正文】 算法，尋 求一條從右下角 [m,n] 出去的路徑。 秋 Slide. 3 37 迷宮求解 分析 ： ⑴ 迷宮可用二維數(shù)組 Maze[i,j] (1≤i≤m, 1≤j≤n) 表示，入口 maze[1,1] = 0 。如圖所示。 設(shè)二維數(shù) 組 move 記下八個(gè)方位的增量； i,j N:( i1, j) NE:(i1, j+1) E:( i, j+1) SE:( i+1, j+1) S:( i+1, j) SW:(i+1, j1) W:(i, j1) NW:(i1, j1) j i 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 h = j + move[ 2, 2 ] = j + 1 。 秋 Slide. 3 39 迷宮求解 ⑷ 采用試探的方法 ， 當(dāng)?shù)竭_(dá)某個(gè)位置且周圍八個(gè)方向走不通時(shí) 需要回退到上一個(gè)位置 ， 并換一個(gè)方向繼續(xù)試探；為解決回退問 題 ， 需設(shè)一個(gè)棧 ， 當(dāng)?shù)竭_(dá)一個(gè)新位置時(shí)將 （ v, i, j） 進(jìn)棧 ， 回退時(shí) 退棧 。 文字描述算法 ： ⑴ 耗子在 (1, 1)進(jìn)入迷宮，并向正東（ v=1）方向試探。若 (g, h)=(m, n)且 maze[m, n]=0，則耗子到達(dá)出口，輸出 走過的路徑；程序結(jié)束。否則仍在 (i, j)方位換一個(gè)方向試探。 若 (i, j)=(1, 1)則到達(dá)入口，說明迷宮走不通。 秋 Slide. 3 40 迷宮求解 Void GETMAZE ( maze , mark ,move ,s ) { (i, j, v) = (1,1,1) 。 top = 0 。 h = move[v, 2] 。amp。amp。 return 。amp。 PUSH( i, j, v, s ) 。 } else if ( v 8 ) v = v + 1 。amp。 if ( top 0 ) (i, j, v＋＋ ) = POP( s ) 。 } while (( top ) amp。 ( v != 8 )) 。 秋 Slide. 3 41 表達(dá)式求值 前綴表達(dá)式（逆波蘭式） 表達(dá)式： 中綴表達(dá)式 后綴表達(dá)式（波蘭式） 例如： *+ab－ ab ( a + b ) * ( a － b) ( a + b ) * ( a － b) ab+ab－ * 高級(jí)語言中，采用類似自然語言的中綴表達(dá)式，但計(jì)算機(jī) 對(duì)中綴表達(dá)式的處理是很困難的，而對(duì) 后綴 或前綴表達(dá)式則顯 得非常簡(jiǎn)單。 ② 后綴表達(dá)式中不需要括弧定義計(jì)算順序，而由運(yùn)算 （操作符）的位置來確定運(yùn)算順序。 秋 Slide. 3 42 表達(dá)式求值 Ⅰ . 將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式 對(duì)中綴表達(dá)式從左至右依次掃描 ， 由于操作數(shù)的順序保持 不變 ， 當(dāng)遇到操作數(shù)時(shí)直接輸出；為調(diào)整運(yùn)算順序 ， 設(shè)立一個(gè) 棧用以保存操作符 ， 掃描到操作符時(shí) ， 將操作符壓入棧中 ， 進(jìn) 棧的原則是保持棧頂操作符的優(yōu)先級(jí)要高于棧中其他操作符的 優(yōu)先級(jí) ， 否則 ， 將棧頂操作符依次退棧并輸出 ， 直到滿足要求 為止 。 Ⅱ . 由后綴表達(dá)式計(jì)算表達(dá)式的值 對(duì)后綴表達(dá)式從左至右依次掃描，與 Ⅰ 相反，遇到操作數(shù) 時(shí)，將操作數(shù)進(jìn)棧保留；當(dāng)遇到操作符時(shí)，從棧中退出兩個(gè)操 作數(shù)并作相應(yīng)運(yùn)算，將計(jì)算結(jié)果進(jìn)棧保留；直到表達(dá)式結(jié)束， 棧中唯一元素即為表達(dá)式的值。 秋 Slide. 3 43 隊(duì)列（ Queue） 隊(duì)列是對(duì)線性表的插入和刪除操作加以限定的另一種限 定型數(shù)據(jù)結(jié)構(gòu)。 a1， a2， a3， an1， an 出隊(duì)列 入隊(duì)列， 插入，排隊(duì) 刪除，出隊(duì) 隊(duì)頭 隊(duì)尾 隊(duì)列示意圖 front rear 操作 ： MAKENULL(Q)、 FRONT(Q)、 ENQUEUE(x, Q)、 DEQUEUE(Q)、 EMPTY(Q) 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 45 隊(duì)列的指針實(shí)現(xiàn) 操作： ① Void MAKENULL( QUEUE amp。 →next = NULL 。 } 。 QUEUE amp。 { if ( == ) return TRUE 。 } 。 QUEUE Q 。 } 。 秋 Slide. 3 46 隊(duì)列的指針實(shí)現(xiàn) ④ Void ENQUEUE ( elementtype x, QUEUE amp。 = →next 。 →next = NULL 。 ⑤ Void DELETE ( QUEUE amp。 if ( EMPTY( Q ) ) error ( ―空隊(duì)列” ) 。 →next = temp→next 。 if ( →next == NULL ) = 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 int front ； int rear ； } a1 a2 a3 a4 Q front rear maxlength 右圖：隊(duì)列 Q狀態(tài) 1 隨著不斷有元素出隊(duì)和進(jìn)隊(duì) （ 插入和刪除 ） ， 隊(duì)列的狀 態(tài)由 1變成 2；此時(shí) an占據(jù)隊(duì) 列的最后一個(gè)位置；第 n+1 個(gè)元素?zé)o法進(jìn)隊(duì) ,但實(shí)際上 ， 前面部分位置空閑 。 an Q front rear 下圖：隊(duì)列 Q狀態(tài) 2 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 第二種方法是采用循環(huán)隊(duì)列。 秋 Slide. 3 49 隊(duì)列的數(shù)組實(shí)現(xiàn) 問題：如何解決循環(huán)隊(duì)列中 隊(duì)空 與 隊(duì)滿 狀態(tài)相同 ？ 方法一：約定隊(duì)列頭指針在隊(duì)列尾指針的下一位置上； 方法二：另設(shè)一個(gè)標(biāo)志位用以區(qū)別隊(duì)空與隊(duì)滿兩種狀態(tài)； 結(jié)論：兩種方法的代價(jià)是相同的。 } 。Q) { = 0 。 } ② boolean EMPTY( Q ) QUEUE Q 。 else return FALSE 。 秋 Slide. 3 50 隊(duì)列的數(shù)組實(shí)現(xiàn) 操作 ：③ elementtype FRONT( QUEUE Q ) { if ( EMPTY( Q ) ) return NULL 。 } 。 else { = addone ( ) 。 } } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 { if ( EMPTY ( Q ) ) error ( ―空隊(duì)列” ) 。 } 。 秋 Slide. 3 52 多項(xiàng)式的代數(shù)運(yùn)算 例如： 多項(xiàng)式 p ( x ) = 3x14 + 2x8 + 1 采用鏈表表示如下： 3 14 2 8 1 0 ∧ P 算法 attch(c, e, d) 建立一個(gè)新結(jié)點(diǎn)，其系數(shù) coef=c，指數(shù) exp=e； 并把它鏈到 d 所指結(jié)點(diǎn)之后，返回該結(jié)點(diǎn)指針。 x = new polynode 。 x→exp = e 。 return x 。 算法 padd 實(shí)現(xiàn)兩個(gè)多項(xiàng)式 a， b 相加 ； c(x) = a(x) + b(x) 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 { polypointer p, q, d, c 。 p = a→link 。 c = new polynode 。 while ( (p != NULL) amp。 (q != NULL) ) switch ( pare ( p→exp, q→exp ) ) { case ?=? : x = p→coef + q→coef 。 p = p→link 。 break 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 break 。 q = q→link 。 } while ( p != NULL ) { d = attch( p→coef, p→exp, d ) 。 } while ( q !=NULL ) { d = attch( q→coef, q→exp, d ) 。 } 多項(xiàng)式的代數(shù)運(yùn)算 d→link = NULL 。 c = c→link 。 return c 。 秋 Slide. 3 55 串 ( String ) 串是線性表的一種特殊形式，表中每個(gè)元素的類型為字符型， 是一個(gè)有限的字符序列。 n 為串的長(zhǎng)度 ； C 語言中串有兩種實(shí)現(xiàn)方法： 字符數(shù)組，如： char str1[10] ； 字符指針，如： char *str2 ； 操作 ： string NULL( ) 。 Void IN( S, a ) 。 Void CONCAT( S1, S2 ) 。 boolean INDEX( S, S1 ) 。 秋 Slide. 3 56 串 ( String ) 例一：將串 T 插在串 S 中第 i 個(gè)字符之后 INSERT( S, T, i )。S, STRING T, int i ) { STRING t1, t2 。 else if ( ISNULL( S ) ) S = T 。 t2 = SUBSTR( S, i + 1, LEN( S ) )。 } } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 S, STRING T ) { STRING t1, t2 。 m = INDEX( S, T )。 else { n = LEN( T ) 。