【正文】 。amp。 數(shù)據結構 第 2章 線性表 57/58 void Add_Poly(PolyType A， PolyType B， PolyType amp。 }// ListDelete_DuL a在 雙 向 鏈 表 中 刪 除結 點 時 指 針 變 化 狀 況b c??①②p數(shù)據結構 第 2章 線性表 54/58 四、一元多項式的表示及相加 一個一元多項式， Pn(x)可按升冪寫成： 它由 n+1個系數(shù)唯一確定，在計算機里，它可用一個線性表 P來表示： 則兩個多項式相加的結果（設 mn） 可用線性表 R表示： ),( 20 1 nppppP ??nnn xpxpxppxP ????? ?2210)()()()( xQxPxR mnn ??),( 1221100 nmmm ppqpqpqpqpR ?? ??????對于形如 的多項式 ，在存儲系數(shù)的同時存儲相應的指數(shù)。L， int i， ElemType amp。 數(shù)據結構 第 2章 線性表 50/58 雙向鏈表示例 n e x tp r i o r e l e m e n t結 點 結 構空 的 雙 向 循 環(huán) 鏈 表LA非 空 的 雙 向 循 環(huán) 鏈 表LB C設 d為 DuLinkList型變量，則顯然有： dnextprior=dpriornext=d 數(shù)據結構 第 2章 線性表 51/58 在雙向鏈表中，有些操作，如 ListLength， GetElem等涉及一個方向的指針的操作與線性鏈表一致 , 但插入、刪除則有很大不同 , 需要同時修改兩個方向上的指針，如下圖所示： a在 雙 向 鏈 表 中 插 入 一 個結 點 時 指 針 變 化 狀 況bx……①②sp④③a在 雙 向 鏈 表 中 刪 除結 點 時 指 針 變 化 狀 況b c??①②p數(shù)據結構 第 2章 線性表 52/58 在雙鏈循環(huán)線性表 L中第 i個位置之前插入元素 int ListInsert_DuL(DuLinkList amp。 struct DuLNode *next。 時間復雜度是： O(1) 數(shù)據結構 第 2章 線性表 49/58 雙向鏈表 原因 ： 單鏈表具有單向性，尋查結點的 直接前趨 執(zhí)行時間較長 在雙向鏈表的結點中有兩個指針域，其一指向直接后繼，另一指向直接前驅，雙向鏈表的結構定義如下： typedef struct DuLNode{ ElemType data。 free(HB)。 Bnext=Anext。 （ 3）有時在循環(huán)鏈表中只設尾指針不設頭指針，可以簡化某些操作，例如合并線性表操作。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)。 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ù)據結構 第 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) 當 b=f時， A中有該元素，所以刪除， 刪除過程和刪除 b相同。 space[k].data!=b) {// 在當前表中查找 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 當 b= a時，在 A中找不到該元素， k==space[7].cur=0 所以需要插入元素 a。space[i].data)； // 輸入 A的元素值 space[r].cur=i； r=i； // 插入到表尾 }// for space[r].cur=0； // 尾結點的指針為空， 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ù)據結構 第 2章 線性表 42/58 for(j=1； j=n； ++j) {// 依次輸入 B的元素，若不在當前表中， //則插入，否則刪除 scanf(b)； p=S； k=space[S].cur； // k指向集合 A中第一個結點 while(k!=space[r].cur amp。amp。S) {// 依次輸入集合 A和 B的元素，在一維數(shù)組 space中建立 //表示集合 (AB)U(BA)的靜態(tài)鏈表 InitSpace_SL(space)； // 初始化備用空間 S=Malloc_SL(space)； //生成 S的頭結點 r=S； // r指向 S的當前最后結點 scanf(m， n)； //輸入 A和 B的元素個數(shù) for (j=1； j=m； ++j) // 建立集合 A的鏈表 { i=Malloc_SL(space)； // 分配結點 scanf(amp。space， int k) {// 將下標為 k的空閑結點回收到備用鏈表 space[k].cur = space[0].cur； space[0].cur=k； }// Free_SL 數(shù)據結構 第 2章 線性表 38/58 void difference(SLinkList amp。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。 數(shù)據結構 第 2章 線性表 36/58 例：以靜態(tài)鏈表實現(xiàn)集合運算 (AB)U(BA) 分析 ： 假設由終端輸入集合元素，先建立表示集合 A的靜態(tài)鏈表 S，而后在輸入集合 B的元素的同時查找 S表，若存在和 B相同的元素，則從 S表中刪除之，否則將此元素插入 S表。 } pcnext = pa?pa： pb； //插入剩余段 ,若 Pa不為空 ,則 pc next = pa //否則 , pc next = pb free(Lb)； //釋放 Lb的頭結點 } 算法的時間復雜度為 O(m+n) 數(shù)據結構 第 2章 線性表 35/58 靜態(tài)鏈表 在有的高級語言中沒有指針這種數(shù)據類型，此時，也可借用一維數(shù)組來描述線性鏈表，為了和指針型描述的線性鏈表相區(qū)別，我們給這種用數(shù)組描述的鏈表起名叫 靜態(tài)鏈表 ，其類型說明如下所示： define MAXSIZE 1000 // 鏈表的最大長度 typedef struct { ElemType data； int cur； //游標，指示結點在數(shù)組中的相對位置 }ponent， SLinkList[MAXSIZE]； 假設 S為 SLinkList型變量，若第 i個分量表示鏈表的第 k個結點，則S[i].cur指示第 k+1個結點的位置。amp。Lb， LinkList amp。 分析 ：在歸并兩個鏈表為一個鏈表時，不需要另建新表的結點空間，而只需將原來兩個鏈表中結點之間的關系解除，重新按元素值非遞減的關系將所有結點鏈接成一個鏈表即可，算法描述如下： void MergeList_L(LinkList amp。L， int n) {//輸入 n個數(shù)據元素，利用頭插法建立帶頭結點的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； Lnext=NULL； //先建立一個帶頭結點的線性鏈表 for( i = 0； i n