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