chapter08_查找

1、查找查找8.1 查找的基本概念查找的基本概念8.2 基于線性表的查找法基于線性表的查找法8.3 基于樹的查找法基于樹的查找法8.4 計算式查找法計算式查找法哈希法哈希法8.5 總結與提高總結與提高習題習題實習題實習題列表列表：由同一類型的數(shù)據(jù)元素（或記錄）構成的集合，可利用任意：由同一類型的數(shù)據(jù)元素（或記錄）構成的集合，可利用任意數(shù)據(jù)結構實現(xiàn)。數(shù)據(jù)結構實現(xiàn)。關鍵字關鍵字：數(shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標識列表中的一個：數(shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標識列表中的一個或一組數(shù)據(jù)元素?；蛞唤M數(shù)據(jù)元素。如果一個關鍵字可以唯一標識列表中的某一個數(shù)據(jù)元素，則稱其為如果一個關鍵字可以唯一標識列表中的

2、某一個數(shù)據(jù)元素，則稱其為主關鍵字，否則為次關鍵字。主關鍵字，否則為次關鍵字。查找查找：根據(jù)給定的關鍵字值，在特定的列表中確定一個其關鍵字與：根據(jù)給定的關鍵字值，在特定的列表中確定一個其關鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。(1) 靜態(tài)查找靜態(tài)查找：在查找過程中只對數(shù)據(jù)元素進行查找。：在查找過程中只對數(shù)據(jù)元素進行查找。(2) 動態(tài)查找動態(tài)查找：在查找的同時，插入找不到的元素，或從查找表中：在查找的同時，插入找不到的元素，或從查找表中刪除已查到的某個元素，即允許表中元素變化。刪除已查到的某個元素，即允許表中元素變化。查找

3、的基本概念查找的基本概念查找的基本概念查找的基本概念平均查找長度平均查找長度：未確定數(shù)據(jù)元素在列表中的位置，需和給定值進行：未確定數(shù)據(jù)元素在列表中的位置，需和給定值進行比較的關鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查比較的關鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。找長度。對于長度為對于長度為n的列表，查找成功時的平均查找長度為：的列表，查找成功時的平均查找長度為：niiinnCPCPCPCPASL12211.其中：其中：Pi為查找列表中第為查找列表中第i個數(shù)據(jù)元素的概率，個數(shù)據(jù)元素的概率，Ci為找到列表中第為找到列表中第i個個數(shù)據(jù)元素時，已經(jīng)進行過的關鍵字比較次數(shù)。

4、數(shù)據(jù)元素時，已經(jīng)進行過的關鍵字比較次數(shù)。所以，等概率情況下：所以，等概率情況下：niinCnCnCnCnASL12111.11基于線性表的查找法基于線性表的查找法特點特點：用所給關鍵字與線性表中各元素的關鍵字逐個比：用所給關鍵字與線性表中各元素的關鍵字逐個比較，直到成功或失敗。較，直到成功或失敗。順序查找法順序查找法存儲結構存儲結構：通常為順序結構，也可為鏈式結構。：通常為順序結構，也可為鏈式結構。順序結構數(shù)據(jù)類型的定義順序結構數(shù)據(jù)類型的定義#define SIZE 20typedef struct element KeyType key; OtherType other_data;Recor

5、dType;typedef struct list RecordType rSIZE+1; int len;RecordList;順序查找法順序查找法算法思想算法思想(1) 在表的一端設置一個稱為在表的一端設置一個稱為“監(jiān)視哨監(jiān)視哨”的附加單元，存放要的附加單元，存放要查找元素的關鍵字。查找元素的關鍵字。(2) 從表的另一端開始查找，如果在從表的另一端開始查找，如果在“監(jiān)視哨監(jiān)視哨”找到要查找元找到要查找元素的關鍵字，返回相應下標，否則返回失敗信息。素的關鍵字，返回相應下標，否則返回失敗信息。學號學號姓名姓名專業(yè)專業(yè)班級班級入學成績?nèi)雽W成績家庭住址家庭住址keyother_data順序查找法順

6、序查找法64801356379219058821012345678910keyint SeqSearch(RocordType list, KeyType key) list.r0=key; i=list.len; while(list.ri!=key) i-; return i;iii順序查找法順序查找法算法分析算法分析(1) 查找第查找第n個數(shù)據(jù)元素，需要比較個數(shù)據(jù)元素，需要比較1次；次；(2) 查找第查找第n-1個數(shù)據(jù)元素，需要比較個數(shù)據(jù)元素，需要比較2次；次；(3) 依此類推，查找第依此類推，查找第i個數(shù)據(jù)元素，需要比較個數(shù)據(jù)元素，需要比較n-i+1次，即次，即Ci=n-i+1。nin

7、iiiniininnCnCPASL111) 1(21) 1(11基于線性表的查找法基于線性表的查找法折半查找法又稱為二分查找法，這種方法對待查找的列折半查找法又稱為二分查找法，這種方法對待查找的列表有兩個要求表有兩個要求折半查找法折半查找法存儲結構存儲結構：必須為順序結構且有序：必須為順序結構且有序順序結構數(shù)據(jù)類型的定義順序結構數(shù)據(jù)類型的定義#define SIZE 20Typedef struct element KeyType key; OtherType other_data;RecordType;typedef struct list RecordType rSIZE+1; int l

8、en;RecordList;二分查找法二分查找法0len-1912132737567982889197lowhigh(1) 設置兩個位置指示器設置兩個位置指示器low和和high分別指向當前查找范圍的兩分別指向當前查找范圍的兩個端點個端點(2) 計算計算mid的位置，的位置，mid=(low+high)/2(3) 比較查找關鍵字和比較查找關鍵字和mid位置上的元素，位置上的元素，key=amid? key=amid，查找成功，查找成功 key!=amid，縮小查找區(qū)間，得到新的，縮小查找區(qū)間，得到新的low、high和和midmid二分查找法二分查找法0len-1912132737567982

9、889197lowhigh(1) keyamid，新的查找區(qū)間為原有區(qū)間的右半?yún)^(qū)域，新的查找區(qū)間為原有區(qū)間的右半?yún)^(qū)域，high不不變，變，low=mid+1mid基于樹的查找法基于樹的查找法二叉排序樹又稱為二叉查找樹，它是一種特殊的二叉樹。二叉排序樹又稱為二叉查找樹，它是一種特殊的二叉樹。二叉排序樹的定義：二叉排序樹或者是一棵空樹，或者是具有二叉排序樹的定義：二叉排序樹或者是一棵空樹，或者是具有如下性質的二叉樹。如下性質的二叉樹。(1) 若它的左子樹非空，則左子樹上所有結點的值均小于它的若它的左子樹非空，則左子樹上所有結點的值均小于它的根結點的值；根結點的值；(2) 若它的右子樹非空，則右子樹

10、上所有結點的值均大于它的若它的右子樹非空，則右子樹上所有結點的值均大于它的根結點的值；根結點的值；(3) 它的左右子樹也分別為二叉排序樹。它的左右子樹也分別為二叉排序樹。二叉排序樹的類型定義二叉排序樹的類型定義641380556759237192188typedef struct node KeyType key; struct node *Lchild,*Rchild;BSTNode,*BSTree;二叉排序樹的查找二叉排序樹的查找因為二叉排序樹可以看做是一個有序表，所以在二叉排序樹上進行查找，因為二叉排序樹可以看做是一個有序表，所以在二叉排序樹上進行查找，和折半查找類似，也是一個逐步縮小查

11、找范圍的過程。和折半查找類似，也是一個逐步縮小查找范圍的過程。首先將待查關鍵字首先將待查關鍵字key與根結點關鍵字與根結點關鍵字t進行比較；進行比較；(1)key=t，查找成功，返回根結點地址：，查找成功，返回根結點地址：(2) keyt，則進一步查找右子樹。，則進一步查找右子樹。算法思想算法思想例：已知二叉排序樹如下，查找是否存例：已知二叉排序樹如下，查找是否存在關鍵字為在關鍵字為28的結點。的結點。452453122890key!=t且且keyLchildkey!=t且且keytp=p-Rchildkey=t，查找成功，查找成功BSTree SearchBST(BSTree root, K

12、eyType key) if(root=NULL) return NULL; else if(root-key=key) return root; else if(root-keykey) return SearchBST(root-Lchild,key); else if(root-keyRchild,key);二叉排序樹的插入二叉排序樹的插入已知一個關鍵字為已知一個關鍵字為key的結點的結點S，若將其插入到二叉排序樹中，若將其插入到二叉排序樹中，只要保證插入后仍符合二叉排序樹的定義即可。只要保證插入后仍符合二叉排序樹的定義即可。(1) 若二叉排序樹是空樹，則若二叉排序樹是空樹，則S稱為二叉

13、排序樹的根；稱為二叉排序樹的根；(2) 若二叉排序樹非空，則將若二叉排序樹非空，則將S.key與二叉排序樹根結點的關鍵字與二叉排序樹根結點的關鍵字進行比較：進行比較： a 如果如果key的值等于根結點的值，則停止插入；的值等于根結點的值，則停止插入； b 如果如果key的值小于根結點的值，則將的值小于根結點的值，則將S插入到左子樹；插入到左子樹； c 如果如果key的值小于根結點的值，則將的值小于根結點的值，則將S插入到左子樹。插入到左子樹。算法思想算法思想例：已知一組序列為例：已知一組序列為45,24,53,12,28,90，請，請將其依次插入到二叉排序樹中。將其依次插入到二叉排序樹中?？諛?/p>

14、空樹45插入插入4545插入插入2424插入插入53452453452453插入插入121245245312插入插入2828插入插入90452453122890二叉排序樹的刪除二叉排序樹的刪除從二叉排序樹中刪除一個結點，只能刪除該結點本身，且不能破壞二叉排從二叉排序樹中刪除一個結點，只能刪除該結點本身，且不能破壞二叉排序樹的性質。序樹的性質。算法思想算法思想641380556759237192188(1) 刪除操作首先查找要刪除的結點，看它是否在二叉排序樹中刪除操作首先查找要刪除的結點，看它是否在二叉排序樹中(2) 假設要刪除的結點為假設要刪除的結點為p，結點，結點p的雙親為的雙親為f。下面分

15、三種情況討。下面分三種情況討論：論：刪除關鍵字為刪除關鍵字為75的結點的結點刪除關鍵字為刪除關鍵字為56的結點的結點刪除關鍵字為刪除關鍵字為19的結點的結點刪除關鍵字為刪除關鍵字為13的結點的結點關鍵字為關鍵字為75的結點為葉節(jié)點的結點為葉節(jié)點直接刪除直接刪除f-Lchild=NULL;二叉排序樹的刪除二叉排序樹的刪除641380556759237192188刪除關鍵字為刪除關鍵字為75的結點的結點641380556759237192188刪除關鍵字為刪除關鍵字為56的結點的結點關鍵字為關鍵字為56的結點只有左孩子的結點只有左孩子用其左孩子代替該結點用其左孩子代替該結點f-Rchild=p-L

16、child;371921關鍵字為關鍵字為19的結點只有右孩子的結點只有右孩子用其右孩子代替該結點用其右孩子代替該結點f-Lchild=p-Rchild;二叉排序樹的刪除二叉排序樹的刪除641380556759237192188刪除關鍵字為刪除關鍵字為19的結點的結點21641380556759237192188刪除關鍵字為刪除關鍵字為13的結點的結點關鍵字為關鍵字為13的結點有左、右兩個孩子的結點有左、右兩個孩子這種情況是最復雜的，該如何處理呢？這種情況是最復雜的，該如何處理呢？二叉排序樹的刪除二叉排序樹的刪除641380556759237192188刪除關鍵字為刪除關鍵字為13的結點的結點方

17、案一：方案一：(1) 找到找到p結點在中序序列中的直接前結點在中序序列中的直接前驅結點驅結點s，(2) p的左子樹改為的左子樹改為f左子樹，左子樹，(3) p的右子樹改為的右子樹改為s的右子樹。的右子樹。p5 13 19 21 37 56 64 75 80 88 92 fs5f-Lchild=p-Lchild;s-Rchild=p-Rchild;free(p);二叉排序樹的刪除二叉排序樹的刪除641380556759237192188刪除關鍵字為刪除關鍵字為13的結點的結點方案二：方案二：(1) 找到找到p結點在中序序列中的直接前結點在中序序列中的直接前驅結點驅結點s，(2) s結點的值替代結

18、點的值替代p結點的值，結點的值，(3) 將將s結點刪除，結點刪除，(4) 原原s結點的左子樹改為結點的左子樹改為s的雙親結點的雙親結點q的的右子樹。的的右子樹。p5 13 19 21 37 56 64 75 80 88 92 fs5p-data=s-data;q-Rchild=s-Lchild;free(s);計算式查找法計算式查找法哈希法哈希法基本思想基本思想：在元素的在元素的關鍵字關鍵字k和元素的和元素的存儲位置存儲位置p之間建立一之間建立一個個對應關系對應關系H，使得，使得p=H(k)，H為哈希函數(shù)。為哈希函數(shù)。哈希法又稱散列法、雜湊法或關鍵字地址計算法等，相應的哈希法又稱散列法、雜湊法

19、或關鍵字地址計算法等，相應的表稱為哈希表、散列表、雜湊表等。表稱為哈希表、散列表、雜湊表等。(1) 創(chuàng)建哈希表時，把關鍵字為創(chuàng)建哈希表時，把關鍵字為k的元素直接存入地址的元素直接存入地址為為H(k)的單元。的單元。具體過程具體過程(2) 當查找關鍵字為當查找關鍵字為k的元素時，再利用哈希函數(shù)計算的元素時，再利用哈希函數(shù)計算出該元素的存儲位置出該元素的存儲位置p=H(k)，從而達到按關鍵字直接，從而達到按關鍵字直接存取元素的目的。存取元素的目的。當關鍵字集合很大時，關鍵字值不同的元素可能會映射到哈當關鍵字集合很大時，關鍵字值不同的元素可能會映射到哈希表的同一個地址上，即希表的同一個地址上，即k1

20、!=k2，但，但H(k1)=H(k2)，這種現(xiàn)，這種現(xiàn)象稱為象稱為沖突沖突。哈希函數(shù)的構造方法哈希函數(shù)的構造方法(1) 數(shù)字分析法數(shù)字分析法(2) 平方取中法平方取中法(3) 分段疊加法分段疊加法(4) 除留余數(shù)法除留余數(shù)法(5) 偽隨機屬法偽隨機屬法假設哈希表長為假設哈希表長為m，p為小于等于為小于等于m的最大素數(shù)，則的最大素數(shù)，則哈希函數(shù)為：哈希函數(shù)為：h(key)=key%p例如：已知待散列元素為例如：已知待散列元素為(18,75,60,43,54,90,46)，表長表長m=10，p=7，則有：，則有： h(18)=4 h(75)=5 h(60)=4 h(43)=1 h(54)=5 h(

21、90)=6 h(46)=4此時沖突較多。為減少沖突，可取較大的此時沖突較多。為減少沖突，可取較大的m值和值和p值，如值，如m=p=13，結果如下：，結果如下： h(18)=5 h(75)=10 h(60)=8 h(43)=4 h(54)=2 h(90)=12 h(46)=7012345678910111254431846607590處理沖突的方法處理沖突的方法這種方法也稱再散列法，其這種方法也稱再散列法，其基本思想基本思想是：是：(1) 當關鍵字當關鍵字key的初始哈希地址的初始哈希地址h0=H(key)出現(xiàn)沖突時，以出現(xiàn)沖突時，以h0為基為基礎，產(chǎn)生另一個地址礎，產(chǎn)生另一個地址h1，(2)

22、如果如果h1仍然沖突，再以仍然沖突，再以h0為基礎，產(chǎn)生另一個哈希地址為基礎，產(chǎn)生另一個哈希地址h2(3) 直到找出一個不沖突的地址直到找出一個不沖突的地址hi，將相應的元素存入其中。，將相應的元素存入其中。函數(shù)表達式為：函數(shù)表達式為：hi=(H(key)+di)%m或或hi=(h0+di)%m(1) 線性探測再散列：線性探測再散列：di=1,2,3,m-1，這種，這種方法方法的特點是沖突發(fā)的特點是沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。(2) 二次探測再散列：二次探測再散列：di=12,-12,22,-22,k

23、2,-k2，這種方法的特點是，這種方法的特點是沖突發(fā)生時，在表的左右進行跳躍性探測，比較靈活。沖突發(fā)生時，在表的左右進行跳躍性探測，比較靈活。(3) 偽隨機探測再散列：偽隨機探測再散列：di=偽隨機序列偽隨機序列，具體實現(xiàn)時，應建立一個，具體實現(xiàn)時，應建立一個偽隨機數(shù)發(fā)生器，（如偽隨機數(shù)發(fā)生器，（如i=(i+p)%m），并給定一個隨機數(shù)做起點。），并給定一個隨機數(shù)做起點。開放定址法開放定址法例：已知一組關鍵字序列例：已知一組關鍵字序列(19,14,23,01,68,20,84,27,55,11,10,79)，按哈希函數(shù)，按哈希函數(shù)H(key)=key%13和線性探測處理沖突構造哈希表和線性探測

24、處理沖突構造哈希表ht0.15，請畫出構造好的哈希表。，請畫出構造好的哈希表。01234567891011121314151H(19)=6H(14)=1H(23)=10H(01)=1出現(xiàn)沖突出現(xiàn)沖突H(68)=3H(20)=719114123201168120384H(84)=6出現(xiàn)沖突出現(xiàn)沖突H(27)=1出現(xiàn)沖突出現(xiàn)沖突H(55)=3出現(xiàn)沖突出現(xiàn)沖突H(11)=11H(10)=10出現(xiàn)沖突出現(xiàn)沖突H(79)=1427355111310979處理沖突的方法處理沖突的方法再哈希法再哈希法 這種方法可以同時構造多個不同的哈希函數(shù)：這種方法可以同時構造多個不同的哈希函數(shù)：Hi=RHi(key)，當哈希，當哈希地址地址H1=RH1(key)發(fā)生沖突時，再計算發(fā)生沖突時，再計算H2=RH2(key)直到?jīng)_突不產(chǎn)生直到?jīng)_突不產(chǎn)生為止。為止。鏈地址法鏈地址法 將所有哈希地址為將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第鏈表的頭指針存在哈希表的第i個單元中。個單元中。建立公共溢出區(qū)建立公共溢出區(qū) 將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素一律填入溢出表。素一律填入溢出表。例：已知一組關鍵