線性表課件

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

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

3、元素有且僅有一個直接后繼,,5,2.1 線性表的類型定義,ADT List定義,,ADT List{ 數(shù)據(jù)對象：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)造一個空的線性表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ù)元素的個數(shù),6,2.1 線性表的類型定義,ADT List定義,,GetElem(L, i ,&e) 初始條件：線性表L已存在，1≤i≤ListLength(L) 操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值 LocateElem(L, e, compare( ))

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

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

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

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

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

11、大線性表La，將存在于線性表Lb中而不存在于線性表La中的數(shù)據(jù)元素插入到線性表La中去。步驟：1．從線性表LB中依次取得每個數(shù)據(jù)元素; 2．依值在線性表LA中進行查訪; 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); // 求線性表的長度 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i個數(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表的長度,10,2.1 線性表的類型定義,基于ADT List的算法設(shè)計例2-2 已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列，要求將La和Lb歸并成一個新的線性表Lc，且

14、Lc中的數(shù)據(jù)元素仍按值非遞減有序排列。輸入：線性表La、線性表Lb(均按值非遞減有序排列) 輸出：Lc(按值非遞減有序排列) ?merge(La, Lb, &Lc) 處理方法：∵La和Lb均按值非遞減有序排列 ∴設(shè)置兩個位置指示器i和j，分別指向La和Lb中的某個元素，初始均指向第1個。比較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é)論使用不同的算法策略，可得到不同時間復雜度的算法輸入線性表的特征會影響算法的策略（是否有序？…）輸出線性表的特征會影響算法的策略（是否有序？…）,,14,2.2 線性表的順序表示和實現(xiàn),定義：用一組地址連續(xù)的存儲單元依次存儲線性表中

19、的數(shù)據(jù)元素特點：邏輯上相鄰，物理上也相鄰。隨機存取,,68 89 70 67 40 78,邏輯序號 1 2 3 4 5 6,C數(shù)組下標 0 1 2 3 4 5,陳述問題時用,15,2.2 -順序表的存儲,,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 –類型定義與基本操作實現(xiàn),順序表定義方案一#define LIST_SIZE 100typedef struct{ ElemTypeelem[LIST_SIZE];/* 存儲空間*/ intlength;/* 當

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

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

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

24、定義與基本操作實現(xiàn),基本操作的實現(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 –類型定義與基本操作實現(xiàn),基本操作的實現(xiàn)初

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

26、exit(OVERFLOW);// 存儲分配失敗 L.length = 0;// 空表長度為0 L.listsize = LIST_INIT_SIZE;// 初始存儲容量 return OK;} // InitList_Sq,,21,2.2 –類型定義與基本操作實現(xiàn),基本操作的實現(xiàn)求表長 L.length取第i個元素 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 –插入操作的實現(xiàn),基本操作的實現(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 –插入操作的實現(xiàn),插入操作——算法設(shè)計(算法2.4)參數(shù)：順序表&L、插入位置i、插入元素e插入分析：第i個位置放e，則原來第i~L.length個數(shù)據(jù)元素必須先后移，以騰出第i個位置; 后移的順序是從最后一個元素開

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

31、間：申請成功則原空間的元素復制到新空間，修改L.listsize，再進行插入工作；否則報錯退出。,,24,2.2 –插入操作的實現(xiàn),Status ListInsert_Sq( SqList &L, int i, ElemType e) { // 位置合法性的判斷 if ( iL.length +1 )return ERROR; // 上溢時增加空間的分配 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 –插入操作的實現(xiàn),時間復雜度頻次最高的操作：移動元素上溢時，空間的再分配與復制(realloc操作)分攤到每次插入操作中若線性表的長度為n，則：最好

34、情況：插入位置i為n+1，此時無須移動元素，T(n)=O(1);最壞情況：插入位置i為1，此時須移動n個元素， T(n)=O(n);平均情況：假設(shè)pi為在第i個元素之前插入一個元素的概率，則：插入時移動次數(shù)的期望值：等概率時，即 ，∴ T(n) = O(n)空間復雜度 S(n) = O(1),,,,,26,2.2 –刪除操作的實現(xiàn),基本操作的實現(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 –刪除操作的實現(xiàn),刪除操作——算法設(shè)計(算法2.5)參數(shù)：順序表&L、刪除位置i 刪除分析：去掉第i 個元素，則原來第i+1~L.length個數(shù)據(jù)元素必須前移，以覆蓋第i個位置; 前移的順序是從第i+1元素開始，逐個往前移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 –刪除操作的實現(xiàn),刪除操作——算法設(shè)計(算法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 –刪除操作的實現(xiàn),時間復雜度頻次最高的操作：移動元素若線性表的長度為n，則：最好情況：刪除位置i為n，此時無須移動元素，T(n)=O(1);最壞情況：刪除位置i為1，此時須前移n-

39、1個元素， T(n)=O(n);平均情況：假設(shè)qi為刪除第i個元素的概率，則：刪除時移動次數(shù)的期望值：等概率時，即 ，∴ T(n) = O(n)空間復雜度 S(n) = O(1),,,,,,,,30,2.2 –算法設(shè)計,基于順序表的算法設(shè)計例2-1和例2-2基本操作在順序表中的實現(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;基于順序表實現(xiàn)例2-1和例2-2基本操作的簡單替換，針對例2-2得到P26算法2.7,,,31,單鏈表循環(huán)鏈表靜態(tài)鏈表基于鏈表的算法設(shè)計 雙向鏈表其他表示,2.3 線性表的鏈式表示和實現(xiàn),,32,單鏈表 順序映像的弱點空間利用率不

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

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

43、即……->next； 有頭結(jié)點空表時，L指向一結(jié)點(稱為頭結(jié)點) 第一個結(jié)點和其余結(jié)點均可統(tǒng)一表示為其直接前驅(qū)結(jié)點的next域所指向的結(jié)點，即……->next。,2.3.1 單鏈表–定義,,35,基本操作的實現(xiàn)取第i個元素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個元素GetElem_L(LinkList L, int i, ElemType &e)參數(shù)：鏈表L、位置i、取得的第i個元素&e （帶頭結(jié)點的單

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

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

47、時，ai可用*(p->next)表示關(guān)鍵步驟：①使p指向ai-1 結(jié)點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é)點的算法】StatusListInsert(LinkLis

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

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

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

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

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

53、 ai+1可用*(p->next->next)表示關(guān)鍵步驟：①使p指向ai-1 結(jié)點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é)點*s插入到第一個結(jié)點之前；當有頭結(jié)點時，待插結(jié)點也可視為插入到第0個結(jié)點(頭結(jié)點)之后。插入步驟：以單鏈表中有頭結(jié)點為例，單個結(jié)點的構(gòu)造和插入步驟如下:① s = (LinkList)malloc(sizeof(LNode)); ② scanf(&s->data); ③ s->next = L->next; ④ L-

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

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

57、在O(1)時間內(nèi)由鏈表指針訪問到第一個結(jié)點和最后一個結(jié)點？——頭指針表示/尾指針表示與單鏈表在基本操作的實現(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) 問題：若語言不支持指針類型，能有鏈式存儲嗎？可以借用語言中的數(shù)組來表示鏈表——靜態(tài)鏈表 數(shù)組元素(數(shù)據(jù)元素的值、指示器)——結(jié)點類型定義

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

59、以0或負數(shù)代表空指針NULL以整型游標i代替動態(tài)指針p，以i = S[i].cur代替p = p->next取下一個元素的位置,47,2.3.3 靜態(tài)鏈表,動態(tài)分配與釋放的模擬 思想：將未使用的分量用游標cur鏈成一個備用鏈；插入時，取備用鏈中的第一個結(jié)點作為插入的新結(jié)點；刪除時將從鏈表中刪除下來的結(jié)點鏈接到備用鏈上 初始化鏈表(算法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)鏈表,動態(tài)分配與釋放的模擬 模擬動態(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;}模擬動態(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è)計,

62、例2-1順序表的實現(xiàn)：基本操作的簡單替換動態(tài)鏈表無須特意求La、Lb的長度——原目的是為了控制線性表的邊界無須每次調(diào)用GetElem_L()——它可以和外層的循環(huán)合二為一無須每次調(diào)用ListInsert_L()——可以引入指針變量記錄La的尾結(jié)點的位置 可以利用Lb的原有結(jié)點空間——前提：Lb本身不再被使用,50,2.3.4 基于鏈表的算法設(shè)計,動態(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的下一個結(jié)點,51,2.3.4 基于鏈表的算法設(shè)計,靜態(tài)鏈表：和動態(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的下一個結(jié)點,52,2.3.4 基于鏈表的算法設(shè)計,例2-2動態(tài)鏈表： (算法2.12, P31)例2-3 (算法2.17, P33~34

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

69、入刪除,2.3.5 雙向鏈表,,,55,存儲結(jié)構(gòu)的具體設(shè)計結(jié)合實際問題操作的特征以及環(huá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、有序表 ——一種特殊的線性表有序順序表、有序鏈表插入操作的特殊性：對于有序表，在插入一個元素時，無須給出插入位置；其插入位置與插入元素的值(序關(guān)鍵字)相關(guān)。,2.3.6 其他表示,,,57,問題描述——合并、分解問題，側(cè)重在鏈表若干源表按一定條件合并成一個目標表示例：例2-1 A=A∪B; 例2-2 C=A∪B將一個源表按一定條件分解成若干目標表示例：已知一線性鏈表中含有三類字符的數(shù)據(jù)元素，試將該鏈表分割為三個循環(huán)鏈表