【正文】 線性表的順序表示和實現(xiàn) 線性表的鏈接表示和實現(xiàn) 一元多項式的表示及相加 目錄 第 二 章 線性表 2 物料管理 LILST 2 DataStructures:LiLst 線性結(jié)構(gòu)特點： 空或者只有一個結(jié)點。將 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， 并仍為遞增序。將 LA 和 LB 進(jìn)行合并至 另一線性表 LC， 并仍為遞增序。amp。 Listinsert(Lc, ++k, ai ) 。 合并操作的 算法 實現(xiàn) 26 物料管理 LILST 26 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]。 (=1,表示線性表中無數(shù)據(jù)元素 ) return L。 29 物料管理 LILST 29 DataStructures:LiLst 插入和刪除的時間復(fù)雜性分析： 刪除第 4 個結(jié)點，移動 6－ 4 次。另外，通過 KEY 查找結(jié)點，代價 O(n)。j=I。刪除 將第 i個元素從線性表中去掉 步驟： ① 將 ai+1~an順序上移 ②修改 len指針（相當(dāng)于修改表長），使之指向最后一個元素 Int Delete_seqlist(seqlist *L, int i) { if(i1||iLlen+1) {printf(“No this value of i”)。查找 查找算法？（同學(xué)自己編寫） 35 物料管理 LILST 35 DataStructures:LiLst 線性表應(yīng)用舉例： （ 1） .將順序表（ a1,a2,…,an ）重新排列為以 a1為界的兩部分： a1前面的值均比 a1小， a1后面的值均比 a1大（這里假設(shè)數(shù)據(jù)元素的類型具有可比性，不妨設(shè)為整型）。 單鏈表 ：鏈表中的每個結(jié)點只有一個指針域，我們將這種鏈表稱為單鏈表。 /* 設(shè)置一個標(biāo)志 ， 初值為 1， 當(dāng)輸入 “ $”時 ， flag為 0， 建表結(jié)束 */ L=(Linklist)malloc(sizeof(Node))； /*為頭結(jié)點分配存儲空間 */ Lnext=NULL。 Node *r, *s。 sdata=c。amp。 / * 找到結(jié)點 key， 退出循環(huán) * / return p。ki1) /*先找到第 i1個數(shù)據(jù)元素的存儲位置 ,使指針 Pre指向它 */ { pre=prenext。 p a1 … ai1 ai … an ∧ p a1 … L … an ∧ ai1 ai ai+1 r L 55 物料管理 LILST 55 DataStructures:LiLst 單鏈表刪除算法實現(xiàn) void DelList(LinkList L,int i,ElemType *e) /*在帶頭結(jié)點的單鏈表 L中刪除第 i個元素 ， 并保存其值到變量 *e中 */ { Node *p,*r。 return ERROR。 j=0。 ? 算法實現(xiàn) ? 算法演示鏈接 58 物料管理 LILST 58 DataStructures:LiLst 求兩個集合的差算法實現(xiàn) void Difference (LinkList LA,LinkList LB) /*此算法求兩個集合的差集 */ { Node *pre。 if (q!=NULL) { r=p。在循環(huán)單鏈表中，表中所有結(jié)點被鏈在一個環(huán)上。 /*找到表 LA的表尾 */ while (qnext!=LB) q=qnext。 e s ① ② ③ ④ … b p a … 67 物料管理 LILST 67 DataStructures:LiLst 雙向鏈表的前插操作算法實現(xiàn) void DlinkIns(DoubleList L,int i,ElemType e) { DNode *s,*p。 } else return FALSE。 return TRUE。 pnextprior=h。我們把這種用游標(biāo)指示器實現(xiàn)的單鏈表叫做 靜態(tài)單鏈表 (Static Linked List)。 space[0]cursor=0。 return i。/*k為已用靜態(tài)單鏈表的第一個元素的下標(biāo)值 */ for(m=1。int *av ) { k=space[0]cursor。 int exp。c,amp。c,amp。amp。 83 物料管理 LILST 83 DataStructures:LiLst 兩個 多項式相加算法實現(xiàn) void polyadd(Polylist polya。 /*在當(dāng)前表尾做插入 */ rear=s。 rear=head =(Polynode *)malloc(sizeof(Polynode))。/*將第 i 個元素占據(jù)的空間回收 */ av=j 。 void delete(StaticList space。 /*修改備用表的頭指針 */ space[j]data=x。 /*設(shè)置備用鏈表頭指針初值 */ } 75 物料管理 LILST 75 DataStructures:LiLst 靜態(tài)鏈表 分配結(jié)點與結(jié)點回收 ? 分配結(jié)點 int getnode(int *av)/*從備用鏈表摘下一個結(jié)點空間 ， 分配給待插入靜態(tài)鏈表中的元素 */ { int i=*av。 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)單鏈表 。 data域存放結(jié)點的數(shù)據(jù)信息，next域為游標(biāo)指示器，指示后繼結(jié)點在結(jié)構(gòu)數(shù)組中的相對位置（即數(shù)組下標(biāo)）。 /* p指向 b結(jié)點 */ q=hprior。 pnextprior=pprior。 pprior=s。這樣形成的鏈表中就有兩條方向不同的鏈，我們稱之為 雙 ( 向 ) 鏈表 (Double Linked List)。 q=LB。 } } } 59 物料管理 LILST 59 DataStructures:LiLst 循環(huán)鏈表 循環(huán)鏈表 (Circular Linked List) 是一個首尾相接的鏈表。amp。 ? 算法思想： 由集合運算的規(guī)則可知，集合的差 AB中包含所有屬于集合 A而不屬于集合 B的元素。 int ListLength(LinkList L) /*L為帶頭結(jié)點的 單鏈表 */ { Node *p。 k=k+1。 prenext=s。 while(pre!=NULLamp。 / * 從表中第一個結(jié)點比較 * / while (p!=NULL) if (pdata!=key) p=pnext。 49 物料管理 LILST 49 DataStructures:LiLst 按序號查找算法實現(xiàn) / * 在帶頭結(jié)點的單鏈表 L中查找第 i個結(jié)點 ， 若找到 (1≤i≤n) ， 則返回該結(jié)點的存儲位置 。 輸入 “ $”時 flag為 0， 建表結(jié)束 */ { c=getchar()。 } else flag=0。 Node *s。 現(xiàn)在我們從兩個角度來討論鏈表： ，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表； ，鏈表可分為單鏈表、循環(huán)鏈 表和雙鏈表。 return(1)。線性表的第 i 個結(jié)點存于 Lelem[i1] 之中。return(0)。在長度為 n 的線性表中刪除一個結(jié)點的平均次數(shù)為： ∑(ni)/n = (n1)/2 時間復(fù)雜性為 O(n)。 i =1 n 30 物料管理 LILST 30 DataStructures:LiLst 插入和刪除的時間復(fù)雜性分析： 插第 4 個結(jié)點之前，移動 6－（ 4－ 1） 次。 L=malloc(sezeof(seqlist))。 則： an ai1 a2 a1 ai LOC(ai) = LOC(ai1) + L = LOC(ai2) + 2L = LOC(ai(i1)) + (i1)L = LOC(a1) + (i1)L }。 ++j。 = ListLength(Lb)。將 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， 并仍為遞增序。對 n0,除了第一個和最后一個元素外，其余各節(jié)點有且僅有一個直接前驅(qū)和直接后繼?；蛘? 存在 唯一的 一個被稱之為 “ 第一個 ” 的結(jié)點。 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é)點為遞增序。 9 物料管理 LILST 9 D