【正文】 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 1 抽象數(shù)據(jù)型線性表 線性表的實(shí)現(xiàn) 棧（ Stack） 隊(duì)列（ Queue） 串（ String） 數(shù)組（ Array） 廣義表 (Lists) 線性表（ Liner List） 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 2 抽象數(shù)據(jù)型線性表 [定義 ] 線性表是由 n(n≥0) 個(gè)相同類型的元素組成的有序集合。 記為： ( a1,a2,a3,…… ai1,ai,ai+1,…… an ) 其中：① n為線性表中元素個(gè)數(shù)，稱為線性表的長(zhǎng)度； 當(dāng) n=0時(shí)，為空表，記為（ ）。 ② ai為線性表中的元素，類型定義為 elementtype ③ a1為表中第 1個(gè)元素，無前驅(qū)元素； an為表中最后一個(gè) 元素，無后繼元素；對(duì)于 …a i1,ai,ai+1…(1in) ，稱 ai1 為 ai的直接前驅(qū)， ai+1為 ai的直接后繼。 ④ 線性表是有限的，也是有序的。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 3 抽象數(shù)據(jù)型線性表 線性表 LIST = ( D , R) D = { ai | ai ∈ Elementset , i = 1, 2, …, n, n ≥ 0 } R = { H } H = { ai1, ai | ai1, ai ∈ D , i = 2 , … , n } 操作： 設(shè) L的型為 LIST線性表實(shí)例， x 的型為 elementtype的元素 實(shí)例， p 為位置變量。所有操作描述為： ① INSERT(x, p, L) ② LOCATE(x, L) ③ RETRIEVE(p, L) ④ DELETE(p, L) ⑤ PREVIOUS(p, L), NEXT(p, L) ⑥ MAKENULL( L) ⑦ FIRST( L) 數(shù)學(xué)模型 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 4 抽象數(shù)據(jù)型線性表 舉例：設(shè)計(jì)函數(shù) DELEVAL（ LIST amp。L, elementtype d) ，其功能 為刪除 L 中所有值為 d 的元素。 Void DELEVAL( LIST amp。L, elementtype d ) { position p 。 p = FIRST( L ) 。 while ( P != END( L ) ) { if ( same( RETRIEVE( p, L ), d ) ) DELETE(p, L ) 。 else p = NEXT(p, L ) 。 } } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 5 線性表的實(shí)現(xiàn) 問題： 確定數(shù)據(jù)結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）實(shí)現(xiàn)型 LIST，并在此基礎(chǔ)上 實(shí)現(xiàn)各個(gè)基本操作。 存儲(chǔ)結(jié)構(gòu)的三種方式： ① 連續(xù)的存儲(chǔ)空間（數(shù)組） → 靜態(tài)存儲(chǔ) ② 非連續(xù)存儲(chǔ)空間 ——指針（鏈表） → 動(dòng)態(tài)存儲(chǔ) ③ 游標(biāo)（連續(xù)存儲(chǔ)空間 +動(dòng)態(tài)管理思想） → 靜態(tài)鏈表 指針和游標(biāo) 指針：地址量，其值為另一存儲(chǔ)空間的地址； 游標(biāo)：整型量，其值為數(shù)組的下標(biāo)，用以表示指定元素 的“地址” 或 “位置” 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 6 線性表的數(shù)組實(shí)現(xiàn) 第 1個(gè)元素 第 2個(gè)元素 …… 最后 1個(gè)元素 …… 0 1 2 maxlength1 last 表 空單元 圖 21 線性表的數(shù)組實(shí)現(xiàn) 表的長(zhǎng)度 …… 第 i 個(gè)元素 1≤ i ≤ last 類型定義： define maxlength 100 struct LIST { elementtype elements [maxlength]。 int last。 }。 位置類型： typedef int position。 線性表 L: LIST L。 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 7 線性表的數(shù)組實(shí)現(xiàn) 操作 ： ① Void INSERT ( elementtype x, position p, LIST amp。L) { position q 。 if ( = maxlength – 1) error( ― 表滿 ” ) ； else if (( P +1 ) || ( p 1) ) error( ― 指定位置不存在 ” ) ； else { for ( q = 。 q = p。 q ) [ q + 1] = [ q ] 。 = + 1 。 [ p ] = x 。 } } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 8 ② position LOCATE ( elementtype x , LIST L ) { position q 。 for ( q = 1。 q = 。 q++ ) if ( [ q ] == x ) return ( q ) 。 return ( + 1 )。 } 線性表的數(shù)組實(shí)現(xiàn) ③ elementtype RETRIEVE ( position p , LIST L ) { if ( p ) error( ―指定元素不存在” ) 。 else return ( [ p ] ) 。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 9 ④ Void DELETE( position p , LIST amp。L) { position q 。 if ( ( p ) || ( p 1 ) ) error ( ―指定位置不存在” ) ； else { = – 1。 for ( q = p 。 q = 。 q ++ ) [ q ] = [ q + 1 ]。 } } 線性表的數(shù)組實(shí)現(xiàn) ⑤ position PREVIOUS( position p , LIST L ) { if ( ( p = 1 ) || ( p ) ) error ( ―前驅(qū)元素不存在” ) 。 else return ( p – 1 )。 } 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 10 ⑧ position END( LIST L ) { return( + 1 )。 } ⑦ position FIRST( LIST L ) { return ( 1 )。 } position NEXT( position p , LIST L ) { if ( ( p 1 ) || ( p = ) ) error ( ―前驅(qū)元素不存在” ) 。 else return ( p + 1 )。 } ⑥ position MAKENULL( LIST amp。L ) { = 0 。 return ( +1 )。 } 線性表的數(shù)組實(shí)現(xiàn) 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 11 線性表的指針實(shí)現(xiàn) 結(jié)點(diǎn)形式 element next 結(jié)點(diǎn)信息 下一結(jié)點(diǎn)地址 celltype 結(jié)點(diǎn)類型 struct celltype { elementtype element 。 celltype *next 。 } 。 typedef celltype *LIST。 typedef celltype *position。 LIST header 。 position p , q。 a1 a2 a3 an ∧ … header q p a2: ( *p ).element 。 q: ( *p ).next 。 a2: p→element 。 q: p→next 。 記法 : 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 12 操作討論 ： 線性表的指針實(shí)現(xiàn) 插入元素 : p a1 x header q ai1 ai x p q an ∧ x ∧ q p (a) 表頭插入元素 (b) 中間插入元素 (c) 表尾插入元素 q = new celltype 。 q→element = x 。 q→next = p→next 。 p→next = q 。 或 : temp = p→next 。 p→next = new celltype 。 p→next→element = x 。 p→next→next = temp 。 討論表頭結(jié)點(diǎn)的作用 算法與數(shù)據(jù)結(jié)構(gòu) . 第三章 線 性 表 國(guó)家示范性軟件學(xué)院 2020 秋 Slide. 3 13 操作討論 ： 線性表的指針實(shí)現(xiàn) 刪除元素 : q = p→next 。 p→next = q→next 。 delete q 。 或： q = p→next 。 p→next = p→next→next 。 delete