【正文】 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 8， 8， 9， 11 ， 11， 15， 20） 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 中的結點為遞增序。 i=j=1。 while ( ( i = ) amp。 if (ai = bj ) { Listinsert(Lc, ++k, ai ) 。 } } while (i = ) { GetElem(La,i,ai)。 while (j = ) { GetElem(Lb,j,bj)。 } // Mergelist La Lb 時間復雜性 : 和 表 LA、 LB 中的結點個數(shù)（之和）成正比。 隨機存?。涸L問任何一個數(shù)據元素或結點花費同樣多時間。 Llen=1。 L= init_seqlist()。 在一般情況下，插在第 i 個結點之前，移動 n(i1) 次。 插在第 n 個結點之后，移動 0 次。刪除（刪除線性表的第 i 個結點） ： 25 12 47 89 36 14 1 2 3 4 5 6 7 8 9 25 12 47 36 14 25 12 47 36 14 25 12 47 36 14 刪除第 4 個結點，移動 6－ 4 次。 i =1 n 插入 Int insert_seqlist(seqlist *L,int i, datatype x) { if ( Llen==MAXSIZE1) {printf(“overflow”)。} /*檢查插入位置的正確性 */ if(j=Llen。 /*新元素插入 */ Llen++。 33 物料管理 LILST 33 DataStructures:LiLst 插入、刪除 、 查找的實現(xiàn)算法： j=Llen。 /*刪除成功 */ } 34 物料管理 LILST 34 DataStructures:LiLst 插入、刪除 、 查找的實現(xiàn)算法： ? 缺點： ，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結點，其效率較低； ，存儲分配只能預先進行靜態(tài)分配。 38 物料管理 LILST 38 DataStructures:LiLst ? 單鏈表 ? 單鏈表上的基本運算 ? 循環(huán)鏈表 ? 雙向鏈表 ?* 靜態(tài)鏈表 ? 順序表和鏈表的比較 鏈表 39 物料管理 LILST 39 DataStructures:LiLst 單鏈表 結點（ Node） 為了正確地表示結點間的邏輯關系，必須在存儲線性表的每個數(shù)據元素值的同時，存儲指示其后繼結點的地址（或位置）信息，這兩部分信息組成的存儲映象叫做 結點（ Node） 。 40 物料管理 LILST 40 DataStructures:LiLst 單鏈表的示例圖 頭指針 H 存儲地址 數(shù)據域 指針域 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 帶頭結點的單鏈表示意圖 有時為了操作的方便，還可以在單鏈表的第一個結點之前附設一個頭結點。 int flag=1。 sdata=c。 } } 46 物料管理 LILST 46 DataStructures:LiLst 尾插法建表 C1 ∧ s r ∧ L c1 r s c2 ∧ L c1 ∧ r s L 47 物料管理 LILST 47 DataStructures:LiLst 尾插法建表算法 Linklist CreateFromTail() /*將新增的字符追加到鏈表的末尾 */ { LinkList L。/*為頭結點分配存儲空間 */ Lnext=NULL。 if(c!=’$’) { s=(Node*)malloc(sizeof(Node))。 rnext=NULL。 否則返回 NULL * / Lnode *Get(LinkList L, int i) { Lnode *p； p=L； j=0； / * 從頭結點開始掃描 * / while (pnext!=NULL amp。算法實現(xiàn) ，算法演示。 else break。 */ Node *pre,*s。amp。 } s=(Node*)malloc(sizeof(Node))。 } 54 物料管理 LILST 54 DataStructures:LiLst 單鏈表刪除 ? 算法描述： 欲在帶頭結點的單鏈表 L中刪除第 i個結點，則首先要通過計數(shù)方式找到第 i1個結點并使 p指向第 i1個結點，而后刪除第 i個結點并釋放結點空間。 while(pnext!=NULLamp。 } if(k!=i1) /* 即 while循環(huán)是因為 pnext=NULL而跳出的 */ { printf(“刪除結點的位置 i不合理 ！ ” )。 /*刪除結點 r*/ e=rdata。 p=Lnext。 } return j。具體做法是，對于集合 A中的每個元素 e，在集合 B的鏈表 LB中進行查找，若存在與 e相同的元素，則從 LA中將其刪除。p=LAnext。qdata!=pdata) q=qnext。 free(r)。 特點 ：將單鏈表最后一個結點的指針域由 NULL改為指向頭結點或線性表中的第一個結點，就得到了單鏈形式的循環(huán)鏈表，并稱為循環(huán)單鏈表。 算法思想 ：先找到兩個鏈表的尾，并分別由指針 p、 q指向它們，然后將第一個鏈表的尾與第二個表的第一個結點鏈接起來，并修改第二個表的尾 Q，使它的鏈域指向第一個表的頭結點。 while (pnext!=LA) p=pnext。/*修改表 LA的尾指針 ， 使之指向表 LB 中的第一個結點 */ free(LB)。 雙向鏈表的 結構定義： typedef struct Dnode { ElemType data； struct DNode *prior， *next； } DNode, * DoubleList； 64 物料管理 LILST 64 DataStructures:LiLst 雙鏈表的結構定義 ? 雙鏈表的結點結構 后繼指針域 prior data next 前驅指針域 數(shù)據域 65 物料管理 LILST 65 DataStructures:LiLst 雙向循環(huán)鏈表示意圖 a1 a2 a3 L L 空的雙向循環(huán)鏈表 非空的雙向循環(huán)鏈表 66 物料管理 LILST 66 DataStructures:LiLst 雙向鏈表的前插操作 ? 算法描述： 欲在雙向鏈表第 i個結點之前插入一個的新的結點，則指針的變化情況如圖所示。 sprior=pprior。 return TRUE。 a b c p ② ① … … 69 物料管理 LILST 69 DataStructures:LiLst 雙向鏈表的刪除操作算法實現(xiàn) int DlinkDel(DoubleList L,int i,ElemType *e) { DNode *p。 free(p)。 算法實現(xiàn) ： void swap(DLinkList L) { DNode * p,*q,*h。 /* 保存 a 結點的前驅 */ hnext=pnext。 Lnext=p。數(shù)組的第 0個分量可以設計成表的頭結點，頭結點的 next域指示了表中第一個結點的位置，為 0表示靜態(tài)單鏈表的結束。 72 物料管理 LILST 72 DataStructures:LiLst 靜態(tài)鏈表的結構定義 define Maxsize= 鏈表可能達到的最大長度 typedef struct { ElemType data。 設 space為靜態(tài)單鏈表的名字 ， av為備用單鏈表的頭指針 ， 其算法如下： void initial(StaticList space,int *av) { int k。k++) space[k]cursor=k+1。 *av=space[*av].cur。 } 76 物料管理 LILST 76 DataStructures:LiLst 靜態(tài)鏈表 前插操作 算法描述 ： 先從備用單鏈表上取一個可用的結點； 將其插入到已用靜態(tài)單鏈表第 i個元素之前 。 k=space[0]cursor。 space[j]cursor=space[k]cursor。int i。 j=space[k]cursor 。 /*置備用表頭指針以新值 */ } 78 物料管理 LILST 78 DataStructures:LiLst 順序表和鏈表的比較 ? 1．基于空間的考慮 ? 2．基于時間的考慮 ? 3．基于語言的考慮 79 物料管理 LILST 79 DataStructures:LiLst 一元多項式的表示及相加 一個一元多項式 Pn(x)可按升冪的形式寫成： Pn(x)=p0+p1x+p2x2+p3x3+ … +p nxn 在計算機內 ， 可以用一個線性表 P來表示： P=（ p0， p1， p2， … ， pn） 用單鏈表存儲多項式的結點結構如下： typedef struct Polynode { int coef。 80 物料管理 LILST 80 DataStructures:LiLst 建立多項式鏈表 ? 算法描述 ：輸入多項式的系數(shù)和指數(shù)，用尾插法建立一元多項式的鏈表。 /*建立多項式的頭結點 ， rear 始終指向單鏈表的尾 */ scanf(“%d,%d”,amp。 /*申請新的結點 */ scoef=c 。 scanf(“%d,%d”,amp。/*將表的最后一個結點的 next置 NULL， 以示表結束 */ return(head)。Polylist polyb) { …… /* p和 q分別指向 polya和 polyb鏈表中的當前計算結點 */ …… /* pre指向和多項式鏈表中的尾結點 */ while p!=NULL am