【正文】 ：與線性鏈表基本一致 , 差別在于算法的循環(huán)條件不是 p或 pnext是否為空， 而是他們是否等于頭指針。 （ 3）有時(shí)在循環(huán)鏈表中只設(shè)尾指針不設(shè)頭指針，可以簡(jiǎn)化某些操作，例如合并線性表操作。 說(shuō)明： 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 48/58 (a)兩個(gè)鏈表 (b)合并后的表 合并操作： HB=Bnext。 Bnext=Anext。 Anext=HBnext。 free(HB)。 A=B。 時(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。 struct DuLNode *prior。 struct DuLNode *next。 } DuLNode, *DuLinkList。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 50/58 雙向鏈表示例 n e x tp r i o r e l e m e n t結(jié) 點(diǎn) 結(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等涉及一個(gè)方向的指針的操作與線性鏈表一致 , 但插入、刪除則有很大不同 , 需要同時(shí)修改兩個(gè)方向上的指針，如下圖所示： a在 雙 向 鏈 表 中 插 入 一 個(gè)結(jié) 點(diǎn) 時(shí) 指 針 變 化 狀 況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。L， int i， ElemType e) {// 在帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表 L中第 i個(gè)位置之前插入元素 e if (!(p=GetElemP_DuL(L， i))) // 在 L中確定第 i個(gè)元素的位置指針 p return 0； //p=NUlL，即第 i個(gè)元素不存在 if (!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return 0； sdata=e； sprior=pprior； ppriornext=s； snext=p； pprior=s； return 1； }// ListInsert_DuL a在 雙 向 鏈 表 中 插 入 一 個(gè)結(jié) 點(diǎn) 時(shí) 指 針 變 化 狀 況bx……①②sp④③數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 53/58 刪除雙鏈循環(huán)線性表 L中第 i個(gè)位置的元素 int ListDelete_DuL(DuLinkList amp。L， int i， ElemType amp。e) {// 刪除帶頭結(jié)點(diǎn)的雙鏈循環(huán)線性表 L的第 i個(gè)元素 if(!(p=GetElemP_DuL(L， i))) //在 L中確定第 i個(gè)元素的位置指針 p return 0； // p=NULL，即第 i個(gè)元素不存在 e=pdata； ppriornext=pnext； pnextprior=pprior； free(p)； return 1。 }// ListDelete_DuL a在 雙 向 鏈 表 中 刪 除結(jié) 點(diǎn) 時(shí) 指 針 變 化 狀 況b c??①②p數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 54/58 四、一元多項(xiàng)式的表示及相加 一個(gè)一元多項(xiàng)式， Pn(x)可按升冪寫成： 它由 n+1個(gè)系數(shù)唯一確定，在計(jì)算機(jī)里，它可用一個(gè)線性表 P來(lái)表示： 則兩個(gè)多項(xiàng)式相加的結(jié)果（設(shè) mn） 可用線性表 R表示： ),( 20 1 nppppP ??nnn xpxpxppxP ????? ?2210)()()()( xQxPxR mnn ??),,( 1221100 nmmm ppqpqpqpqpR ?? ??????對(duì)于形如 的多項(xiàng)式 ，在存儲(chǔ)系數(shù)的同時(shí)存儲(chǔ)相應(yīng)的指數(shù)。一般情況下的一元 n次多項(xiàng)式可寫成： 對(duì)應(yīng)的線性表表示為： 20 00010 000 231)( xxxS ???memee xpxpxpxP ???? ?21 21)()),(,),(),(( 2211 mm epepep ?數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 55/58 一元多項(xiàng)式也可以有兩種存儲(chǔ)表示方法： 順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 適用范圍： 順序存儲(chǔ) ：只對(duì)多項(xiàng)式進(jìn)行“求值”等不改變多項(xiàng)式的系數(shù)和指數(shù)的運(yùn)算 鏈?zhǔn)酱鎯?chǔ) ：對(duì)多項(xiàng)式“求和”等 改變多項(xiàng)式的系數(shù)和指數(shù)的運(yùn)算 一元多項(xiàng)式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義如下： typedef struct PNode{ float coef； // 系數(shù) int expn； // 指數(shù) struct PNode *next； }PNode, *PolyType； 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 56/58 例：利用線性鏈表的基本操作來(lái)實(shí)現(xiàn)一元多項(xiàng)式的加法運(yùn)算 分析：假設(shè)一元多項(xiàng)式為 和 ，每個(gè)結(jié)點(diǎn)表示多項(xiàng)式中的一項(xiàng)，則多項(xiàng)式 A和 B的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖所示： 17817 5937)( xxxxA ???? 878 9228)( xxxxB ??? 運(yùn)算規(guī)則 如下：假設(shè)指針 qa和 qb分別指向多項(xiàng)式 A和多項(xiàng)式 B中當(dāng)前進(jìn)行比較的某個(gè)結(jié)點(diǎn)，則比較兩個(gè)結(jié)點(diǎn)中的指數(shù)項(xiàng)，有下列三種情況： （ 1） qaexpqbexp： 取 qa指針?biāo)附Y(jié)點(diǎn)插入到“和多項(xiàng)式”鏈表中去； （ 2） qaexp==qbexp： 系數(shù)相加： x=qacoef+qbcoef x≠0：修改 qa所指結(jié)點(diǎn)的系數(shù)值，同時(shí)釋放 qb所指結(jié)點(diǎn)； x=0：從多項(xiàng)式 A的鏈表中刪除相應(yīng)結(jié)點(diǎn)，并釋放指針 qa和 qb所指結(jié)點(diǎn)； （ 3） qaexpqbexp： 取 qb指針?biāo)附Y(jié)點(diǎn)插入到“和多項(xiàng)式”鏈表中去。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 57/58 void Add_Poly(PolyType A， PolyType B， PolyType amp。C) {// 對(duì)用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的兩個(gè)一元多項(xiàng)式 A和 B進(jìn)行相加運(yùn)算，結(jié)果放在 C中 qa=Anext； qb=Bnext； // qa和 qb分別指向 A和 B多項(xiàng)式鏈表中的第一個(gè)結(jié)點(diǎn) C=pre=A； // pre指向 qa的前驅(qū)； C指向多項(xiàng)式 C的頭結(jié)點(diǎn) while (qa amp。amp。 qb ) if (qaexpqbexp) { pre=qa； qa=qanext； } // qa指針后移 else if (qaexp= =qbexp) { x=qacoef+qbcoef； if (x) {qacoef=x； pre=qa； } else {prenext=qanext； free(qa)； } // 刪除 qa qa=prenext； u=qb； qb=qbnext； free(u)； } else { u=qbnext； qbnext=qa； prenext=qb； pre=qb； qb=u； }// qb插入在 qa之前 if (qb) prenext=qb； // 連接 B多項(xiàng)式的剩余部分 free(B)； // 釋放 B多項(xiàng)式的頭結(jié)點(diǎn) }// Add_Poly 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 58/58 五、本章小結(jié) ?線性表的定義及抽象數(shù)據(jù)類型的定義； ?線性表的順序表示與實(shí)現(xiàn)，線性表的順序存儲(chǔ)結(jié)構(gòu)又稱作隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)，用順序存儲(chǔ)結(jié)構(gòu)表示的線性表又稱作順序表； ?線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又稱作非隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)，鏈表有單鏈表、循環(huán)鏈表和多重鏈表； ?線性表的應(yīng)用：一元多項(xiàng)式的表示及運(yùn)算。