【導(dǎo)讀】數(shù)據(jù)結(jié)構(gòu)要研究什么問題？如何描述線性表？它們的特點(diǎn)是什么？數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)的專業(yè)技術(shù)基礎(chǔ)課。在存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上實(shí)現(xiàn)對(duì)數(shù)據(jù)的操作。了解線性DS的邏輯結(jié)構(gòu)、物。有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念。人口預(yù)報(bào)——微分方程。優(yōu)化問題——線性規(guī)劃、非線性規(guī)劃。震動(dòng)問題——矩陣分析；特征值、特征。信息管理——二維數(shù)據(jù)表。下棋——人工智能。交通管理——最佳道路選擇。它是客觀事物的符號(hào)表示。是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個(gè)體。式和相關(guān)操作方法的學(xué)問。課題組由1名教師、1~3名研究生、1~6名本科生。形式上進(jìn)行研究、推理、運(yùn)算等各種操作。算法的最終實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。儲(chǔ)單元中的存儲(chǔ)形式。插入、刪除操作不便。非連續(xù)存放,借助指針來表示元素間的關(guān)系;結(jié)構(gòu)較復(fù)雜，需要額外存儲(chǔ)空間。增、刪操作簡(jiǎn)單。在數(shù)據(jù)元素與存儲(chǔ)位置之間建立一種。哈希查找中的哈希表就是這樣一種存。–數(shù)據(jù)元素間無內(nèi)在聯(lián)系；

　　

【正文】 雙循環(huán)鏈表為空的條件 : head ?.prior = head ?.next = head 表示形式為 : head head ... ... ^ ^ an a2 a1 下一頁 上一頁 停止放映 第 76 頁 雙向循環(huán)鏈表特點(diǎn) ?適合于兩個(gè)方向的移動(dòng)。 ?找其前趨結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（ 1）。 下一頁 上一頁 停止放映 第 77 頁 十字鏈表 prior data next up down 上指針 下指針 后繼結(jié) 點(diǎn)指針 前趨結(jié) 點(diǎn)指針 特點(diǎn)： 四個(gè)方向可 以自由移動(dòng) 下一頁 上一頁 停止放映 第 78 頁 4. 鏈表結(jié)點(diǎn)及標(biāo)識(shí)符 約定： 設(shè)指針 p指向結(jié)點(diǎn) ai ? ai作為一個(gè)變量，其標(biāo)識(shí)符為 p? ? 由于 p?是記錄類型，它的分量分別表示為： 數(shù)據(jù)域標(biāo)識(shí)符為 p? .data 后繼結(jié)點(diǎn)指針 域標(biāo)識(shí)符 為 p?.next p p p?.data p?.next ai ai 下一頁 上一頁 停止放映 第 79 頁 鏈表結(jié)點(diǎn)及各分量標(biāo)識(shí)符 (雙鏈表 ) 約定： 設(shè)指針 p指向結(jié)點(diǎn) ai ? ai作為一個(gè)變量，其標(biāo)識(shí)符為 p? ? p?的分量分別表示為： ? 數(shù)據(jù)域標(biāo)識(shí)符為 p? .data ? 后繼結(jié)點(diǎn)指針域 標(biāo)識(shí)符 為 p?.next ? 前趨結(jié)點(diǎn)指針域 標(biāo)識(shí)符 為 p? .prior。 ai1的標(biāo)識(shí)符為 : p?.prior, ai1的數(shù)據(jù)域標(biāo)識(shí)符為 : p?.prior ? .data ai+1的標(biāo)識(shí)符為 : p?.next, ai+1的數(shù)據(jù)域標(biāo)識(shí)符為 : p?. next ? .data p a i+1 ai a i1 下一頁 上一頁 停止放映 第 80 頁 鏈表存儲(chǔ)結(jié)構(gòu)的特點(diǎn) 插入、刪除操作極為方便 數(shù)據(jù)非連續(xù)存放、順序存取 邏輯上相鄰，物理上不一定相鄰 存儲(chǔ)結(jié)構(gòu)較復(fù)雜、需要額外的存儲(chǔ)空間 結(jié)論 ： 鏈表存儲(chǔ)結(jié)構(gòu)適合于表中元素頻繁變動(dòng)的線性表。 下一頁 上一頁 停止放映 第 81 頁 5. 鏈表的動(dòng)態(tài)生成 鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。因此，建立鏈表的過程是動(dòng)態(tài)生成的過程。 按鏈表結(jié)點(diǎn)建立的順序、方向不同，分為兩種方法： 從前往后的動(dòng)態(tài)生成法 （ 算法 16） 從后往前的動(dòng)態(tài)生成法 （算法 17） 下一頁 上一頁 停止放映 第 82 頁 鏈表動(dòng)態(tài)生成（方法一）從前往后 算法操作步驟： step1 初始化；頭指針置 NULL step2 輸入結(jié)點(diǎn)數(shù)據(jù)非 0循環(huán) 1)、使 s指向新生成的結(jié)點(diǎn)， sdata = num 2)、若 head=NULL(第 1個(gè)結(jié)點(diǎn) ),head=s 3)、否則 pnext=s 4)、指針 p始終指向 s,p=s step3 結(jié)束循環(huán) ,pnext =NULL, 返回頭指針 head。 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。 head ^ ... s ai1 ai an ai2 下一頁 上一頁 停止放映 第 84 頁 例題分析一 將一個(gè)單鏈表分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表 A和 B， A中含有原表中序號(hào)為奇數(shù)的元素， B中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序。 算法分析： 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 為止。 下一頁 上一頁 停止放映 第 85 頁 例題一程序 void separate( NODE *head_a , NODE *head_b ) { int data1, j 。 j = length(head_a) 。 if ( j%2 == 1) j 。 while ( j = 2) { data1= get( head_a, j )。 /* 取偶數(shù)編號(hào)的元素 */ insert(head_b , data1 , 1) 。 /* 插在 B的表頭 */ delete(head_a , j )。 /* 將 A中偶數(shù)元素刪除 */ 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是遞增有序的。 ? 算法分析： Step1 初始化，求 A的 B表長(zhǎng) len_a和 len_b, i、 j和 k分別取初值 1，表示指向三個(gè)鏈表當(dāng)前位置的指針 Step2 i和 j均分別 ≤ len_a和 len_b的循環(huán) 分別取出兩個(gè)表中的當(dāng)前元素進(jìn)行比較 ： 若 a b , 則 i 加 1 。 若 a b , 則 j 加 1 。 若 a = b , 則將 a插入 C中 ,i、 j和 k均加 1。 Step3 重復(fù)執(zhí)行 Step2 ，直到所有表都處理完為止。 下一頁 上一頁 停止放映 第 87 頁 例題二示意圖 A a1 a2 a3 … ai ai+1 … an B b1 b2 b3 … bi bi+1 … bm 比較） i j A a1 a2 a3 … ai ai+1 … an B b1 b2 b3 … bi bi+1 … bm 比較） i j 若 ab, 則 i++ A a1 a2 a3 … ai ai+1 … an B b1 b2 b3 … bi bi+1 … bm 比較） i j 若 ab, 則 j++ 下一頁 上一頁 停止放映 第 88 頁 例題二程序 void separate( NODE *a , NODE *b， NODE *c ) { int i=1， j=1， k=1， len_a, len_b, data_a, data_b 。 len_a = length(a) 。 len_b = length(b) 。 /* 求 a和 b的長(zhǎng)度 */ while ( ( i = len_a)amp。amp。 ( j = len_b)) { data_a = get( a, i )。 data_b = get( b, j) 。 /* 取 A和 B中的元素 */ if (data_a data_b) i ++。 else if (data_a data_b) j ++。 else if ( data_a == data_b) { insert ( c, data_a, k )。 k ++ 。 i ++ 。 j++。 } } } 例如： 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中，得結(jié)果： C={ 3}； 下一頁 上一頁 停止放映 第 89 頁 結(jié)束語 歡迎參加到中心網(wǎng)站 《 軟件基礎(chǔ) 》 課程的學(xué)習(xí)討論中來。 中心網(wǎng)址： 課件下載地址 : 我的 Email地址 : 答疑安排： 每星期四下午： 4： 00～ 6： 00 地點(diǎn)： 計(jì)教中心 102房間（ 1300大教室對(duì)面）