【正文】 int i,elementtype x) { int j。 if (i0||i=listn){ /*位置不合理 */ printf(“not exit!\n”)。 return(0)。 } if (listn==Maxnum) { /*空間已滿 */ printf(“out of space!\n”)。return (0)。 } for (j=listn1。j=i。j) /*向后移動元素 */ listelement[j+1]= listelement[j]。 listelement[i]=x。 /*插入元素 */ listn++。 /*長度加 1*/ return(1)。 } 演示 5. 刪除 delete(L, i) 功能： 刪除順序表 L中下標為 i（ 0≤in 1）的數據元 素 ,刪除前線性表為 ( a0， a1， … ， an1 ) 刪除后 ,線性表長度為 n1, 線性表為 ( a0， a1， … ， ai1， ai+1， … ， an1 ) 刪除前 n=8 刪除后 n=7 刪除操作示意圖： Delete(p,3) 11 12 34 3 27 16 147 44 12 34 3 11 27 16 147 44 a0 a1 a2 a3 a4 a5 a6 a7 a0 a1 a2 a3 a4 a5 a6 a7 刪除操作算法 int Delete(ptsqlist list,int i) { int j。 if (i0||i=listn){ /*位置不合理 */ printf(“not exist!\n”)。 return (0)。 } for (j=i。j=listn1。j++) /*向前移動元素 */ listelement[j]= listelement[j+1]。 listn。 /*長度減 1 */ return(1)。 } 演示 viod fanzhuanlist(ptsqlist list) { elementtype mid。 int a,z。 a=0。z=listn1。 for (。az。a++,z) /*逆轉順序表 */ { mid=listelement[a]。 listelement[a]=listelement[z]。 listelement[z]=mid。 } } a0 a1 … ai1 ai ai+1 … an1 mid 怎樣分析插入和刪除算法 的 T（ n）呢？ 在下標為 i的位置 (第 i+1個位置 )前插入 元素下標 移動元素個數 0 n 1 n1 i ni n1 1 n 0 三、算法時間復雜度分析 在順序表中插入元素，時間主要耗費在移動元素上，而移動的個數取決于插入的位置以及表的長度。 1 2 i1 i i+1 n a0 a1 … ai1 ai ai+1 … an1 假設在線性表的任何位置插入元素的概率相同，即 pi= 1/(n+1) 則有： 假設 pi是在第 i個元素之前插入元素的概率，在長度為 n的順序表中插入一個元素，所需移動元素個數數學期望值為： ninnEnii 21)(110???? ??????niii pinE0*)(假設在線性表的任何位置刪除元素的概率相同，即 pd= 1/n 則有： 刪除下標為 i的元素（第 i+1個）需移動 ni1個元素，設在相應位置刪除元素的概率是 pd，則刪除的平均移動次數是： 21)1(1 10????? ???ninnEnid??????10*)1(nidd pinE在順序表中插入或刪除元素的 時間時間復雜度 為 O(n) 相關例題 例 1 利用順序表設計一算法，用以清除表 L中的多余的重復結點。如表 L（ 21， 3， 5， 3， 21， 3， 90， 5）運算后變?yōu)?L（ 21， 3， 5， 90） 算法思想應該是怎樣的呢？ 相關代碼： void Purge(ptsqlist list) { int i,j,k。 i=0。 while (ilistn) { j=i+1。 while (jlistn) { if (listelement[i]==listelement[j]) { for (k=j+1。klistn 。k++ ) listelement[k1]=listelement[k]。 listn=listn1。 }else j=j+1。 } i=i+1。 } } 作業(yè)：設計相關算法，完成線性表的其它操作：Locate(p,x)。 Union(p,q). 小結 順序表的特點： 1 通過元素的存儲順序反映線性表中 數據元素之間的邏輯關系； 2 可隨機存取順序表的元素； 3 順序表的插入、刪除操作要通過移動 元素實現； 線性表的鏈式存儲結構是用一組 任意 的存儲單元存儲線性表的數據元素。為了表示線性表中元素的先后關系，每個結點除了需要存儲自身的信息外，還需存儲一個指示其直接后繼的信息（直接后繼的存儲位置）。 ai+1 a1 ai1 a2 ai an 線性表的鏈式存儲結構 1010 1012 1014 1016 1018 1020 1022 1024 1026 用線性鏈表存儲線性表時，數據元素之間的關系是通過保存直接后繼元素的存儲位置來實現的 線性鏈表 一，線性鏈表的概念 a4 a3 a1 a2 NULL 1010 1024 1014 a1 a4 a2 結點 數據域 指針域 ? 線性鏈表有關術語 ? 結點： 數據元素及直接后繼的存儲位置（地址）組成一個數據元素的存儲結構，稱為一個結點； ? 結點的數據域 ： 結點中用于保存數據元素的部分 。 ? 結點的指針域 ： 結點中用于保存數據元素直接后繼存儲地址的部分 。 存儲數據元素 存儲直接后繼 結點的地址 怎樣在計算機上 實現線性鏈表？ 結點變量圖示 LNode ：結構類型名； LNode類型結構變量有兩個域： data： 用于存放線性表的數據元素， next： 用于存放元素直接后繼結點的地址； 該類型結構變量用于表示線性鏈表中的一個結點； data next LNode類型 結構變量 p p是 LNode類型的指針變量 線性鏈表的結點類型定義及指向結點的指針類型定義 typedef struct Node { Etype data。 struct Node *next。 }LNode, *LinkList。 數據域 指針域 順序 建立單鏈表 （尾插法） H p a q H p a q H p a q b q H b c p q q a ① ① ② ② Lnode* Screat_List (void)