【正文】 q 。 討論結(jié)點 ai 的位置 p a1 header (a) 刪除第一個元素 a2 q p ai1 ai p q (b) 刪除中間元素 ai+1 an ∧ an1 q p (c) 刪除表尾元素 ∧ 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 14 操作 ： 線性表的指針實現(xiàn) ① position END ( LIST ) { position q 。 q = L 。 while ( q→next != NULL ) q = q→next 。 return ( q ) 。 } 。 ② Void INSERT ( elementtype x, position p, LIST amp。L ) { position q 。 q = new celltype 。 q →element = x 。 q →next = p →next 。 p →next = q 。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 15 操作 ： 線性表的指針實現(xiàn) ③ position LOCATE ( elementtype x, LIST L ) { position p 。 p = L 。 while ( p→next != NULL ) if ( p→next→element == x ) return p 。 else p = p→next 。 return p 。 } ④ elementtype RETRIEVE ( position p , LIST L ) { return ( p →next →element )。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 16 操作 ： 線性表的指針實現(xiàn) ⑤ Void DELETE ( position p, LIST amp。L ) { position q 。 if ( p→next != NULL ) { q = p →next 。 p →next = q →next 。 delete q 。 } } 。 ⑥ position PREVIOUS ( position p, LIST L ) { position q 。 if ( p == L→next ) error ( “不存在前驅(qū)元素” ) ； else { q = L 。 while ( q→next != p ) q = q→next 。 return q 。 } } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 17 操作 ： 線性表的指針實現(xiàn) ⑦ position NEXT ( position p, LIST L ) { position q 。 if ( p→next == NULL ) error ( “不存在后繼元素” ) ； else { q = p→next。 return q 。 } } ⑧ position MAKENULL ( LIST amp。L ) { L = new celltype 。 L→next = NULL。 return L 。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 18 操作 ： 線性表的指針實現(xiàn) ⑨ position FIRST ( LIST L ) { return L。 } 靜態(tài)鏈表 與 動態(tài)鏈表的 比較 比較參數(shù) ← 表的容量 → ← 存取操作 → ← 時間 → ← 空間 → 鏈?zhǔn)酱鎯? 靈活，易擴充 順序存取 訪問元素費時間 實際長度，節(jié)省空間 順序存儲 固定，不易擴充 隨機存取 插入刪除費時間 估算表長度，浪費空間 舉例：遍歷線性鏈表，按照線性表中 元素的順序，依次訪問表中的 每一個元素，每個元素只能被 訪問一次。 Void VISITE( LIST L ) { position p 。 p = L→next 。 while ( p != NULL) { cout p→element 。 p = p→next 。 } } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 19 線性表的游標(biāo)實現(xiàn) 結(jié)點形式 element next 結(jié)點信息 下一結(jié)點位置 spacestr 結(jié)點類型 struct spacestr { elementtype element 。 int next 。 } 。 線性表： spacestr SPACE[ maxsize ] 。 typedef int position。 元素： SPACE[ i ].element → ― 型”為 elementtype( 基本、復(fù)合 ) 下一元素位置： SPACE[ i ].next → ― 型”為 int 類似指針鏈表，對游標(biāo)實現(xiàn)的線性表仍設(shè)表頭結(jié)點。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 20 線性表的游標(biāo)實現(xiàn) d 6 5 c 1 0 a 10 8 e 1 4 1 11 b 2 12 1 0 1 2 3 4 5 6 7 8 9 10 11 12 SPACE 7 3 L M 9 available 線性表 ： L = ( a, b, c ) L = 7 M = ( d, e ) M = 3 空閑表 ： available = 9 q = new spacestr 。 q = SPACE[available].next 。 SPACE[available].next = SPACE[ q ].next 。 delete q 。 SPACE [ q ].next = SPACE[available].next 。 SPACE[available].next = q 。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 21 ① Void INSERT ( elementtype x, position p, spacestr *SPACE ) { position q 。 q = new spacestr 。 SPACE[ q ].element = x 。 SPACE[ q ].next = SPACE[ p ].next 。 SPACE[ p ].next = q 。 } ② Void DELETE ( position p, spacestr *SPACE ) { position q 。 if ( SPACE[ p ].next != 1 ) { SPACE[ q ] = SPACE[ p ].next 。 SPACE[ p ].next = SPACE[ q ].next 。 delete q 。 } } 。 線性表的游標(biāo)實現(xiàn) 操作 ： 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 22 雙向鏈表 結(jié)點形式 element next 結(jié)點信息 后繼結(jié)點指針 dcelltype previous 前驅(qū)結(jié)點指針 結(jié)點類型 struct dcelltype { elementtype element 。 dcelltype *next, *previous 。 } 。 typedef dcelltype *DLIST 。 typedef dcelltype *position 。 ai1 a i ai+1 p 刪除位置 p的元素 ： p→previous→next = p→next。 p→next→previous = p→previous 。 ∧ header a n ∧ tail 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 23 雙向鏈表 操作 ： Void INSERT( elementtype x, position p, DLIST amp。L ) ； { position q 。 q = new dcelltype 。 q→element = x 。 q→previous→next = q 。 q→previous = p→previous 。 q→next = p 。 p→previous = q 。 } 。 討論：元素的位置？ 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slide. 3 24 環(huán)形鏈表 單向線性鏈表 雙向線性鏈表 單向循環(huán)鏈表 雙向循環(huán)鏈表 對線性鏈表的改進， 解決“單向操作”的 問題；改進后的鏈 表，能夠從任意位 置元素開始，訪問 表中的每一個元素。 單向環(huán)形鏈表 ： a1 a2 a3 an … R 其結(jié)構(gòu)與單向線性鏈表相同，用表尾指針標(biāo)識鏈表，從 而省去了表頭結(jié)點。 表頭： R→next ( 亦即表中的一個元素 a1 ) 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國家示范性軟件學(xué)院 2020 秋 Slid