【正文】 1 頁 時間復雜度舉例 （ a） X： =X+1 ； O（ 1） （ b） FOR I： =1 TO n DO X： = X+1； O（ n） （ c） FOR I： = 1 TO n DO FOR J： = 1 TO n DO O（ n2 ） X： = X+1； 下一頁 上一頁 停止放映 第 32 頁 二、線性表 是指數據元素之間的關系為一一對應的線性關系的數據結構。 形式定義： 含有 n個數據元素的線性表是一種數據結構，表示為： Linear_list=( D , R ) 其中 : D={ai | ai?D0,i=1,2,3,…,n,n ?0} R={N}, N={ai1,ai|ai1,ai ?D0 ,i=1,…,n} D是數據元素的有限集合， R是 D上邏輯關系的有限集合。 采用順序存儲結構的線性表簡稱為“順序表”。 step3 表的長度 +1。ki。 /* 將 x存放在第 i+1 位置 */ ?元素個數加“ 1” last++； /* last加“ 1”后，結果為“ 9” */ ?最后，得到的結果數列是 {4,5,8,10,21,25,30,43,59} 下一頁 上一頁 停止放映 第 40 頁 算法 11 插入算法 insert（ int i， int x） { int k； if（ last==MAXLENGTH） { printf（“線性表已滿！ \n”)。 } else { for (k=last1。 ++last。 printf(“Enter x、 loc\n”)。 for (j=0。 /* 插入操作子函數 */ for (j=0。 step3 表的長度 1。k=last。 exit(1)。 last。 printf(“Enter loc\n”)。jMAXLENGTH,j++) printf(“%d “,list[j])。jMAXLENGTH,j++) printf(“%d “,list[j])。 ? 順序表 缺點是： – 難于插入、刪除操作； – 需要預先分配空間，不管這些空間能否最大限度地利用。 struct node *next 。 頭結點 為方便操作，在頭指針和頭結點之間設置的結點。例如，要刪除結點 ai，首先要使指針 P指向 ai，即： a1 ... ... head ai an ^ p 指針 p是指向存儲單元 ai的指針，地址內的內容可以通過 Pdata得到，指向下個元素的指針用 pnext得到 下一頁 上一頁 停止放映 第 56 頁 指針的基本操作列表 p=（ NODE*） malloc（ sizeof（ NODE）） 申請一個結點空間 ,并將地址送入 p中 free（ p） 釋放 p指針所指結點的空間 p=q 指針 p指向指針 q所指的結點 p=qnext 指針 p指向指針 q所指結點的后繼 p=pnext 指針 p向后移動一個結點 pnext=q 將指針 q所指結點改接為指針 p所指結點的后繼 pnext=NULL 將指針 p所指結點與后繼結點斷開 下一頁 上一頁 停止放映 第 57 頁 指針操作的舉例 1 申請一個結點空間 ,并將地址送入 p中 p 操作前狀態(tài) 操作后狀態(tài) p p=（ NODE*） malloc（ sizeof（ NODE）） 下一頁 上一頁 停止放映 第 58 頁 指針操作的舉例 2 p=pnext 指針右移一個結點位置。 算法描述： ?從數列左邊開始（即從第 1個元素開始）進行處理； ?每次處理，將計數器值加“ 1”、指針右移，共處理 i次； while((p!=NULL)amp。 /* 計數器加“ 1” */ } ? 退出循環(huán)后，如果 i值正確，則返回 p值；否則返回空值。 /* 返回 i的值 */ else return NULL。 while((p!=NULL)amp。 } if((p!=NULL)amp。 } 下一頁 上一頁 停止放映 第 64 頁 單鏈表長度計數的算法 單鏈表長度計數算法操作步驟 : step1 初始化 ,指針 P指向頭指針， 計數器置 0 step2 P非空循環(huán) step3 每循環(huán)一次 ,P后移一個位置 , 計數器加 1 step4 循環(huán)結束 ,返回計數器值。 while( p!=NULL) { p=pnext。 if(i==1) p=head。 } else { s=(NODE*)malloc(sizeof(NODE))。 } } /* 令 P指向 A i1 */ /* 若 i=1， P指向頭指針 */ /* P為空，說明找不到 i位置 */ /* P定位成功 */ 下一頁 上一頁 停止放映 第 68 頁 單鏈表刪除算法 14 算法 14操作步驟 : ? step1 找到 ai1的位置 ,使指針 p指向 ai1 ? step2 使指針 t指向 p所指結點的后繼 ? step3 使 t所指結點 ai 脫鏈 ? step4 釋放 t p t a i1 ai a i+1 示例 t=pnext pnext=tnext free(t) 下一頁 上一頁 停止放映 第 69 頁 單鏈表的刪除算法程序 delete(NODE *head, int i) { NODE *p,*t。 exit(0)。 pnext = tnext。 ?如果讓鏈表首尾相接，構成環(huán)形，這就是 單循環(huán)鏈表 。 下一頁 上一頁 停止放映 第 73 頁 雙向循環(huán)鏈表 ?在單向循環(huán)鏈表中，也存在檢索前趨結點費時的問題（所需時間是 O（ n））。 ai1的標識符為 : p?.prior, ai1的數據域標識符為 : p?.prior ? .data ai+1的標識符為 : p?.next, ai+1的數據域標識符為 : p?. next ? .data p a i+1 ai a i1 下一頁 上一頁 停止放映 第 80 頁 鏈表存儲結構的特點 插入、刪除操作極為方便 數據非連續(xù)存放、順序存取 邏輯上相鄰，物理上不一定相鄰 存儲結構較復雜、需要額外的存儲空間 結論 ： 鏈表存儲結構適合于表中元素頻繁變動的線性表。 head s ^ ... p a i ai1 a2 a1 下一頁 上一頁 停止放映 第 83 頁 鏈表的動態(tài)生成（方法二）從后往前 算法操作步驟： step1 初始化；頭指針置 NULL,線性表元素存于A[N]中 ,i=N1 step2 i = 0 循環(huán) 1) 使 s指向新生成的結點， 2) sdata = A[i] ,snext = head 3) 指針 s始終指向頭指針 head=s step3 結束循環(huán) , 返回頭指針 head。 j = length(head_a) 。 /* 插在 B的表頭 */ delete(head_a , j )。 若 a b , 則 j 加 1 。 len_a = length(a) 。 ( j = len_b)) { data_a = get( a, i )。 else if ( data_a == data_b) { insert ( c, data_a, k )。 } } } 例如： A = { 1,3,5}， B={2,3,6}, C={}； Step1 從 A中取出 1和 B中 2比較， i ++； Step2 從 A中取出 3和 B中 2比較， j ++； Step3 從 A中取出 3和 B中 3比較，將 3插入C中，得結果： C={ 3}；