【正文】 狀 況bx……①②sp④③a在 雙 向 鏈 表 中 刪 除結(jié) 點(diǎn) 時(shí) 指 針 變 化 狀 況b c??①②p數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 52/58 在雙鏈循環(huán)線性表 L中第 i個(gè)位置之前插入元素 int ListInsert_DuL(DuLinkList amp。 時(shí)間復(fù)雜度是： O(1) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 49/58 雙向鏈表 原因 ： 單鏈表具有單向性，尋查結(jié)點(diǎn)的 直接前趨 執(zhí)行時(shí)間較長(zhǎng) 在雙向鏈表的結(jié)點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前驅(qū)，雙向鏈表的結(jié)構(gòu)定義如下： typedef struct DuLNode{ ElemType data。 Bnext=Anext。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。 space[k].data!=b) {// 在當(dāng)前表中查找 p=k； k=space[k].cur； }// while 0 8 1 2 2 c 3 3 b 4 4 e 5 5 g 6 6 f 7 7 d 0 8 9 9 10 10 11 11 0 Space(0:11) S 1 當(dāng) b= a時(shí)，在 A中找不到該元素， k==space[7].cur=0 所以需要插入元素 a。amp。space， int k) {// 將下標(biāo)為 k的空閑結(jié)點(diǎn)回收到備用鏈表 space[k].cur = space[0].cur； space[0].cur=k； }// Free_SL 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 38/58 void difference(SLinkList amp。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 36/58 例：以靜態(tài)鏈表實(shí)現(xiàn)集合運(yùn)算 (AB)U(BA) 分析 ： 假設(shè)由終端輸入集合元素，先建立表示集合 A的靜態(tài)鏈表 S，而后在輸入集合 B的元素的同時(shí)查找 S表，若存在和 B相同的元素，則從 S表中刪除之，否則將此元素插入 S表。amp。 分析 ：在歸并兩個(gè)鏈表為一個(gè)鏈表時(shí)，不需要另建新表的結(jié)點(diǎn)空間，而只需將原來(lái)兩個(gè)鏈表中結(jié)點(diǎn)之間的關(guān)系解除，重新按元素值非遞減的關(guān)系將所有結(jié)點(diǎn)鏈接成一個(gè)鏈表即可，算法描述如下： void MergeList_L(LinkList amp。 Lnext = p。L， int n) {//輸入 n個(gè)數(shù)據(jù)元素，利用尾插法建立帶頭結(jié)點(diǎn)的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； pre=L。即從 “ 空表 ” 的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。amp。L, int i, ElemType amp。 分析 ：在單鏈表中刪除結(jié)點(diǎn)其操作類(lèi)似于插入操作，無(wú)需移動(dòng)元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語(yǔ)句描述即為： q=pnext。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 27/58 算法描述如下： void ListInsert_L(LinkList amp。amp。 struct LNode *next。 // 插入 La的剩余元素 while( j ) [k++] = [j++]。amp。amp。 ； //表長(zhǎng)減 1 }// ListDelete_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 18/58 插入 /刪除操作時(shí)間復(fù)雜度分析 ?基本操作：移動(dòng)元素操作 ?順序表進(jìn)行插入及刪除操作的時(shí)間復(fù)雜度為 O(n)。 //i值不合法 e=[i1]。 [i1] = e。 //初始存儲(chǔ)容量 }//InitList_Sq 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 14/58 （ 2）插入：在線性表的第 i個(gè)元素前插入一個(gè)元素 分析 ：若要在線性表的第 i個(gè)元素前插入一個(gè)元素，除非 i=n+1，否則，須將第 n至第 i（共 ni+1）個(gè)元素依次往后移動(dòng)一個(gè)位臵，如下圖所示 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 插入 25 25 12 13 21 24 28 30 42 77 1 2 3 4 5 6 7 8 序號(hào) 數(shù)據(jù)元素 9 表的長(zhǎng)度增加 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 15/58 順序表的插入 void ListInsert_Sq(SqList amp。L){ // 構(gòu)造一個(gè)空的線性表 L = (ElemType *) malloc (LIST_INIT_SIZE *sizeof(ElemType))。 //存儲(chǔ)空間基址 int length。(j=Lb_len)) {//La和 Lb均非空 GetElem(La， i， ai)； GetElem(Lb， j， bj)； if(ai=bj) { ListInsert(Lc， ++k， ai)； ++i； } else { Listlnsert(Lc， ++k， bj)； ++j； } } while(i=Lalen) { GetElem(La， i++， ai)； ListInsert(Lc， ++k， ai)； } while(j=Lb_len) { GetElem(Lb， j++， bj)； ListInsert(Lc， ++k， bj)； } }//MergeList 該算法的時(shí)間復(fù)雜度為： O(m+n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 9/58 二、線性表的順序表示與實(shí)現(xiàn) 線性表的順序表示描述 類(lèi)型定義 基本操作 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 10/58 線性表順序表示 ：是指用一組 地址連續(xù) 的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。Lc) {//已知線性表 La和 Lb中的數(shù)據(jù)元素按值非遞減排列。e) 刪除線性表中的第 i個(gè)元素； … … }ADT List 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 6/58 利用上面的基本操作，還可以進(jìn)行一些更復(fù)雜的操作，例如： 已知線性表 La和 Lb中的元素按值非遞減有序排列，現(xiàn)要求將 La和 Lb歸并為一個(gè)新的線性表 Lc，且 Lc中的數(shù)據(jù)元素仍按值非遞減有序排列。L) 初始化線性表 L，設(shè)臵為空表； ListLength(L) 求線性表的長(zhǎng)度 ； GetElem(L, i, amp。 根據(jù)它們之間的關(guān)系可以排成一個(gè)線性序列，記作： (a1， a2， … ， an) 這里的 ai(1≤i≤n)屬于 同一數(shù)據(jù)對(duì)象 ， n代表線性表的 表長(zhǎng) ，即線性表中數(shù)據(jù)元素的個(gè)數(shù)。數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 1/58 第 2章 線性表 學(xué)習(xí)目的與要求： 1．了解線性表的邏輯結(jié)構(gòu)； 2．掌握順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法； 3．掌握線性表在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本操作：查找、插入和刪除的算法； 4．能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場(chǎng)合； 5．理解靜態(tài)鏈表的定義及使用方法，并區(qū)分與單鏈表的不同。線性表是n(n≥0)個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 5/58 2. 抽象數(shù)據(jù)類(lèi)型線性表的定義 ADT List{ 數(shù)據(jù)對(duì)象： D={ai | ai∈ ElemSet， i=1， 2， … ， n， n≥0 } 數(shù)據(jù)關(guān)系： R={ai1, ai | ai1, ai ∈ D, i=1, 2, …, n } 基本操作： InitList(amp。L, i, amp。 ??????時(shí)當(dāng)時(shí)當(dāng)babbaac數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 7/58 1）初始化 i， j， k的值 2）分別求 La和 Lb的長(zhǎng)度 L