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