【正文】 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。 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)酱鎯?chǔ)結(jié)構(gòu)。因此在靜態(tài)鏈表中實(shí)現(xiàn)線性表的操作和動(dòng)態(tài)鏈表相似，插入與刪除操作不用移動(dòng)元素。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 31/58 用尾插法建立鏈表的算法描述如下： void CreateList_L(LinkList amp。ji1) //尋找第 i1個(gè)結(jié)點(diǎn) { p=pnext； ++j； } if( !p || ji1 ) exit(0)； //i大于表長(zhǎng)或者小于 1 s = (LinkList)malloc(sizeof(LNode))； //生成新結(jié)點(diǎn) sdata = e； snext = pnext； pnext = s； //插入 } 算法的時(shí)間復(fù)雜度為 O(n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 28/58 ③ 刪除：在以 L為頭結(jié)點(diǎn)的單鏈表中刪除第 i個(gè)元素。 while( i ) [k++] = [i++]。e) {//在順序表 L中刪除第 i個(gè)元素，并用 e返回其值 if(i1||i) exit(0)。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 11/58 a1 a2 ai an b b+l … … b+(i1)l b+(n1)l … … … … 1 2 i n 空閑 存儲(chǔ)地址 內(nèi)存狀態(tài) 數(shù)據(jù)元素在線性表中的位臵 線性表的順序存儲(chǔ)結(jié)構(gòu)圖 相鄰數(shù)據(jù)元素位臵關(guān)系： LOC(ai+1)=LOC(ai)+l ai的存儲(chǔ)位臵： LOC(ai)=LOC(a1)+(i1) l 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 12/58 define LIST_INIT_SIZE 100 //空間初始分配量 define LISTINCREMENT 10 //空間分配增量 typedef struct{ ElemType *elem。 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 5/58 2. 抽象數(shù)據(jù)類型線性表的定義 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) 初始化線性表 L，設(shè)臵為空表； ListLength(L) 求線性表的長(zhǎng)度 ； GetElem(L, i, amp。 //存儲(chǔ)空間基址 int length。 //i值不合法 e=[i1]。 // 插入 La的剩余元素 while( j ) [k++] = [j++]。 分析 ：在單鏈表中刪除結(jié)點(diǎn)其操作類似于插入操作，無(wú)需移動(dòng)元素，只需修改相應(yīng)的指針即可，如下圖所示： 上述指針修改用語(yǔ)句描述即為： q=pnext。L， int n) {//輸入 n個(gè)數(shù)據(jù)元素，利用尾插法建立帶頭結(jié)點(diǎn)的線性鏈表 L=(LinkList)malloc(sizeof(LNode))； pre=L。 數(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表。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。 }// 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ù)。L， int i， ElemType 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時(shí)， A中有該元素，所以刪除， 刪除過(guò)程和刪除 b相同。 } pcnext = pa?pa： pb； //插入剩余段 ,若 Pa不為空 ,則 pc next = pa //否則 , pc next = pb free(Lb)； //釋放 Lb的頭結(jié)點(diǎn) } 算法的時(shí)間復(fù)雜度為 O(m+n) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 35/58 靜態(tài)鏈表 在有的高級(jí)語(yǔ)言中沒(méi)有指針這種數(shù)據(jù)類型，此時(shí)，也可借用一維數(shù)組來(lái)描述線性鏈表，為了和指針型描述的線性鏈表相區(qū)別，我們給這種用數(shù)組描述的鏈表起名叫 靜態(tài)鏈表 ，其類型說(shuō)明如下所示： define MAXSIZE 1000 // 鏈表的最大長(zhǎng)度 typedef struct { ElemType data； int cur； //游標(biāo)，指示結(jié)點(diǎn)在數(shù)組中的相對(duì)位置 }ponent， SLinkList[MAXSIZE]； 假設(shè) S為 SLinkList型變量，若第 i個(gè)分量表示鏈表的第 k個(gè)結(jié)點(diǎn)，則S[i].cur指示第 k+1個(gè)結(jié)點(diǎn)的位置。 pre = p。amp。 else [k++] = [j++]。L， int i， ElemType amp。 3）做插入或刪除操作時(shí)需移動(dòng)大量元素，效率不高，適合做查詢操作。 對(duì)于 ai，當(dāng) 1i≤n 時(shí)，它有一個(gè)直接前驅(qū) ai1；當(dāng) 1≤in 時(shí)，它有一個(gè)直接后繼 ai+1。e) 求表 L中的第 i個(gè)元素，結(jié)果由 e返回； ListInsert(amp。 //當(dāng)前長(zhǎng)度 int listsize。 for(j = i1。 // 插入 Lb的剩余元素 }// MergeList_Sq 算法 MergeList的時(shí)間復(fù)雜度為 O(+) 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 21/58 三、線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 線性鏈表 靜態(tài)鏈表 循環(huán)鏈表 雙向鏈表 數(shù)據(jù)結(jié)構(gòu) 第 2章 線性表 22/58 線性鏈表 順序存儲(chǔ)結(jié)構(gòu)弱點(diǎn) ：在作插入或刪除操作時(shí)需要移動(dòng)大量元素。 pnext=qnext。 for(i = 0； i n； ++i)