【正文】 d,i1)。 } } /* P定位操作 */ /* P定位成功 */ 下一頁 上一頁 停止放映 第 70 頁 3. 循環(huán)單鏈表和雙向鏈表 ?鏈表檢索只能從頭指針開始 ,且只能順鏈表方向移動(dòng)。 ?找其前趨結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（ 1）。 算法分析： Step0 初始化，求 A的長(zhǎng)度送 j ，若 j 為奇數(shù)則減 1； Step1 從 A的后部取出第 1個(gè)偶數(shù)編號(hào)的元素（ a2*i） Step2 將取出的偶數(shù)編號(hào)的元素插入 B的開頭 Step3 從 A中刪除該偶數(shù)元素 Step4 每處理一個(gè)過程， j 減 2 （長(zhǎng)度減?。?，繼續(xù)執(zhí)行 13步，直到 j 2 為止。 } } 例如： A = { a1， a2， a3， a4， a5}， B={}； Step1 從 A中取出 a4插入 B中，從 A中刪除 a4 A = { a1， a2， a3， a5}， B={a4}； Step2 從 A中取出 a2插入 B中，從 A中刪除 a2 A = { a1， a3， a5}， B={ a2， a4}； 下一頁 上一頁 停止放映 第 86 頁 例題分析二 ? 求兩個(gè)鏈表 A和 B的交集 C（由 A和 B中相同元素組成的集合為交集），且 A和 B是遞增有序的。 /* 求 a和 b的長(zhǎng)度 */ while ( ( i = len_a)amp。 i ++ 。 else if ( data_a == data_b) { insert ( c, data_a, k )。 len_a = length(a) 。 /* 插在 B的表頭 */ delete(head_a , j )。 head s ^ ... p a i ai1 a2 a1 下一頁 上一頁 停止放映 第 83 頁 鏈表的動(dòng)態(tài)生成（方法二）從后往前 算法操作步驟： step1 初始化；頭指針置 NULL,線性表元素存于A[N]中 ,i=N1 step2 i = 0 循環(huán) 1) 使 s指向新生成的結(jié)點(diǎn)， 2) sdata = A[i] ,snext = head 3) 指針 s始終指向頭指針 head=s step3 結(jié)束循環(huán) , 返回頭指針 head。 下一頁 上一頁 停止放映 第 73 頁 雙向循環(huán)鏈表 ?在單向循環(huán)鏈表中，也存在檢索前趨結(jié)點(diǎn)費(fèi)時(shí)的問題（所需時(shí)間是 O（ n））。 pnext = tnext。 } } /* 令 P指向 A i1 */ /* 若 i=1， P指向頭指針 */ /* P為空，說明找不到 i位置 */ /* P定位成功 */ 下一頁 上一頁 停止放映 第 68 頁 單鏈表刪除算法 14 算法 14操作步驟 : ? step1 找到 ai1的位置 ,使指針 p指向 ai1 ? step2 使指針 t指向 p所指結(jié)點(diǎn)的后繼 ? step3 使 t所指結(jié)點(diǎn) 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。 if(i==1) p=head。 } 下一頁 上一頁 停止放映 第 64 頁 單鏈表長(zhǎng)度計(jì)數(shù)的算法 單鏈表長(zhǎng)度計(jì)數(shù)算法操作步驟 : step1 初始化 ,指針 P指向頭指針， 計(jì)數(shù)器置 0 step2 P非空循環(huán) step3 每循環(huán)一次 ,P后移一個(gè)位置 , 計(jì)數(shù)器加 1 step4 循環(huán)結(jié)束 ,返回計(jì)數(shù)器值。 while((p!=NULL)amp。 /* 計(jì)數(shù)器加“ 1” */ } ? 退出循環(huán)后，如果 i值正確，則返回 p值；否則返回空值。例如，要?jiǎng)h除結(jié)點(diǎn) ai，首先要使指針 P指向 ai，即： a1 ... ... head ai an ^ p 指針 p是指向存儲(chǔ)單元 ai的指針，地址內(nèi)的內(nèi)容可以通過 Pdata得到，指向下個(gè)元素的指針用 pnext得到 下一頁 上一頁 停止放映 第 56 頁 指針的基本操作列表 p=（ NODE*） malloc（ sizeof（ NODE）） 申請(qǐng)一個(gè)結(jié)點(diǎn)空間 ,并將地址送入 p中 free（ p） 釋放 p指針?biāo)附Y(jié)點(diǎn)的空間 p=q 指針 p指向指針 q所指的結(jié)點(diǎn) p=qnext 指針 p指向指針 q所指結(jié)點(diǎn)的后繼 p=pnext 指針 p向后移動(dòng)一個(gè)結(jié)點(diǎn) pnext=q 將指針 q所指結(jié)點(diǎn)改接為指針 p所指結(jié)點(diǎn)的后繼 pnext=NULL 將指針 p所指結(jié)點(diǎn)與后繼結(jié)點(diǎn)斷開 下一頁 上一頁 停止放映 第 57 頁 指針操作的舉例 1 申請(qǐng)一個(gè)結(jié)點(diǎn)空間 ,并將地址送入 p中 p 操作前狀態(tài) 操作后狀態(tài) p p=（ NODE*） malloc（ sizeof（ NODE）） 下一頁 上一頁 停止放映 第 58 頁 指針操作的舉例 2 p=pnext 指針右移一個(gè)結(jié)點(diǎn)位置。 struct node *next 。jMAXLENGTH,j++) printf(“%d “,list[j])。 printf(“Enter loc\n”)。 exit(1)。 step3 表的長(zhǎng)度 1。 for (j=0。 ++last。 /* 將 x存放在第 i+1 位置 */ ?元素個(gè)數(shù)加“ 1” last++； /* last加“ 1”后，結(jié)果為“ 9” */ ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,25,30,43,59} 下一頁 上一頁 停止放映 第 40 頁 算法 11 插入算法 insert（ int i， int x） { int k； if（ last==MAXLENGTH） { printf（“線性表已滿！ \n”)。 step3 表的長(zhǎng)度 +1。 形式定義： 含有 n個(gè)數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表示為： 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是數(shù)據(jù)元素的有限集合， R是 D上邏輯關(guān)系的有限集合。 下一頁 上一頁 停止放映 第 30 頁 算法的評(píng)價(jià) 算法評(píng)價(jià)的標(biāo)準(zhǔn)： 時(shí)間復(fù)雜度 指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。 算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系 為了充分地利用系統(tǒng)資源；既要效率高、速度快，又要存儲(chǔ)空間少。存儲(chǔ)時(shí)分為：數(shù)據(jù)項(xiàng)和索引號(hào)；通過索引表記錄邏輯號(hào)（記錄號(hào)）和物理號(hào)（存儲(chǔ)序號(hào)）之間的對(duì)應(yīng)關(guān)系。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : d1 d2 …… dn 數(shù)據(jù)域 特點(diǎn) : ? 連續(xù)存放 。 下一頁 上一頁 停止放映 第 11 頁 數(shù)據(jù)結(jié)構(gòu)分類 線性表 堆棧 隊(duì)列 串 數(shù)組 樹 二叉樹 圖 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) DS 下一頁 上一頁 停止放映 第 12 頁 1. 數(shù)據(jù)的邏輯結(jié)構(gòu) 它是描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們?cè)谟?jì)算機(jī)中如何存放。它研究的主要問題： ? 分析數(shù)據(jù)（加工對(duì)象）的特征 ? 選擇邏輯存儲(chǔ)結(jié)構(gòu)和物理存儲(chǔ)結(jié)構(gòu) ? 在存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上實(shí)現(xiàn)對(duì)數(shù)據(jù)的操作 下一頁 上一頁 停止放映 第 4 頁 第 2單元 線性數(shù)據(jù)結(jié)構(gòu)（一） 教學(xué)目標(biāo)： ? 了解數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念 什么是線性 DS、線性表 ? 了解線性 DS的特點(diǎn) ? 了解線性 DS的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及操作 下一頁 上一頁 停止放映 第 5 頁 學(xué)習(xí)要求 通過本單元的學(xué)習(xí)，了解并掌握： ? 有關(guān) 數(shù)據(jù)結(jié)構(gòu)（ DS）的基本概念 –數(shù)據(jù)元素、 DS、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、 DS的分類及特點(diǎn)、算法、時(shí)間復(fù)雜度等 ? 線性 DS的常用存儲(chǔ)結(jié)構(gòu) –順序、鏈表、索引、散列存儲(chǔ)結(jié)構(gòu) –單向、雙向、循環(huán)鏈表等 ? 線性 DS的有關(guān)算法 –增、刪、改 下一頁