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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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