數(shù)據(jù)結(jié)構(gòu)課件 第2章線性表

1、第二章第二章 線性表線性表什么是線性表？ 線性表是一種最簡單的線性結(jié)構(gòu)。什么是線性結(jié)構(gòu)？ 線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集合它有四個(gè)基本特征：1集合中必存在唯一的一個(gè)“第一元素”；2集合中必存在唯一的一個(gè)“最后元素”；3除最后元素之外，其它數(shù)據(jù)元素均有唯一的“后繼”；4除第一元素之外，其它數(shù)據(jù)元素均有唯一的前驅(qū)。第二章第二章 線性表線性表2.1線性表的類型定義線性表線性表 (Linear_List)是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。 通常可以用下列“ n 個(gè)數(shù)據(jù)元素的序列”表示（a1,a2,ai-1,ai,ai+1,an）n 定義為線性表的表長，n=0時(shí)的線性表為空表i為ai在線性表中的位

2、序由此，我們也可以將線性表看成是由(i,ai) 構(gòu)成的集合。第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義線性表中的數(shù)據(jù)元素可以是各種各樣的，只要是屬于同一個(gè)集合即可。例如，26個(gè)小寫英文字母是一個(gè)線性表(a，b，z)同一花色的13張撲克牌 (2,3,4,5,6,7,8,9,10,J,Q,K,A) 均可以構(gòu)成一個(gè)線性表。序偶 表示 ai-1是 ai的直接前驅(qū)，反之，ai是ai-1的直接后繼。第二章第二章 線性表線性表2.1.1抽象數(shù)據(jù)類型線性表的定義線性表的操作很多，為討論方便起見可歸為四類。1.1.結(jié)構(gòu)初始化結(jié)構(gòu)初始化2.2.銷毀結(jié)構(gòu)銷毀結(jié)構(gòu) 3.3.引用型操作引用型操作 4

3、.4.加工型操作加工型操作 第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義其抽象數(shù)據(jù)類型的定義如下：ADT ADT ListList 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：Dai| ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1 | ai-1，ai D, i=2,.,n 第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義基本操作：基本操作： 結(jié)構(gòu)初始化結(jié)構(gòu)初始化 InitList( & &L ) 操作結(jié)果：構(gòu)造一個(gè)空的線性表 L 。 銷毀結(jié)構(gòu)銷毀結(jié)構(gòu) DestroyList( & &L ) 初始條件：線性表 L 已存在。 操作

4、結(jié)果：銷毀線性表 L 。 第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 引用型操作引用型操作 PriorElem( L, cur_e, & &pre_e ) 初始條件：線性表 L 已存在。 操作結(jié)果：若 cur_e 是 L 中的數(shù)據(jù)元素， 則用 pre_e 返回它的前驅(qū)， 否則操作失敗，pre_e 無定義第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 NextElem( L, cur_e, & &next_e ) 初始條件：線性表 L 已存在。 操作結(jié)果：若 cur_e 是 L 中的數(shù)據(jù)元素， 則用 next_e返回它的后繼，

5、否則操作失敗，next_e 無定義。 第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 GetElem( L, i, & &e ) 初始條件：線性表 L 已存在， 1iLengthList(L)。 操作結(jié)果：用e返回L中第i個(gè)元素的值。第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 LocateElem( L, e, compare( ) ) 初始條件；線性表 L 已存在, compare( ) 是元素判定函數(shù)。 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系 compare( ) 的元素的位序。 若這樣的元素不存在，則返回值為0。第二章第二章 線性表線性表

6、2.1.1 抽象數(shù)據(jù)類型線性表的定義 ListTraverse(L, visit( ) 初始條件：線性表 L 已存在， visit( ) 為元素的訪問函數(shù)。 操作結(jié)果：依次對(duì) L 的每個(gè)元素調(diào)用 函數(shù) visit( )。 一旦 visit( ) 失敗，則操作失敗。第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 加工型操作加工型操作 ClearList( & &L ) 初始條件：線性表 L 已存在。 操作結(jié)果：將 L 重置為空表。 PutElem( & &L, i, & &e ) 初始條件：線性表L已存在， 1iLengthList

7、(L)。操作結(jié)果：L 中第 i 個(gè)元素賦值同 e 的值。 第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 ListInsert( & &L, i, e )初始條件：線性表 L 已存在， 1iLengthList(L)+1。操作結(jié)果：在 L 的第 i 個(gè)元素之前 插入新的元素 e，L 的長度增1。 第二章第二章 線性表線性表2.1.1 抽象數(shù)據(jù)類型線性表的定義 ListDelete( & &L, i, & &e )初始條件：線性表 L 已存在且非空， 1iLengthList(L)1iLengthList(L)。操作結(jié)果：刪除刪除

8、L 的第 i 個(gè)元素， 并用 e 返回其值，L 的長度減長度減1 1。 ADT ADT List第二章第二章 線性表線性表2.1.2 線性表類型的應(yīng)用線性表類型的應(yīng)用例例2-12-1 已知集合 A 和 B，求兩個(gè)集合的并集，使 AAB，且 B 不再單獨(dú)存在。具體操作步驟為： 1從線性表 LB 中取出一個(gè)數(shù)據(jù)元素； 2依值在線性表 LA 中進(jìn)行查詢； 3若不存在，則將它插入到 LA 中。 重復(fù)上述三步直至 LB 為空表止。ListDelete( LB, 1, e );LocateElem( LA, e, equal() );ListInsert( LA,n+1,e )第二章第二章 線性表線性表2

9、.1.2 線性表類型的應(yīng)用線性表類型的應(yīng)用算法算法2.12.1voidvoid union(List & &LA, List & &LB)。 / / 將所有在線性表將所有在線性表LBLB中但不在中但不在LALA中的數(shù)據(jù)元素插入到中的數(shù)據(jù)元素插入到LA LA 中中, , /算法執(zhí)行之后，線性表算法執(zhí)行之后，線性表 LB LB 不再存在不再存在La_len = ListLength(LA);/求得線性表 LA 的長度whilewhile (! !ListEmpty(LB)/依次處理 LB 中元素直至 LB 為空表止 ListDelete(LB,1,e); / 從 L

10、B 中刪除第1個(gè)數(shù)據(jù)元素并賦給 e if if (!LocateElem(LA,e,equal( ) ListInsert(LA,+La_len,e);/ 當(dāng)LA中不存在和 e 值相同的數(shù)據(jù)元素時(shí)進(jìn)行插入 / whileDestroyList(LB);/ 銷毀線性表 LB / union 第二章第二章 線性表線性表2.1.2 線性表類型的應(yīng)用線性表類型的應(yīng)用例例2-22-2 已知一個(gè)“非純集合” B，試構(gòu)造一個(gè)集合 A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。與與例例2-12-1所不同之處所不同之處僅僅在于兩點(diǎn)僅僅在于兩點(diǎn)：1.算法2.1中 LA 是已知的，而在此的 LA 是待新建的；2.在

11、算法2.1求得并集之后，原來的兩個(gè)集合不再保留，而在此構(gòu)建新的集合A的同時(shí)，原來的集合 B 不變。 第二章第二章 線性表線性表2.1.2 線性表類型的應(yīng)用線性表類型的應(yīng)用算法算法2.22.2voidvoid purge(List & &LA, List LB) / / 構(gòu)造線性表構(gòu)造線性表LALA，使其只包含，使其只包含LBLB中所有值不相同的數(shù)據(jù)中所有值不相同的數(shù)據(jù)/ / 元素元素, ,算法不改變線性表算法不改變線性表LBLB InitList(LA); / 創(chuàng)建一個(gè)空的線性表 LA La_len = 0;Lb_len = ListLength(LB); / 求線性表 LB

12、的長度forfor (i = 1; i = Lb_len; i+)/ 依次處理 LB 中每個(gè)元素 GetElem(LB, i, e); / 取 LB 中第 i 個(gè)數(shù)據(jù)元素賦給 e ifif (! !LocateElem( LA, e, equal( ) ) ListInsert( LA, +La_len, e );/ 當(dāng) LA 中不存在和 e 值相同的數(shù)據(jù)元素時(shí)進(jìn)行插入 / for / purge第二章第二章 線性表線性表2.1.2 線性表類型的應(yīng)用線性表類型的應(yīng)用 算法分析 算法2.1的時(shí)間復(fù)雜度為O ( ListLength (LA) * listLength (LB) ) 算法2.2的時(shí)

13、間復(fù)雜度為O ( ListLength (LA) + listLength (LB) )第二章第二章 線性表線性表2.2 2.2.1 2.2.1 順序表順序表順序表順序表是線性表的順序存儲(chǔ)表示的簡稱 用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次依次存放存放線性表中的數(shù)據(jù)元素，即以存儲(chǔ)位置相鄰存儲(chǔ)位置相鄰表示位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系(有序?qū)?以表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址線性表的基地址。如下圖所示第二章第二章 線性表線性表2.2.1 順序表后繼元素的存儲(chǔ)地址和其前驅(qū)元素相隔一個(gè)常量c即：LOC( ai ) = LOC( ai-1 ) + C C則任

14、意元素ai相對(duì)于第一個(gè)元素a1的存儲(chǔ)地址為 LOC(ai ) = LOC(a1 ) + (i-1)C 基地址基地址 第二章第二章 線性表線性表2.2.1 順序表用C語言描述的順序表類型順序表類型如下所示： / / 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) #define LIST_INIT_SIZE 100; /初始分配量 #define LISTINCREMENT 10; /分配增量typedef structtypedef struct ElemType * *elem; / 存儲(chǔ)空間基址 intint length; / 當(dāng)前長度 intint listsize; / 允許的最大存儲(chǔ)容量(以sizeofsize

15、of(ElemType)為單位) SqList;/ 俗稱 順序表順序表第二章第二章 線性表線性表2.2.1 順序表/ / 基本操作接口基本操作接口( (函數(shù)聲明函數(shù)聲明) ) voidvoid InitList ( SqList & &L, intint maxsize );/構(gòu)造一個(gè)最大存儲(chǔ)容量為 maxsize 的空的順序表 L。 voidvoid DestroyList ( SqList & &L )/銷毀順序表 L。 boolbool ListEmpty ( SqList L )/若順序表 L 為空表，則返回TRUETRUE，否則返回 FALSEFALS

16、E。 intint ListLength ( SqList L )/返回順序表 L 中元素個(gè)數(shù)。 intint PriorElem ( SqList L, ElemType cur_e )/若 cur_e 是順序表 L 的元素，則返回其前驅(qū)的位序/(設(shè)第一個(gè)元素的前驅(qū)的位序?yàn)?)，否則返回 -1。第二章第二章 線性表線性表2.2.1 順序表intint NextElem ( SqList L, ElemType cur_e )/若 cur_e 是順序表 L 的元素，則返回其后繼的位(設(shè)最后一個(gè)元素的后繼的位序?yàn)長的表長+1)，否則返回-1。boolbool GetElem ( SqList L

17、, intint pos, ElemType & &e )/若1posLengthList(L)1posLengthList(L)，則用 e 帶回順序表 L 第/ pos 個(gè)元素的值且返回函數(shù)值為TRUETRUE，否則返回函數(shù)/值為FALSEFALSE。 intint LocateElem ( SqList L, ElemType e, boolbool (*compare)(ElemType, ElemType ) ) /返回順序表L中第第1 1個(gè)個(gè)與 e 滿足滿足關(guān)系 compare( ) 的數(shù)/據(jù)元素的位序。若這樣的元素不存在，則返回值為0。/ compare( )為數(shù)據(jù)

18、元素的判定函數(shù)。第二章第二章 線性表線性表2.2.1 順序表voidvoid ClearList( SqList & &L )/將順序表 L 重置為空表。boolbool PutElem ( SqList L, intint pos, ElemType & &e )/若1posLengthList(L)1posLengthList(L)，則對(duì)順序表L中第pos個(gè)元素賦值同 e 的值且返回函數(shù)值為 TRUE，否則返回函數(shù)值為 FALSE。boolbool ListInsert ( SqList & &L, intint pos, ElemType

19、e )/若存儲(chǔ)空間未滿且1posLengthList(L)+11posLengthList(L)+1，則在順序表 L 的第 pos 個(gè)元素之前插入新的元素 e，L的長度增1，且返回函數(shù)值為TRUE，否則不改變順序表且返回函數(shù)值為 FALSE。 第二章第二章 線性表線性表2.2.1 順序表boolbool ListDelete ( SqList & &L, intint pos, ElemType & &e)/若1posLengthList(L)1posLengthList(L)，則刪除順序表 L 的第 pos 個(gè)元素 e，L的長度增1，且返回函數(shù)值為TRUE，否

20、則不改變順序表且返回函數(shù)值為FALSE。第二章第二章 線性表線性表2.2.2順序表中基本操作的實(shí)現(xiàn)順序表中基本操作的實(shí)現(xiàn)下面重點(diǎn)討論順序表類型定義中五個(gè)操作的實(shí)現(xiàn) 一、初始化操作、初始化操作 二、元素定位操作二、元素定位操作 三、插入元素操作三、插入元素操作 四、刪除元素操作四、刪除元素操作 五、銷毀結(jié)構(gòu)操作五、銷毀結(jié)構(gòu)操作由于順序表的“長度”是個(gè)“顯值”，且由于第i個(gè)元素恰好存儲(chǔ)在數(shù)組的第 i 個(gè)分量(數(shù)組下標(biāo)為 i-1)中，因此其“求長”、“判空”以及“存取第 i 個(gè)數(shù)據(jù)元素”等操作都很容易實(shí)現(xiàn)。第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)一、初始化操作一、初始化操作對(duì)順序

21、表而言，初始化的實(shí)質(zhì)是為它分配一個(gè)足夠應(yīng)用的元素存儲(chǔ)空間，由用戶根據(jù)它對(duì)線性表的使用要求定義一個(gè)最大存儲(chǔ)容量 maxsize，并約定當(dāng)用戶沒有提出特殊需求(maxsize=0) 時(shí)，按予設(shè)的最大存儲(chǔ)量 LIST_INIT_SIZE 進(jìn)行分配。第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)算法算法2.42.4voidvoid InitList_Sq(SqList & &L, intint maxsize) / / 構(gòu)造一個(gè)空的線性表構(gòu)造一個(gè)空的線性表 L L ifif ( maxsize = 0 ) maxsize = LIST_INIT_SIZE; L.elem

22、= newnew ElemTypemaxsize; if if (! !L.elem) exitexit(1); / 存儲(chǔ)分配失敗L.length = 0; / 順序表的初始長度為0 L.listsize = LIST_INIT_SIZE; / 該順序表可以存儲(chǔ)元素的最大容量 / InitList此算法的時(shí)間復(fù)雜度為O O (1) (1)。 第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)二、元素定位操作 在順序表中“查詢”是否存在一個(gè)和給定值滿足判定條件的元素的最簡單的辦法是，依次取出結(jié)構(gòu)中的每個(gè)元素和給定值進(jìn)行比較。例如:順序表23754138528960L.elemL.lis

23、tsizepL.length=7e=38 50i=1算法算法 2.52.5intint LocateElem(SqList L, ElemType e,voidvoid (*compare)(ElemType, ElemType)/ / 在順序表在順序表L L中查找第中查找第1 1個(gè)值與個(gè)值與 e e 滿足判定條件滿足判定條件compare( )compare( )的元素，若找到，則返回其在的元素，若找到，則返回其在 L L 中的位序，中的位序，否則返回否則返回0 0。i = 1;/ i 的初值為第1元素的位序p = L.elem; / p 的初值為第1元素的存儲(chǔ)位置whilewhile (i

24、 = L.length & !& !(*compare)(*p+,e)+i; / 依次進(jìn)行判定ifif (i = L.length) returnreturn i; / 找到滿足判定條件的數(shù)據(jù)元素為第 i 個(gè)元素elseelse returnreturn 0; / 該線性表中不存在滿足判定的數(shù)據(jù)元素 / LocateElem 此算法的時(shí)間復(fù)雜度為：O ( ListLength(L)第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)二、元素定位操作例如:順序表23754138528960L.elemL.listsizepL.length=7e=38 50i= 1pppp

25、pppi= 2i= 3i= 4i= 5i= 6i= 7i= 8返回i= 4返回i= 0e=38 50第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)三、插入元素操作三、插入元素操作“插入元素”使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？假設(shè)在線性表的第i個(gè)元素之前插入一個(gè)元素x，使得線性表(a1 ,a2 ,ai-1, ai,ai+1 ,an ) 改變?yōu)?a1 ,a2 ,ai-1, x,ai,ai+1 ,an )即：(1) 改變了表中元素之間的關(guān)系， 使 改變?yōu)楹?(2) 表長增1由于順序表是以存儲(chǔ)位置相鄰 表示元素之間的前驅(qū)和后繼關(guān)系，則必須移動(dòng)元素來體現(xiàn)元素之間發(fā)生的變化。算法算法 2.62

26、.6（p24-p24-算法算法2.42.4）boolbool ListInsert(SqList & &L, intint pos, ElemType x)/ / 若存儲(chǔ)空間不滿且若存儲(chǔ)空間不滿且1posListlength(L)+11posListlength(L)+1，則在，則在順序表順序表 L L 的的 第第 pos pos 個(gè)元素之前插入新的元素個(gè)元素之前插入新的元素 e e 且返回且返回TRUETRUE，否則返回，否則返回 FALSEFALSEifif (pos L.length+1) return FALSEreturn FALSE ; /插入位置不合法 ifif

27、(L.length = L.listsize) return FALSEreturn FALSE;/ 當(dāng)前存儲(chǔ)空間已滿，無法插入 forfor (j=L.length-1; j=pos-1; -j)L.elemj+1 = L.elemj;/插入位置及之后的元素右移L.elempos-1 =x; / 插入 x +L.length; / 表長增1returnreturn TRUETRUE; / ListInsert 此算法的時(shí)間復(fù)雜度為：O O (ListLength(L(ListLength(L)請(qǐng)參看動(dòng)畫演示請(qǐng)參看動(dòng)畫演示ai-1.a2a1alegth ai+1ai xelemlengthli

28、stsize.a2a1alength.ai+1ai01i-1iLength-1P（P+1）q ai-1. a2 a1 ai ai+1 alegth alegth ai+1 ai x算法算法 2.6（p24-算法算法2.4）bool ListInsert(SqList &L, int pos, ElemType x)if (pos L.length+1) return FALSE ; if (L.length = L.listsize) return FALSE; for (j=L.length-1; j=pos-1; -j)L.elemj+1 = L.elemj; L.elempos-

29、1 =x; +L.length; return TRUE; / ListInsert 第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)四、刪除元素操作四、刪除元素操作(a1 ,a2 ,ai-1, ai,ai+1 ，,an )(a1 ,a2 ,ai-1,ai+1 ,an )即：(1)使和 (2) 表長減1算法算法 2.72.7boolbool ListDelete(SqList & &L, intint pos, ElemType & &e)/若若1posListlength(L)1posListlength(L)，則以，則以e e帶回從順序表帶回從順

30、序表L L 中中/刪除的第刪除的第 pos pos 個(gè)元素且返回個(gè)元素且返回 TRUETRUE，否則返回，否則返回 FALSEFALSEifif (pos L.length)return FALSEreturn FALSE ; / 刪除位置不合法 e=L.elempos-1;forfor (j = pos; jL.length; +j) L.elemj-1=L.elemj;/被刪除元素之后的元素左移 -L.length; / 表長減1return TRUEreturn TRUE; / ListDelete 此算法的時(shí)間復(fù)雜度為：O O (ListLength(L(ListLength(L) 請(qǐng)

31、參看動(dòng)畫演示請(qǐng)參看動(dòng)畫演示elemlength listsize.a2a1alength.ai+1ai01i-1iLength-1P（P+1）qbool ListDelete(SqList &L, int pos, ElemType &e) if (pos L.length)return FALSE ; / 刪除位置不合法for (j = pos; jL.length; +j) L.elemj-1=L.elemj; /被刪除元素之后的元素左移 -L.length; / 表長減1return TRUE; / ListDelete .a2a1alegth ai+1aiai-1aia

32、i+1.a2a1alegth ai+1aiai-1alegt第二章第二章 線性表線性表2.2.2 順序表中基本操作的實(shí)現(xiàn)五、銷毀結(jié)構(gòu)操作五、銷毀結(jié)構(gòu)操作算法算法 2.82.8voidvoid DestroyList( SqList & &L ) / / 釋放順序表釋放順序表 L L 所占存儲(chǔ)空間所占存儲(chǔ)空間deletedeleteL.elem;L.listsize = 0;L.length = 0; / DestroyList_Sq 此算法的時(shí)間復(fù)雜度為：O O (1)(1)第二章第二章 線性表線性表2.2.3 順序表其他算法舉例何謂順序表的“大”“小”？現(xiàn)作如下規(guī)定： 設(shè)順序

33、表A=(a1,am) B=(b1,bn) A和B分別為 A 和 B中除去最大共同前綴后的子表 若A=B=空表，則 A=B； 若A=空表，而B空表，或者兩者均不為空表， 且A的首元小于B的首元，則 AB。 例例2-4 試編寫算法“比較”兩個(gè)順序表的大小。第二章第二章 線性表線性表2.2.3 順序表其他算法舉例解題分析：解題分析：(1)算法要求對(duì)兩個(gè)順序表進(jìn)行“比較”，是一種“引用型”操作，因此在算法中算法中不應(yīng)該破壞已不應(yīng)該破壞已知表知表(2)按注解中的規(guī)定，只有在兩個(gè)表的長度相等，且每個(gè)對(duì)應(yīng)元素都相同時(shí)才相等；否則兩個(gè)順序表的大小主要取決于兩表中除去最大公共前綴后的第一個(gè)元素。因此，比較兩表的

34、大小不應(yīng)該先比較它們的長度，而應(yīng)該設(shè)一個(gè)下標(biāo)變量設(shè)一個(gè)下標(biāo)變量 j 同時(shí)控制兩個(gè)表同時(shí)控制兩個(gè)表，即對(duì)兩表中位序相同 的元素進(jìn)行比較。第二章第二章 線性表線性表2.2.3 順序表其他算法舉例算法的基本思想為： 若aj =bj，則 j 增 1，之后繼續(xù)比較后繼元素； 否則即可得出比較結(jié)果。 顯然，j 的的初值應(yīng)為初值應(yīng)為 0，循環(huán)的條件是，循環(huán)的條件是 j 不超出不超出其中任何一個(gè)表的范圍其中任何一個(gè)表的范圍。 若在循環(huán)內(nèi)不能得出比較結(jié)果，則循環(huán)結(jié)束時(shí)有三種可能出現(xiàn)的情況需要區(qū)分。根據(jù)以上分析可得下列算法第二章第二章 線性表線性表2.2.3 順序表其他算法舉例算法算法 2.9 int compa

35、re( SqList A, SqList B ) / 若若 AB，則返回，則返回 1 j=0;while ( jA.length & jB.length )if ( A.elemj B.elemj ) return(1);else j+; if ( A.length = B.length ) return (0); else if ( A.length data 表示結(jié)點(diǎn)表示結(jié)點(diǎn)ai的的數(shù)據(jù)域數(shù)據(jù)域， p-next 表示結(jié)點(diǎn)表示結(jié)點(diǎn)ai 的的指針域指針域， 若非空，則指向其若非空，則指向其后繼后繼結(jié)點(diǎn)結(jié)點(diǎn)ai+1。 指針型變量只能作指針型變量只能作同類型同類型的的指針指針賦值與賦值與比

36、較比較操作。操作。指針型變量的指針型變量的賦值賦值：1.由同類型的指針變量賦值由同類型的指針變量賦值2.都必須用都必須用 C 語言中的語言中的動(dòng)態(tài)分配函數(shù)動(dòng)態(tài)分配函數(shù)得到。得到。例如，例如，p = new LNode; delete p2.3 2.3.1 單鏈表和指針單鏈表和指針2.3 2.3.2 單鏈表中基本操作的實(shí)現(xiàn)單鏈表中基本操作的實(shí)現(xiàn) 線性表的線性表的五個(gè)基本操作五個(gè)基本操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)。 一、初始化操作一、初始化操作 建立一個(gè)空的鏈表建立一個(gè)空的鏈表算法算法2.13void InitList( SLink &L )/ 創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表創(chuàng)

37、建一個(gè)帶頭結(jié)點(diǎn)的空鏈表,L 為指向頭結(jié)點(diǎn)的指針為指向頭結(jié)點(diǎn)的指針L = new LNode;if (!L) exit(1); / 存儲(chǔ)空間分配失敗存儲(chǔ)空間分配失敗L-next = NULL; /InitList 算法的時(shí)間復(fù)雜度為O (1)。二、銷毀結(jié)構(gòu)操作二、銷毀結(jié)構(gòu)操作 算法算法2.14void DestroyList( SLink &L)/ 銷毀以銷毀以L為頭指針的單鏈表，釋放鏈表中所有結(jié)點(diǎn)空間為頭指針的單鏈表，釋放鏈表中所有結(jié)點(diǎn)空間 while (L) p = L;L = L-next;delete p; / while L = NULL; / DestroyList算法的時(shí)間

38、復(fù)雜度為O (Listlength(L)。 三、存取元素操作三、存取元素操作單鏈表是一種單鏈表是一種“順序存取順序存取”的結(jié)構(gòu)，的結(jié)構(gòu)，即：為取第即：為取第 i 元素，首先必須先找到第元素，首先必須先找到第 i-1 個(gè)元個(gè)元素。因此不論素。因此不論 i 值為多少，都必須值為多少，都必須從頭結(jié)點(diǎn)開始從頭結(jié)點(diǎn)開始起起點(diǎn)數(shù)點(diǎn)數(shù)，直數(shù)到，直數(shù)到第第 i 個(gè)為止個(gè)為止。頭結(jié)點(diǎn)可看成是。頭結(jié)點(diǎn)可看成是第第0個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)。算法算法2.15bool GetElem ( SLink L, int pos, ElemType &e )/ 若若1posLengthList(L)，則，則 e 帶回帶回L指向的

39、單鏈指向的單鏈/表表 中第中第 pos 個(gè)元素的值且返回個(gè)元素的值且返回TRUE,否則為否則為FALSEp = L-next; j =1; / 變量初始化，p 指向第一個(gè)結(jié)點(diǎn)while ( p & jnext; +j; / whileif ( !p | jpos ) return FALSE; / 不存在第 pos 個(gè)結(jié)點(diǎn)e = p-data; / 取到第 pos 個(gè)元素return TRUE; / GetElem 算法的時(shí)間復(fù)雜度為O (ListLength(L)。 四、插入元素操作四、插入元素操作在線性表中在線性表中插入插入一個(gè)元素時(shí)，使一個(gè)元素時(shí)，使改變?yōu)楦淖優(yōu)楹秃?。需要修改元?/p>

40、。需要修改元素e和元素和元素ai-1 所在結(jié)所在結(jié)點(diǎn)的指針。點(diǎn)的指針。算法的基本思想:找到第i-1個(gè)結(jié)點(diǎn)，修改相應(yīng)指針。ai-1aianep算法算法2.16bool ListInsert ( SLink &L, int pos, ElemType e )/ 若若1posLengthList(L)+1，則在第，則在第 pos 個(gè)元素之個(gè)元素之/前插入前插入e，且返回，且返回TRUE， 否則不插入返回否則不插入返回/ FALSE。 p=L; j=0;while (p & jnext; +j; / whileif (!p |jpos-1) return FALSE; / pos 小于

41、小于1 ；大于表長；大于表長+1s=new LNode;if (!s) exit(1); / 存儲(chǔ)空間分配失敗存儲(chǔ)空間分配失敗s-data=e; / 創(chuàng)建新元素的結(jié)點(diǎn)創(chuàng)建新元素的結(jié)點(diǎn)s-next=p- next; p-next=s; / 修改指針修改指針return TRUE; / ListInsert 算法時(shí)間復(fù)雜度為算法時(shí)間復(fù)雜度為O (ListLength(L)。單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-

42、1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-next=p-next; p-next=s; return OK; babaxPP單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=

43、x; s-next=p-next; p-next=s; return OK; Sxanaia1a2ai-1Lanaia1a2Pai-1L單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-next=p-next; p-next=s; return OK; 單鏈表的插入運(yùn)算單

44、鏈表的插入運(yùn)算anaia1a2ai-1LStatus ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-next=p-next; p-next=s; return OK; PPPPP單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType

45、x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-next=p-next; p-next=s; return OK; anaia1a2ai-1LPS單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;

46、s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-next=p-next; p-next=s; return OK; Panaia1a2ai-1LxS單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-ne

47、xt=p-next; p-next=s; return OK; anaia1a2ai-1LxSP單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算Status ListInsert_L(LinkList &L,int i, ElemType x)p=L; j=0;while( p&jnext; +j; if( ! p ji-1) return ERROR;s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; s-next=p-next; p-next=s; return OK; Panaia1a2ai-1LxS五、刪除元素操作五、刪除元

48、素操作刪除元素ai ai+1 不再是 ai 的后繼，而是 ai-1 的后繼，因此需要修改 ai-1 元素所在結(jié)點(diǎn)的指針。算法基本思想是：首先找到第 i-1 個(gè)結(jié)點(diǎn)，然后修改相應(yīng)指針。 ai-1aiai+1an算法算法2.17（P30-SF2.10）bool ListDelete ( SLink &L, int pos, ElemType &e)/ 若若1posLengthList(L)，則刪除單鏈表，則刪除單鏈表 中第中第 pos 元素并以元素并以 e /帶其值，返回帶其值，返回TRUE， 否則不刪除操作且返回函數(shù)值為否則不刪除操作且返回函數(shù)值為 FALSEp = L; j =

49、 0;while (p-next & j next; +j;if (!(p-next) | j i-1)return FALSE; / 刪除位置不合理q = p-next; p-next = q-next;/ 修改指針e = q-data; delete(q);/ 釋放結(jié)點(diǎn)空間 return TRUE; / ListDelete_L 算法時(shí)間復(fù)雜度為O (ListLength(L)。2.3 2.3.3 單鏈表其它算法舉例單鏈表其它算法舉例 例例2-7 逆序創(chuàng)建鏈表 假設(shè)線性表(a1，a2，an )的數(shù)據(jù)元素存儲(chǔ)在一維數(shù)組 An中，則從數(shù)組的最后一個(gè)分量起，依次生成結(jié)點(diǎn)，并逐個(gè)插入到一個(gè)

50、初始為空的鏈表中。 例如：線性表 (a,b,c,d,e) 的逆序創(chuàng)建的過程。 LeddebcaL算法算法2.19void CreateList_L(SLink &L, int n, ElemType A) / 數(shù)組數(shù)組 A 中中n 個(gè)數(shù)據(jù)元素，個(gè)數(shù)據(jù)元素， 逆序建立帶頭結(jié)點(diǎn)的單鏈表。逆序建立帶頭結(jié)點(diǎn)的單鏈表。L = new LNode;if (!L) exit(1); / 存儲(chǔ)空間分配失敗存儲(chǔ)空間分配失敗L-next = NULL;/ 建立一個(gè)帶頭結(jié)點(diǎn)的空的單鏈表建立一個(gè)帶頭結(jié)點(diǎn)的空的單鏈表for (i = n; i 0; -i) p = new LNode;if (!p) exit(

51、1); / 存儲(chǔ)空間分配失敗存儲(chǔ)空間分配失敗 p-data = Ai-1; / 賦元素值賦元素值 p-next = L-next; L-next = p; / 插入在頭結(jié)點(diǎn)之后插入在頭結(jié)點(diǎn)之后 / for / CreateList_L 容易看出，算法的時(shí)間復(fù)雜度為容易看出，算法的時(shí)間復(fù)雜度為O (ListLength(L)。例例2-8 以鏈表作存儲(chǔ)結(jié)構(gòu)將線性表 ( a1,a2,am,b1,b2,bn) 改變成 (b1,b2,bn,a1,a2,am ) 。 (1) 從鏈表中刪除( a1,a2,am )；(2) 將(b1,b2,bn )鏈接到頭結(jié)點(diǎn)之后；(3) 將( a1,a2,am) 鏈接到 b

52、n 之后。 算法算法2.20void exchange_L( SLink &L，int m )/ 本算法實(shí)現(xiàn)單鏈表中前本算法實(shí)現(xiàn)單鏈表中前 m 個(gè)結(jié)點(diǎn)和后個(gè)結(jié)點(diǎn)和后 n 個(gè)結(jié)點(diǎn)的互換個(gè)結(jié)點(diǎn)的互換if ( m & L-next ) / 鏈表不空且 m!=0 p = L-next; k = 1;while( knext; +k; / while if (p & p-next) / n!=0 時(shí)才需要修改指針 ha = L-next; / 以指針 ha 記 a1 結(jié)點(diǎn)的位置 L-next = p-next; / 將b1 結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后 p-next = NULL;/ 設(shè)

53、am 的后繼為空 q = L-next;/ 令q 指向b1 結(jié)點(diǎn)while (q-next) q = q-next; / 查找 bn 結(jié)點(diǎn)q-next = ha; / 將 a1 結(jié)點(diǎn)鏈接到bn 結(jié)點(diǎn)之后 / if(p) / if(m) / exchange_L 算法的時(shí)間復(fù)雜度為O (ListLength(L)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)勢在于：(1) 能有效利用存儲(chǔ)空間；(2) 用“指針”指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行“插入”、“刪除”等操作；劣勢則是：1）不能隨機(jī)存取數(shù)據(jù)元素。丟失了一些順序表有的長處，如線性表的“表長”和數(shù)據(jù)元素在線性表中的“位序”，在上述的單鏈表中都看不見了。2）不便于在表尾插入元素，需遍歷整個(gè)表才能找到插入的位置。 2.3 2.3.4 循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表循環(huán)鏈表(Circular Linked List)是線性表的另一種形式的鏈?zhǔn)酱鎯?chǔ)表示。 特點(diǎn)：是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表成為一個(gè)由鏈指針相鏈接的環(huán)，并且將頭指針設(shè)成指向最后一個(gè)結(jié)點(diǎn)。 循環(huán)鏈表的操作和單鏈表基本一致，差別僅在于，判別鏈表