【正文】 8， 8， 9， 11， 11， 15， 20） 合并的方法如下： 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結點為遞增序。 } else { Listinsert(Lc, ++k, bj ) 。設每個結點占用 L 個單元。插入（在線性表的第 i 個位置上插入 x） ： 25 12 47 89 36 14 1 2 3 4 5 6 7 8 9 25 12 47 99 89 36 14 99插入 25 12 47 89 36 14 25 12 47 89 36 14 25 12 47 89 36 14 總共 n 種情況 /*插入成功，返回 */ } // initList_Sq。 37 物料管理 LILST 37 DataStructures:LiLst 線性表的鏈式存儲 ? 鏈表定義： 采用鏈式存儲結構的線性表稱為 鏈表 。 Lnext=s。 算法實現(xiàn) ，算法演示。 int k=0。ki1) /*尋找被刪除結點 i的前驅結點 */ { p=pnext。 57 物料管理 LILST 57 DataStructures:LiLst 求兩個集合的差 ? 已知： 以單鏈表表示集合，假設集合 A用單鏈表 LA表示，集合 B用單鏈表 LB表示，設計算法求兩個集合的差，即 AB。 p=pnext。 } 63 物料管理 LILST 63 DataStructures:LiLst 雙向鏈表 雙向鏈表： 在單鏈表的每個結點里再增加一個指向其前趨的指針域 prior。 ppriornext=pnext。當申請結點時，每個結點應含有兩個域： data域和 next域。 /*標記鏈尾 */ *av=1。} 77 物料管理 LILST 77 DataStructures:LiLst 靜態(tài)鏈表 刪除 算法描述： 首先尋找第 i 1個元素的位置 ， 之后通過修改相應的游標域進行刪除；在將被刪除的結點空間鏈到可用靜態(tài)單鏈表中 ， 實現(xiàn)回收 。 int c,e。 算法實現(xiàn) ， 算法演示 若 pexp qexp， 則結點 p所指的結點應 是 “ 和多項式 ” 中的一項 ， 令指針 p后移； 若 pexpqexp， 則結點 q所指的結點應是 “ 和多項式 ” 中的一項 ， 將結點 q插入在結點 p之前 ， 且令指針 q在原來的鏈表上后移； 若 pexp=qexp， 則將兩個結點中的系數(shù)相加 ， 當和不為零時修改結點 p的系數(shù)域 ， 釋放 q結點；若和為零 ， 則和多項式中無此項 ， 從 A中刪去 p結點 ， 同時釋放 p和 q結點 。e)。 Polynode *next。mi1。/*設置靜態(tài)單鏈表的頭指針指向位置 0*/ for(k=0。 /*變換指針指向 */ pprior=q。 } 算法演示連接 。 /*找到表 LB的表尾 */ qnext=LA。 prenext=pnext。 /*用來存放單鏈表的長度 */ while(p!=NULL) { p=pnext。 p=L。 } 52 物料管理 LILST 52 DataStructures:LiLst 單鏈表插入操作 ? 算法描述： 要在帶頭結點的單鏈表 L中第 i個數(shù)據(jù)元素之前插入一個數(shù)據(jù)元素 e，需要首先在單鏈表中找到第 i1個結點并由指針 pre指示，然后申請一個新的結點并由指針 s指示，其數(shù)據(jù)域的值為 e，并修改第 i1個結點的指針使其指向 s，然后使 s結點的指針域指向第 i個結點。 rnext=s。 while(flag) { c=getchar()。 （ 2） .有順序表 A和 B,其元素均按從小到大的升序排列，編寫算法將他們合并成一個順序表 C，要求 C的元素也是從小到大的升序排列。j) Ldata[j+1]=Ldata[j]。 在一般情況下，刪除第 i 個結點，移動 ni 次。 } // init_seq。順序表示：在物理位置上緊靠在一起。 ( j = ) ) { GetElem(La,i,ai)。 21 物料管理 LILST 21 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 ） 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 中的結點為遞增序。 13 物料管理 LILST 13 DataStructures:LiLst LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2 ， 3 ， 5 ， 6， 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 中的結點為遞增序。 5 物料管理 LILST 5 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， 20） 合并的方法如下： LA ＝ （ 3， 5， 8， 11） LB ＝ （ 2， 6， 8， 9， 11， 15， 20） LC ＝ （ 2） i j k 2. 基本操作： 插入、刪除、查找 …… :已知線性表 LA 和線性表 LB 中的結點為遞增序。對 n0,除了第一個和最后一個元素外，其余各節(jié)點有且僅有一個直接前驅和直接后繼。將 LA 和 LB 進行合并至 另一線性表 LC， 并仍為遞增序。將 LA 和 LB 進行合并至 另一線性表 LC， 并仍為遞增序。 = ListLength(Lb)。 }。 L=malloc(sezeof(seqlist))。 i =1 n 30 物料管理 LILST 30 DataStructures:LiLst 插入和刪除的時間復雜性分析： return(0)。 return(1)。 Node *s。 輸入 “ $”時 flag為 0， 建表結束 */ { c=getchar()。 / * 從表中第一個結點比較 * / while (p!=NULL) if (pdata!=key) p=pnext。 prenext=s。 int ListLength(LinkList L) /*L為帶頭結點的 單鏈表 */ { Node *p。amp。 q=LB。 pprior=s。 /* p指向 b結點 */ q=hprior。 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[j]data=x。/*將第 i 個元素占據(jù)的空間回收 */ av=j 。 /*在當前表尾做插入 */ rear=s。amp。c,amp。int *av ) { k=space[0]cursor。 return i。我們把這種用游標指示器實現(xiàn)的單鏈表叫做 靜態(tài)單鏈表 (Static Linked List)。 return TRUE。 e s ① ② ③ ④ … b p a … 67 物料管理 LILST 67 DataStructures:LiLst 雙向鏈表的前插操作算法實現(xiàn) void DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p。在循環(huán)單鏈表中，表中所有結點被鏈在一個環(huán)上。 ? 算法實現(xiàn) ? 算法演示鏈接 58 物料管理 LILST 58 DataStructures:LiLst 求兩個集合的差算法實現(xiàn) void Difference (LinkList LA,LinkList LB) /*此算法求兩個集合的差集 */ { Node *pre。 return ERROR。ki1) /*先找到第 i1個數(shù)據(jù)元素的存儲位置 ,使指針 Pre指向它 */ { pre=prenext。amp。 Node *r, *s。 單鏈表 ：鏈表中的每個結點只有一個指針域，我們將這種鏈表稱為單鏈表。刪除 將第 i個元素從線性表中去掉 步驟： ① 將 ai+1~an順序上移 ②修改 len指針（相當于修改表長），使之指向最后一個元素 Int Delete_seqlist(seqlist *L, int i) { if(i1||iLlen+1) {printf(“No this value of i”)。另外，通過 KEY 查找結點，代價 O(n)。 29 物料管理 LILST 29 DataStructures:LiLst 插入和刪除的時間復雜性分析： 線性表的順序表示和實現(xiàn) 27 物料管理 LILST 27 DataStructures:LiLst an ai1 a2 a1 ai 在 c 中的表示和實現(xiàn)： define MAXSIZE 100 typedef struct { data type data[MAXSIZE]。