【正文】 t1 = SUBSTR( S, 1, m 1 ) 。 if ( m==0 ) error ?串 S中不包含子串 T‘ 。 int m, n 。 秋 Slide. 3 57 串 ( String ) Void DELETE( STRING amp。 S = CONCAT( t1, CONCAT( T, t2 ) )。 else if ( ISNULL ( T ) ) { t1 = SUBSTR( S, 1, i ) 。 if ( ( i 0 ) || ( i LEN( S ) ) error ?指定位置不對’ 。 Void INSERT( STRING amp。 抽象數(shù)據(jù)型串 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 string SUBSTR( S, m, n ) 。 int LEN( S ) 。 boolean ISNULL ( S ) 。a n‘ ； 其中： char ai ； 0 ≤ i ≤ n ； n ≥ 0 ； 當 n = 0 時，為空串。 串的基本形式可表示成： S = ? a1a2a3 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 delete p 。 p = c 。 q = q→link 。 p = p→link 。 break 。 case ??: d = attch( q→coef, q→exp, d ) 。 秋 Slide. 3 54 p = p→link 。 case ?‘: d = attch( p→coef, p→exp, d )。 q = q→link 。 if ( x ) d = attch( x, p→exp, d ) 。amp。 d = c 。 q = b→link 。 int x 。 秋 Slide. 3 53 多項式的代數(shù)運算 polypointer padd ( ) polypointer a , polypointer b 。 } 。 d→link = x 。 x→coef = c 。 polypointer attch ( int c , int e , polypointer d ) { polypointer x 。 多項式的代數(shù)運算 結(jié)點結(jié)構(gòu) coef exp link 系數(shù) 指數(shù) 下一項地址 結(jié)點類型： struct polynode { int coef ； int exp ； polylink *link ； } typedef polynode *polypointer ； 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 else = addone ( ) 。 秋 Slide. 3 51 隊列的數(shù)組實現(xiàn) ⑤ Void DEQUEUE ( QUEUE Q ) 。 [ ] = x 。 ④ Void ENQUEUE ( elementtype x, QUEUE Q ) { if ( addone ( addone( ) ) == ) error ( ―隊列滿” ) 。 else return ([ Q. front ] )。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 { if ( addone() == ) return TRUE 。 = maxlength – 1。 ① Void MAKENULL ( QUEUE amp。 操作 ： int addone( int i ) { return ( ( i + 1） % maxlength ) 。 插入元素： = ( + 1） % maxlength 刪除元素： = ( + 1） % maxlength 隊空 ： ( + 1） % maxlength == 隊滿 ： ( + 1 ) % maxlength == ? 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 0 1 maxlength1 隊列 Q 秋 Slide. 3 48 隊列的數(shù)組實現(xiàn) 解決假溢出的方法有多種；一是通過不斷移動元素位置， 每當有元素出隊列時，后面的元素前移一個位置，是隊頭元 素始終占據(jù)隊列的第一個位置。 ―假溢出“ maxlength a1 a2 a3 a4 a5 a6 an 秋 Slide. 3 47 隊列的數(shù)組實現(xiàn) 隊列的 “型” ： struct QUEUE { elementtype element [ maxlength ] 。 } } 。 delete temp 。 else { temp = →next 。Q ) { celltype *temp 。 } 。 →element = x 。Q ) { →next = new celltype 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 { return →element 。 ③ elementtype FRONT ( Q ) 。 else return FALSE 。Q 。 ② boolean EMPTY( Q ) 。 = 。Q ) { = New celltype 。 秋 Slide. 3 44 隊列（ Queue） 隊列的指針實現(xiàn) 元素結(jié)構(gòu) ： struct celltype { elementtype element ； celltype *next ； } ； 隊列的 “型” ： struct QUEUE { celltype *front ； celltype *rear ； } a1 a2 an ∧ … 隊列的指針實現(xiàn)示意圖 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 [定義 ] 將線性表的插入和刪除操作分別限制在表的兩端進行， 和棧相反，隊列是一種先進先出（ First In First Out， 簡稱 FIFO 結(jié)構(gòu)）的線性表。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 遇到 “ （ ” 進棧 ， 當遇到 “ ） ” 時 ， 退棧輸出直到 “ ） ” 為止 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 后綴表達式的特點 ： ① 在后綴表達式中，變量（操作數(shù)）出現(xiàn)的順序與中 綴表達式順序相同。 cout ―路徑不存在！” ； } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 amp。 } 。 (!EMPTY(s))) POP( s ) 。 else { while (( == 8) amp。 (i, j, v) = (g, h, 1) 。 mark[g, h] == 0)) { mark[g, h] = 1 。 } if ((maze[g, h] ==0) amp。 (maze[m, n] == 0 )) { output( S ) 。 ( h == n) amp。 if (( g == m) amp。 do { g = move[v, 1] 。 mark[1, 1] = 1 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 ⑷ 若 (i, j)方位周圍 8個方位阻塞或已經(jīng)過，則需退一步，并換一個方位試探。 ⑶ 若 (g, h) ≠(m, n),但 (g, h)方位能走通且第一次經(jīng)過 ,則記下這一步，并從 (g, h) 出發(fā)，再向東試探下一步。 ⑵ 檢測下一方位 (g, h)。 ⑸ 每次換方向?qū)ふ倚挛恢脮r，需測試該位置以前是否已經(jīng)經(jīng)過， 對已到達的位置，不能重復(fù)試探，為此設(shè)矩陣 mark，其處置為 0， 一旦到達位置 ( i , j )時，置 mark[i, j] = 1。 V i j 說明 1 0 1 E 2 1 1 SE 3 1 0 S 4 1 1 SW 5 0 1 W 6 1 1 NW 7 1 0 N 8 1 1 NE 迷宮求解 ⑶ 為避免時時監(jiān)測邊界狀態(tài)，可把二維數(shù)組 maze[1:m, 1:n]擴大 為 maze[0:m+1, 0:n+1]，且另 0行和 0列、 m+1行和 n+1列的值為 1； 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 38 出 口 入 口 迷宮示例 從 ( i , j ) 到 ( g , h ) 且 v = 2 ( 東南）則 有： g = i + move[ 2, 1 ] = i + 1 。 方向 v 按從正東開始且順時針分別記為 18， v=1,8。 耗子在任意位置可用（ i,j） 坐標表示； ⑵ 位置 ( i, j) 周圍有 8個方 向可以走通，分別記為： E,SE,S,SW,W,NW,N,NE。 11 15→m n 棧和遞歸過程 75 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 36 出 口 入 口 迷宮示例