【正文】 雙向鏈表的刪除操作 ? 算法描述： 欲刪除雙向鏈表中的第 i個(gè)結(jié)點(diǎn)，則指針的變化情況如圖所示。 pnextprior=pprior。 算法思想： 實(shí)際上是交換表中前兩個(gè)元素的次序。 /* p指向 b結(jié)點(diǎn) */ q=hprior。 pnext=h。 data域存放結(jié)點(diǎn)的數(shù)據(jù)信息，next域?yàn)橛螛?biāo)指示器，指示后繼結(jié)點(diǎn)在結(jié)構(gòu)數(shù)組中的相對(duì)位置（即數(shù)組下標(biāo)）。 ? 基本操作： 初始化 、 分配結(jié)點(diǎn)與結(jié)點(diǎn)回收 、 前插操作 、 刪除 。 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)單鏈表 。kMaxsize1。 /*設(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=k。 /*修改備用表的頭指針 */ space[j]data=x。m++) /*尋找第 i 1個(gè)元素的位置 k */ k=space[k]cursor。 void delete(StaticList space。m++) /*尋找第 i1個(gè)元素的位置 k */ k=space[k]cursor 。/*將第 i 個(gè)元素占據(jù)的空間回收 */ av=j 。 } Polynode , * Polylist。 rear=head =(Polynode *)malloc(sizeof(Polynode))。/*鍵入多項(xiàng)式的系數(shù)和指數(shù)項(xiàng) */ while(c!=0) /*若 c=0， 則代表多項(xiàng)式的輸入結(jié)束 */ { s=(Polynode*)malloc(sizeof(Polynode))。 /*在當(dāng)前表尾做插入 */ rear=s。 } rearnext=NULL。 83 物料管理 LILST 83 DataStructures:LiLst 兩個(gè) 多項(xiàng)式相加算法實(shí)現(xiàn) void polyadd(Polylist polya。 若系數(shù)為 0則刪除 p， q節(jié)點(diǎn) */} else{ … /*將 q結(jié)點(diǎn)加入到和多項(xiàng)式中 */} } … ../*將多項(xiàng)式 polya或 polyb中剩余的結(jié)點(diǎn)加入到和多項(xiàng)式中 */ } 。amp。} 81 物料管理 LILST 81 DataStructures:LiLst 多項(xiàng)式的單鏈表表示示意圖 說明：圖示分別為多項(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)式 ” 中 。c,amp。 sexp=e 。c,amp。 Polylist polycreate() { Polynode *head, *rear, *s。 int exp。 space[k]cursor=space[j]cursor。int *av ) { k=space[0]cursor。 /*修改游標(biāo)域 */ space[k]cursor=j。/*k為已用靜態(tài)單鏈表的第一個(gè)元素的下標(biāo)值 */ for(m=1。 void insbefore(StaticList space,int i,int *av) { j=*av 。 return i。 /*連鏈 */ space[Maxsize1]=0。 space[0]cursor=0。 int cursor。我們把這種用游標(biāo)指示器實(shí)現(xiàn)的單鏈表叫做 靜態(tài)單鏈表 (Static Linked List)。 } 71 物料管理 LILST 71 DataStructures:LiLst * 靜態(tài)鏈表 ? 基本概念： 游標(biāo)實(shí)現(xiàn)鏈表的方法 ：定義一個(gè)較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點(diǎn)空間（即存儲(chǔ)池）。 pnextprior=h。 h=Lnext。 return TRUE。 ? /*首先檢查待插入的位置 i是否合法 */ ? /*若位置 i合法 ， 則讓指針 p指向它 */ *e=pdata。 } else return FALSE。 ppriornext=s。 e s ① ② ③ ④ … b p a … 67 物料管理 LILST 67 DataStructures:LiLst 雙向鏈表的前插操作算法實(shí)現(xiàn) void DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p。 return(LA)。 /*找到表 LA的表尾 */ while (qnext!=LB) q=qnext。 62 物料管理 LILST 62 DataStructures:LiLst 循環(huán)單鏈表合并算法實(shí)現(xiàn) LinkList merge_1(LinkList LA,LinkList LB) /*此算法將兩個(gè)鏈表的首尾連接起來 */ { Node *p, *q。在循環(huán)單鏈表中，表中所有結(jié)點(diǎn)被鏈在一個(gè)環(huán)上。 } else { pre=p。 if (q!=NULL) { r=p。 /*p向表中的某一結(jié)點(diǎn) ， pre始終指向 p的前驅(qū) */ while(p!=NULL) { q=LBnext。 ? 算法實(shí)現(xiàn) ? 算法演示鏈接 58 物料管理 LILST 58 DataStructures:LiLst 求兩個(gè)集合的差算法實(shí)現(xiàn) void Difference (LinkList LA,LinkList LB) /*此算法求兩個(gè)集合的差集 */ { Node *pre。 } 算法演示鏈接 。 j=0。 free(r)。 return ERROR。amp。 p a1 … ai1 ai … an ∧ p a1 … L … an ∧ ai1 ai ai+1 r L 55 物料管理 LILST 55 DataStructures:LiLst 單鏈表刪除算法實(shí)現(xiàn) void DelList(LinkList L,int i,ElemType *e) /*在帶頭結(jié)點(diǎn)的單鏈表 L中刪除第 i個(gè)元素 ， 并保存其值到變量 *e中 */ { Node *p,*r。 /*為 e申請(qǐng)一個(gè)新的結(jié)點(diǎn) */ sdata=e。ki1) /*先找到第 i1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置 ,使指針 Pre指向它 */ { pre=prenext。 pre=L。 / * 找到結(jié)點(diǎn) key， 退出循環(huán) * / return p。 51 物料管理 LILST 51 DataStructures:LiLst 按值查找算法實(shí)現(xiàn) / * 在帶頭結(jié)點(diǎn)的單鏈表 L中查找其結(jié)點(diǎn)值等于 key的結(jié)點(diǎn) ， 若找到則返回該結(jié)點(diǎn)的位置 p， 否則返回 NULL * / Node *Locate( LinkList L,ElemType key) { Node *p。amp。 } } } 48 物料管理 LILST 48 DataStructures:LiLst 單鏈表查找 ? 按序號(hào)查找 算法描述： 設(shè)帶頭結(jié)點(diǎn)的單鏈表的長(zhǎng)度為 n，要查找表中第 i個(gè)結(jié)點(diǎn)，則需要從單鏈表的頭指針 L出發(fā)，從頭結(jié)點(diǎn)（ Lnext）開始順著鏈域掃描，用指針 p指向當(dāng)前掃描到的結(jié)點(diǎn) ,初值指向頭結(jié)點(diǎn)（ p=Lnext），用 j做記數(shù)器，累計(jì)當(dāng)前掃描過的結(jié)點(diǎn)數(shù)（初值為 0），當(dāng) j = i 時(shí)，指針 p所指的結(jié)點(diǎn)就是要找的第 i個(gè)結(jié)點(diǎn) 。 sdata=c。 r=L。 Node *r, *s。 snext=Lnext。 /* 設(shè)置一個(gè)標(biāo)志 ， 初值為 1， 當(dāng)輸入 “ $”時(shí) ， flag為 0， 建表結(jié)束 */ L=(Linklist)malloc(sizeof(Node))； /*為頭結(jié)點(diǎn)分配存儲(chǔ)空間 */ Lnext=NULL。 ? 帶頭結(jié)點(diǎn)的空單鏈表 ? 帶頭結(jié)點(diǎn)的單鏈表 ∧ H a1 a2 … H an ∧ 42 物料管理 LILST 42 DataStructures:LiLst 單鏈表的存儲(chǔ)結(jié)構(gòu)描述 typedef struct Node / * 結(jié)點(diǎn)類型定義 * / { ElemType data； struct Node * next； }Node, *LinkList； /* LinkList為結(jié)構(gòu)指針類型 */ 43 物料管理 LILST 43 DataStructures:LiLst 單鏈表上的基本運(yùn)算 ? 線性表的基本運(yùn)算 ： 建立單鏈表 單鏈表查找 單鏈表插入操作 單鏈表刪除 ? 算法應(yīng)用示例： 求單鏈表的長(zhǎng)度 求兩個(gè)集合的差 44 物料管理 LILST 44 DataStructures:LiLst 建立單鏈表 ? 頭插法建表 算法描述： 從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。 單鏈表 ：鏈表中的每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，我們將這種鏈表稱為單鏈表。因此當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。查找 查找算法？（同學(xué)自己編寫） 35 物料管理 LILST 35 DataStructures:LiLst 線性表應(yīng)用舉例： （ 1） .將順序表（ a1,a2,…,an ）重新排列為以 a1為界的兩部分： a1前面的值均比 a1小， a1后面的值均比 a1大（這里假設(shè)數(shù)據(jù)元素的類型具有可比性，不妨設(shè)為整型）。j++) Ldata[j1]=Ldata[j]。刪除 將第 i個(gè)元素從線性表中去掉 步驟： ① 將 ai+1~an順序上移 ②修改 len指針（相當(dāng)于修改表長(zhǎng)），使之指向最后一個(gè)元素 Int Delete_seqlist(seqlist *L, int i) { if(i1||iLlen+1) {printf(“No this valu