【正文】 指向 S的當(dāng)前最后結(jié)點 ,r=1 S 1 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 41/58 scanf(m， n)； //輸入 A和 B的元素個數(shù) for (j=1； j=m； ++j) // 建立集合 A的鏈表 { i=Malloc_SL(space)； // 分配結(jié)點 //每次分配結(jié)點都要改變 space[0].cur的值 scanf(amp。amp。 （ 3） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 43/58 if(k＝ =space[r].cur) { //當(dāng)前表中不存在該元素，插入在 r所指結(jié)點 //之后，且 r的位置不變 i=Malloc_SL(space)； space[i].data=b； space[i].cur=space[r].cur； space[r].cur=i； }// if 0 9 1 2 2 c 3 3 b 4 4 e 5 5 g 6 6 f 7 7 d 8 8 a 0 9 10 10 11 11 0 Space(0:11) S K==space[7].cur=0 i=8 Space[8].cur=0 Space[7].cur=8 注意此時 r=7 1 調(diào)用 Malloc_SL(space) i=space[0].cur=80 所以 space[0].cur= space[8].cur= 9 （ 4） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 44/58 當(dāng) b=b時，需要刪除元素，先查找到 b的位置， p=2， k=3，且 kspace[7].cur=8 Space[2].cur=space[3].cur=4 調(diào)用 Free_SL(space， k)； 0 3 1 2 2 c 4 3 b 9 4 e 5 5 g 6 6 f 7 7 d 8 8 a 0 9 10 10 11 11 0 Space(0:11) S Space[3].cur= space[0].cur=9 space[0].cur= k=3 r=7k=3,此時說明刪除的元素不是最后一個元素 1 （ 5） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 45/58 當(dāng) b=n時， A中沒有該元素，所以加入， 加入過程和插入 a相同。 P=5,k=6, space[5].cur= space[6].cur=7 space[6].cur= space[0].cur=9 space[0].cur=k=6 （ 7） 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 47/58 循環(huán)鏈表 循環(huán)鏈表 (CircularLinked List)是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。由此，從表中任一結(jié)點出發(fā)均可找到表中其它結(jié)點，如下圖所示： （ 1） 類型定義，存儲結(jié)構(gòu)描述與線性鏈表一致 （ 2）基本操作：與線性鏈表基本一致 , 差別在于算法的循環(huán)條件不是 p或 pnext是否為空， 而是他們是否等于頭指針。 說明： 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 48/58 (a)兩個鏈表 (b)合并后的表 合并操作： HB=Bnext。 Anext=HBnext。 A=B。 struct DuLNode *prior。 } DuLNode, *DuLinkList。L， int i， ElemType e) {// 在帶頭結(jié)點的雙鏈循環(huán)線性表 L中第 i個位置之前插入元素 e if (!(p=GetElemP_DuL(L， i))) // 在 L中確定第 i個元素的位置指針 p return 0； //p=NUlL，即第 i個元素不存在 if (!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return 0； sdata=e； sprior=pprior； ppriornext=s； snext=p； pprior=s； return 1； }// ListInsert_DuL a在 雙 向 鏈 表 中 插 入 一 個結(jié) 點 時 指 針 變 化 狀 況bx……①②sp④③數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 53/58 刪除雙鏈循環(huán)線性表 L中第 i個位置的元素 int ListDelete_DuL(DuLinkList amp。e) {// 刪除帶頭結(jié)點的雙鏈循環(huán)線性表 L的第 i個元素 if(!(p=GetElemP_DuL(L， i))) //在 L中確定第 i個元素的位置指針 p return 0； // p=NULL，即第 i個元素不存在 e=pdata； ppriornext=pnext； pnextprior=pprior； free(p)； return 1。一般情況下的一元 n次多項式可寫成： 對應(yīng)的線性表表示為： 20 00010 000 231)( xxxS ???memee xpxpxpxP ???? ?21 21)()),(,),(),(( 2211 mm epepep ?數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 55/58 一元多項式也可以有兩種存儲表示方法： 順序存儲和鏈?zhǔn)酱鎯? 適用范圍： 順序存儲 ：只對多項式進(jìn)行“求值”等不改變多項式的系數(shù)和指數(shù)的運算 鏈?zhǔn)酱鎯?：對多項式“求和”等 改變多項式的系數(shù)和指數(shù)的運算 一元多項式的鏈?zhǔn)酱鎯Y(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 例：利用線性鏈表的基本操作來實現(xiàn)一元多項式的加法運算 分析：假設(shè)一元多項式為 和 ，每個結(jié)點表示多項式中的一項，則多項式 A和 B的鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖所示： 17817 5937)( xxxxA ???? 878 9228)( xxxxB ??? 運算規(guī)則 如下：假設(shè)指針 qa和 qb分別指向多項式 A和多項式 B中當(dāng)前進(jìn)行比較的某個結(jié)點，則比較兩個結(jié)點中的指數(shù)項，有下列三種情況： （ 1） qaexpqbexp： 取 qa指針?biāo)附Y(jié)點插入到“和多項式”鏈表中去； （ 2） qaexp==qbexp： 系數(shù)相加： x=qacoef+qbcoef x≠0：修改 qa所指結(jié)點的系數(shù)值，同時釋放 qb所指結(jié)點； x=0：從多項式 A的鏈表中刪除相應(yīng)結(jié)點，并釋放指針 qa和 qb所指結(jié)點； （ 3） qaexpqbexp： 取 qb指針?biāo)附Y(jié)點插入到“和多項式”鏈表中去。C) {// 對用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的兩個一元多項式 A和 B進(jìn)行相加運算，結(jié)果放在 C中 qa=Anext； qb=Bnext； // qa和 qb分別指向 A和 B多項式鏈表中的第一個結(jié)點 C=pre=A； // pre指向 qa的前驅(qū)； C指向多項式 C的頭結(jié)點 while (qa 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多項式的剩余部分 free(B)； // 釋放 B多項式的頭結(jié)點 }// Add_Poly 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 58/58 五、本章小結(jié) ?線性表的定義及抽象數(shù)據(jù)類型的定義； ?線性表的順序表示與實現(xiàn)，線性表的順序存儲結(jié)構(gòu)又稱作隨機(jī)存儲的存儲結(jié)構(gòu)，用順序存儲結(jié)構(gòu)表示的線性表又稱作順序表； ?線性表的鏈?zhǔn)奖硎九c實現(xiàn)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)又稱作非隨機(jī)存儲的存儲結(jié)構(gòu)，鏈表有單鏈表、循環(huán)鏈表和多重鏈表； ?線性表的應(yīng)用：一元多項式的表示及