數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容19.1 9.1 基本概念基本概念9.2 9.2 靜態(tài)查找表靜態(tài)查找表9.3 9.3 動態(tài)查找表動態(tài)查找表9.4 9.4 哈希表哈希表第第9 9章章 查找查找教材第教材第8 8、1111和和1212章省略，因章省略，因操作系統(tǒng)操作系統(tǒng)課程會涉及。課程會涉及。29.1 9.1 基本概念基本概念若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找表查查 找找查找成功查找成功查找不成功查找不成功靜態(tài)查找靜態(tài)查找動態(tài)查找動態(tài)查找關(guān)鍵字關(guān)鍵字主關(guān)鍵字主關(guān)鍵字次關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查詢查詢(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄記錄中某個數(shù)據(jù)項的值，可用來識別一個記錄 (預(yù)先確定的記錄的某種標(biāo)志預(yù)先確定的記錄的某種標(biāo)志)可以可以唯一唯一標(biāo)識一個記錄的關(guān)鍵字標(biāo)識一個記錄的關(guān)鍵字例如例如“學(xué)號學(xué)號”例如例如“女女”是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)識別若干記錄的關(guān)鍵字識別若干記錄的關(guān)鍵字3（2）對查找表常用的操作有）對查找表常用的操作有哪些？哪些？v查詢某個查詢某個“特定的特定的”數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；v查詢某個查詢某個“特定的特定的”數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；v在查找表中插入一元素；在查找表中插入一元素；v從查找表中刪除一元素。從查找表中刪除一元素。（3)有哪些查找方法？有哪些查找方法？查找方法取決于表中數(shù)據(jù)的排列方式查找方法取決于表中數(shù)據(jù)的排列方式;討論：討論：（1）查找的過程是怎樣的？）查找的過程是怎樣的？給定一個值給定一個值K K，在含有，在含有n n個記錄的文件中進(jìn)行搜索，尋找個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于一個關(guān)鍵字值等于K K的記錄，如找到則輸出該記錄，否則輸出的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。查找不成功的信息。例如查字典例如查字典針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同。“特定的特定的”=關(guān)關(guān)鍵字鍵字4（4）如何評估查找方法的優(yōu)劣？）如何評估查找方法的優(yōu)劣？明確：明確：查找的過程就是將給定的查找的過程就是將給定的K K值與文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字項進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)項進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為劣。稱為平均查找長度平均查找長度（ASLASL：average search lengthaverage search length）。）。其中：其中：n是文件記錄個數(shù)；是文件記錄個數(shù)；P Pi i是查找第是查找第i i個記錄的查找概率（通常取等概率個記錄的查找概率（通常取等概率,即即P Pi i=1/n=1/n）;C Ci i是找到第是找到第i i個記錄時所經(jīng)歷的比較次數(shù)。個記錄時所經(jīng)歷的比較次數(shù)。統(tǒng)計意義上的統(tǒng)計意義上的數(shù)學(xué)期望值數(shù)學(xué)期望值物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為一元素所需的比較次數(shù)之總和再取平均，即為ASLASL。顯然，顯然，ASLASL值越小，時間效率越高。值越小，時間效率越高。5針對靜態(tài)查找表的查找算法主要有：針對靜態(tài)查找表的查找算法主要有：9.2 9.2 靜態(tài)查找表靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材P216。一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹表的查找三、靜態(tài)樹表的查找四、分塊查找（索引順序查找）四、分塊查找（索引順序查找）6一、順序查找（一、順序查找（Linear search，又稱線性查找又稱線性查找）（1）順序表的機(jī)內(nèi)存儲結(jié)構(gòu)：順序表的機(jī)內(nèi)存儲結(jié)構(gòu)：typedef struct ElemType *elem;/表基址，表基址，0 0號單元留空。表容量為全部元素號單元留空。表容量為全部元素 int length;/表長，即表中數(shù)據(jù)元素個數(shù)表長，即表中數(shù)據(jù)元素個數(shù)SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。直接的辦法。v對對順序結(jié)構(gòu)順序結(jié)構(gòu)如何線性查找？如何線性查找？見下頁之例見下頁之例或教材或教材P216P216；v對對單單鏈鏈表表結(jié)結(jié)構(gòu)構(gòu)如如何何線線性性查查找找？函函數(shù)數(shù)雖雖未未給給出出，但但也也很很容容易易編寫；只要知道頭指針編寫；只要知道頭指針headhead就可以就可以“順藤摸瓜順藤摸瓜”；v對對非線性樹結(jié)構(gòu)非線性樹結(jié)構(gòu)如何順序查找如何順序查找?可借助各種遍歷操作！可借助各種遍歷操作！7（2）算法的實現(xiàn)：算法的實現(xiàn)：技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），），這樣可以加快執(zhí)行速度。這樣可以加快執(zhí)行速度。例：例：若將待查找的特定值若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號單元）號單元），則順序查找的實現(xiàn)方案為：，則順序查找的實現(xiàn)方案為：從后向前從后向前逐個比較！逐個比較！int Search_Seq(SSTable ST,KeyType key)/在順序表在順序表STST中，查找關(guān)鍵字與中，查找關(guān)鍵字與keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否則返回置信息，否則返回0 0 ST.elem0.key=key;/設(shè)立哨兵，可免去查找過程中每一步設(shè)立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當(dāng)都要檢測是否查找完畢。當(dāng)n1000n1000時，查找時間將減少一半。時，查找時間將減少一半。for(i=ST.length;ST.elem i.key!=key;-i );/不要用不要用for(i=n;i0;-i)for(i=n;i0;-i)或或 for(i=1;i=n;i+)for(i=1;i=n;i+)return i;/若到達(dá)若到達(dá)0 0號單元才結(jié)束循環(huán)，說明不成功，返回號單元才結(jié)束循環(huán)，說明不成功，返回0 0值值(i=0)(i=0)。成功時則返回找到的那個元素的位置。成功時則返回找到的那個元素的位置i i。/Search_Seq8返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨哨兵兵”，就是將關(guān)鍵字送入末地址，就是將關(guān)鍵字送入末地址ST.elemST.elem0 0.key.key使之結(jié)束并返回使之結(jié)束并返回 i=0i=0。討論討論 查找效率怎樣計算？查找效率怎樣計算？用平均查找長度用平均查找長度ASL衡量。衡量。討論討論 查不到怎么辦？查不到怎么辦？討論討論 如何計算如何計算ASL？分析：分析：查找第查找第1個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為1；查找第查找第2個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為2；查找第查找第n個元素所需的比較次數(shù)為個元素所需的比較次數(shù)為n；總計全部比較次數(shù)為：總計全部比較次數(shù)為：12n=(1+n)n/2未考慮查找不成功的未考慮查找不成功的情況：查找哨兵所需情況：查找哨兵所需的比較次數(shù)為的比較次數(shù)為n+1n+1這是查找成功的情況這是查找成功的情況若求某一個元素的平均查找次數(shù)，還應(yīng)當(dāng)除以若求某一個元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），（等概率），即：即：ASL（1n）/2 ，時間效率為，時間效率為 O(n)9二、折半查找（又稱二分查找或?qū)Ψ植檎遥┒⒄郯氩檎遥ㄓ址Q二分查找或?qū)Ψ植檎遥﹥?yōu)點(diǎn)：優(yōu)點(diǎn)：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：缺點(diǎn)：ASL 太長，時間效率太低。太長，時間效率太低。這是一種容易想到的查找方法。這是一種容易想到的查找方法。先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與正中元素相比，若與正中元素相比，若keykey小，則縮小至右半部內(nèi)查找；再取其中小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小值比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。v對對順序表結(jié)構(gòu)順序表結(jié)構(gòu)如何編程實現(xiàn)折半查找算法？如何編程實現(xiàn)折半查找算法？見下頁之例見下頁之例，或見教材（，或見教材（P219P219）v對對單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何折半查找？如何折半查找？無法實現(xiàn)！因全部元素的定位只能從頭指針無法實現(xiàn)！因全部元素的定位只能從頭指針headhead開始開始v對對非線性非線性(樹樹)結(jié)構(gòu)結(jié)構(gòu)如何折半查找？如何折半查找？可借助二叉排序樹來查找（屬動態(tài)查找表形式）?？山柚媾判驑鋪聿檎遥▽賱討B(tài)查找表形式）。如何改進(jìn)？如何改進(jìn)？討論討論 順序查找的特點(diǎn)：順序查找的特點(diǎn)：10 運(yùn)算步驟運(yùn)算步驟：(1)low=1,high=11,mid=6(1)low=1,high=11,mid=6，待查范圍是，待查范圍是 1,111,11；(2)(2)若若 ST.elemmid.key ST.elemmid.key key keykey，說明，說明keykey low,midlow,mid-1-1，則令：則令：high=midhigh=mid1 1;重算重算 mid mid；(4)(4)若若 ST.elem mid.key ST.elem mid.key=key=key，說明查找成功，元素序號，說明查找成功，元素序號=mid;=mid;結(jié)束條件：結(jié)束條件：（1 1）查找成功）查找成功 ：ST.elemmid.key=keyST.elemmid.key=key （2 2）查找不成功）查找不成功 ：highlowhighdata.key)return(T)；/查找結(jié)束查找結(jié)束 else if LT(key,Tdata.key)/在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 return(SearchBST(Tlchild,key)；else return(SearchBST(Trchild,key)；/在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找 /SearchBST20Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree&p)if(!T)p=f；return FALSE；/查找不成功查找不成功 else if EQ(key,Tdata.key)p=T；return TRUE；/查找成功查找成功 else if LT(key,Tdata.key)return SearchBST(Tlchild,key,T,p);/在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 else return SearchBST(Trchild,key,T,p);/在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找 /SearchBST21Status InsertBST(BiTree&T,ElemType e)if(!SearchBST(T,e.key,NULL,p)/查找不成功查找不成功 s=(BiTree)malloc(sizeof(BiTNode)；sdata=e；slchild=srchild=NULL；/建立新結(jié)點(diǎn)建立新結(jié)點(diǎn) if(!p)T=s；/T為空樹為空樹 else if LT(e.key,pdata.key)plchild=s；/被插結(jié)點(diǎn)被插結(jié)點(diǎn)*s為左孩子為左孩子 else prchild=s；/被插結(jié)點(diǎn)被插結(jié)點(diǎn)*s為右孩子為右孩子 return TRUE；else return FALSE；/樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入 /Insert BST22對于二叉排序樹，刪除樹上一個結(jié)點(diǎn)相當(dāng)于刪除有序序列中對于二叉排序樹，刪除樹上一個結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個記錄，刪除后仍需保持二叉排序樹的特性。的一個記錄，刪除后仍需保持二叉排序樹的特性。（對鏈表進(jìn)行刪除操作是很方便的）（對鏈表進(jìn)行刪除操作是很方便的）討論討論2 2：二叉排序樹的刪除操作：二叉排序樹的刪除操作如何刪除一個結(jié)點(diǎn)？如何刪除一個結(jié)點(diǎn)？假設(shè)：假設(shè)：*p p表示被刪結(jié)點(diǎn)的指針；表示被刪結(jié)點(diǎn)的指針；P PL和和PR 分別表示分別表示*P P的左、右孩子指針；的左、右孩子指針；*f f表示表示*p p的雙親結(jié)點(diǎn)指針；并假定的雙親結(jié)點(diǎn)指針；并假定*p p是是*f f的的左孩子左孩子；則可能有三種情況：；則可能有三種情況：PR 為為*S S 的右子樹；的右子樹；S SL 為為 Q（*S S的雙親結(jié)點(diǎn)）右孩子的雙親結(jié)點(diǎn)）右孩子*p*p為葉子：為葉子：刪除此結(jié)點(diǎn)時，直接修改刪除此結(jié)點(diǎn)時，直接修改*f f指針域即可；指針域即可；*p p只有一棵子樹（或左或右）：只有一棵子樹（或左或右）：令令P PL或或PR為為*f f的左孩子即可；的左孩子即可；*p p有兩棵子樹：情況最復(fù)雜有兩棵子樹：情況最復(fù)雜 23*p*p有兩棵子樹時，如何進(jìn)行刪除操作？有兩棵子樹時，如何進(jìn)行刪除操作？分析：分析：設(shè)刪除前的中序遍歷序列為：設(shè)刪除前的中序遍歷序列為：.s p PR ./顯然顯然顯然顯然p p p p的直接前驅(qū)是的直接前驅(qū)是的直接前驅(qū)是的直接前驅(qū)是s s s s希望刪除希望刪除p p后，其它元素的相對位置不變。有兩種解決方法：后，其它元素的相對位置不變。有兩種解決方法：法法1 1：令令*p p的左子樹為的左子樹為 *f f的左子樹，的左子樹，*p p的右子樹為的右子樹為*s s的右子的右子樹；樹；/即即即即F FL L=P=PL L ;F;FR R=P=PR R ;法法2 2：令令*s s代替代替*p p /*s*s*s*s為為為為*p p p p左子樹最右下的葉子左子樹最右下的葉子左子樹最右下的葉子左子樹最右下的葉子 見課本見課本見課本見課本P230 P230 P230 P230 圖圖圖圖9.99.99.99.924F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2:2:F FC CCLS SSLQLPPRQ法法1:1:例：例：請從下面的二叉排序樹中刪除結(jié)點(diǎn)請從下面的二叉排序樹中刪除結(jié)點(diǎn)P。S SSL25四、平衡二叉樹四、平衡二叉樹四、平衡二叉樹四、平衡二叉樹平衡二叉樹又稱平衡二叉樹又稱AVL樹，它是具有如下性質(zhì)的樹，它是具有如下性質(zhì)的二叉樹：二叉樹：為了方便起見，給每個結(jié)點(diǎn)附加一個為了方便起見，給每個結(jié)點(diǎn)附加一個數(shù)字?jǐn)?shù)字，給，給出出該結(jié)點(diǎn)左子樹與右子樹的高度差該結(jié)點(diǎn)左子樹與右子樹的高度差。這個數(shù)字。這個數(shù)字稱為結(jié)點(diǎn)的稱為結(jié)點(diǎn)的平衡因子平衡因子balancebalance。這樣，可以得到這樣，可以得到AVL樹的其它性質(zhì)：樹的其它性質(zhì)：即即|左子樹深度左子樹深度-右子樹深度右子樹深度|1|1左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對值所有結(jié)點(diǎn)的左、右子樹深度之差的絕對值 126(a)(a)平衡樹平衡樹 (b)(b)不平衡樹不平衡樹例：判斷下列二叉樹是否例：判斷下列二叉樹是否AVL樹？樹？v任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1、0 或或 1；如果；如果樹中任意一個結(jié)點(diǎn)的平衡因子的絕對值大于樹中任意一個結(jié)點(diǎn)的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是則這棵二叉樹就失去平衡，不再是AVL樹；樹；v對于一棵有對于一棵有n個結(jié)點(diǎn)的個結(jié)點(diǎn)的AVL樹，其樹，其高度保持在高度保持在O(log2n)數(shù)量級，數(shù)量級，ASL也保持在也保持在O(log2n)量級。量級。0001 11 1-1-12 2 2 20001-127如果在一棵如果在一棵AVL樹中插入一個新結(jié)點(diǎn)，就有可能造樹中插入一個新結(jié)點(diǎn)，就有可能造成失衡，此時必須成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)。現(xiàn)分別介紹這四種平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：平衡旋轉(zhuǎn)可以歸納為四類：v LL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)v RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)v LR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)v RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)28若在若在A的的左子樹的左子樹上插入左子樹的左子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加增加至至2，需要進(jìn)行一次，需要進(jìn)行一次順時針旋轉(zhuǎn)順時針旋轉(zhuǎn)。(以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）A AB BC CA AB BC C1 1）LLLL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：A AB B29若在若在A的的右子樹的右子樹上插入右子樹的右子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從-1增增加至加至-2，需要進(jìn)行一次，需要進(jìn)行一次逆時針旋轉(zhuǎn)逆時針旋轉(zhuǎn)。(以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）2 2）RRRR平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：A AB BC CA AB BC CA AB B30若在若在A的的左子樹的左子樹的右右子樹上插入子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至2，需要，需要先進(jìn)行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。先進(jìn)行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）A AB BC CA AB BA AB BC C3 3）LRLR平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：A AB BC C31若在若在A的的右子樹的左子樹上插入右子樹的左子樹上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從-1增增加至加至-2，需要，需要先進(jìn)行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。先進(jìn)行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）4 4）RLRL平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)：A AB BA AB BC CA AB BC CA AB BC C320 013130 037370 02424例：例：請將下面序列構(gòu)成一棵請將下面序列構(gòu)成一棵平衡二叉排序樹平衡二叉排序樹：（13，24，37，90，53）0 013130 03737-1-113130 02424-1-12424-2-2-2-21313需要需要RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根）0 09090-1-12424-1-137370 053531 19090-2-2-2-23737需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞C先順后逆）先順后逆）0 037370 090900 053530 037370 090900 05353 339.4 9.4 哈希查找表哈希查找表一、哈希表的概念一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法三、沖突處理方法沖突處理方法四、哈希表的查找及分析四、哈希表的查找及分析34一、哈希表的概念一、哈希表的概念哈希表：哈希表：即散列存儲結(jié)構(gòu)。即散列存儲結(jié)構(gòu)。散列法存儲的基本思想：散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的建立關(guān)鍵碼字與其存儲位置的對應(yīng)對應(yīng)關(guān)系，關(guān)系，或者說，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。優(yōu)點(diǎn)：優(yōu)點(diǎn)：查找速度極快（查找速度極快（O(1)O(1)）,查找效率與元素個數(shù)查找效率與元素個數(shù)n n無關(guān)！無關(guān)！例例1：若將學(xué)生信息按如下方式存入計算機(jī)，如：若將學(xué)生信息按如下方式存入計算機(jī)，如：將將20010118102200101181020101的所有信息存入的所有信息存入VV0101 單元；單元；將將20010118102200101181020202的所有信息存入的所有信息存入VV0202 單元；單元；將將20010118102200101181023131的所有信息存入的所有信息存入V31V31單元。單元。欲查找學(xué)號為欲查找學(xué)號為20010118102200101181021616的信息，便可直接訪問的信息，便可直接訪問V16V16！35例例2：有有數(shù)數(shù)據(jù)據(jù)元元素素序序列列(14(14，2323，3939，9 9，2525，11)11)，若若規(guī)規(guī)定定每個元素每個元素k k的存儲地址的存儲地址H H（k k）k k，請畫出存儲結(jié)構(gòu)圖。，請畫出存儲結(jié)構(gòu)圖。（注：（注：H H（k k）k k稱為散列函數(shù)）稱為散列函數(shù)）解：解：根據(jù)散列函數(shù)根據(jù)散列函數(shù)H H（k k）k k，可知元素，可知元素1414應(yīng)當(dāng)存入地址為應(yīng)當(dāng)存入地址為1414的單元，元素的單元，元素2323應(yīng)當(dāng)存入地址為應(yīng)當(dāng)存入地址為2323的單元，的單元，對應(yīng)散列存儲表（哈希表）如下：對應(yīng)散列存儲表（哈希表）如下：討論：如何進(jìn)行散列查找？討論：如何進(jìn)行散列查找？根據(jù)存儲時用到的散列函數(shù)根據(jù)存儲時用到的散列函數(shù)H(k)H(k)表達(dá)式表達(dá)式，迅即可查到結(jié)果！，迅即可查到結(jié)果！例如，查找例如，查找key=9,key=9,則訪問則訪問H(9)=9H(9)=9號地址，若內(nèi)容為號地址，若內(nèi)容為9 9則成功；則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個特殊值，例如空指針或空記錄。若查不到，應(yīng)當(dāng)設(shè)法返回一個特殊值，例如空指針或空記錄。地址地址 9111423242539內(nèi)容內(nèi)容14119232539缺點(diǎn)：空間效率低！缺點(diǎn)：空間效率低！缺點(diǎn)：空間效率低！缺點(diǎn)：空間效率低！36選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；并按此存放；查找時，由同一個函數(shù)查找時，由同一個函數(shù)對給定值對給定值k k計算地址，計算地址，將將k k與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同可能將不同的關(guān)鍵碼映射到同一個哈希地址上一個哈希地址上，這種現(xiàn)象稱為，這種現(xiàn)象稱為沖突沖突。若干術(shù)語若干術(shù)語 哈希方法哈希方法 (雜湊法雜湊法)哈希函數(shù)哈希函數(shù)(雜湊函數(shù)雜湊函數(shù))哈哈 希希 表表 (雜湊表雜湊表)沖沖 突突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)哈希函數(shù)(雜雜湊函數(shù)湊函數(shù))按上述思想構(gòu)造的表稱為按上述思想構(gòu)造的表稱為哈希表哈希表(雜湊表雜湊表)37有有6個元素的關(guān)鍵碼分別為：（個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。）。選取關(guān)鍵碼與元素位置間的函數(shù)為選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7通過哈希函數(shù)對通過哈希函數(shù)對6 6個元素建立哈希表：個元素建立哈希表：253923914沖突現(xiàn)象舉例：沖突現(xiàn)象舉例：沖突現(xiàn)象舉例：沖突現(xiàn)象舉例：6個元素用個元素用7個個地址應(yīng)該足夠地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！有沖突！有沖突！有沖突！0 1 2 3 4 5 638所以，所以，所以，所以，哈希方法必須解決以下兩個問題：哈希方法必須解決以下兩個問題：哈希方法必須解決以下兩個問題：哈希方法必須解決以下兩個問題：1 1）構(gòu)造好的哈希函數(shù)構(gòu)造好的哈希函數(shù)構(gòu)造好的哈希函數(shù)構(gòu)造好的哈希函數(shù)（a a）所選函數(shù)盡可能）所選函數(shù)盡可能簡單簡單，以便提高轉(zhuǎn)換速度；，以便提高轉(zhuǎn)換速度；（b b）所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在）所選函數(shù)對關(guān)鍵碼計算出的地址，應(yīng)在哈希地址集哈希地址集中中大致大致均勻均勻分布，以減少空間浪費(fèi)。分布，以減少空間浪費(fèi)。2 2 2 2）制定一個好的解決沖突的方案）制定一個好的解決沖突的方案）制定一個好的解決沖突的方案）制定一個好的解決沖突的方案查查找找時時，如如果果從從哈哈希希函函數(shù)數(shù)計計算算出出的的地地址址中中查查不不到到關(guān)關(guān)鍵鍵碼碼，則則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)