【文章內容簡介】 i 個結點之前，移動 n(i1) 次。 29 物料管理 LILST 29 DataStructures:LiLst 插入和刪除的時間復雜性分析： 插第 4 個結點之前，移動 6－（ 4－ 1） 次。 在一般情況下，插在第 i 個結點之前，移動 n(i1) 次 插在第 1 個結點之前，移動 n 次 插在第 2 個結點之前，移動 n1 次 插在第 i 個結點之前，移動 n(i1) 次 插在第 n 個結點之前，移動 1 次。 插在第 n 個結點之后，移動 0 次。 總共 n+1 種情況 在長度為 n 的線性表中插入一個結點的平均次數為： ∑(ni+1)/(n+1) = n/2 時間復雜性為 O(n)。 i =1 n 30 物料管理 LILST 30 DataStructures:LiLst 插入和刪除的時間復雜性分析： 刪除（刪除線性表的第 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 個結點，移動 ni 次。 刪除 31 物料管理 LILST 31 DataStructures:LiLst 插入和刪除的時間復雜性分析： 刪除第 4 個結點，移動 6－ 4 次。 在一般情況下，刪除第 i 個結點，移動 ni 次 刪除第 1 個結點，移動 n1 次 刪除第 2 個結點，移動 n2 次 刪除第 i 個結點，移動 ni 次 刪除第 n 個結點，移動 0 次。 總共 n 種情況 在長度為 n 的線性表中刪除一個結點的平均次數為： ∑(ni)/n = (n1)/2 時間復雜性為 O(n)。 i =1 n 另外，通過 KEY 查找結點，代價 O(n)。 查找第 i 個結點，代價 O(1)。 32 物料管理 LILST 32 DataStructures:LiLst 插入、刪除、查找的實現(xiàn)算法： 插入 Int insert_seqlist(seqlist *L,int i, datatype x) { if ( Llen==MAXSIZE1) {printf(“overflow”)。 return(1)。} /*表空間已滿，不能插入 */ if (i1 || iLlen+1) {printf(“Infeasible”)。return(0)。} /*檢查插入位置的正確性 */ if(j=Llen。j=I。j) Ldata[j+1]=Ldata[j]。 /*結點移動 */ Ldata[i1]=x。 /*新元素插入 */ Llen++。 /*表的長度增加 */ return(1)。 /*插入成功，返回 */ } // initList_Sq。線性表的第 i 個結點存于 Lelem[i1] 之中。 33 物料管理 LILST 33 DataStructures:LiLst 插入、刪除 、 查找的實現(xiàn)算法： 刪除 將第 i個元素從線性表中去掉 步驟： ① 將 ai+1~an順序上移 ②修改 len指針（相當于修改表長），使之指向最后一個元素 Int Delete_seqlist(seqlist *L, int i) { if(i1||iLlen+1) {printf(“No this value of i”)。 return(0)。} for(j=i。 j=Llen。j++) Ldata[j1]=Ldata[j]。 /*向上移動 */ Llen。 return(1)。 /*刪除成功 */ } 34 物料管理 LILST 34 DataStructures:LiLst 插入、刪除 、 查找的實現(xiàn)算法： 查找 查找算法？（同學自己編寫） 35 物料管理 LILST 35 DataStructures:LiLst 線性表應用舉例： （ 1） .將順序表（ a1,a2,…,an ）重新排列為以 a1為界的兩部分： a1前面的值均比 a1小， a1后面的值均比 a1大（這里假設數據元素的類型具有可比性，不妨設為整型）。 （ 2） .有順序表 A和 B,其元素均按從小到大的升序排列，編寫算法將他們合并成一個順序表 C，要求 C的元素也是從小到大的升序排列。 36 物料管理 LILST 36 DataStructures:LiLst 順序存儲結構的優(yōu)點和缺點 ? 優(yōu)點： ； 。 ? 缺點： ，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結點，其效率較低； ，存儲分配只能預先進行靜態(tài)分配。因此當表長變化較大時，難以確定合適的存儲規(guī)模。 37 物料管理 LILST 37 DataStructures:LiLst 線性表的鏈式存儲 ? 鏈表定義： 采用鏈式存儲結構的線性表稱為 鏈表 。 現(xiàn)在我們從兩個角度來討論鏈表： ，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表； ，鏈表可分為單鏈表、循環(huán)鏈 表和雙鏈表。 38 物料管理 LILST 38 DataStructures:LiLst ? 單鏈表 ? 單鏈表上的基本運算 ? 循環(huán)鏈表 ? 雙向鏈表 ?* 靜態(tài)鏈表 ? 順序表和鏈表的比較 鏈表 39 物料管理 LILST 39 DataStructures:LiLst 單鏈表 結點（ Node） 為了正確地表示結點間的邏輯關系，必須在存儲線性表的每個數據元素值的同時，存儲指示其后繼結點的地址（或位置）信息，這兩部分信息組成的存儲映象叫做 結點（ Node） 。 單鏈表 ：鏈表中的每個結點只有一個指針域，我們將這種鏈表稱為單鏈表。 單鏈表包括 兩個域 ： 數據域 用來存儲結點的值； 指針域 用來存儲數據元素的直接后繼的地址（或位置）。 頭指針 ：指向鏈表頭結點的指針。 40 物料管理 LILST 40 DataStructures:LiLst 單鏈表的示例圖 頭指針 H 存儲地址 數據域 指針域 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 帶頭結點的單鏈表示意圖 有時為了操作的方便，還可以在單鏈表的第一個結點之前附設一個頭結點。 ? 帶頭結點的空單鏈表 ? 帶頭結點的單鏈表 ∧ H a1 a2 … H an ∧ 42 物料管理 LILST 42 DataStructures:LiLst 單鏈表的存儲結構描述 typedef struct Node / * 結點類型定義 * / { ElemType data； struct Node * next； }Node, *LinkList； /* LinkList為結構指針類型 */ 43 物料管理 LILST 43 DataStructures:LiLst 單鏈表上的基本運算 ? 線性表的基本運算 ： 建立單鏈表 單鏈表查找 單鏈表插入操作 單鏈表刪除 ? 算法應用示例： 求單鏈表的長度 求兩個集合的差 44 物料管理 LILST 44 DataStructures:LiLst 建立單鏈表 ? 頭插法建表 算法描述： 從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭結點之后，直至讀入結束標志為止。 c1 ∧ s L ∧ L ci1 ∧ c2 c1 ∧ ci s … c1 ∧ 45 物料管理 LILST 45 DataStructures:LiLst 頭插法建表算法 Linklist CreateFromHead() { LinkList L。 Node *s。 int flag=1。 /* 設置一個標志 ， 初值為 1， 當輸入 “ $”時 ， flag為 0， 建表結束 */ L=(Linklist)malloc(sizeof(Node))； /*為頭結點分配存儲空間 */ Lnext=NULL。 while(flag) { c=getchar()。 if(c!=’$’) /*為讀入的字符分配存儲空間 */ { s=(Node*)malloc(sizeof(Node))。 sdata=c。 snext=Lnext。 Lnext=s。 } else flag=0。 } } 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。 Node *r, *s。 int flag =1。 L=(Node * )malloc(sizeof(Node))。/*為頭結點分配存儲空間 */ Lnext=NULL。 r=L。 /*r指針始終動態(tài)指向鏈表的當前表尾 */ while(flag) /*標志 ， 初值為 1。 輸入 “ $”時 flag為 0， 建表結束 */ { c=getchar()。 if(c!=’$’) { s=(Node*)malloc(sizeof(Node))。 sdata=c。 rnext=s。 r=s } else { flag=0。 rnext=NULL。 } } } 48 物料管理 LILST 48 DataStructures:LiLst 單鏈表查找 ? 按序號查找 算法描述： 設帶頭結點的單鏈表的長度為 n，要查找表中第 i個結點，則需要從單鏈表的頭指針 L出發(fā)，從頭結點（ Lnext）開始順著鏈域掃描，用指針 p指向當前掃描到的結點 ,初值指向頭結點（ p=Lne