線性表課件

1、1,數(shù)據(jù)結(jié)構(gòu)——線性表,2,重點(diǎn)：順序表和鏈表上各種基本算法的實(shí)現(xiàn)及相關(guān)的時(shí)間性能分析難點(diǎn)：線性表應(yīng)用的算法設(shè)計(jì),第二章 線性表,3,第二章 線性表,2.1 線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 靜態(tài)鏈表 2.3.4 基于鏈表的算法設(shè)計(jì) 2.3.5 雙向鏈表

2、 2.3.6 其他表示2.4 基于線性表的應(yīng)用2.5 一元多項(xiàng)式的表示及相加,4,2.1 線性表的類型定義,定義n(≥0)個(gè)數(shù)據(jù)元素的有限序列,記作(a1, …ai-1, ai, ai+1,…, an)其中，ai 是表中數(shù)據(jù)元素，n 是表長(zhǎng)度(n=0時(shí)稱為空表)邏輯特征n>0時(shí)有且僅有一個(gè)“第一個(gè)”數(shù)據(jù)元素有且僅有一個(gè)“最后一個(gè)”數(shù)據(jù)元素除第一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)直接前驅(qū)除最后一個(gè)數(shù)據(jù)元素外，其它

3、元素有且僅有一個(gè)直接后繼,,5,2.1 線性表的類型定義,ADT List定義,,ADT List{ 數(shù)據(jù)對(duì)象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 數(shù)據(jù)關(guān)系：R={R1},R1={|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitList(&L) 操作結(jié)果：構(gòu)造一個(gè)空的線性表L DestroyList(&

4、L) 初始條件：線性表L已存在 操作結(jié)果：銷毀線性表L ClearList(&L) 初始條件：線性表L已存在 操作結(jié)果：將線性表L重置為空表 ListEmpty(L) 初始條件：線性表L已存在 操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE ListLength

5、(L) 初始條件：線性表L已存在 操作結(jié)果：返回線性表L中數(shù)據(jù)元素的個(gè)數(shù),6,2.1 線性表的類型定義,ADT List定義,,GetElem(L, i ,&e) 初始條件：線性表L已存在，1≤i≤ListLength(L) 操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值 LocateElem(L, e, compare( ))

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

7、，則用pre_e返回它的前驅(qū)， 否則操作失敗，pre_e無定義 NextElem(L, cur_e ,&next_e) 初始條件：線性表L已存在 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼， 否則操作失敗，next_e無定義

8、 ListInsert(&L, i, e) 初始條件：線性表L已存在，1≤i≤ListLength(L)+1 操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L的長(zhǎng)度加1 ListDelete(&L, i, &e) 初始條件：線性表L已存在，1≤i≤ListLength(L) 操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值

9、，L的長(zhǎng)度減1 ListTraverse(L, visit( )) 初始條件：線性表L已存在 操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，則操作失敗}ADT List,,,,7,2.1 線性表的類型定義,ADT List定義P19基本操作初始化、銷毀查詢：個(gè)體、整體動(dòng)態(tài)變化：插入、刪除重點(diǎn)掌握以下三個(gè)基本操作GetElem(L, i

10、,&e) ListInsert(&L, i, e) ListDelete(&L, i, &e),,8,2.1 線性表的類型定義,基于ADT List的算法設(shè)計(jì)例2-1 假設(shè)利用兩個(gè)線性表La和Lb分別表示兩個(gè)集合A和B（即：線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個(gè)新的集合A＝A∪B。輸入：線性表La、線性表Lb輸出：變化了的La?union(&La, Lb)處理方法：擴(kuò)

11、大線性表La，將存在于線性表Lb中而不存在于線性表La中的數(shù)據(jù)元素插入到線性表La中去。步驟：1．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素; 2．依值在線性表LA中進(jìn)行查訪; 3．若不存在，則插入之。算法：算法2.1 P20,,ListLengthGetElem,LocateElem,ListInsert,,9,2.1 線性表的類型定義,void union(List &La, List Lb) { // 將所有在

12、線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中 La_len = ListLength(La); Lb_len = ListLength(Lb); // 求線性表的長(zhǎng)度 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i個(gè)數(shù)據(jù)元素賦給e if(!LocateElem(La, e, equ

13、al)) // La中不存在和e相同的元素，則插入之 ListInsert(La, ++La_len, e); }} // union,,T(na, nb) =O(nb*na), na、nb表示A表和B表的長(zhǎng)度,10,2.1 線性表的類型定義,基于ADT List的算法設(shè)計(jì)例2-2 已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列，要求將La和Lb歸并成一個(gè)新的線性表Lc，且

14、Lc中的數(shù)據(jù)元素仍按值非遞減有序排列。輸入：線性表La、線性表Lb(均按值非遞減有序排列) 輸出：Lc(按值非遞減有序排列) ?merge(La, Lb, &Lc) 處理方法：∵La和Lb均按值非遞減有序排列 ∴設(shè)置兩個(gè)位置指示器i和j，分別指向La和Lb中的某個(gè)元素，初始均指向第1個(gè)。比較i和j所指向的元素ai和bj，選取值小的插入到Lc的尾部，并使相應(yīng)的位置指示器向后移。算法：算法2.2 P21,,,11,

15、2.1 線性表的類型定義,void MergeList(List La, List Lb, List &Lc) { // 已知線性表La和Lb中的元素按值非遞減排列。 // 歸并La和Lb得到新的線性表Lc，Lc的元素按值非遞減排列。 InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListL

16、ength(Lb); while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; }el

17、se { ListInsert(Lc, ++k, bj); ++j; } },,12,2.1 線性表的類型定義,while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } while (j <= Lb_len) { GetElem(Lb, j++

18、, bj); ListInsert(Lc, ++k, bj); }} // MergeList,,T(na, nb) =O(na+nb),13,2.1 線性表的類型定義,結(jié)論使用不同的算法策略，可得到不同時(shí)間復(fù)雜度的算法輸入線性表的特征會(huì)影響算法的策略（是否有序？…）輸出線性表的特征會(huì)影響算法的策略（是否有序？…）,,14,2.2 線性表的順序表示和實(shí)現(xiàn),定義：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中

19、的數(shù)據(jù)元素特點(diǎn)：邏輯上相鄰，物理上也相鄰。隨機(jī)存取,,68 89 70 67 40 78,邏輯序號(hào) 1 2 3 4 5 6,C數(shù)組下標(biāo) 0 1 2 3 4 5,陳述問題時(shí)用,15,2.2 -順序表的存儲(chǔ),,LOC(a i+1) = LOC( a i )+lLOC(a i) = LOC(a1)+(i-1)*l,1 2 …

20、 i … … … n,,,,,,,,,,a a+l … a+(i-1)*l … … … a+(n-1)*l idle,,,,,16,2.2 –類型定義與基本操作實(shí)現(xiàn),順序表定義方案一#define LIST_SIZE 100typedef struct{ ElemTypeelem[LIST_SIZE];/* 存儲(chǔ)空間*/ intlength;/* 當(dāng)

21、前長(zhǎng)度*/}SqList_static; 評(píng)價(jià)：1)LIST_SIZE過小，則會(huì)導(dǎo)致順序表上溢；2) LIST_SIZE過大，則會(huì)導(dǎo)致空間的利用率不高,,17,2.2 –類型定義與基本操作實(shí)現(xiàn),方案二#define LIST_INIT_SIZE 100/* 存儲(chǔ)空間的初始分配量*/#define LISTINCREMENT 10/* 存儲(chǔ)空間的分配增量 */typedef struct{ Elem

22、Type*elem;/* 存儲(chǔ)空間的基址*/ intlength; /* 當(dāng)前長(zhǎng)度*/ intlistsize;/* 當(dāng)前分配的存儲(chǔ)容量*/}SqList; 該方案解決方案一中的“上溢”問題和“空間利用率不高”問題 ，但是有時(shí)間和空間代價(jià)的 。1) 必須記載當(dāng)前線性表的實(shí)際分配的空間大小；2) 當(dāng)線性表不再使用時(shí)，應(yīng)釋放其所占的空間；3) 要求實(shí)現(xiàn)級(jí)的語言能提供空間的動(dòng)態(tài)分配與釋放管

23、理。,,18,2.2 –類型定義與基本操作實(shí)現(xiàn),C中的動(dòng)態(tài)分配與釋放函數(shù)void *malloc(unsigned int size)生成一大小為size的結(jié)點(diǎn)空間，將該空間的起始地址賦給p；free(void *p)回收p所指向的結(jié)點(diǎn)空間;void *realloc(void *p, unsigned int size)將p所指向的已分配內(nèi)存區(qū)的大小改為size，size可以比原分配的空間大或小。,,,19,2.2 –類型

24、定義與基本操作實(shí)現(xiàn),基本操作的實(shí)現(xiàn)P10/* 函數(shù)結(jié)果狀態(tài)代碼*/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2/* 函數(shù)結(jié)果狀態(tài)類型，其值為上述的狀態(tài)代碼*/typedefintStatus;,,20,2.2 –類型定義與基本操作實(shí)現(xiàn),基本操作的實(shí)現(xiàn)初

25、始化 Status InitList_Sq(SqList &L)Status InitList_Sq( SqList &L) { // 構(gòu)造一個(gè)空的線性表L L.elem = (ElemType *) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if ( L.elem == NULL )

26、exit(OVERFLOW);// 存儲(chǔ)分配失敗 L.length = 0;// 空表長(zhǎng)度為0 L.listsize = LIST_INIT_SIZE;// 初始存儲(chǔ)容量 return OK;} // InitList_Sq,,21,2.2 –類型定義與基本操作實(shí)現(xiàn),基本操作的實(shí)現(xiàn)求表長(zhǎng) L.length取第i個(gè)元素 L.elem[i-1] (0<i<L.length+1)

27、按值查找 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)){ for(i=0; i<L.length && !(*compare)(L.elem[i],e); i++); if (i<L.length) return i+1; else return 0;},,2

28、2,2.2 –插入操作的實(shí)現(xiàn),基本操作的實(shí)現(xiàn)插入操作 Status ListInsert_Sq(SqList &L, int i, ElemType e),,,,,15 23 46 16 57 10 64 ??,,,,,1 2 3 4 5 6 7 8,48,插入 e,0 1 2 3 4 5 6 7,,,,i,,

29、,,,15 23 46 16 57 10 64 ??,,,,,1 2 3 4 5 6 7 8 9,,,,48,,23,2.2 –插入操作的實(shí)現(xiàn),插入操作——算法設(shè)計(jì)(算法2.4)參數(shù)：順序表&L、插入位置i、插入元素e插入分析：第i個(gè)位置放e，則原來第i~L.length個(gè)數(shù)據(jù)元素必須先后移，以騰出第i個(gè)位置; 后移的順序是從最后一個(gè)元素開

30、始，逐個(gè)往后移for ( j = L.length; j >= i; j--) L.elem[j] = L.elem[j-1]; // 后移L.elem[i -1] = e; //第i個(gè)元素存放在L.elem[i-1]中，起始下標(biāo)為0L.length = L.length+1;合法的位置：i:1..L.length+1上溢及處理：上溢發(fā)生的條件：L.length≥L.listsize，處理：先申請(qǐng)一個(gè)有一定增量的空

31、間：申請(qǐng)成功則原空間的元素復(fù)制到新空間，修改L.listsize，再進(jìn)行插入工作；否則報(bào)錯(cuò)退出。,,24,2.2 –插入操作的實(shí)現(xiàn),Status ListInsert_Sq( SqList &L, int i, ElemType e) { // 位置合法性的判斷 if ( iL.length +1 )return ERROR; // 上溢時(shí)增加空間的分配 if( L.length >=

32、L.listsize){ newbase = (ElemType *) realloc(L.elem, (L.listsize+ LISTINCREMENT)*sizeof(ElemType)); if ( newbase == NULL ) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT;

33、 } // 插入元素 for ( j = L.length; j >= i; j--)L.elem[j] = L.elem[j-1]; L.elem[i-1] = e; L.length++; return OK;},,25,2.2 –插入操作的實(shí)現(xiàn),時(shí)間復(fù)雜度頻次最高的操作：移動(dòng)元素上溢時(shí)，空間的再分配與復(fù)制(realloc操作)分?jǐn)偟矫看尾迦氩僮髦腥艟€性表的長(zhǎng)度為n，則：最好

34、情況：插入位置i為n+1，此時(shí)無須移動(dòng)元素，T(n)=O(1);最壞情況：插入位置i為1，此時(shí)須移動(dòng)n個(gè)元素， T(n)=O(n);平均情況：假設(shè)pi為在第i個(gè)元素之前插入一個(gè)元素的概率，則：插入時(shí)移動(dòng)次數(shù)的期望值：等概率時(shí)，即 ，∴ T(n) = O(n)空間復(fù)雜度 S(n) = O(1),,,,,26,2.2 –刪除操作的實(shí)現(xiàn),基本操作的實(shí)現(xiàn)刪除操作 Status

35、ListDelete_Sq(SqList &L, int i, ElemType &e),,,,,15 23 46 16 57 10 64 ??,,,,,1 2 3 4 5 6 7 8,16,刪除 e,0 1 2 3 4 5 6 7,,,i,,,,,15 23 46 57 10 64 ??

36、,,,,,1 2 3 4 5 6 7,,,27,2.2 –刪除操作的實(shí)現(xiàn),刪除操作——算法設(shè)計(jì)(算法2.5)參數(shù)：順序表&L、刪除位置i 刪除分析：去掉第i 個(gè)元素，則原來第i+1~L.length個(gè)數(shù)據(jù)元素必須前移，以覆蓋第i個(gè)位置; 前移的順序是從第i+1元素開始，逐個(gè)往前移for ( j = i; j < L.length ; j++)L.elem[j-1] = L.e

37、lem[j]; L.length = L.length-1;合法的位置：i:1..L.length下溢及處理：下溢發(fā)生的條件：L.length≤0處理：隱含在i的條件中,,28,2.2 –刪除操作的實(shí)現(xiàn),刪除操作——算法設(shè)計(jì)(算法2.5)Status ListDelete_Sq( SqList &L, int i) { // 位置合法性的判斷 if ( iL.length )return ERRO

38、R; // 刪除 for ( j = i; j < L.length ; j++) L.elem[j-1] = L.elem[j]; L.length--; return OK;},,29,2.2 –刪除操作的實(shí)現(xiàn),時(shí)間復(fù)雜度頻次最高的操作：移動(dòng)元素若線性表的長(zhǎng)度為n，則：最好情況：刪除位置i為n，此時(shí)無須移動(dòng)元素，T(n)=O(1);最壞情況：刪除位置i為1，此時(shí)須前移n-

39、1個(gè)元素， T(n)=O(n);平均情況：假設(shè)qi為刪除第i個(gè)元素的概率，則：刪除時(shí)移動(dòng)次數(shù)的期望值：等概率時(shí)，即 ，∴ T(n) = O(n)空間復(fù)雜度 S(n) = O(1),,,,,,,,30,2.2 –算法設(shè)計(jì),基于順序表的算法設(shè)計(jì)例2-1和例2-2基本操作在順序表中的實(shí)現(xiàn)ListLength(La) La.length GetElem(Lb, i, e) e

40、 = Lb.elem[i-1];LocateElem(La, e, equal) ListInsert(La, ++La_len, e) La.elem[La_len++] = e;基于順序表實(shí)現(xiàn)例2-1和例2-2基本操作的簡(jiǎn)單替換，針對(duì)例2-2得到P26算法2.7,,,31,單鏈表循環(huán)鏈表靜態(tài)鏈表基于鏈表的算法設(shè)計(jì) 雙向鏈表其他表示,2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn),,32,單鏈表 順序映像的弱點(diǎn)空間利用率不

41、高（預(yù)先按最大空間分配） 表的容量不可擴(kuò)充（針對(duì)順序表的方案一） 即使表的容量可以擴(kuò)充（針對(duì)順序表的方案二），由于其空間再分配和復(fù)制的開銷，也不允許它頻繁地使用插入或刪除時(shí)需移動(dòng)大量元素鏈表定義特點(diǎn)邏輯上相鄰的元素，物理上未必相鄰；非隨機(jī)存取,2.3.1 單鏈表–定義,,33,鏈表定義結(jié)點(diǎn)-數(shù)據(jù)元素的存儲(chǔ)映像，包括數(shù)據(jù)域和指針域（其信息稱為指針或鏈）頭指針-鏈表存取的開始 ；空(NULL)-最后一個(gè)結(jié)點(diǎn)的指針,2.3.1

42、 單鏈表–定義,,頭指針,,,,,,,,,34,鏈表定義typedef struct LNode{ ElemType data;//數(shù)據(jù)域 struct LNode *next;//后向指針域}LNode, *LinkList;單鏈表中是否引入頭結(jié)點(diǎn)？無頭結(jié)點(diǎn)空表時(shí)，L為NULL 第一個(gè)結(jié)點(diǎn)無前驅(qū)結(jié)點(diǎn),只能通過某指針變量來指向，如L； 其余結(jié)點(diǎn)均有前驅(qū)結(jié)點(diǎn)，故可通過其直接前驅(qū)結(jié)點(diǎn)的next域來指向，

43、即……->next； 有頭結(jié)點(diǎn)空表時(shí)，L指向一結(jié)點(diǎn)(稱為頭結(jié)點(diǎn)) 第一個(gè)結(jié)點(diǎn)和其余結(jié)點(diǎn)均可統(tǒng)一表示為其直接前驅(qū)結(jié)點(diǎn)的next域所指向的結(jié)點(diǎn)，即……->next。,2.3.1 單鏈表–定義,,35,基本操作的實(shí)現(xiàn)取第i個(gè)元素GetElem_L(LinkList L, int i, ElemType &e) 插入操作ListInsert_L(LinkList &L, int i, ElemType

44、e)刪除操作ListDelete_L(LinkList &L, int i, ElemType &e)創(chuàng)建單鏈表CreateList_L(LinkList &L) 頭插法尾插法,2.3.1 單鏈表–基本操作,,36,取第i個(gè)元素GetElem_L(LinkList L, int i, ElemType &e)參數(shù)：鏈表L、位置i、取得的第i個(gè)元素&e （帶頭結(jié)點(diǎn)的單

45、鏈表）算法 帶頭結(jié)點(diǎn)的單鏈表中取第i個(gè)元素Status GetElem_L( LinkList L, int i, ElemType &e) { // j表示當(dāng)前p所指向的元素在線性表中的位序 p = L->next; j = 1; while ( j next; j++;// 后移指針并計(jì)數(shù)j } if ( p == NULL || j > i)return ERROR;/

46、/ 第i個(gè)元素不存在 e = p->data;// 取第i個(gè)元素 return OK; },2.3.1 單鏈表–取第i個(gè)元素,,T(n) =O(n),37,插入操作ListInsert_L(LinkList &L, int i, ElemType e)【設(shè)計(jì)思路】相關(guān)結(jié)點(diǎn)：ai-1和ai結(jié)點(diǎn)的表示：引入指針變量LinkList p;∵鏈表結(jié)點(diǎn)的指針域是指向該結(jié)點(diǎn)的直接后繼∴當(dāng)p指向ai-1

47、時(shí)，ai可用*(p->next)表示關(guān)鍵步驟：①使p指向ai-1 結(jié)點(diǎn)p≠NULL，則② s = (LinkList)malloc (sizeof(LNode));③ s->data = e;④ s->next = p->next;⑤ p->next = s;,2.3.1 單鏈表–插入操作,,T(n) =O(n),38,【有頭結(jié)點(diǎn)的算法】StatusListInsert(LinkLis

48、t &L, int i, ElemType e){ // 有頭結(jié)點(diǎn)，無須對(duì)i為1的插入位置作特殊處理 p = L; j = 0;// 對(duì)p,j初始化; *p為L(zhǎng)的第j個(gè)結(jié)點(diǎn) while( p != NULL && jnext; j++;// 尋找第i-1個(gè)結(jié)點(diǎn)的位置 } if( p == NULL || j>i-1) return ERROR;

49、// i小于1或大于表長(zhǎng) s = (LinkList )malloc(sizeof(LNode));// 生成新結(jié)點(diǎn) if ( s == NULL ) exit(OVERFLOW);// 空間分配不成功，報(bào)錯(cuò)返回 s->data = e; s->next = p->next; // 插入L中 p->next = s; return OK; },2.

50、3.1 單鏈表–插入操作,,39,【無頭結(jié)點(diǎn)的算法】StatusListInsert(LinkList &L, int i, ElemType e){ //無頭結(jié)點(diǎn)，須對(duì)i為1的插入位置作特殊處理 if ( i==1){ s = (LinkList )malloc(sizeof(LNode)); // 生成新結(jié)點(diǎn) if ( s == NULL ) e

51、xit(OVERFLOW); // 空間分配不成功，報(bào)錯(cuò)返回 s->data = e; s->next = L;// 插入到鏈表L中 L = s; // 修改鏈頭指針L }else{ p = L; j = 1; // 對(duì)p,j初始化; *p為鏈表的第j個(gè)結(jié)點(diǎn) …… //同有頭結(jié)點(diǎn)算法的處理：①~⑤ } return OK;

52、}【思考】對(duì)比無頭結(jié)點(diǎn)和有頭結(jié)點(diǎn)在插入算法上的不同，分析其中的原因。,2.3.1 單鏈表–插入操作,,40,刪除操作ListDelete_L(LinkList &L, int i, ElemType &e)【設(shè)計(jì)思路】相關(guān)結(jié)點(diǎn)：ai-1、ai和ai+1結(jié)點(diǎn)的表示：引入指針變量LinkList p;∵鏈表結(jié)點(diǎn)的指針域是指向該結(jié)點(diǎn)的直接后繼∴當(dāng)p指向ai-1時(shí)，ai可用*(p->next)表示，

53、 ai+1可用*(p->next->next)表示關(guān)鍵步驟：①使p指向ai-1 結(jié)點(diǎn)P->next≠NULL，則② q = p->next;③ p->next = p->next->next;④ free(q);,2.3.1 單鏈表–刪除操作,,T(n) =O(n),41,創(chuàng)建單鏈表 CreateList_L(LinkList &L) 頭插法尾插法,2

54、.3.1 單鏈表–創(chuàng)建操作,,42,頭插法(算法2.11, P30) 思想：每次將待插結(jié)點(diǎn)*s插入到第一個(gè)結(jié)點(diǎn)之前；當(dāng)有頭結(jié)點(diǎn)時(shí)，待插結(jié)點(diǎn)也可視為插入到第0個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn))之后。插入步驟：以單鏈表中有頭結(jié)點(diǎn)為例，單個(gè)結(jié)點(diǎn)的構(gòu)造和插入步驟如下:① s = (LinkList)malloc(sizeof(LNode)); ② scanf(&s->data); ③ s->next = L->next; ④ L-

55、>next = s;算法分析：由上可看出每次插入一個(gè)結(jié)點(diǎn)所需的時(shí)間為O(1)∴頭插法創(chuàng)建單鏈表的時(shí)間復(fù)雜度 T(n) = O(n),2.3.1 單鏈表–創(chuàng)建操作,,43,尾插法思想：待插結(jié)點(diǎn)*s插入到最后一個(gè)結(jié)點(diǎn)之后 。插入步驟：① 獲得最后一個(gè)結(jié)點(diǎn)的位置,使p指向該結(jié)點(diǎn) ② p->next = (LinkList)malloc( sizeof(LNode));③ p = p->next; ④ scanf(

56、 &p->data ); ⑤ p->next = NULL;算法分析：要想獲取最后一個(gè)結(jié)點(diǎn)的位置，必須從頭指針開始順著next鏈搜索鏈表的全部結(jié)點(diǎn)，該過程的時(shí)間復(fù)雜度是 O(n)。如果每次插入都按此方法獲取最后一個(gè)結(jié)點(diǎn)的位置，則整個(gè)創(chuàng)建算法的時(shí)間復(fù)雜度為T(n) = O(n2)。,2.3.1 單鏈表–創(chuàng)建操作,,44,循環(huán)鏈表 問題1如何從一個(gè)結(jié)點(diǎn)出發(fā)，訪問到鏈表中的全部結(jié)點(diǎn)？——循環(huán)鏈表問題2如何

57、在O(1)時(shí)間內(nèi)由鏈表指針訪問到第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)？——頭指針表示/尾指針表示與單鏈表在基本操作的實(shí)現(xiàn)上的差異如鏈表的創(chuàng)建循環(huán)結(jié)束條件的判斷:p==NULL => p->next==L,2.3.2 循環(huán)鏈表,,,45,2.3.3 靜態(tài)鏈表,靜態(tài)鏈表 (P31~34) 問題：若語言不支持指針類型，能有鏈?zhǔn)酱鎯?chǔ)嗎？可以借用語言中的數(shù)組來表示鏈表——靜態(tài)鏈表 數(shù)組元素(數(shù)據(jù)元素的值、指示器)——結(jié)點(diǎn)類型定義

58、#define MAXSIZE1000typedef struct{ ElemTypedata; intcur;//替代動(dòng)態(tài)鏈表結(jié)點(diǎn)中的指針域}component, SLinkList[MAXSIZE];,46,2.3.3 靜態(tài)鏈表,與動(dòng)態(tài)鏈表使用上的差異鏈表的結(jié)點(diǎn)是數(shù)組中的一個(gè)分量數(shù)組分量中的cur代替動(dòng)態(tài)鏈表中的指針域，用來指示直接后繼或直接前驅(qū)結(jié)點(diǎn)在數(shù)組中的相對(duì)位置數(shù)組的第0個(gè)分量可視為頭結(jié)點(diǎn)

59、以0或負(fù)數(shù)代表空指針NULL以整型游標(biāo)i代替動(dòng)態(tài)指針p，以i = S[i].cur代替p = p->next取下一個(gè)元素的位置,47,2.3.3 靜態(tài)鏈表,動(dòng)態(tài)分配與釋放的模擬 思想：將未使用的分量用游標(biāo)cur鏈成一個(gè)備用鏈；插入時(shí)，取備用鏈中的第一個(gè)結(jié)點(diǎn)作為插入的新結(jié)點(diǎn)；刪除時(shí)將從鏈表中刪除下來的結(jié)點(diǎn)鏈接到備用鏈上 初始化鏈表(算法2.14, P33)space[0].cur為備用鏈的頭指針，cur為0表示空指針voi

60、d InitSpace_SL(SLinkList &space){　for( i=0 ; i < MAXSIZE-1; i++) space[i].cur=i+1;　space[MAXSIZE-1].cur = 0;},48,2.3.3 靜態(tài)鏈表,動(dòng)態(tài)分配與釋放的模擬 模擬動(dòng)態(tài)分配(算法2.15, P33) int Malloc_SL(SLinkList &space){ i =

61、space[0].cur; if ( space[0].cur!=0 ) space[0].cur = space[i].cur; return i;}模擬動(dòng)態(tài)釋放(算法2.16, P33) void Free_SL(SLinkList &space, int k){ space[k].cur = space[0].cur; space[0].cur = k;},49,2.3.4 基于鏈表的算法設(shè)計(jì),

62、例2-1順序表的實(shí)現(xiàn)：基本操作的簡(jiǎn)單替換動(dòng)態(tài)鏈表無須特意求La、Lb的長(zhǎng)度——原目的是為了控制線性表的邊界無須每次調(diào)用GetElem_L()——它可以和外層的循環(huán)合二為一無須每次調(diào)用ListInsert_L()——可以引入指針變量記錄La的尾結(jié)點(diǎn)的位置 可以利用Lb的原有結(jié)點(diǎn)空間——前提：Lb本身不再被使用,50,2.3.4 基于鏈表的算法設(shè)計(jì),動(dòng)態(tài)鏈表：算法需要重新整合！void Union_L(LinkList

63、 &La, LinkList &Lb){ for ( pa = La; pa->next != NULL; pa=pa->next); for ( pb = Lb; pb->next !=NULL; ){ e = pb->next->data; for(qa = La->next; qa != NULL && !equal(qa->dat

64、a, e) ; qa=qa->next); if (qa == NULL) { pa->next = pb->next; pa = pa->next; pb->next = pb->next->next; } else pb = pb->next; }//end of for pa->next

65、 = NULL; },查到，取Lb的下一個(gè)結(jié)點(diǎn),51,2.3.4 基于鏈表的算法設(shè)計(jì),靜態(tài)鏈表：和動(dòng)態(tài)鏈表類似，也需要重新整合！void Union_SL(SLinkList &space, int &sla, int &slb){ for ( pa = sla; space[pa].cur != 0; pa=space[pa].cur); for ( pb = slb; space[pb].cur!

66、=0; ){ e = space[space[pb].cur]].data; for(qa = space[pa].cur; qa != 0 && !equal(space[qa].data, e) ; qa=space[qa].cur); if (qa == 0) { space[pa].cur = space[pb].cur; pa =

67、space[pa].cur; space[pb].cur = space[space[pb].cur].cur; } else pb = space[pb].cur ; }//end of for space[pa].cur = 0; },查到，取Lb的下一個(gè)結(jié)點(diǎn),52,2.3.4 基于鏈表的算法設(shè)計(jì),例2-2動(dòng)態(tài)鏈表： (算法2.12, P31)例2-3 (算法2.17, P33~34

68、)求差集，即(A-B)U(B-A),53,雙向鏈表 問題如何在O(1)時(shí)間內(nèi)找到一個(gè)結(jié)點(diǎn)的直接前驅(qū)和后繼？——雙向鏈表類型定義typedef struct DuLNode{ ElemTypedata; struct DuLNode*prior; struct DuLNode*next;}DuLNode, *DuLinkList;基本操作：插入、刪除,2.3.5 雙向鏈表,,,54,雙向鏈表 插

69、入刪除,2.3.5 雙向鏈表,,,55,存儲(chǔ)結(jié)構(gòu)的具體設(shè)計(jì)結(jié)合實(shí)際問題操作的特征以及環(huán)境進(jìn)行選取如單鏈表的另一種結(jié)構(gòu)typedef struct LNode{ElemTypedata;struct LNode*next;}LNode, *Link, *Position;typedef struct {Linkhead, tail;intlen;}LinkList;,2.3.6 其他表示,,,56,

70、有序表 ——一種特殊的線性表有序順序表、有序鏈表插入操作的特殊性：對(duì)于有序表，在插入一個(gè)元素時(shí)，無須給出插入位置；其插入位置與插入元素的值(序關(guān)鍵字)相關(guān)。,2.3.6 其他表示,,,57,問題描述——合并、分解問題，側(cè)重在鏈表若干源表按一定條件合并成一個(gè)目標(biāo)表示例：例2-1 A=A∪B; 例2-2 C=A∪B將一個(gè)源表按一定條件分解成若干目標(biāo)表示例：已知一線性鏈表中含有三類字符的數(shù)據(jù)元素，試將該鏈表分割為三個(gè)循環(huán)鏈表