【正文】 插入一個新元素 x； ListDelete(amp。為使 LC中元素按值非遞減有序排列，可設(shè)兩個指針 i和 j分別指向 LA和 LB中某個元素，若設(shè) i當(dāng)前所指的元素為 a， j當(dāng)前所指的元素為 b，則當(dāng)前應(yīng)插入到 LC中的元素 c為： 顯然，指針 i和 j的初值均為 1，在所指元素插入 LC之后，在 LA或 LB中順序后移。 InitList(Lc)； i=j=1； k=0； La_len=ListLength(La)； Lb_len=ListLength(Lb)； while((i=La_len)amp。 3）做插入或刪除操作時需移動大量元素，效率不高，適合做查詢操作。 //當(dāng)前分配存儲容量 }SqList。 //存儲分配失敗 = 0。 j=i1。L， int i， ElemType amp。 j。 void Union(SqList amp。Lc) {// 已知順序線性表 La和 Lb的元素按值非遞減排列， // 歸并 La和 Lb得到新的順序線性表 Lc， Lc的元素也按值非遞減排列 i = j = k = 0。 else [k++] = [j++]。 鏈?zhǔn)酱鎯Y(jié)構(gòu)特點 ：邏輯上相鄰的元素在物理位臵上不一定相鄰 ,沒有順序存儲結(jié)構(gòu)的弱點 , 但也失去了順序表可隨機存取的優(yōu)點。 ^Lana1a2…L^( a ) 非 空 表( b ) 空 表帶 頭 結(jié) 點 的 單 鏈 表數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 25/58 ① 查找：在以 L為頭結(jié)點的單鏈表中查找值為 e的結(jié)點。 分析 ：由于鏈表的特殊性，在某個元素前插入一個元素，無需移動元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語句描述即為： snext = pnext。amp。 free(q)。 j=0。 分析 ：根據(jù)前面的插入操作可以看到，整個可用存儲空間可為多個鏈表共同享用，每個鏈表占用的空間不需預(yù)先分配，而是可以由系統(tǒng)應(yīng)需求即時生成。 pre = p。pdata)； //輸入元素值 prenext = p； pre = p； //插入 } prenext = NULL； //修改尾指針 } 算法的時間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 32/58 用頭插法建立鏈表 ? 分析，尾插法使得每次插入的元素都是最后一個結(jié)點，而頭插法恰恰相反，每次插入的元素都是首元結(jié)點，而且這個鏈表帶有頭結(jié)點。L， int n) {//輸入 n個數(shù)據(jù)元素，利用頭插法建立帶頭結(jié)點的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； Lnext=NULL； //先建立一個帶頭結(jié)點的線性鏈表 for( i = 0； i n； ++i ) { p = (LinkList)malloc(sizeof(LNode))； //生成新結(jié)點 scanf(amp。Lb， LinkList amp。 } pcnext = pa?pa： pb； //插入剩余段 ,若 Pa不為空 ,則 pc next = pa //否則 , pc next = pb free(Lb)； //釋放 Lb的頭結(jié)點 } 算法的時間復(fù)雜度為 O(m+n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 35/58 靜態(tài)鏈表 在有的高級語言中沒有指針這種數(shù)據(jù)類型，此時，也可借用一維數(shù)組來描述線性鏈表，為了和指針型描述的線性鏈表相區(qū)別，我們給這種用數(shù)組描述的鏈表起名叫 靜態(tài)鏈表 ，其類型說明如下所示： define MAXSIZE 1000 // 鏈表的最大長度 typedef struct { ElemType data； int cur； //游標(biāo)，指示結(jié)點在數(shù)組中的相對位置 }ponent， SLinkList[MAXSIZE]； 假設(shè) S為 SLinkList型變量，若第 i個分量表示鏈表的第 k個結(jié)點，則S[i].cur指示第 k+1個結(jié)點的位置。space) { // 將一維數(shù)組 space中各分量鏈成一個備用鏈表， space[0].cur為頭指針，“ 0”表示空指針 for(i=0； iMAXSIZE1； ++i) space[i].cur= i+1； space[MAXSIZE1].cur=0； }// InitSpace_SL int Malloc_SL(SLinkList amp。S) {// 依次輸入集合 A和 B的元素，在一維數(shù)組 space中建立 //表示集合 (AB)U(BA)的靜態(tài)鏈表 InitSpace_SL(space)； // 初始化備用空間 S=Malloc_SL(space)； //生成 S的頭結(jié)點 r=S； // r指向 S的當(dāng)前最后結(jié)點 scanf(m， n)； //輸入 A和 B的元素個數(shù) for (j=1； j=m； ++j) // 建立集合 A的鏈表 { i=Malloc_SL(space)； // 分配結(jié)點 scanf(amp。space[i].data)； // 輸入 A的元素值 space[r].cur=i； r=i； // 插入到表尾 }// for space[r].cur=0； // 尾結(jié)點的指針為空， r=7 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 18（ 2） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 42/58 for(j=1； j=n； ++j) {// 依次輸入 B的元素，若不在當(dāng)前表中， //則插入，否則刪除 scanf(b)； p=S； k=space[S].cur； // k指向集合 A中第一個結(jié)點 while(k!=space[r].cur amp。 P=7,k=space[7].cur=8, i=space[0].cur=30 space[0].cur= space[3].cur=9 space[3].cur= space[7].cur=8 space[7].cur=3 0 9 1 2 2 c 4 3 n 8 4 e 5 5 g 6 6 f 7 7 d 3 8 a 0 9 10 10 11 11 0 S 1 Space(0:11) （ 6） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 46/58 0 6 1 2 2 c 4 3 n 8 4 e 5 5 g 7 6 f 9 7 d 3 8 a 0 9 10 10 11 11 0 S 1 Space(0:11) 當(dāng) b=f時， A中有該元素，所以刪除， 刪除過程和刪除 b相同。 （ 3）有時在循環(huán)鏈表中只設(shè)尾指針不設(shè)頭指針，可以簡化某些操作，例如合并線性表操作。 free(HB)。 struct DuLNode *next。L， int i， ElemType amp。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 57/58 void Add_Poly(PolyType A， PolyType B， PolyType amp。 。amp。 }// ListDelete_DuL a在 雙 向 鏈 表 中 刪 除結(jié) 點 時 指 針 變 化 狀 況b c??①②p數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 54/58 四、一元多項式的表示及相加 一個一元多項式， Pn(x)可按升冪寫成： 它由 n+1個系數(shù)唯一確定，在計算機里，它可用一個線性表 P來表示： 則兩個多項式相加的結(jié)果（設(shè) mn） 可用線性表 R表示： ),( 20 1 nppppP ??nnn xpxpxppxP ????? ?2210)()()()( xQxPxR mnn ??),( 1221100 nmmm ppqpqpqpqpR ?? ??????對于形如 的多項式 ，在存儲系數(shù)的同時存儲相應(yīng)的指數(shù)。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 50/58 雙向鏈表示例 n e x tp r i o r e l e m e n t結(jié) 點 結(jié) 構(gòu)空 的 雙 向 循 環(huán) 鏈 表LA非 空 的 雙 向 循 環(huán) 鏈 表LB C設(shè) d為 DuLinkList型變量，則顯然有： dnextprior=dpriornext=d 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 51/58 在雙向鏈表中，有些操作，如 ListLength， GetElem等涉及一個方向的指針的操作與線性鏈表一致 , 但插入、刪除則有很大不同 , 需要同時修改兩個方向上的指針，如下圖所示： a在 雙 向 鏈 表 中 插 入 一 個結(jié) 點 時 指 針 變 化