【正文】 /*將表的最后一個(gè)結(jié)點(diǎn)的 next置 NULL， 以示表結(jié)束 */ return(head)。 80 物料管理 LILST 80 DataStructures:LiLst 建立多項(xiàng)式鏈表 ? 算法描述 ：輸入多項(xiàng)式的系數(shù)和指數(shù)，用尾插法建立一元多項(xiàng)式的鏈表。 space[j]cursor=space[k]cursor。k++) space[k]cursor=k+1。 Lnext=p。 a b c p ② ① … … 69 物料管理 LILST 69 DataStructures:LiLst 雙向鏈表的刪除操作算法實(shí)現(xiàn) int DlinkDel(DoubleList L,int i,ElemType *e) { DNode *p。/*修改表 LA的尾指針 ， 使之指向表 LB 中的第一個(gè)結(jié)點(diǎn) */ free(LB)。 free(r)。 } return j。 while(pnext!=NULLamp。 */ Node *pre,*s。 rnext=NULL。 sdata=c。 ? 缺點(diǎn)： ，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動(dòng)大量的結(jié)點(diǎn)，其效率較低； ，存儲(chǔ)分配只能預(yù)先進(jìn)行靜態(tài)分配。 /*新元素插入 */ Llen++。刪除第 4 個(gè)結(jié)點(diǎn)，移動(dòng) 6－ 4 次。 L= init_seqlist()。 if (ai = bj ) { Listinsert(Lc, ++k, ai ) 。 22 物料管理 LILST 22 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11 ， 11， 15） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線(xiàn)性表 LA 和線(xiàn)性表 LB 中的結(jié)點(diǎn)為遞增序。 14 物料管理 LILST 14 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線(xiàn)性表 LA 和線(xiàn)性表 LB 中的結(jié)點(diǎn)為遞增序。 6 物料管理 LILST 6 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線(xiàn)性表 LA 和線(xiàn)性表 LB 中的結(jié)點(diǎn)為遞增序。 除最后一個(gè)結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)均 只有一個(gè)后繼結(jié)點(diǎn) 。將 LA 和 LB 進(jìn)行合并至 另一線(xiàn)性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線(xiàn)性表 LC， 并仍為遞增序。 k=0。 Listinsert(Lc, ++k, bj ) 。表示： 總共 n+1 種情況 return(1)。j++) Ldata[j1]=Ldata[j]。 ? 帶頭結(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)類(lèi)型定義 * / { ElemType data； struct Node * next； }Node, *LinkList； /* LinkList為結(jié)構(gòu)指針類(lèi)型 */ 43 物料管理 LILST 43 DataStructures:LiLst 單鏈表上的基本運(yùn)算 ? 線(xiàn)性表的基本運(yùn)算 ： 建立單鏈表 單鏈表查找 單鏈表插入操作 單鏈表刪除 ? 算法應(yīng)用示例： 求單鏈表的長(zhǎng)度 求兩個(gè)集合的差 44 物料管理 LILST 44 DataStructures:LiLst 建立單鏈表 ? 頭插法建表 算法描述： 從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。 r=L。 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。 /*為 e申請(qǐng)一個(gè)新的結(jié)點(diǎn) */ sdata=e。 free(r)。 /*p向表中的某一結(jié)點(diǎn) ， pre始終指向 p的前驅(qū) */ while(p!=NULL) { q=LBnext。 62 物料管理 LILST 62 DataStructures:LiLst 循環(huán)單鏈表合并算法實(shí)現(xiàn) LinkList merge_1(LinkList LA,LinkList LB) /*此算法將兩個(gè)鏈表的首尾連接起來(lái) */ { Node *p, *q。 ppriornext=s。 h=Lnext。 int cursor。 void insbefore(StaticList space,int i,int *av) { j=*av 。 space[k]cursor=space[j]cursor。 sexp=e 。 若系數(shù)為 0則刪除 p， q節(jié)點(diǎn) */} else{ … /*將 q結(jié)點(diǎn)加入到和多項(xiàng)式中 */} } … ../*將多項(xiàng)式 polya或 polyb中剩余的結(jié)點(diǎn)加入到和多項(xiàng)式中 */ } 。/*鍵入多項(xiàng)式的系數(shù)和指數(shù)項(xiàng) */ while(c!=0) /*若 c=0， 則代表多項(xiàng)式的輸入結(jié)束 */ { s=(Polynode*)malloc(sizeof(Polynode))。m++) /*尋找第 i1個(gè)元素的位置 k */ k=space[k]cursor 。 *av=k。 ? 基本操作： 初始化 、 分配結(jié)點(diǎn)與結(jié)點(diǎn)回收 、 前插操作 、 刪除 。 算法思想： 實(shí)際上是交換表中前兩個(gè)元素的次序。 if (s) { sdata=e。 60 物料管理 LILST 60 DataStructures:LiLst 帶頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖 L a1 … … ai1 ai an L a1 … … ai1 ai an rear *(rearnext) *rear 空鏈表 帶 頭 結(jié)點(diǎn)的一般形式 帶 尾 結(jié)點(diǎn)的一般形式 61 物料管理 LILST 61 DataStructures:LiLst 循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表 已知 ： 有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表 LA、 LB，編寫(xiě)一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為 LA。 pre=LA。 pnext=pnextnext 。 } if(k!=i1) { printf(“插入位置不合理 ！ ” )； return。查找過(guò)程從單鏈表的頭指針指向的頭結(jié)點(diǎn)出發(fā)，順著鏈逐個(gè)將結(jié)點(diǎn)的值和給定值 e作比較。 L=(Node * )malloc(sizeof(Node))。 頭指針 ：指向鏈表頭結(jié)點(diǎn)的指針。} for(j=i。 32 物料管理 LILST 32 DataStructures:LiLst 插入、刪除、查找的實(shí)現(xiàn)算法： 在一般情況下，插在第 i 個(gè)結(jié)點(diǎn)之前，移動(dòng) n(i1) 次 插在第 1 個(gè)結(jié)點(diǎn)之前，移動(dòng) n 次 插在第 2 個(gè)結(jié)點(diǎn)之前，移動(dòng) n1 次 插在第 i 個(gè)結(jié)點(diǎn)之前，移動(dòng) n(i1) 次 插在第 n 個(gè)結(jié)點(diǎn)之前，移動(dòng) 1 次。 } seqlist。 }。 Lc) { InitiList( Lc )。將 LA 和 LB 進(jìn)行合并至 另一線(xiàn)性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線(xiàn)性表 LC， 并仍為遞增序。 存在 唯一的 一個(gè)被稱(chēng)之為 “ 最后一個(gè) ” 的結(jié)點(diǎn)。 7 物料管理 LILST 7 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線(xiàn)性表 LA 和線(xiàn)性表 LB 中的結(jié)點(diǎn)為遞增序。 15 物料管理 LILST 15 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8 ） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6， 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線(xiàn)性表 LA 和線(xiàn)性表 LB 中的結(jié)點(diǎn)為遞增序。 23 物料管理 LILST 23 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11 ， 11， 15） i j k LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2， 3， 5， 6，