數(shù)據(jù)結(jié)構(gòu)查找

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容9.1 9.1 基本概念基本概念9.2 9.2 靜態(tài)查找表靜態(tài)查找表9.3 9.3 動(dòng)態(tài)查找表動(dòng)態(tài)查找表9.4 9.4 哈希表哈希表教材第教材第8 8、1111和和1212章省略，因章省略，因操作系統(tǒng)操作系統(tǒng)課程會(huì)涉及。課程會(huì)涉及。9.1 9.1 基本概念基本概念若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找表查查 找找查找成功查找成功查找不成功查找不成功靜態(tài)查找靜態(tài)查找動(dòng)態(tài)查找動(dòng)態(tài)查找關(guān)鍵字關(guān)鍵字主關(guān)鍵字主

2、關(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ù)元素。記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄 ( 預(yù)先確定的記錄的某種標(biāo)志預(yù)先確定的記錄的某種標(biāo)志 ) 可以可以唯一唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字例如例如“學(xué)號(hào)學(xué)號(hào)”例如例如“女女”是一種數(shù)據(jù)結(jié)構(gòu)是一種數(shù)據(jù)結(jié)構(gòu)識(shí)別若干記錄的關(guān)鍵字

3、識(shí)別若干記錄的關(guān)鍵字（2）對(duì)查找表常用的操作有）對(duì)查找表常用的操作有哪些？哪些？ v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素是否在表中；數(shù)據(jù)元素是否在表中；v查詢某個(gè)查詢某個(gè)“特定的特定的”數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性；v在查找表中插入一元素；在查找表中插入一元素；v從查找表中刪除一元素。從查找表中刪除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的排列方式查找方法取決于表中數(shù)據(jù)的排列方式;討論：討論：（1）查找的過(guò)程是怎樣的？）查找的過(guò)程是怎樣的？ 給定一個(gè)值給定一個(gè)值K K，在含有，在含有n n個(gè)記錄的文件中進(jìn)行搜索，尋找個(gè)記錄的文件中進(jìn)行搜索，尋找一

4、個(gè)關(guān)鍵字值等于一個(gè)關(guān)鍵字值等于K K的記錄，如找到則輸出該記錄，否則輸出的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。查找不成功的信息。例如查字典例如查字典針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同?！疤囟ǖ奶囟ǖ摹?關(guān)鍵字關(guān)鍵字（4）如何評(píng)估查找方法的優(yōu)劣？）如何評(píng)估查找方法的優(yōu)劣？明確：明確：查找的過(guò)程就是將給定的查找的過(guò)程就是將給定的K K值與文件中各記錄的關(guān)鍵字值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱為劣。稱為平均查找長(zhǎng)度平均查找長(zhǎng)

5、度（ASLASL：average search lengthaverage search length）。）。其中：其中：n是文件記錄個(gè)數(shù)；是文件記錄個(gè)數(shù)；P Pi i是查找第是查找第i i個(gè)記錄的查找概率（通常取等概率個(gè)記錄的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。統(tǒng)計(jì)意義上的統(tǒng)計(jì)意義上的數(shù)學(xué)期望值數(shù)學(xué)期望值物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為一元素所需的比較次數(shù)之總和再取平均

6、，即為ASLASL。顯然，顯然，ASLASL值越小，時(shí)間效率越高。值越小，時(shí)間效率越高。 針對(duì)靜態(tài)查找表的查找算法主要有：針對(duì)靜態(tài)查找表的查找算法主要有： 9.2 9.2 靜態(tài)查找表靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型參見(jiàn)教材靜態(tài)查找表的抽象數(shù)據(jù)類型參見(jiàn)教材P216。一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹(shù)表的查找三、靜態(tài)樹(shù)表的查找四、分塊查找（索引順序查找）四、分塊查找（索引順序查找）一、順序查找（一、順序查找（ Linear search，又稱線性查找又稱線性查找 ）（1）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)

7、：typedef struct ElemType *elem; /表基址，表基址，0 0號(hào)單元留空。表容量為全部元素號(hào)單元留空。表容量為全部元素 int length; /表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。直接的辦法。 v 對(duì)對(duì)順序結(jié)構(gòu)順序結(jié)構(gòu)如何線性查找？如何線性查找？見(jiàn)下頁(yè)之例見(jiàn)下頁(yè)之例或教材或教材P216P216；v 對(duì)對(duì)單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易如何線性查找？函數(shù)雖未給出，但也很容易編寫(xiě)；只要知道頭指針編寫(xiě)

8、；只要知道頭指針headhead就可以就可以“順藤摸瓜順藤摸瓜”；v 對(duì)對(duì)非線性樹(shù)結(jié)構(gòu)非線性樹(shù)結(jié)構(gòu)如何順序查找如何順序查找? ?可借助各種遍歷操作！可借助各種遍歷操作！（2）算法的實(shí)現(xiàn)：算法的實(shí)現(xiàn)：技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），），這樣可以加快執(zhí)行速度。這樣可以加快執(zhí)行速度。例：例：若將待查找的特定值若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號(hào)單號(hào)單元），則順序查找的實(shí)現(xiàn)方案為：元），則順序查找的實(shí)現(xiàn)方案為：從后向前從后向前逐個(gè)比較！逐個(gè)比較！int Search_Seq( SSTabl

9、e ST , KeyType key ) /在順序表在順序表STST中，查找關(guān)鍵字與中，查找關(guān)鍵字與keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否則返回置信息，否則返回0 0 ST.elem0.key =key; /設(shè)立哨兵，可免去查找過(guò)程中每一步設(shè)立哨兵，可免去查找過(guò)程中每一步都要檢測(cè)是否查找完畢。當(dāng)都要檢測(cè)是否查找完畢。當(dāng)n1000n1000時(shí)，查找時(shí)間將減少一半。時(shí)，查找時(shí)間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) for(i=n; i0

10、; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+) return i; /若到達(dá)若到達(dá)0 0號(hào)單元才結(jié)束循環(huán)，說(shuō)明不成功，返回號(hào)單元才結(jié)束循環(huán)，說(shuō)明不成功，返回0 0值值(i=0)(i=0)。成功時(shí)則返回找到的那個(gè)元素的位置。成功時(shí)則返回找到的那個(gè)元素的位置i i。 / Search_Seq返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨哨兵兵”，就是將關(guān)鍵字送入末地址，就是將關(guān)鍵字送入末地址ST.elemST.elem0 0.key.key使之結(jié)束并返回使之結(jié)束并返回 i=0i=0。討論討論 查找

11、效率怎樣計(jì)算？查找效率怎樣計(jì)算？用平均查找長(zhǎng)度用平均查找長(zhǎng)度ASL衡量。衡量。討論討論 查不到怎么辦？查不到怎么辦？討論討論 如何計(jì)算如何計(jì)算ASL？分析：分析：查找第查找第1個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為1；查找第查找第2個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為2；查找第查找第n個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：總計(jì)全部比較次數(shù)為：12n = (1+n)n/2未考慮查找不成功的未考慮查找不成功的情況：查找哨兵所需情況：查找哨兵所需的比較次數(shù)為的比較次數(shù)為n+1n+1這是查找成功的情況這是查找成功的情況若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以

12、若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），（等概率），即：即： ASL（1n）/2 ，時(shí)間效率為，時(shí)間效率為 O(n)二、折半查找（又稱二分查找或?qū)Ψ植檎遥┒?、折半查找（又稱二分查找或?qū)Ψ植檎遥﹥?yōu)點(diǎn)：優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：缺點(diǎn)： ASL 太長(zhǎng)，時(shí)間效率太低。太長(zhǎng)，時(shí)間效率太低。這是一種容易想到的查找方法。這是一種容易想到的查找方法。先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與正中元素相比，若與正中元素相比，若keykey小，則縮小至右半部?jī)?nèi)

13、查找；再取其中小，則縮小至右半部?jī)?nèi)查找；再取其中值比較，每次縮小值比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。v 對(duì)對(duì)順序表結(jié)構(gòu)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)折半查找算法？如何編程實(shí)現(xiàn)折半查找算法？ 見(jiàn)下頁(yè)之例見(jiàn)下頁(yè)之例，或見(jiàn)教材（，或見(jiàn)教材（P219P219）v 對(duì)對(duì)單鏈表結(jié)構(gòu)單鏈表結(jié)構(gòu)如何折半查找？如何折半查找？ 無(wú)法實(shí)現(xiàn)！因全部元素的定位只能從頭指針無(wú)法實(shí)現(xiàn)！因全部元素的定位只能從頭指針headhead開(kāi)始開(kāi)始v 對(duì)對(duì)非線性非線性(樹(shù)樹(shù))結(jié)構(gòu)結(jié)構(gòu)如何折半查找？如何折半查找？ 可借助二叉排序樹(shù)來(lái)查找（屬動(dòng)態(tài)查找表形式）?？山柚媾判驑?shù)來(lái)查找（屬動(dòng)態(tài)查

14、找表形式）。 如何改進(jìn)？如何改進(jìn)？討論討論 順序查找的特點(diǎn)：順序查找的特點(diǎn)： 運(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，說(shuō)明，說(shuō)明keykey low ,midlow ,mid-1-1 ， 則令：則令：high =midhigh =mid1 1; ;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key ST.elem mid .key

15、= key= key，說(shuō)明查找成功，元素序號(hào)，說(shuō)明查找成功，元素序號(hào)=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) / 在左子樹(shù)中繼續(xù)查找在左子樹(shù)中繼續(xù)查找 return ( SearchBST(Tlchild, key) )； else return ( SearchBST(Trchild, key) )；

16、 / 在右子樹(shù)中繼續(xù)查找在右子樹(shù)中繼續(xù)查找 / SearchBSTStatus 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); / 在左子樹(shù)中繼續(xù)查找在左子樹(shù)中繼續(xù)查找 else return Search

17、BST(Trchild, key, T, p); / 在右子樹(shù)中繼續(xù)查找在右子樹(shù)中繼續(xù)查找 / SearchBSTStatus 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為空樹(shù)為空樹(shù) else if LT (e.key, pdata.key) plchil

18、d = s；/ 被插結(jié)點(diǎn)被插結(jié)點(diǎn)*s為左孩子為左孩子 else prchild = s； /被插結(jié)點(diǎn)被插結(jié)點(diǎn)*s為右孩子為右孩子 return TRUE； else return FALSE；/ 樹(shù)中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入樹(shù)中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入 / Insert BST對(duì)于二叉排序樹(shù)，刪除樹(shù)上一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中對(duì)于二叉排序樹(shù)，刪除樹(shù)上一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個(gè)記錄，刪除后仍需保持二叉排序樹(shù)的特性。的一個(gè)記錄，刪除后仍需保持二叉排序樹(shù)的特性。（對(duì)鏈表進(jìn)行刪除操作是很方便的）（對(duì)鏈表進(jìn)行刪除操作是很方便的）討論討論2 2：二叉排序樹(shù)的刪除操作：二叉排序樹(shù)的刪除

19、操作如何刪除一個(gè)結(jié)點(diǎn)？如何刪除一個(gè)結(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 的右子樹(shù)；的右子樹(shù)； S SL 為為 Q（ * * S S的雙親結(jié)點(diǎn)）右孩子的雙親結(jié)點(diǎn)）右孩子* *p p為葉子：為葉子： 刪除此結(jié)點(diǎn)時(shí)，直接修改刪除此結(jié)點(diǎn)時(shí)，直接修改* *f f指針域即可；指針域即可；* *p p只有一棵

20、子樹(shù)（或左或右）：只有一棵子樹(shù)（或左或右）：令令P PL或或PR為為* *f f的左孩子即可；的左孩子即可；* *p p有兩棵子樹(shù)：情況最復(fù)雜有兩棵子樹(shù)：情況最復(fù)雜 * *p p有兩棵子樹(shù)時(shí)，如何進(jìn)行刪除操作？有兩棵子樹(shù)時(shí)，如何進(jìn)行刪除操作？分析：分析：設(shè)刪除前的中序遍歷序列為：設(shè)刪除前的中序遍歷序列為：. s p PR . 希望刪除希望刪除p p后，其它元素的相對(duì)位置不變。有兩種解決方法：后，其它元素的相對(duì)位置不變。有兩種解決方法：法法1 1：令令* *p p的左子樹(shù)為的左子樹(shù)為 * *f f的左子樹(shù)，的左子樹(shù)，* *p p的右子樹(shù)為的右子樹(shù)為* *s s的右子的右子樹(shù)；樹(shù)； 法法2 2：令

21、令* *s s代替代替* *p p F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2:2:F FC CCLS SSLQLPPRQ法法1:1:例：例：請(qǐng)從下面的二叉排序樹(shù)中刪除結(jié)點(diǎn)請(qǐng)從下面的二叉排序樹(shù)中刪除結(jié)點(diǎn)P。S SSL平衡二叉樹(shù)又稱平衡二叉樹(shù)又稱AVL樹(shù)，它是具有如下性質(zhì)的樹(shù)，它是具有如下性質(zhì)的二叉樹(shù)：二叉樹(shù)：為了方便起見(jiàn)，給每個(gè)結(jié)點(diǎn)附加一個(gè)為了方便起見(jiàn)，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字?jǐn)?shù)字，給，給出出該結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度差該結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度差。這個(gè)數(shù)字。這個(gè)數(shù)字稱為結(jié)點(diǎn)的稱為結(jié)點(diǎn)的平衡因子平衡因子balancebalance。這樣，可以得到這樣，

22、可以得到AVL樹(shù)的其它性質(zhì)：樹(shù)的其它性質(zhì)：即即| |左子樹(shù)深度左子樹(shù)深度- -右子樹(shù)深度右子樹(shù)深度| 1| 1左、右子樹(shù)是平衡二叉樹(shù)；左、右子樹(shù)是平衡二叉樹(shù)；所有結(jié)點(diǎn)的左、右子樹(shù)深度之差的絕對(duì)值所有結(jié)點(diǎn)的左、右子樹(shù)深度之差的絕對(duì)值 1(a) (a) 平衡樹(shù)平衡樹(shù) (b) (b) 不平衡樹(shù)不平衡樹(shù)例：判斷下列二叉樹(shù)是否例：判斷下列二叉樹(shù)是否AVL樹(shù)？樹(shù)？v任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1、0 或或 1；如果；如果樹(shù)中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于樹(shù)中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉樹(shù)就失去平衡，不再是則這棵二叉樹(shù)就失去平衡，不再是AVL樹(shù)；樹(shù)；v對(duì)于一

23、棵有對(duì)于一棵有n個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的AVL樹(shù)，其樹(shù)，其高度保持在高度保持在O(log2n)數(shù)量級(jí)，數(shù)量級(jí)，ASL也保持在也保持在O(log2n)量級(jí)。量級(jí)。0001 11 1-1-10001-1如果在一棵如果在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有可能樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須造成失衡，此時(shí)必須重新調(diào)整樹(shù)的結(jié)構(gòu)重新調(diào)整樹(shù)的結(jié)構(gòu)，使之恢，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)?，F(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)平衡旋

24、轉(zhuǎn)v RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)若在若在A的的左子樹(shù)的左子樹(shù)上插入左子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加增加至至2，需要進(jìn)行一次，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)。(以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A的的右子樹(shù)的右子樹(shù)上插入右子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從-1增增加至加至-2，需要進(jìn)行一次，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn)。(以以B為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A的的左子樹(shù)的左子樹(shù)的右右子樹(shù)上插入子樹(shù)上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從1增加至增加至2，需要，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(

25、以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）若在若在A的的右子樹(shù)的左子樹(shù)上插入右子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)，使結(jié)點(diǎn)，使A的平衡因子從的平衡因子從-1增增加至加至-2，需要，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）0 013130 037370 02424例：例：請(qǐng)將下面序列構(gòu)成一棵請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹(shù)平衡二叉排序樹(shù)： （ 13，24，37，90，53）0 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根）0 09090-

26、1-12424-1-137370 053531 190903737需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞C先順后逆）先順后逆）0 037370 090900 053530 037370 090900 05353哈希表：哈希表：即散列存儲(chǔ)結(jié)構(gòu)。即散列存儲(chǔ)結(jié)構(gòu)。 散列法存儲(chǔ)的基本思想：散列法存儲(chǔ)的基本思想：建立關(guān)鍵碼字與其存儲(chǔ)位置的建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)對(duì)應(yīng)關(guān)系，關(guān)系，或者說(shuō)，或者說(shuō)，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：查找速度極快（查找速度極快（O(1)O(1)）, ,查找效率與元素個(gè)數(shù)查找效率與元素個(gè)數(shù)n n無(wú)關(guān)！無(wú)關(guān)！例例1：若將學(xué)生信息按如下方式

27、存入計(jì)算機(jī)，如：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將將20010118102200101181020101的所有信息存入的所有信息存入VV0101 單元；單元；將將20010118102200101181020202的所有信息存入的所有信息存入VV0202 單元；單元；將將20010118102200101181023131的所有信息存入的所有信息存入V31V31單元。單元。欲查找學(xué)號(hào)為欲查找學(xué)號(hào)為20010118102200101181021616的信息，便可直接訪問(wèn)的信息，便可直接訪問(wèn)V16V16！例例2 ： 有數(shù)據(jù)元素序列有數(shù)據(jù)元素序列(14(14，2323，3939，9 9，252

28、5，11)11)，若規(guī)定，若規(guī)定每個(gè)元素每個(gè)元素k k的存儲(chǔ)地址的存儲(chǔ)地址H H（k k）k k，請(qǐng)畫(huà)出存儲(chǔ)結(jié)構(gòu)圖。，請(qǐng)畫(huà)出存儲(chǔ)結(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的單元，的單元，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：討論：如何進(jìn)行散列查找？討論：如何進(jìn)行散列查找？根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)H(k)表達(dá)式表達(dá)式，迅即可查到結(jié)

29、果！，迅即可查到結(jié)果！例如，查找例如，查找key=9,key=9,則訪問(wèn)則訪問(wèn)H(9)=9H(9)=9號(hào)地址，若內(nèi)容為號(hào)地址，若內(nèi)容為9 9則成功；則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。 地址地址 9111423242539內(nèi)容內(nèi)取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；并按此存放；查找時(shí)，由同一個(gè)函數(shù)查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值對(duì)給定值k k計(jì)算地址，計(jì)算地址，將將k k與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。與地

30、址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上一個(gè)哈希地址上，這種現(xiàn)象稱為，這種現(xiàn)象稱為沖突沖突。若干術(shù)語(yǔ)若干術(shù)語(yǔ) 哈希方法哈希方法 ( (雜湊法雜湊法) ) 哈希函數(shù)哈希函數(shù)( (雜湊函數(shù)雜湊函數(shù)) ) 哈哈 希希 表表 ( (雜湊表雜湊表) ) 沖沖 突突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)哈希函數(shù)( (雜雜湊函數(shù)湊函數(shù)) )按上述思想構(gòu)造的表稱為按上述思想構(gòu)造的表稱為哈希表哈

31、希表( (雜湊表雜湊表) ) 有有6個(gè)元素的關(guān)鍵碼分別為：（個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。）。選取關(guān)鍵碼與元素位置間的函數(shù)為選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7通過(guò)哈希函數(shù)對(duì)通過(guò)哈希函數(shù)對(duì)6 6個(gè)元素建立哈希表：個(gè)元素建立哈希表：2539239146個(gè)元素用個(gè)元素用7個(gè)個(gè)地址應(yīng)該足夠地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4 0 1 2 3 4 5 6（a a）所選函數(shù)盡可能）所選函數(shù)盡可能簡(jiǎn)單簡(jiǎn)單，以便提高轉(zhuǎn)換速度；，以便提高轉(zhuǎn)換速度；（b b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在）所選函數(shù)對(duì)關(guān)鍵碼

32、計(jì)算出的地址，應(yīng)在哈希地址集哈希地址集中中大致大致均勻均勻分布，以減少空間浪費(fèi)。分布，以減少空間浪費(fèi)。查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。二、常用的哈希函數(shù)構(gòu)造方法有：常用的哈希函數(shù)構(gòu)造方法有：要求一：要求一：n n個(gè)數(shù)據(jù)原僅占用個(gè)數(shù)據(jù)原僅占用n n個(gè)地址，個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。希望散列的地址空間盡量小。要求二：要求二：無(wú)論用什么方法存儲(chǔ)，目無(wú)論用什么方

33、法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免的都是盡量均勻地存放元素，以避免沖突。沖突。Hash(key) = akey + b ( (a、b為常數(shù)為常數(shù)) )優(yōu)點(diǎn)：優(yōu)點(diǎn)：以關(guān)鍵碼以關(guān)鍵碼keykey的某個(gè)線性函數(shù)值為哈希地址，的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突不會(huì)產(chǎn)生沖突. .缺點(diǎn)：缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。要占用連續(xù)地址空間，空間效率低。 例：例：關(guān)鍵碼集合為關(guān)鍵碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為選取哈希函數(shù)為Hash(key)=key/100， 則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：0 1 2 3 4 5 6 7 8 9

34、900800700500300100Hash(key)=key mod p (p (p是一個(gè)整數(shù)是一個(gè)整數(shù)) )特點(diǎn)：特點(diǎn)：以關(guān)鍵碼除以以關(guān)鍵碼除以p的余數(shù)作為哈希地址。的余數(shù)作為哈希地址。關(guān)鍵：關(guān)鍵：如何選取合適的如何選取合適的p？技巧：技巧：若設(shè)計(jì)的哈希表長(zhǎng)為若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取，則一般取pm且為且為質(zhì)數(shù)質(zhì)數(shù) （也可以是不包含小于（也可以是不包含小于20質(zhì)因子的合數(shù)）。質(zhì)因子的合數(shù)）。自練：自練：自測(cè)卷簡(jiǎn)答題第自測(cè)卷簡(jiǎn)答題第4 4小題小題 特點(diǎn)：特點(diǎn)：某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。是

35、：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。 3 4 7 0 5 2 4 3 4 9 1 4 8 73 4 8 2 6 9 63 4 8 5 2 7 03 4 8 6 3 0 53 4 9 8 0 5 83 4 7 9 6 7 13 4 7 3 9 1 9例：例：有一組（例如有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：個(gè)）關(guān)鍵碼，其樣式如下：討論：討論： 第第1 1、2 2位均是位均是“3 3和和4 4”，第，第3 3位也位也只有只有“ 7 7、8 8、9 9”，因此，這幾位不，因此，這幾位不能用，能用，余下四位分布較均勻余下四位分布較均勻，可作，可作為哈希地址選用。為哈希地址選用。位號(hào)：位號(hào)： 若哈希

36、地址取兩位（因元素僅若哈希地址取兩位（因元素僅8080個(gè)），則可取這四位中的任意兩位組個(gè)），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈其它兩位疊加求和后，取低兩位作哈希地址。希地址。特點(diǎn)：特點(diǎn)：對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。作為哈希地址。理由：理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。 例：例：25892589的平方值為的平方值為67029216702921，可以取中間的，可以取中間的029029為地址。為地址。

37、 特點(diǎn)：特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長(zhǎng)，取后幾位作為哈希地址。希表表長(zhǎng)，取后幾位作為哈希地址。適用于：適用于：每一位上各符號(hào)出現(xiàn)概率大致相同的情況。每一位上各符號(hào)出現(xiàn)概率大致相同的情況。法法1 1：移位法移位法 將各部分的最后一位對(duì)齊相加。將各部分的最后一位對(duì)齊相加。法法2 2：間界疊加法間界疊加法從一端向另一端沿分割界來(lái)回折疊后從一端向另一端沿分割界來(lái)回折疊后, ,最后一位對(duì)齊相加。最后一位對(duì)齊相加。 例：例：元素元素42

38、751896, 42751896, 用法用法1 1： 4274275185189696= =10411041 用法用法2 2： 427427 518 518 9696 724+518+69 = 724+518+69 =13111311Hash(key) = random ( key ) (random (random為隨機(jī)函數(shù)為隨機(jī)函數(shù)) )適用于：適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）； 關(guān)鍵字的長(zhǎng)度；關(guān)鍵字的長(zhǎng)度； 哈希表的大??；哈希表的大??； 關(guān)鍵字的分布情況；關(guān)

39、鍵字的分布情況； 查找頻率。查找頻率。三、常見(jiàn)的沖突處理方法有：常見(jiàn)的沖突處理方法有：設(shè)計(jì)思路：設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。到，并將數(shù)據(jù)元素存入。 具體實(shí)現(xiàn)：具體實(shí)現(xiàn)：Hi=(Hash(key)+di) mod m ( 1i m ) 其中：其中： Hash(key)為哈希函數(shù)為哈希函數(shù) m為哈希表長(zhǎng)度為哈希表長(zhǎng)度 di 為增量序列為增量序列 1，2，m-1，且，且di=i關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：設(shè)：

40、哈希表表長(zhǎng)為哈希表表長(zhǎng)為m=m=11； 哈希函數(shù)為哈希函數(shù)為Hash(key)=key mod 11； 擬用擬用處理沖突。建哈希表如下：處理沖突。建哈希表如下：解釋：解釋： 47、7（以及（以及11、16、92）均是由哈希函數(shù)得到的沒(méi)有沖突均是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址；的哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：例：291116922283 Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8為空，因此將為空，因此將29存入。存入。

41、另外，另外，22、8、3同樣在哈希地址上有沖突，也是由同樣在哈希地址上有沖突，也是由H1找到空找到空的哈希地址的。的哈希地址的。線性探測(cè)法的優(yōu)點(diǎn)：線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：線性探測(cè)法的缺點(diǎn)：可能使第可能使第i個(gè)哈希地址的同義詞個(gè)哈希地址的同義詞存入第存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)個(gè)哈希地址的元素變成了第哈希地址的元素變成了第i+2個(gè)哈希地址的同個(gè)哈希地址的同義詞，義詞， 因此，可能出現(xiàn)很多元素在相鄰的哈希地址因此，可能出現(xiàn)很多元素在相鄰的哈希地址上上“堆積堆積”起來(lái)，大大降低了查找效率。起來(lái)，大大降低了查找效率。