【正文】 priornext=s。 snext=p。 pprior=s。 return TRUE。 } else return FALSE。 } 算法演示連接 。 68 物料管理 LILST 68 DataStructures:LiLst 雙向鏈表的刪除操作 ? 算法描述： 欲刪除雙向鏈表中的第 i個(gè)結(jié)點(diǎn)，則指針的變化情況如圖所示。 a b c p ② ① … … 69 物料管理 LILST 69 DataStructures:LiLst 雙向鏈表的刪除操作算法實(shí)現(xiàn) int DlinkDel(DoubleList L,int i,ElemType *e) { DNode *p。 ? /*首先檢查待插入的位置 i是否合法 */ ? /*若位置 i合法 ， 則讓指針 p指向它 */ *e=pdata。 ppriornext=pnext。 pnextprior=pprior。 free(p)。 return TRUE。 } 70 物料管理 LILST 70 DataStructures:LiLst 雙向鏈表應(yīng)用舉例 已知 ： 設(shè)一個(gè)循環(huán)雙鏈表 L=（ a,b,c,d）編寫(xiě)一個(gè)算法將鏈表轉(zhuǎn)換為 L=（b,a,c,d）。 算法思想： 實(shí)際上是交換表中前兩個(gè)元素的次序。 算法實(shí)現(xiàn) ： void swap(DLinkList L) { DNode * p,*q,*h。 h=Lnext。 /* h指向表中的第一個(gè)結(jié)點(diǎn) ， 即 a */ p=hnext。 /* p指向 b結(jié)點(diǎn) */ q=hprior。 /* 保存 a 結(jié)點(diǎn)的前驅(qū) */ hnext=pnext。 pnextprior=h。 /*變換指針指向 */ pprior=q。 pnext=h。 Lnext=p。 } 71 物料管理 LILST 71 DataStructures:LiLst * 靜態(tài)鏈表 ? 基本概念： 游標(biāo)實(shí)現(xiàn)鏈表的方法 ：定義一個(gè)較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間（即存儲(chǔ)池）。當(dāng)申請(qǐng)結(jié)點(diǎn)時(shí)，每個(gè)結(jié)點(diǎn)應(yīng)含有兩個(gè)域： data域和 next域。 data域存放結(jié)點(diǎn)的數(shù)據(jù)信息，next域?yàn)橛螛?biāo)指示器，指示后繼結(jié)點(diǎn)在結(jié)構(gòu)數(shù)組中的相對(duì)位置（即數(shù)組下標(biāo)）。數(shù)組的第 0個(gè)分量可以設(shè)計(jì)成表的頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的 next域指示了表中第一個(gè)結(jié)點(diǎn)的位置，為 0表示靜態(tài)單鏈表的結(jié)束。我們把這種用游標(biāo)指示器實(shí)現(xiàn)的單鏈表叫做 靜態(tài)單鏈表 (Static Linked List)。 靜態(tài)鏈表的結(jié)構(gòu)定義 ， 靜態(tài)鏈表的插入和刪除操作示例 。 ? 基本操作： 初始化 、 分配結(jié)點(diǎn)與結(jié)點(diǎn)回收 、 前插操作 、 刪除 。 72 物料管理 LILST 72 DataStructures:LiLst 靜態(tài)鏈表的結(jié)構(gòu)定義 define Maxsize= 鏈表可能達(dá)到的最大長(zhǎng)度 typedef struct { ElemType data。 int cursor。 }Component, StaticList[Maxsize]。 73 物料管理 LILST 73 DataStructures:LiLst 靜態(tài)鏈表的插入和刪除操作示例 已知 ： 線性表 a， b， c， d， f， g， h， i）， Maxsize=11 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 1 a 2 b 3 c 4 d 9 f 6 g 8 h 8 i 0 e 5 1 a 2 b 3 c 4 d 9 f 6 g 7 h 8 i 0 e 5 1 a 2 b 3 c 4 d 5 f 6 g 7 h 8 i 0 0 1 2 3 4 5 6 7 8 9 10 (a)初始化 (b)插入 e后 (c)刪除 h后 74 物料管理 LILST 74 DataStructures:LiLst 靜態(tài)鏈表 初始化 算法描述 ：初始化操作是指將這個(gè)靜態(tài)單鏈表初始化為一個(gè)備用靜態(tài)單鏈表 。 設(shè) space為靜態(tài)單鏈表的名字 ， av為備用單鏈表的頭指針 ， 其算法如下： void initial(StaticList space,int *av) { int k。 space[0]cursor=0。/*設(shè)置靜態(tài)單鏈表的頭指針指向位置 0*/ for(k=0。kMaxsize1。k++) space[k]cursor=k+1。 /*連鏈 */ space[Maxsize1]=0。 /*標(biāo)記鏈尾 */ *av=1。 /*設(shè)置備用鏈表頭指針初值 */ } 75 物料管理 LILST 75 DataStructures:LiLst 靜態(tài)鏈表 分配結(jié)點(diǎn)與結(jié)點(diǎn)回收 ? 分配結(jié)點(diǎn) int getnode(int *av)/*從備用鏈表摘下一個(gè)結(jié)點(diǎn)空間 ， 分配給待插入靜態(tài)鏈表中的元素 */ { int i=*av。 *av=space[*av].cur。 return i。 } ? 結(jié)點(diǎn)回收 void freenode(int *av,int k) /*將下標(biāo)為 k的空閑結(jié)點(diǎn)插入到備用鏈表 */ { space[k].cursor=*av。 *av=k。 } 76 物料管理 LILST 76 DataStructures:LiLst 靜態(tài)鏈表 前插操作 算法描述 ： 先從備用單鏈表上取一個(gè)可用的結(jié)點(diǎn)； 將其插入到已用靜態(tài)單鏈表第 i個(gè)元素之前 。 void insbefore(StaticList space,int i,int *av) { j=*av 。 /*j為從備用表中取到的可用結(jié)點(diǎn)空間的下標(biāo) */ av=space[av]cursor。 /*修改備用表的頭指針 */ space[j]data=x。 k=space[0]cursor。/*k為已用靜態(tài)單鏈表的第一個(gè)元素的下標(biāo)值 */ for(m=1。mi1。m++) /*尋找第 i 1個(gè)元素的位置 k */ k=space[k]cursor。 space[j]cursor=space[k]cursor。 /*修改游標(biāo)域 */ space[k]cursor=j。} 77 物料管理 LILST 77 DataStructures:LiLst 靜態(tài)鏈表 刪除 算法描述： 首先尋找第 i 1個(gè)元素的位置 ， 之后通過(guò)修改相應(yīng)的游標(biāo)域進(jìn)行刪除；在將被刪除的結(jié)點(diǎn)空間鏈到可用靜態(tài)單鏈表中 ， 實(shí)現(xiàn)回收 。 void delete(StaticList space。int i。int *av ) { k=space[0]cursor。 for(m=1,mi1。m++) /*尋找第 i1個(gè)元素的位置 k */ k=space[k]cursor 。 j=space[k]cursor 。 space[k]cursor=space[j]cursor。/*從刪除第 i個(gè)元素 */ space[j]cursor=*av。/*將第 i 個(gè)元素占據(jù)的空間回收 */ av=j 。 /*置備用表頭指針以新值 */ } 78 物料管理 LILST 78 DataStructures:LiLst 順序表和鏈表的比較 ? 1．基于空間的考慮 ? 2．基于時(shí)間的考慮 ? 3．基于語(yǔ)言的考慮 79 物料管理 LILST 79 DataStructures:LiLst 一元多項(xiàng)式的表示及相加 一個(gè)一元多項(xiàng)式 Pn(x)可按升冪的形式寫(xiě)成： Pn(x)=p0+p1x+p2x2+p3x3+ … +p nxn 在計(jì)算機(jī)內(nèi) ， 可以用一個(gè)線性表 P來(lái)表示： P=（ p0， p1， p2， … ， pn） 用單鏈表存儲(chǔ)多項(xiàng)式的結(jié)點(diǎn)結(jié)構(gòu)如下： typedef struct Polynode { int coef。 int exp。 Polynode *next。 } Polynode , * Polylist。 80 物料管理 LILST 80 DataStructures:LiLst 建立多項(xiàng)式鏈表 ? 算法描述 ：輸入多項(xiàng)式的系數(shù)和指數(shù)，用尾插法建立一元多項(xiàng)式的鏈表。 Polylist polycreate() { Polynode *head, *rear, *s。 int c,e。 rear=head =(Polynode *)malloc(sizeof(Polynode))。 /*建立多項(xiàng)式的頭結(jié)點(diǎn) ， rear 始終指向單鏈表的尾 */ scanf(“%d,%d”,amp。c,amp。e)。/*鍵入多項(xiàng)式的系數(shù)和指數(shù)項(xiàng) */ while(c!=0) /*若 c=0， 則代表多項(xiàng)式的輸入結(jié)束 */ { s=(Polynode*)malloc(sizeof(Polynode))。 /*申請(qǐng)新的結(jié)點(diǎn) */ scoef=c 。 sexp=e 。rearnext=s 。 /*在當(dāng)前表尾做插入 */ rear=s。 scanf(“%d,%d”,amp。c,amp。e)。 } rearnext=NULL。/*將表的最后一個(gè)結(jié)點(diǎn)的 next置 NULL， 以示表結(jié)束 */ return(head)。} 81 物料管理 LILST 81 DataStructures:LiLst 多項(xiàng)式的單鏈表表示示意圖 說(shuō)明：圖示分別為多項(xiàng)式 A(x)=7+3x+9x8+5x17 B(x)=8x+22x79x8 1 7 0 3 1 5 17 ∧ 9 8 8 1 1 22 7 9 8 ∧ 82 物料管理 LILST 82 DataStructures:LiLst 兩個(gè) 多項(xiàng)式相加 ? 運(yùn)算規(guī)則 ： 兩個(gè)多項(xiàng)式中所有指數(shù)相同的項(xiàng)的對(duì)應(yīng)系數(shù)相加 ， 若和不為零 ， 則構(gòu)成 “ 和多項(xiàng)式 ” 中的一項(xiàng)；所有指數(shù)不相同的項(xiàng)均復(fù)抄到 “和多項(xiàng)式 ” 中 。 算法實(shí)現(xiàn) ， 算法演示 若 pexp qexp， 則結(jié)點(diǎn) p所指的結(jié)點(diǎn)應(yīng) 是 “ 和多項(xiàng)式 ” 中的一項(xiàng) ， 令指針 p后移； 若 pexpqexp， 則結(jié)點(diǎn) q所指的結(jié)點(diǎn)應(yīng)是 “ 和多項(xiàng)式 ” 中的一項(xiàng) ， 將結(jié)點(diǎn) q插入在結(jié)點(diǎn) p之前 ， 且令指針 q在原來(lái)的鏈表上后移； 若 pexp=qexp， 則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加 ， 當(dāng)和不為零時(shí)修改結(jié)點(diǎn) p的系數(shù)域 ， 釋放 q結(jié)點(diǎn)；若和為零 ， 則和多項(xiàng)式中無(wú)此項(xiàng) ， 從 A中刪去 p結(jié)點(diǎn) ， 同時(shí)釋放 p和 q結(jié)點(diǎn) 。 83 物料管理 LILST 83 DataStructures:LiLst 兩個(gè) 多項(xiàng)式相加算法實(shí)現(xiàn) void polyadd(Polylist polya。Polylist polyb) { …… /* p和 q分別指向 polya和 polyb鏈表中的當(dāng)前計(jì)算結(jié)點(diǎn) */ …… /* pre指向和多項(xiàng)式鏈表中的尾結(jié)點(diǎn) */ while p!=NULL amp。amp。 q!=NULL） { if （ pexp qexp） { … /*將 p結(jié)點(diǎn)加入到和多項(xiàng)式中 */} else if ( pexp= =qexp） { … /*若指數(shù)相等 ， 則相應(yīng)的系數(shù)相加 。 若系數(shù)為 0則刪除 p， q節(jié)點(diǎn) */} else{ … /*將 q結(jié)點(diǎn)加入到和多項(xiàng)式中 */} } … ../*將多項(xiàng)式 polya或 polyb中剩余的結(jié)點(diǎn)加入到和多項(xiàng)式中 */ }