【文章內(nèi)容簡介】 e. 3 25 操作 ： ①在表左端插入結(jié)點(diǎn) INSERT(x,FIRST(R),R)。 → LINSERT(x,R) Void LINSERT( elementtype x , LIST amp。R ) { celltype *p 。 p = new celltype 。 p→element = x 。 if ( R == NULL ) { p→next = p 。 R = p 。 } else { p→next = R→next 。 R→next = p 。 } } 。 環(huán)形鏈表 ② 在表右端插入結(jié)點(diǎn) INSERT(x,END(R),R)。 → RINSERT(x,R) Void RINSERT( elementtype x , LIST R ) { LINSERT ( x , R ) 。 R = R→next 。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 26 操作 ： ③從表左端刪除結(jié)點(diǎn) DELETE(FIRST(R),R)。 →LDELETE(R) Void LDELETE( LIST amp。R ) { celltype *p 。 if ( R == NULL ) error ( “空表” )。 else { p = R→next 。 R→next = p→next 。 if ( p == R ) R=NULL。 delete p 。 } } 。 環(huán)形鏈表 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 27 環(huán)形鏈表 雙向環(huán)形鏈表 ： a1 ai an … … R 雙向環(huán)形鏈表的結(jié)構(gòu)與雙向連表結(jié)構(gòu)相同，只是將表頭元素 的空 previous域指向表尾，同時將表尾的空 next域指向表頭結(jié)點(diǎn)， 從而形成向前和向后的兩個環(huán)形鏈表，對鏈表的操作變得更加靈 活。 舉例：設(shè)計(jì)算法，將一個單向環(huán)形鏈表反向。頭元素變成尾 元素，尾元素變成新的頭元素，依次類推。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 28 環(huán)形鏈表 a1 a2 a3 an … R an an1 an2 a1 … R Void REVERS( LIST amp。R ) { position p, q。 p = R→next 。 R→next = p→next 。 p→next = p 。 while ( R != NULL ) { q = R→next 。 R→next = q→next 。 q→next = p→next 。 p→next = q 。 } R = p 。 } ； 算法如下 ： 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 29 棧（ Stack） 棧是線性表的一種特殊形式，是一種限定性數(shù)據(jù)結(jié)構(gòu)， 也就是在對線性表的操作加以限制后，形成的一種新的數(shù) 據(jù)結(jié)構(gòu)。 定義 ：是限定只在表尾進(jìn)行 插入和刪除操作的線性表。 棧又稱為 后進(jìn)先出 (Last In First Out )的線性表。 簡稱 LIFO結(jié)構(gòu)。 棧舉例 a1 a2 an1 an Insert Delete top bottom 棧底 棧頂 棧示意圖 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 30 棧 棧的基本 ① MAKENULL ( S ) 操作 ② TOP ( S ) ③ POP ( S ) ④ PUSH ( x , S ) ⑤ EMPTY ( S ) 舉例 ：利用棧實(shí)現(xiàn)行編輯處理。 設(shè)定符號“ ”為擦訖符，用以刪 除“ ”前的字符；符號“ @”為刪 行符，用以刪除當(dāng)前編輯行。 原理： 一般字符進(jìn)棧； 讀字符 擦訖符退棧； 刪行符則清棧 算法 ： Void LINEEDIT( ) { STACK Ｓ； char c 。 MAKENULL ( S )。 c = getchar ( ) 。 while ( c != ?\n‘ ) { if ( c == ?‘ ) POP ( S )。 else if ( c == ?@‘ ) MAKENULL ( S )。 else PUSH ( c , S )。 c = getchar( )。 } 逆序輸出棧中所有元素； ｝ 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 31 棧的實(shí)現(xiàn) 棧 順序存儲 順序棧示意圖 an ai a3 a2 a1 maxlength1 3 2 1 0 top 結(jié)構(gòu)類型： typedef struct { elementtype elements[maxlength]。 int top 。 } STACK 。 STACK S 。 棧的容量： maxlength – 1 。 棧空： = 0 。 棧滿： = maxlength – 1 。 棧頂元素： [ ] 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 32 棧的實(shí)現(xiàn) 順序存儲 操作 ： ① Void MAKENULL( STACK amp。S ) { = 0 。 } 。 ② Boolean EMPTY( STACK S ) { if ( 1 ) return TRUE else return FALSE 。 } 。 ③ elementtype TOP( STACK S ) { if EMPTY( S ) return NULL。 else return ( [ ] )。 }。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 33 棧的實(shí)現(xiàn) 順序存儲 操作 ： ④ elementtype POP( STACK amp。S ) { if ( EMPTY (S ) ) error ( ―?？铡? ) 。 else = – 1 。 } 。 ⑤ Void PUSH ( elementtype x, STACK amp。S ) { if ( == maxlength 1 ) error ( ―棧滿” ) 。 else { = + 1 。 [ ] = x 。 } } 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 34 棧的實(shí)現(xiàn) 鏈?zhǔn)酱鎯? 采用由指針形成的線性鏈表來實(shí)現(xiàn)棧 的存儲 ,要考慮鏈表的哪一端實(shí)現(xiàn)元素的插 入和刪除比較方便。 實(shí)現(xiàn)的方式如右圖所示，其操作與線 性鏈表的表頭插入和刪除元素相同。 an an1 a2 a1 ∧ top 多個棧共用一個存儲空間的討論 STACK[ maxlength ] bot[1] top[1] bot[2] top[2] bot[3] top[3] top[2] bot[n] top[n] 0 Maxlength1 bot[n+1] bot[i] top[i] 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 35 Int Is_Stack_i_Full ( STACK S , int bot , int top , int i ) /* 判斷第 i 個棧是否滿，滿返回 1，否則返回 0 */ { … … } Void Move_Stack_i ( STACK amp。S , int amp。bot , intamp。 top , int i , int dt ) /* 移動第 i 個棧， dt 為位移量 */ { … … } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 36 出 口 入 口 迷宮示例 迷宮求解 棧的應(yīng)用 問題： 0 1 0 0 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 一個迷宮可用上圖所示方陣 [m,n]表示， 0表示能通過， 1 表 示不