第2章線性表1-類型定義

1、線性結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)是：的特點(diǎn)是：（1）存在惟一的一個(gè)被稱作）存在惟一的一個(gè)被稱作“第一個(gè)第一個(gè)”的數(shù)據(jù)元素；的數(shù)據(jù)元素；在數(shù)據(jù)元素的非空有限集中，在數(shù)據(jù)元素的非空有限集中，（2）存在惟一的一個(gè)被稱作）存在惟一的一個(gè)被稱作“最后一個(gè)最后一個(gè)”的數(shù)據(jù)元素；的數(shù)據(jù)元素；（3）除第一個(gè)之外，集合中到每個(gè)數(shù)據(jù)元素均只有一）除第一個(gè)之外，集合中到每個(gè)數(shù)據(jù)元素均只有一個(gè)直接前驅(qū)；個(gè)直接前驅(qū)；（4）除最后一個(gè)之外，集合中到每個(gè)數(shù)據(jù)元素均只有）除最后一個(gè)之外，集合中到每個(gè)數(shù)據(jù)元素均只有一個(gè)直接后繼。一個(gè)直接后繼。線性結(jié)構(gòu)線性結(jié)構(gòu)的數(shù)據(jù)包括：的數(shù)據(jù)包括：線性表線性表 棧棧隊(duì)列隊(duì)列串串線性表線性表2.1 線性表

2、的類型定義線性表的類型定義2.3 線性表的線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.2 線性表的線性表的順序表示和實(shí)現(xiàn)順序表示和實(shí)現(xiàn)2.1 線性表的類型定義線性表的類型定義線性表線性表（linear_list）是最常用最簡單）是最常用最簡單的一種數(shù)據(jù)結(jié)構(gòu)。簡言之，一個(gè)線性的一種數(shù)據(jù)結(jié)構(gòu)。簡言之，一個(gè)線性表是表是n個(gè)數(shù)據(jù)元素的有限序列。個(gè)數(shù)據(jù)元素的有限序列。線性表線性表（linear_list）的特點(diǎn)：）的特點(diǎn)：u同一線性表中的元素必定具有相同的特性，同一線性表中的元素必定具有相同的特性，即屬于同一即屬于同一 ；u相鄰元素之間存在著相鄰元素之間存在著 關(guān)系；關(guān)系；u若將線性表記為：若將線性表記為：

3、(a1,ai-1,ai,ai+1an)，則，則，ai的直接前驅(qū)為的直接前驅(qū)為 ；ai的直接后繼為的直接后繼為 ；u線性表中的元素個(gè)數(shù)為線性表中的元素個(gè)數(shù)為 個(gè)；個(gè)； 時(shí)為空表；時(shí)為空表；u每個(gè)元素都有一個(gè)確定的位置：每個(gè)元素都有一個(gè)確定的位置： a1為第一個(gè)為第一個(gè)元素、元素、an為最后一個(gè)元素、為最后一個(gè)元素、ai為第為第i個(gè)元素，稱個(gè)元素，稱i為數(shù)據(jù)元素為數(shù)據(jù)元素ai在線性表中的在線性表中的 。數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象序偶序偶ai-1ai+1n位序位序n=0線性表線性表（linear_list）的抽象數(shù)據(jù)類型定義：）的抽象數(shù)據(jù)類型定義： ADT定義定義ADT List 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：D ai

4、| ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 基本操作：基本操作： 初始化線性表初始化線性表：InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表操作結(jié)果：構(gòu)造一個(gè)空的線性表L 。 撤銷線性表撤銷線性表：DestroyList(&L)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：銷毀線性表操作結(jié)果：銷毀線性表L。(3)清空線性表清空線性表:ClearList(&L)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：將操作結(jié)果：將L重置為空表。重置為空表。(4)判空線性表：判

5、空線性表：ListEmpty(L)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：若操作結(jié)果：若L為空表為空表,則返回則返回TRUE，否則返回否則返回FlASE。(5)求線性表的長度：求線性表的長度：ListLength(L)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：返回線性表操作結(jié)果：返回線性表L中的數(shù)據(jù)元素的個(gè)數(shù)。中的數(shù)據(jù)元素的個(gè)數(shù)。(6) 取表元素：取表元素：GetElem(L,i,&e)初始條件：表初始條件：表L存在且存在且1=i=ListLength(L)。操作結(jié)果：用操作結(jié)果：用e返回線性表返回線性表L中的第個(gè)元素的中的第個(gè)元素的值。值。(7)

6、定位查找操作：定位查找操作：LocateElem (L,e,compare( )初始條件：線性表初始條件：線性表L存在存在, compare( )是數(shù)據(jù)元素是數(shù)據(jù)元素判定函數(shù)。判定函數(shù)。操作結(jié)果：返回操作結(jié)果：返回L中第一個(gè)與中第一個(gè)與e滿足關(guān)系滿足關(guān)系compare( )的數(shù)據(jù)元素的位序的數(shù)據(jù)元素的位序,若這樣的數(shù)據(jù)元若這樣的數(shù)據(jù)元素不存在，則返回素不存在，則返回0。(8)求前驅(qū)：求前驅(qū)：PriorElem(L,cur_e,&pre_e)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：若操作結(jié)果：若cur_e是是L的數(shù)據(jù)元素，且不是第一個(gè)，的數(shù)據(jù)元素，且不是第一個(gè)，則用則

7、用pre_e返回它的前驅(qū)，否則操作失敗，返回它的前驅(qū)，否則操作失敗，pre_e無定無定義。義。(9)求后繼：求后繼：NextElem(L, cur_e,&next_e)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：若操作結(jié)果：若cur_e是是L的數(shù)據(jù)元素，且不是最后一的數(shù)據(jù)元素，且不是最后一 個(gè)，則用個(gè)，則用next_e返回它的后繼，否則操作失敗，返回它的后繼，否則操作失敗，next_e無定義。無定義。(10)插入操作：插入操作：ListInsert(&L,i,e)初始條件：線性表初始條件：線性表L已存在，插入位置正確已存在，插入位置正確 (1=i=ListLen

8、gth(L)+1)。 操作結(jié)果：在操作結(jié)果：在L中第中第i個(gè)位置前插入新的數(shù)據(jù)元素個(gè)位置前插入新的數(shù)據(jù)元素e，L的長度加的長度加1。(11)刪除操作：刪除操作：ListDelete(&L,i,&e)初始條件：線性表初始條件：線性表L已存在，且非空，已存在，且非空，1=i=ListLength(L)。操作結(jié)果：刪除操作結(jié)果：刪除L的第的第i個(gè)元素個(gè)元素,并且用并且用e返回其值，返回其值，L的長度減的長度減1。ADT List(12)遍歷操作：遍歷操作：ListTraverse(L,visit()初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：依次對(duì)操作結(jié)果：依次對(duì)L的

9、每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦。一旦visit（）失敗，則操作失敗。（）失敗，則操作失敗。關(guān)于關(guān)于“基本操作基本操作”的說明的說明基本操作名基本操作名(參數(shù)表參數(shù)表) 初始條件：初始條件： 操作結(jié)果：操作結(jié)果：每個(gè)每個(gè)基本操作基本操作的定義格式為：的定義格式為： 初始化線性表初始化線性表：InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表操作結(jié)果：構(gòu)造一個(gè)空的線性表L 。(5)求線性表的長度：求線性表的長度：ListLength(L)初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：返回線性表操作結(jié)果：返回線性表L中的數(shù)據(jù)元素的個(gè)數(shù)。中的數(shù)據(jù)

10、元素的個(gè)數(shù)。基本操作名基本操作名(參數(shù)表參數(shù)表) 初始條件：初始條件： 操作結(jié)果：操作結(jié)果：每個(gè)每個(gè)基本操作基本操作的定義格式為：的定義格式為：參數(shù)表中參數(shù)表中有兩種參數(shù)：有兩種參數(shù)：賦值參數(shù)賦值參數(shù):只為操作提供輸入值；只為操作提供輸入值；引用參數(shù)引用參數(shù):以以&打頭，除可提供輸入值，還將返回操作結(jié)果。打頭，除可提供輸入值，還將返回操作結(jié)果。(6) 取表元素：取表元素：GetElem(L,i,&e)初始條件：表初始條件：表L存在且存在且1=i=ListLength(L)。操作結(jié)果：用操作結(jié)果：用e返回線性表返回線性表L中的第個(gè)元素的值。中的第個(gè)元素的值?！俺跏紬l件初始條件”描

11、述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！安僮鹘Y(jié)果操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀態(tài)和應(yīng)返回的結(jié)果。狀態(tài)和應(yīng)返回的結(jié)果。若初始條件為空，則省略！若初始條件為空，則省略！基本操作基本操作的定義格式為：的定義格式為：基本操作名基本操作名(參數(shù)表參數(shù)表) 初始條件：初始條件： 操作結(jié)果：操作結(jié)果：利用上述定義的線性表類型線性表類型 可以實(shí)現(xiàn)其它更復(fù)雜的操作例例 2-2例例 2-1線性表類型的線性表類型的應(yīng)用舉例應(yīng)

12、用舉例假設(shè):有兩個(gè)集合集合 A 和和 B 分別用兩個(gè)線性表線性表 LA 和和 LB 表示（已知條件），即：線性表中的數(shù)據(jù)元素即為集合中的成員。 要求：一個(gè)新的集合要求：一個(gè)新的集合AAB。例例 2-1（理解）（理解） 將存在于線性表存在于線性表LB 中中而不存在于不存在于線性表線性表 LA 中中的數(shù)據(jù)元素插入到線插入到線性表性表 LA 中中去，得到一個(gè)擴(kuò)大后的LA。上述問題可演繹為上述問題可演繹為要求對(duì)線性表作如下操作：要求對(duì)線性表作如下操作：已知：已知：LA和和LB是線性表，是線性表，類型為類型為List基本操作有基本操作有12種種1依次從線性表依次從線性表 LB 中中取取一個(gè)數(shù)據(jù)元素一個(gè)數(shù)

13、據(jù)元素;2按照按照LB中取的值在中取的值在 LA 中中查找查找是否存在是否存在相等的元素相等的元素; 3若不存在，則將該元素若不存在，則將該元素插入插入LA中中（插入（插入LA表尾即可）表尾即可），LA長度長度+1 。GetElem(Lb, i ,e) /i=1ListLength(LB) LocateElem(La, e, equal( ) ListInsert(La, 表長表長+1, e) /表長表長=ListLength(LA)操作步驟：4. 重復(fù)步驟重復(fù)步驟13，直到取完，直到取完LB所有元素所有元素 / 取取Lb中第中第i個(gè)數(shù)據(jù)元素賦給個(gè)數(shù)據(jù)元素賦給e if ( ) / La中不存在

14、和中不存在和 e 相同的數(shù)據(jù)元素，則將相同的數(shù)據(jù)元素，則將e插入插入La表尾表尾 for (i=1; i= Lb_len; i+) La_len = ListLength(La); Lb_len = ListLength(Lb); / 求線性表的長度求線性表的長度void union(List &La, List Lb) /算法算法2.1-類類C語言語言GetElem(Lb, i, e); ! LocateElem(La, e, equal( ) ListInsert(La, +La_len, e);例例 2-2已知：已知：線性表線性表LALA和和LBLB中的數(shù)據(jù)中的數(shù)據(jù)元素按值元素按

15、值非遞減有序非遞減有序排列。排列?，F(xiàn)要求：現(xiàn)要求：將將LALA和和LBLB歸并為一個(gè)歸并為一個(gè)新的線性表新的線性表LCLC，且，且LCLC中的數(shù)據(jù)元素中的數(shù)據(jù)元素仍按值仍按值非遞減有序非遞減有序排列。排列。(Ordered List)例如例如：LA=3,5,8,11LB=2,6,8,9,11,15,20則歸并后則歸并后：LC= 策略？策略？2,3,5,6,8,8,9,11,11,15,201初始化初始化 LC 為空表；為空表；操作步驟：操作步驟：2分別從分別從 LA和和LB中中取得當(dāng)前元素取得當(dāng)前元素 ai 和和 bj；3若若 aibj，則將，則將 ai 插入插入到到 LC 表尾表尾(i 加加

16、1)，否則，將否則，將bj 插入插入到到 LC 表尾表尾( j 加加1 ) ；i, j 分別為分別為LA和和LB元元素的當(dāng)前素的當(dāng)前位序位序值。值。畫圖畫圖4重復(fù)重復(fù) 2. 和和 3. 兩步兩步，直至，直至 LA或或LB 中元素中元素 被取完為止；被取完為止；5將將 LB表或表或 LA表中剩余元素復(fù)制插入到表中剩余元素復(fù)制插入到 LC 表中。表中。操作步驟：操作步驟：InitList(Lc)1初始化初始化 LC 為空表；為空表；2分別從分別從 LA和和LB中中取得當(dāng)前元素取得當(dāng)前元素 ai 和和 bj；GetElem(La, i, ai); GetElem(Lb, j, bj);ListIns

17、ert(Lc, 表長表長+1, ai); i+;ListInsert(Lc, 表長表長+1, bj); j+;3若若 aibj，則將，則將 ai 插入插入到到 LC 表尾表尾(i 加加1)，否則，將否則，將bj 插入插入到到 LC 表尾表尾( j 加加1 ) ；void MergeList(List La, List Lb, List &Lc) /本算法將非遞減的有序表本算法將非遞減的有序表 La 和和 Lb 歸并為歸并為 Lcwhile (i = La_len) & (j = Lb_len) GetElem(La, i, ai); GetElem(Lb, j, bj); if

18、 (ai = bj) / 將將 ai 插入到插入到 Lc 中中 ListInsert(Lc, +k, ai); +i; else / 將將 bj 插入到插入到 Lc 中中 ListInsert(Lc, +k, bj); +j; /La和和Lb均不空均不空InitList(Lc); / 構(gòu)造空的線性表構(gòu)造空的線性表 Lci = j = 1; k = 0; /初始化各個(gè)三個(gè)表的位序（指針）初始化各個(gè)三個(gè)表的位序（指針）La_len = ListLength(La);Lb_len = ListLength(Lb); / MergeList while (i = La_len) / 當(dāng)當(dāng)La不空時(shí)不空時(shí) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 當(dāng)當(dāng)Lb不空時(shí)不空時(shí) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素課本中給出的算法不能直接運(yùn)行！課本中給出的算法不能直接運(yùn)行！補(bǔ)充說明：補(bǔ)充說明：1、沒有、沒有main函數(shù)函數(shù)2、使用、使用“類類C”語言描述，