【正文】 LILST 48 DataStructures:LiLst 單鏈表查找 ? 按序號查找 算法描述： 設(shè)帶頭結(jié)點(diǎn)的單鏈表的長度為 n，要查找表中第 i個結(jié)點(diǎn)，則需要從單鏈表的頭指針 L出發(fā)，從頭結(jié)點(diǎn)（ Lnext）開始順著鏈域掃描，用指針 p指向當(dāng)前掃描到的結(jié)點(diǎn) ,初值指向頭結(jié)點(diǎn)（ p=Lnext），用 j做記數(shù)器，累計當(dāng)前掃描過的結(jié)點(diǎn)數(shù)（初值為 0），當(dāng) j = i 時，指針 p所指的結(jié)點(diǎn)就是要找的第 i個結(jié)點(diǎn) 。 r=L。 snext=Lnext。 ? 帶頭結(jié)點(diǎn)的空單鏈表 ? 帶頭結(jié)點(diǎn)的單鏈表 ∧ H a1 a2 … H an ∧ 42 物料管理 LILST 42 DataStructures:LiLst 單鏈表的存儲結(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)用示例： 求單鏈表的長度 求兩個集合的差 44 物料管理 LILST 44 DataStructures:LiLst 建立單鏈表 ? 頭插法建表 算法描述： 從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭結(jié)點(diǎn)之后，直至讀入結(jié)束標(biāo)志為止。因此當(dāng)表長變化較大時，難以確定合適的存儲規(guī)模。j++) Ldata[j1]=Ldata[j]。 /*表的長度增加 */ return(1)。 return(1)。 在一般情況下，刪除第 i 個結(jié)點(diǎn)，移動 ni 次 刪除第 1 個結(jié)點(diǎn)，移動 n1 次 刪除第 2 個結(jié)點(diǎn)，移動 n2 次 刪除第 i 個結(jié)點(diǎn)，移動 ni 次 刪除第 n 個結(jié)點(diǎn)，移動 0 次。 總共 n+1 種情況 …. // 生成順序存 / 儲的線性表 28 物料管理 LILST 28 DataStructures:LiLst 插入和刪除的時間復(fù)雜性分析： 表示： 設(shè)第一個結(jié)點(diǎn)的存儲地址為 LOC(a1), 余類推。 Listinsert(Lc, ++k, bj ) 。 ++i。 k=0。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。 除最后一個結(jié)點(diǎn)之外，每個結(jié)點(diǎn)均 只有一個后繼結(jié)點(diǎn) 。 除第一個結(jié)點(diǎn)之外，每個結(jié)點(diǎn)均只有 一個前驅(qū)結(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. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點(diǎn)為遞增序。 10 物料管理 LILST 10 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6 ） 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. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 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. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點(diǎn)為遞增序。 18 物料管理 LILST 18 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11 ） 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. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點(diǎn)為遞增序。 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. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結(jié)點(diǎn)為遞增序。 i=j=1。 if (ai = bj ) { Listinsert(Lc, ++k, ai ) 。 while (j = ) { GetElem(Lb,j,bj)。 L= init_seqlist()。 插在第 n 個結(jié)點(diǎn)之后，移動 0 次。刪除第 4 個結(jié)點(diǎn)，移動 6－ 4 次。插入 Int insert_seqlist(seqlist *L,int i, datatype x) { if ( Llen==MAXSIZE1) {printf(“overflow”)。 /*新元素插入 */ Llen++。 j=Llen。 ? 缺點(diǎn)： ，除表尾的位置外，在表的其它位置上進(jìn)行插入或刪除操作都必須移動大量的結(jié)點(diǎn)，其效率較低； ，存儲分配只能預(yù)先進(jìn)行靜態(tài)分配。 40 物料管理 LILST 40 DataStructures:LiLst 單鏈表的示例圖 頭指針 H 存儲地址 數(shù)據(jù)域 指針域 1 D 43 7 B 13 13 C 1 19 H NULL 25 F 37 31 A 7 37 G 19 43 E 25 31 41 物料管理 LILST 41 DataStructures:LiLst 帶頭結(jié)點(diǎn)的單鏈表示意圖 有時為了操作的方便，還可以在單鏈表的第一個結(jié)點(diǎn)之前附設(shè)一個頭結(jié)點(diǎn)。 sdata=c。/*為頭結(jié)點(diǎn)分配存儲空間 */ Lnext=NULL。 rnext=NULL。算法實現(xiàn) ，算法演示。 */ Node *pre,*s。 } s=(Node*)malloc(sizeof(Node))。 while(pnext!=NULLamp。 /*刪除結(jié)點(diǎn) r*/ e=rdata。 } return j。p=LAnext。 free(r)。 算法思想 ：先找到兩個鏈表的尾，并分別由指針 p、 q指向它們，然后將第一個鏈表的尾與第二個表的第一個結(jié)點(diǎn)鏈接起來，并修改第二個表的尾 Q，使它的鏈域指向第一個表的頭結(jié)點(diǎn)。/*修改表 LA的尾指針 ， 使之指向表 LB 中的第一個結(jié)點(diǎn) */ free(LB)。 sprior=pprior。 a b c p ② ① … … 69 物料管理 LILST 69 DataStructures:LiLst 雙向鏈表的刪除操作算法實現(xiàn) int DlinkDel(DoubleList L,int i,ElemType *e) { DNode *p。 算法實現(xiàn) ： void swap(DLinkList L) { DNode * p,*q,*h。 Lnext=p。 72 物料管理 LILST 72 DataStructures:LiLst 靜態(tài)鏈表的結(jié)構(gòu)定義 define Maxsize= 鏈表可能達(dá)到的最大長度 typedef struct { ElemType data。k++) space[k]cursor=k+1。 } 76 物料管理 LILST 76 DataStructures:LiLst 靜態(tài)鏈表 前插操作 算法描述 ： 先從備用單鏈表上取一個可用的結(jié)點(diǎn)； 將其插入到已用靜態(tài)單鏈表第 i個元素之前 。 space[j]cursor=space[k]cursor。 j=space[k]cursor 。 80 物料管理 LILST 80 DataStructures:LiLst 建立多項式鏈表 ? 算法描述 ：輸入多項式的系數(shù)和指數(shù)，用尾插法建立一元多項式的鏈表。 /*申請新的結(jié)點(diǎn) */ scoef=c 。/*將表的最后一個結(jié)點(diǎn)的 next置 NULL， 以示表結(jié)束 */ return(head