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