1、查找表查找表（Search Table）是由一些具有相同可辨認(rèn)特性的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。關(guān)鍵字關(guān)鍵字（key）是數(shù)據(jù)元素中某個數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素。主關(guān)鍵字唯一地標(biāo)識一個元素， 次關(guān)鍵字識別若干元素 查找查找（searching）根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。 定義：定義：查找過程中先后和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值稱作查找算法的平均查找長度平均查找長度(Average Search Length)。 查找表通常可分兩類： 1.靜態(tài)查找表靜態(tài)查找表 2.動態(tài)查找表動態(tài)查找表如何評價查找算法的時間效率？對查找表經(jīng)常進(jìn)行的

2、操作有：（1）查詢某個特定的數(shù)據(jù)元素是否在表中；（2）檢索某個特定的數(shù)據(jù)元素的各種屬性；（3）在查找表中插入一個數(shù)據(jù)元素；（4）從查找表中刪除某個數(shù)據(jù)元素。9.1 靜態(tài)查找表9.1.1 順序表的查找實(shí)現(xiàn)靜態(tài)查找表的最簡單的方法是以“順序存儲結(jié)構(gòu)的線性表-順序表”表示之 。查找過程為：從第一個或最后一個數(shù)據(jù)元素起，逐個進(jìn)行“比較”直至其中某個數(shù)據(jù)元素的關(guān)鍵字等于給定值為止。 缺點(diǎn)：其平均查找長度較大，特別是當(dāng)表中記錄數(shù) n 很大時，查找效率較低。優(yōu)點(diǎn)：算法簡單且適應(yīng)面廣，無論表中記錄是否按關(guān)鍵字有序排列均可應(yīng)用，而且，上述討論對鏈?zhǔn)酱鎯Φ木€性表也同樣適用。 9.1.2 有序表的查找 折半查找(B

3、inary Search)又稱二分查找折半查找的過程為：給定值首先和處于待查區(qū)間“中間位置”的關(guān)鍵字進(jìn)行比較，若相等，則查找成功，否則將查找區(qū)間縮小到“前半個區(qū)間” 或 “后半個區(qū)間” 之后繼續(xù)進(jìn)行查找。例如，在有序表(05,13,19,21,37,56,64,75,80,88,92)中查找關(guān)鍵字為21和85的數(shù)據(jù)元素。算法算法 int Search_Bin ( SSTable ST, KeyType kval ) / 在有序表在有序表ST中折半查找其關(guān)鍵字等于中折半查找其關(guān)鍵字等于kval的數(shù)據(jù)元素，的數(shù)據(jù)元素，/ 若找到，則函數(shù)值為該元素在表中的位置，否則為若找到，則函數(shù)值為該元素在表中的

4、位置，否則為0。low = 1; high = ST.length; / 置區(qū)間初值while (low = high) mid = (low + high) / 2;if ( kval = ST.elemmid.key )return mid; / 找到待查元素else if ( kval ST.elemmid.key )high = mid - 1; / 繼續(xù)在前半?yún)^(qū)間內(nèi)進(jìn)行查找else low = mid + 1;/ 繼續(xù)在后半?yún)^(qū)間內(nèi)進(jìn)行查找 / whilereturn 0; / 有序表中不存在待查元素 / Search_Bin9.1.3 索引順序表的查找 線性表中的記錄按關(guān)鍵字“分段有

5、序” 稱它為分塊有序表)，同時，另建一個索引，由分塊有序表和相應(yīng)的索引構(gòu)成一個索引順序表， 索引表最大關(guān)鍵字起始地址9.2動態(tài)查找表9.2.1 動態(tài)查找表的類型定義 動態(tài)查找表的特點(diǎn)：在查找過程中尚需進(jìn)行插入或刪除的操作。因此，表示動態(tài)查找表的結(jié)構(gòu)應(yīng)不僅便于查找，還應(yīng)便于插入和刪除。抽象數(shù)據(jù)類型動態(tài)查找表的定義參見教材P226-2279.2.2 二叉查找樹 一、二叉查找樹的定義一、二叉查找樹的定義 二叉查找樹或者是一棵空樹；或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；（3）它的左、右

6、子樹也都分別是二叉查找樹。例如，下圖所示是一棵二叉查找樹 二叉鏈表作為二叉查找樹的存儲結(jié)構(gòu)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) ElemType data;/ 數(shù)據(jù)元素struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BSTree; 例如，下圖所示是不是一棵二叉查找樹？ 二、二叉查找樹的二、二叉查找樹的查找算法查找算法 若二叉查找樹為空，則查找不成功；否則1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。 三、

7、二叉查找樹的插入算法 二叉查找樹結(jié)構(gòu)本身正是從空樹開始逐個插入生成的。 插入的原則：若二叉查找樹為空樹空樹，則插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)新的根結(jié)點(diǎn)；否則，插入的結(jié)點(diǎn)必為一個新的葉子結(jié)點(diǎn)新的葉子結(jié)點(diǎn)，其插入位置插入位置由查找過程確定。 例如，若給定值序列為 50,30,40,80,20,36,90,40,38 四、二叉查找樹的四、二叉查找樹的刪除算法刪除算法 分三種情況討論：(1) 被刪結(jié)點(diǎn)為“葉子”，僅需修改其雙親結(jié)點(diǎn)的相應(yīng)指針；(2) 被刪結(jié)點(diǎn)只有左子樹或右子樹，則只需保持該結(jié)點(diǎn)的子樹和其雙親之間原有的關(guān)系 (3) 被刪結(jié)點(diǎn)的左右子樹均不空。 四、二叉查找樹的四、二叉查找樹的刪除算法刪除算法 F

8、PPLPRfp（a）（b）fFPCPRCLQQLSLScpqs四、二叉查找樹的四、二叉查找樹的刪除算法刪除算法 FCCLfc（c）SLPRSs方法方法1*p的左子樹為的左子樹為*f的左子樹的左子樹*p的右子樹為的右子樹為*s的右子樹的右子樹（b）fFPCPRCLQQLSLScpqs四、二叉查找樹的四、二叉查找樹的刪除算法刪除算法 （d）fFSCPRCLQQLSLcpq方法方法2*p的直接前的直接前驅(qū)或直接后驅(qū)或直接后繼代替繼代替*p，然后再從二然后再從二叉排序樹中叉排序樹中刪除它的直刪除它的直接前驅(qū)或直接前驅(qū)或直接后繼。接后繼。（b）fFPCPRCLQQLSLScpqs參見教材參見教材p230

9、算法算法9.7算法算法9.89.2.3 平衡二叉(查找)樹 平衡二叉樹：它或是空樹，或具有下列特性：其左子樹和右子樹都是平衡二叉樹，且左右子樹深度之差的絕對值不大于1。 平衡二叉樹非平衡二叉樹樹中結(jié)點(diǎn)內(nèi)的數(shù)值稱作結(jié)點(diǎn)的平衡因子，定義為左子樹的深度減去右子樹的深度。 平衡處理的原則是保證二叉查找樹始終處于平衡狀態(tài)。從空樹起（空樹是平衡樹），每插入一個關(guān)鍵字都需要檢查二叉查找樹是否失去平衡，如因插入新的結(jié)點(diǎn)引起不平衡，則需對它進(jìn)行平衡旋轉(zhuǎn)處理。 9.3 哈希表 9.3.1 何謂哈希表 記錄在表中的位置為關(guān)鍵字的某個函數(shù)，通常稱這種函數(shù)為“哈希函數(shù)哈希函數(shù)”。 若關(guān)鍵字不同而函數(shù)值相同，則稱這兩個關(guān)

10、鍵字（對于該哈希函數(shù)而言）為同義詞，并稱這種現(xiàn)象為沖突。 根據(jù)設(shè)定的哈希函數(shù)哈希函數(shù) H(key)和所選中的處理沖突處理沖突的方法，將一組關(guān)鍵字映象到一個映象到一個有限的、地址連續(xù)的地址集地址集(區(qū)間區(qū)間)上上，并以關(guān)鍵字在地址集中的象象作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表哈希表，這一映象的過程亦被稱為散列散列。 9.3.2 構(gòu)造哈希函數(shù)的方法 若對于關(guān)鍵字集合中的任意一個關(guān)鍵字，經(jīng)哈希函數(shù)映象到地址集合中任何一個地址的概率相等，則稱此類哈希函數(shù)為均勻的哈希函數(shù) 構(gòu)造均勻的哈希函數(shù)的方法有如下幾種：一、直接定址法 Hash(key)=key 或 Hash(key)=a key+b

11、（a 和 b 均為常數(shù)） 直接定址所得地址集的大小和關(guān)鍵字集的大小相同，關(guān)鍵字和地址一一對應(yīng)，決不會產(chǎn)生沖突。但實(shí)際應(yīng)用中能采用直接定址的情況極少。二、數(shù)字分析法 如果可能出現(xiàn)的關(guān)鍵字的數(shù)位相同，且取值事先知道，則可對關(guān)鍵字進(jìn)行分析，取其中“分布均勻”的若干位或它們的組合作為哈希表的地址。 02146532021722420228742702201367022288170223298202354152023685350231932702395715 例如 已知80個記錄的關(guān)鍵字為8位十進(jìn)制數(shù)（右圖列出其中部分），假設(shè)哈希表的表長為100，即地址為0099。三、平方取中法 如果關(guān)鍵字的所有各位分

12、布都不均勻，則可取關(guān)鍵字的平方值的中間若干位作為哈希表的地址。 例如：右表八進(jìn)制數(shù)的關(guān)鍵字及其哈希地址關(guān)鍵字(關(guān)鍵字)2哈希地址010000100000101100121000021012001440000440116013704003702061431054131020624314704314216147347417342162474130474121634745651745四、折疊法四、折疊法 若關(guān)鍵字的位數(shù)很多，且每一位上數(shù)字分布大致均勻，則可采用移位疊加移位疊加或間界疊加間界疊加，即將關(guān)鍵字分成若干部分，然后以它們的疊加和(舍去進(jìn)位)作為哈希地址。 例如，key = 110108780

13、428895 ，(哈希表的表長為1000) 895 824 780 801+）110 3410 895 428 780 108+）110 2321間界疊加移位疊加五、除留余數(shù)法五、除留余數(shù)法 以關(guān)鍵字被某個數(shù)p除后所得余數(shù)作為哈希地址。 即 Hash(key) = key MOD p 其中，MOD表示取模運(yùn)算，p 為不大于表長的素?cái)?shù)或不包含小于20的質(zhì)因素的合數(shù)。 六、隨機(jī)數(shù)法六、隨機(jī)數(shù)法當(dāng)關(guān)鍵字不等長時，可取關(guān)鍵字的某個偽隨機(jī)函數(shù)值作為哈希地址。Hash(key) = random(key) 對于非數(shù)值型關(guān)鍵字，則需先將它們轉(zhuǎn)化為數(shù)字。實(shí)際造表時，采用何種采用何種構(gòu)造哈希函數(shù)的方法方法取決于

14、建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小使產(chǎn)生沖突的可能性降到盡可能地小。 9.3.3 處理沖突的方法處理沖突的方法有兩類處理沖突的方法:一、開放定址法一、開放定址法 二、鏈地址法二、鏈地址法 一、開放定址 處理沖突的辦法是，設(shè)法為發(fā)生沖突的關(guān)鍵字找到哈希表中另一個尚未被記錄占用的位置。哈希表的表長為m（即哈希表中可用地址為：0m-1），若關(guān)鍵字key，Hash(key)的位置已被占用，則下一個地址H1=(Hash(key)+d1)MODm，若也已被占用，則再H2=(Hash(key)+d2)MODm，依次類推直至找到一個地址Hs=(Hash

15、(key)+ds)MODm未被占用為止。即Hi是為解決沖突生成的一個地址序列，其值取決于設(shè)定增量序列di。對于di通常可有三種設(shè)定方法： “線性探測再散列”，di=1,2,3,m-1，2.“平方探測再散列”， di = 12,-12, 22 , -22 , k2(km/2)，3.偽隨機(jī)探測再散列“或”雙散列函數(shù)探測再散列 為偽隨機(jī)數(shù)列或者di=i H2(key)，（H2 (key)為關(guān)鍵字的另一個哈希函數(shù)） 按線性探測再散列處理沖突構(gòu)造的哈希表為：按平方探測再散列處理沖突構(gòu)造的哈希表為：按雙散列函數(shù)探測處理沖突構(gòu)造的哈希表為：二、鏈地址法 將所有關(guān)鍵字為同義詞的記錄鏈接在一個線性鏈表中 例如，

16、假設(shè)關(guān)鍵字序列為 19,56,23,14,68,82,70,36,91 ，哈希表的表長為 7，哈希函數(shù)為 Hash(key)=key % 7，則構(gòu)建的以鏈地址處理沖突的哈希表如flash9-4-2所示。 9.4.4 開放定址的哈希表的查找和插入 在利用開放定址處理沖突的哈希表中進(jìn)行查找時，首先應(yīng)計(jì)算給定值的哈希函數(shù)值，若表中該位置上沒有記錄， 則表明關(guān)鍵字等于給定值的記錄不存在；若該位置上的記錄的關(guān)鍵字和給定值不等， 則依據(jù)建表時設(shè)定的增量值尋找“下一個”地址，直至查找成功(即某個位置上的記錄的關(guān)鍵字等于給定值)或查找不成功（哈希表中不存在關(guān)鍵字等于給定值的記錄），且在查找不成功的情況下，該地

17、址為新的記錄的插入位置。 本章小結(jié) 在本章中介紹了查找表的三類存儲表示方法：順序表、樹表和哈希表。這里的順序表指的是順序存儲結(jié)構(gòu)，包括有序表和索引順序表，因此主要用于表示靜態(tài)查找表，樹表包括靜態(tài)查找樹、二叉查找樹，樹表和哈希表主要用于表示動態(tài)查找表。 查找樹的特點(diǎn)是，每經(jīng)過一次比較便可將繼續(xù)查找的范圍縮小到某一棵子樹上，但查找樹并不僅限于二叉樹，以后還將介紹其它形式的查找樹。 所有順序結(jié)構(gòu)的表和查找樹的平均查找長度都是隨之查找表中記錄數(shù)的增加而增大，而哈希表的平均查找長度是裝填因子的函數(shù)，因此有可能設(shè)計(jì)出使平均查找長度不超過某個期望值的哈希表。 課后習(xí)題 1.試分別畫出在線性表(a,b,c,d,e,e,f)中進(jìn)行折半查找，以查關(guān)鍵字等于 e、f 和 g 的過程。 2.選取哈希函數(shù) H(k)=(3k) MO