數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料

1、word數(shù)據(jù)的邏輯結(jié)構(gòu)，指數(shù)據(jù)元素之間的邏輯關(guān)系。 數(shù)據(jù)的存儲結(jié)構(gòu)，指數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器中的存儲方式，也稱為數(shù)據(jù) 的物理結(jié)構(gòu)。數(shù)據(jù)運算，指施加在數(shù)據(jù)上的操作。算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中，每一條指令表 示一個或多個操作。粗略地說，算法是為了求解問題而給出的一個指令序列，程序是算法的一種具體 實現(xiàn)。一個算法必須滿足以下五個重要特性：1. 有窮性 2. 確定性 3. 可行性 算法的重要特征(1)(2)(3)4. 有輸入5. 有輸出有窮性 : 算法在有窮步之后結(jié)束，每一步在有窮時間內(nèi)完成。確定性 : 算法中的每一條指令有明確的含義，無二義性?？尚行?: 可

2、通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)算法中的所有操作。 算法分析的兩個主要方面是分析算法的時間復(fù)雜度和空間復(fù)雜度。算法的執(zhí)行時間數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)是一門討論 “描述現(xiàn)實世界實體的數(shù)學(xué)模型 (非數(shù)值計算 )及其上的操作在 計算機(jī)中如何表示和實現(xiàn)”的學(xué)科。,可以看作是相互之間存在著某數(shù)據(jù)結(jié)構(gòu)：是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系 種特定關(guān)系的數(shù)據(jù)元素的集合。對數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括以下幾個方面：4.5.6.主要與問題的規(guī)模有關(guān)。問題規(guī)模是一個與輸入有關(guān)的量。語句頻度是指算法中該語句被重復(fù)執(zhí)行的次數(shù)。算法中所有語句的頻度之和記作T(n),是該算法所求解問題規(guī)模的函數(shù)。當(dāng)問題規(guī)模趨向無窮大時，T(n)

3、的數(shù)量級稱為漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度，記作T(n)=O(f(n)。通常采用算法中表示基本運算的語句的頻度來分析算法的時間復(fù)雜度。例題：1.2.3.4.5.6.數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)是指 (),物理結(jié)構(gòu)是指(算法的基本特征包括有窮性、 ()、()、有輸入和輸出 。算法的有窮性是指( 算法的確定性是指( 算法的可行性是指()。)。)。)。7.8.算法分析的兩個主要方面是分析算法的( )和空間復(fù)雜度。 語句頻度是指( 算法中該語句被重復(fù)執(zhí)行的次數(shù) )。設(shè)n為正整數(shù)，對下面的程序段，寫出語句、的頻度及該程序段的時間復(fù) 雜度。for (i=1; i =n; i+)s=0;for (j=1; j =n

4、; j+) n2 ns=s+i X j；if (s%2) print(s);第二章線性表本章內(nèi)容：2.1線性表的基本概念一個線性表是有n個數(shù)據(jù)元素的有限序列：（ai, a2,，ai,，01）2.2線性表的順序存儲結(jié)構(gòu)線性表的順序存儲指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。這稱 為順序表。特點：存儲單元地址連續(xù)（需要一段連續(xù)空間）邏輯上相鄰的數(shù)據(jù)元素其物理位置也相鄰存儲密度大（100%）隨機(jī)存取，元素的存儲位置存在如下關(guān)系：Loc（a） = Loc（ai） + （i - 1） * d（1 i n）2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯χ赣萌我獾拇鎯卧娣啪€性表中的元素，每個元素

5、與其直接前 驅(qū)和（或）直接后繼之間的關(guān)系用指針來表示。這稱為鏈表。苜元結(jié)點單鏈表示恿圖頭指針是指向鏈表第一個結(jié)點的指針。頭結(jié)點是鏈表中的第一個結(jié)點但是頭結(jié)點中不存放數(shù)據(jù)元素。 單鏈表、循環(huán)鏈表的類型定義typ edef struct LNode ElemType data;/*存儲數(shù)據(jù)元素*/struct LNode *next; /* 指向后繼結(jié)點 */ SLink,*LinkList;LinkList head,tail;例題1.2.3.順序表中，邏輯上相鄰的數(shù)據(jù)元素在物理位置上（也相鄰 ）。線性表L=（ai,a2,.,an）采用順序存儲，假定在不同的n+1個位置上的插入概率相同，則插入一

6、個新元素平均需要移動的元素個數(shù)是（n/2 ）。在一個長度為n的順序表中，在第i個元素（1 i n）之前插入一個新元素時，需向后 移動（n-i+1 ）個元素。在表長為 尋找。在一個具有 復(fù)雜度為（n的單鏈表中，取得第i （1 i n ext; if (P)s = p-n ext; p- next = NULL;headleadP = s;s = s -n ext;p-n ext =head - n ext; head - n ext = p;P = s;leads = s -n ext;p-n ext =head - n ext; head - n ext = p;將原鏈表看成由兩部分組成：已經(jīng)

7、完成逆置的部分和未完成逆置的部分。設(shè)置兩個指針P和S, P指向已完成逆置部分鏈表的第一個結(jié)點，s指向未逆置部分的第一個結(jié)點。初始時令指針P指向第一個元素結(jié)點，S指向P所指結(jié)點的后繼。將第一個元素結(jié) 點的指針域置為空。將未逆置部分的結(jié)點逐個插入到頭結(jié)點之后。算法：void reverse(LinkList head) /帶頭結(jié)點的單鏈表逆置P = head-next; if (!p) return;s = p-next; p-next = NULL;while (s) p = s; s = s - next; p - next = head - next; head-next = p;第三章棧和

8、隊列棧是后進(jìn)先出的線性表，隊列是先進(jìn)先出的線性表；在應(yīng)用中，棧和隊列都是容器，因此需要判斷是否“棧空”或“隊空” 采用順序存儲結(jié)構(gòu)時，棧和隊列都可能存在“溢出”問題，分別稱為 滿”；采用順序結(jié)構(gòu)的隊列常見形式是循環(huán)隊列?！皸M”、“隊棧的運算演示（1）A、B、C、D四個元素依次進(jìn)入一個棧，再依次出棧，得到一個輸出序列 例題DCBA。1.3、4，為得到出棧序2.3.用S、X分別表示入棧、出棧操作，若元素入棧順序為1、2、列1、3、4、2,則相應(yīng)的 S和X操作串是（SXSSXSXX）。若Push pop分別表示入棧、出棧操作，初始棧為空且元素a、b、c依次進(jìn)棧，則經(jīng)過操作序列 Push、Push

9、pop、pop、push、pop之后，得到的出棧序列為 （b a c ）。如果進(jìn)棧的序列為1、2、3,則不能得到的出棧序列為（a、3 12 )。令隊列空間中的一個單元閑置，使得在任何時刻，保持 間隔一個空閑單元Q.rear和Q.front之間至少MAXSIZE=8(Q.rear+1)%MAXSIZE= Q.front隊列空：Q.rear=Q.front隊列長度：(Q.rear - Q.front+ MAXSIZE)% MAXSIZE例題1.在循環(huán)隊列結(jié)構(gòu)中(隊列空間容量為M), Q .rear指向隊尾元素所在位置，Q .front指向隊頭元素所在位置，則隊列的長度為(Q.rear - Q.fr

10、ont + 1 + M) % M )。2.用循環(huán)鏈表表示的隊列長度為n,若只設(shè)頭指針，則出隊和入隊的時間復(fù)雜度分別是(0(1)和(0(n);若只設(shè)尾指針，則出隊和入隊的時間復(fù)雜度分別是(0(1)和(O(1)。1.若以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和隊列中元素的個數(shù)。 完善下面的入隊列和出隊列的算法。#define MAXSIZE 100 / 最大隊列長度typ edef struct Qelemtype *base; /base為隊列所在存儲區(qū)域的首地址/隊列長度/隊尾元素位置int length;int rear;)return ERROR /隊列滿，無法插入(

11、2); /計算元素e的插入位置/在隊尾加入新的元素/隊列長度加1Q.length+; return OK; Q.length =MAXSIZE(2)(Q .rear + 1)% MAXSIZE(3) Q.baseQ .rear1.若以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和隊列中元素的個數(shù)。 請完善下面的入隊列和出隊列的算法。#define MAXSIZE 100 / 最大隊列長度typ edef struct Qelemtype *base; /base為隊列所在存儲區(qū)域的首地址int length,rear;/隊列長度和隊尾元素位置SqQueue;Status EnQ

12、ueue( SqQueue &Q, Qelemtype e)/將元素e插入隊列Qif (1)Q.rear = _=e;(3)第四章串1.2.了解串的基本運算 了解串的模式匹配算法第六章樹和二叉樹二叉樹或者是一棵空樹；或者由一個根結(jié)點和兩棵互不相交的稱為左子樹和右子樹的二叉 樹組成滿二叉樹中所有分支結(jié)點都有左孩子和右孩子，葉結(jié)點都集中在二叉樹的最后一層。滿二叉樹結(jié)點的編號：從樹根為1開始，按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。wordI Lchild I dataRchild完全二叉樹中，最多只有最下面兩層的結(jié)點的度數(shù)可以小于 都排列在該層最左邊的位置上。完全二叉樹結(jié)點的編號：從樹根為 大

13、、同一層從左到右的次序進(jìn)行。例題1. 一棵滿二叉樹中共有 n個結(jié)點，其中有m個葉子結(jié)點,2，最下面一層的葉結(jié)點1開始,按照層數(shù)從小到則n和m的關(guān)系為（n=2m-1 ）。2.在完全二叉樹中，若一個結(jié)點沒有左孩子子結(jié)點，則它一定沒有A.父結(jié)點C.左兄弟結(jié)點B.右孩子結(jié)點D.右兄弟結(jié)點性質(zhì) 性質(zhì) 性質(zhì) 性質(zhì)(B )。72i-1個結(jié)點個結(jié)點（h 1）非空二叉樹上第 高度為h的二叉樹至多有2 -1非空二叉樹上葉結(jié)點數(shù)（度為0）等于雙分支結(jié)點數(shù)（度為2）加1。對完全二叉樹中編號為i的結(jié)點（1 0）結(jié)點的完全二叉樹的高度為Iog2 （n+q）!或Llog2n_+1o1234i層上至多有hi ol二叉樹的順序

14、存儲指的是用元素在數(shù)組中的下標(biāo)表示一個結(jié)點與其孩子和父結(jié)點的 關(guān)系.-完全二叉樹的順序存儲A B ClDlElFl TH1 2 3 4 5 6 7 8 9 10 11 12-非完全二叉樹的顚序存儲lAlBld IrTF G1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16b非完全二叉楓不適合進(jìn)行穎序存儲般用二叉鏈表存儲二叉樹（每個結(jié)點有兩個指針域）word3.rootI , VIrTnmcA樹的遍歷是訪問樹中每個結(jié)點僅一次的過程。 條線上，或者將一棵樹進(jìn)行線性化的處理。 先序遍歷 層序遍歷 先序遍歷 中序遍歷 后序遍歷I A I F 丨 / I A I G I A可以

15、認(rèn)為遍歷是把所有的結(jié)點放在一DLRDLRLDRLRD中序遍歷LDR后序遍歷LRD訪問根結(jié)點、先序遍歷左子樹、先序遍歷右子樹 中序遍歷左子樹、訪問根結(jié)點、中序遍歷右子樹 后序遍歷左子樹、后序遍歷右子樹、訪問根結(jié)點訪問根結(jié)點、先序遍歷左子樹、先序遍歷右子樹。下圖的先序遍歷序列先序遍歷：為 A B D E G C F中序遍歷：中序遍歷左子樹、訪問根結(jié)點、中序遍歷右子樹。下圖的中序遍歷序列為 D B G E A C F后序遍歷：后序遍歷左子樹、后序遍歷右子樹、訪問根結(jié)點。下圖的后序遍歷序列為 D G E B F C A層序遍歷：先根后子樹、先左子樹后右子樹。 下圖的層序遍歷序列為 A B C D E

16、F Groot例題1.2.A.B.C.D.在有n個結(jié)點的二叉樹的二叉鏈表中必定存在（n+1）個空鏈域。前序遍歷序列與中序遍歷序列相同的二叉樹為（D）。根結(jié)點無左子樹的二叉樹根結(jié)點無右子樹的二叉樹只有根結(jié)點的二叉樹或非葉子結(jié)點只有左子樹的二叉樹只有根結(jié)點的二叉樹或非葉子結(jié)點只有右子樹的二叉樹已知一棵二叉樹的先序遍歷序列為ABDGCEF中序遍歷序列為 DGBAECF畫出此二word叉樹。樹（森林）采用孩子兄弟鏈存儲結(jié)構(gòu)。可以將一棵樹或一個森林轉(zhuǎn)換為一棵二叉樹，反之亦然。樹的孩子兄弟鏈存儲結(jié)構(gòu)是指在一個結(jié)點中既指出當(dāng)前結(jié)點的第一個孩子，也指 示出當(dāng)前結(jié)點的兄弟。下圖（a）的樹對應(yīng)的孩子兄弟鏈存儲結(jié)構(gòu)

17、如圖（b）所示。森林轉(zhuǎn)換為二叉樹的過程：左指針：父子關(guān)系右指針：兄弟關(guān)系線索二叉樹對于具有n個結(jié)點的二叉樹，采用二叉鏈存儲結(jié)構(gòu)時，每個結(jié)點有兩個指針域，總共有2n個指針域，又由于只有 n-1個結(jié)點被有效指針?biāo)赶颍╪個結(jié)點中只有樹根 結(jié)點沒有被有效指針域所指向），則共有2n-（n-1）=n+1個空鏈域。遍歷二叉樹的結(jié)果是一個結(jié)點的線性序列。可以利用這些空鏈域存放指向結(jié)點的前驅(qū)和后 繼結(jié)點的指針。這些指向結(jié)點在某種遍歷序列中的“前驅(qū)”和“后繼”的指針，稱作線索Lchild data Rchildfl|Ltag| Lchild data Rchild Mag|Lchild指向左子樹根結(jié)點Ltag=

18、Lchild指向前驅(qū)結(jié)點Rchild指向右子樹根結(jié)點R匚hild指向后繼結(jié)點 哈夫曼樹root中序序列：DBGEACFC NULL*?(go禺fNULL哈夫曼樹（或最優(yōu)二叉樹） 是一類帶權(quán)路徑長度最短的樹，這種樹的葉子結(jié)點帶有 權(quán)值。路徑和路徑長度路徑，路從樹中的一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的 徑上的分支數(shù)目稱作 路徑長度。結(jié)點的帶權(quán)路徑長度從根到該結(jié)點的路徑長度與該結(jié)點權(quán)的乘積稱為結(jié)點的帶權(quán)路徑長度樹的帶權(quán)路徑長度樹中所有葉子的帶權(quán)路徑長度之和稱為 樹的帶權(quán)路徑長度，記作nWPL =2wklkk 1樹的帶權(quán)路徑長度dC24 WPL = 7*2+5*2+2*2+4*2 =

19、36O cr設(shè)有四個葉子 夫曼樹。WPL= 4*2 + 7*3 +5*3 + 2*1 = 46a、b、c和d的二叉樹中，對應(yīng)的權(quán)值分別為7、5、2和4，構(gòu)造哈 75247練習(xí)題1.2.設(shè)n為某棵哈夫曼樹的葉子結(jié)點數(shù)目則該哈夫曼樹共有已知組成電文的字符集D及其概率分布 W為：D= a,b,c,d,eW= 0.25,0.30,0.12,0.25, 0.08用哈夫曼算法為該字符集中的字符編碼，2n-1 ）個結(jié)點。畫出哈夫曼樹。0.3b).1.0CCd1,40.2a1.2.3.4.01b:llC： 000-審：一1廠一出001二叉樹第i層上的結(jié)點數(shù)目最多為（在n個結(jié)點的線索二叉樹中，線索的數(shù)目是（ 假

20、設(shè)二叉樹中所有非葉子結(jié)點都有左、右子樹，結(jié)點總數(shù)為（2m-1）。已知二叉樹T的后序遍歷序列和中序遍歷序列分別為H C D F I G B A和D H C E F B GI A。（1）（2）（3）2“n+1則對有m個葉子結(jié)點的此類二叉樹,第七章圖試畫出二叉樹 T;畫出與二叉樹 T對應(yīng)的中序線索二叉樹; 畫出與該二叉樹對應(yīng)的樹（森林）。存儲1.鄰接矩陣頂點之間相鄰關(guān)系用矩陣表示。J 1頂點丫二與助間有邊（弧） lo頂點”i與舫間無邊（?。?10OJ000100101. 鄰接矩陣頂點之間相鄰關(guān)系用矩陣表示。Wij頂點間有邊（?。?8頂點VI與巧間無邊（弧）18462.鄰接鏈表頂點：通常按編號順序?qū)㈨?/p>

21、點數(shù)據(jù)存儲在一維數(shù)組中 關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲ocor1 cc oc?下標(biāo)4 A4 A固的存儲結(jié)構(gòu)2鄰接鏈表）表頭頂點的 鄰摟頂雖編號和辺相關(guān) 的信息指向下一個 銘接頂點的指針（冃）表結(jié)點結(jié)構(gòu)6 19 I9683671ViV2也V4Vs譏2345618-41 1 8121755 |4 -kT24f JA62A直但只有足（b）鄰接讎表從圖的某個頂點出發(fā)，訪問圖中的所有頂點，且使每個頂點僅被訪問一次。這一過 程叫做圖的遍歷。遍歷方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷-從頂點出發(fā)進(jìn)行深度優(yōu)先遍歷（DFS）（VpDFS遍歷序列二宀丸*1巾V岳7&-從頂點討出發(fā)進(jìn)行廣度優(yōu)先遍歷（BFS） 亍BFS遍

22、歷序列：勺口門也丫宀*生成樹一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點,以構(gòu)成一棵樹的n-1條邊。QI生成樹的代價等于其邊上的權(quán)值之和，我們把具有權(quán)值最小的生成樹稱為最小生成 樹。普里姆算法和克魯斯卡爾算法是兩種常用的構(gòu)造最小生成樹的方法。（S）生成樹160。拓?fù)渑判蚍椒?1）2）3）在有向圖中選一個無前趨的頂點V，輸出之；從有向圖中刪除 V及以V為尾的??；重復(fù)1）、2），直接全部輸出全部頂點或有向圖中不存在無前趨的結(jié)點時為止。最短路徑問題（迪杰斯特拉算法）1. 單源點最短路徑問題：從一個頂點到其余各頂點的最短路徑2. 每一對頂點間的最短路徑問題（弗洛伊德算法）問題：給定一個帶權(quán)

23、有向圖G與源點V,求從v到G中其他頂點的最短路徑，并限定各邊上的權(quán)值大于或等于 0。迪杰斯特拉算法以路徑長度遞增的方式解單源點最短路徑問題。word始點終點最短路e路徑長度V0VI無?1_J1|gv2(0, V2)10 key=key) return bt;else if (key key)return BSTSearch (bt-lchild, key);elsereturn BSTSearch (bt-rchild, key);BSTSearch/btword二叉排序樹的查找性能分析若查找成功，則走了一條從根結(jié)點到某結(jié)點的路徑，若查找失敗，則走到一棵空的 子樹時為止。因此，最壞情況下，其平

24、均查找長度不會超過樹的高度。1253dASL = V PSd = 1AS 山功=(1+2*2+3*3+4*2+5*2+6*1)/111（24）100= 38/11大于WQ的數(shù)55大于12且小于24的數(shù)78人5蛭敗=（2十3宰4+4半2+5串3十6宰2）/121_ 大于90且小 干:L00的教二叉排序樹的構(gòu)造StwS子廳夕畔52卅3）折旳一義琲呼爾下所示1224493-關(guān)鍵字序列為(12,2437.43,53,93)構(gòu)造的二叉排序樹如-具有n個結(jié)點的二叉樹的高度取決于其形態(tài)，二叉排序楓 的形態(tài)取決于關(guān)鍵字序列的初始排序45245312Ca)12(c)(b)平衡二叉樹曠平衡二叉樹或者是一棵空樹，或

25、者是具有下列性質(zhì)的二叉樹: 它的左子樹和右子樹都是平衡二叉樹，且左，右子樹的深度 之差的絕對值不超過1 =平禽因子定義二叉楓中結(jié)點的平衡因子bf等于結(jié)點左孑捌的高度減 去右子駆高g平衡二叉樹中結(jié)點的平衡因孑為S 1或-1。四種平衡處理在平衡二叉排序樹上插入結(jié)點時，其祖先結(jié)點的平衡因子可能發(fā)生變化，離插入結(jié) 點最近且平衡因子變?yōu)?2或-2的祖先結(jié)點作為根的子樹稱為最小不平衡子樹。一般情況下，假設(shè)由于在二叉排序樹上插入結(jié)點而失去平衡的最小子樹根結(jié)點的指 針為a,則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為以下四種情況：RR型左旋平衡處理LL型右旋平衡處理LR型先左后右旋轉(zhuǎn)平衡處理RL型先右后左旋轉(zhuǎn)平衡處理哈

26、希表查找一個散列結(jié)構(gòu)是一塊地址連續(xù)的存儲空間，它與一個稱為散列(哈希)函數(shù)的函數(shù) 相關(guān)聯(lián)，該函數(shù)是數(shù)據(jù)記錄的關(guān)鍵字到地址空間的映射。Hash：關(guān)鍵字7 哈希地址這種存儲空間的使用方式，使得(1) 存儲記錄時，通過散列函數(shù)計算出記錄的存儲位置并按此存儲位置存儲記錄記錄位置=Hash(記錄的關(guān)鍵字)(2) 訪問記錄時，同樣利用散列函數(shù)計算存儲位置，然后根據(jù)所計算出的存儲位置訪問 記錄散列技術(shù)中的主要問題表面上看，設(shè)置了散列函數(shù)后，只需作簡單的函數(shù)計算就可以實現(xiàn)元素的定位及查找 操作，但事實上沒有這么簡單，概括起來，主要有以下兩個問題：(1)沖突及解決一般情況下，設(shè)計出的散列函數(shù)很難是單射的，即不同

27、的關(guān)鍵字會對應(yīng)到同一個存儲位 置，這樣就造成了沖突(碰撞)。此時，發(fā)生沖突的關(guān)鍵字互為同義詞。散列函數(shù)的設(shè)計設(shè)計一個簡單、均勻、存儲空間利用率高、沖突少的散列函數(shù)是關(guān)鍵。構(gòu)造哈希函數(shù)的常用方法1直接定址法2. 數(shù)字分析法3. 平方取中法4折疊法該方法的散列函數(shù)形式為:5除留余數(shù)法Hash(key) = key % p其中，p為不大于散列表表長m的整數(shù)6.隨機(jī)法 常用的沖突解決方法1. 開放地址法開放定址法利用下列公式求“下一個”空地址Hi = (H(key)+d) MOD m i=1,2,K(K=m其中H(key)為散列函數(shù)，m為散列表長度，di為增量序列線性探測再散列 二次探測再散列 偽隨機(jī)

28、探測再散列根據(jù)di的取法，解決沖突時常使用下面一些方法：(1)m。假設(shè)哈希表的地址為 0m-1，則哈希表的長度為m-1若一個關(guān)鍵字在地址 d處發(fā)生沖突，則依次探查d+1, d+2，當(dāng)達(dá)到表尾 時，又從0, 1, 2,開始探查，直到找到一個空閑位置來存儲沖突的關(guān)鍵字， 將這一種方法稱為線性探測再散列。Hi = (H(key)+di) MOD mi = 1,2,k -k)其中，H(key)為關(guān)鍵字key的哈希函數(shù)值，di=1,2,3, 例如：給定關(guān)鍵字序列如下，散列函數(shù)為H(k)=k%1319, 14, 23, 1, 68, 20, 84, 27, 55, 11, 試用線性探測再散列法建立散列表。m-1m10, 79011 121411923 19% 13 = 614% 13 = 1 23% 13 = 10 1% 13= 12. 鏈地址法2.鏈地址法-把相互發(fā)生沖突的同義01-H14I* 11 -H271 -7911詞用_個單璉表鏈接起來。23T閔11 -T羽人1ASL 成功=(1 *6+2*4+3+4)/1245=21/126T綱1 -7-1201rASL 失敗=(4+2*3+1+1)/138= 12/13g10H23-H1011T11A12對于查找算法來說，通常以（平均查找長度）作為衡量查找算法好壞