數(shù)據(jù)結(jié)構(gòu)“ 查找表”課件

1、第第 6 章章 查找表查找表6.1 6.1 基本概念基本概念查找表是一種查找表是一種以集合為邏輯結(jié)構(gòu)以集合為邏輯結(jié)構(gòu)、以查找、以查找為為“核心核心”運(yùn)算、同時(shí)包括其它運(yùn)算的數(shù)據(jù)結(jié)運(yùn)算、同時(shí)包括其它運(yùn)算的數(shù)據(jù)結(jié)構(gòu)。構(gòu)。 6.1.1 6.1.1 集合的基本概念集合的基本概念集合：由任意一些可分辨的對(duì)象構(gòu)成的整集合：由任意一些可分辨的對(duì)象構(gòu)成的整體。例如，所有整數(shù)放在一起構(gòu)成一個(gè)集合，體。例如，所有整數(shù)放在一起構(gòu)成一個(gè)集合，稱為整數(shù)集?？占遣缓魏卧氐募?，記稱為整數(shù)集。空集是不含任何元素的集合，記為為。 在數(shù)據(jù)結(jié)構(gòu)課程中，通常只考慮那些由具在數(shù)據(jù)結(jié)構(gòu)課程中，通常只考慮那些由具有相同類型的數(shù)據(jù)元

2、素構(gòu)成的集合。有相同類型的數(shù)據(jù)元素構(gòu)成的集合。 6.1.2 6.1.2 查找表的基本概念查找表的基本概念 查找是一種常用運(yùn)算，其功能是從大查找是一種常用運(yùn)算，其功能是從大量的數(shù)據(jù)元素中找出某個(gè)特定的數(shù)據(jù)元素。量的數(shù)據(jù)元素中找出某個(gè)特定的數(shù)據(jù)元素。標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)稱為標(biāo)識(shí)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)稱為關(guān)鍵字關(guān)鍵字，簡稱簡稱鍵鍵。該數(shù)據(jù)項(xiàng)的值稱為。該數(shù)據(jù)項(xiàng)的值稱為鍵值鍵值。能夠唯一地標(biāo)識(shí)能夠唯一地標(biāo)識(shí)數(shù)據(jù)元素?cái)?shù)據(jù)元素的的關(guān)鍵字稱關(guān)鍵字稱為為主關(guān)鍵字主關(guān)鍵字。不不能唯一地標(biāo)識(shí)能唯一地標(biāo)識(shí)數(shù)據(jù)元素?cái)?shù)據(jù)元素的的關(guān)鍵字稱關(guān)鍵字稱為為次關(guān)鍵字次關(guān)鍵字。查找運(yùn)算的功能的確切表述：根據(jù)查找運(yùn)算的功能的確切表述：根據(jù)給

3、定的某個(gè)值給定的某個(gè)值K，在查找表中尋找一個(gè)，在查找表中尋找一個(gè)其鍵值等于其鍵值等于K的數(shù)據(jù)元素。若找到一個(gè)的數(shù)據(jù)元素。若找到一個(gè)這樣的數(shù)據(jù)元素，則查找成功，運(yùn)算結(jié)這樣的數(shù)據(jù)元素，則查找成功，運(yùn)算結(jié)果為該數(shù)據(jù)元素在表中的位置；否則，果為該數(shù)據(jù)元素在表中的位置；否則，查找不成功，此時(shí)的運(yùn)算結(jié)果為一個(gè)特查找不成功，此時(shí)的運(yùn)算結(jié)果為一個(gè)特殊標(biāo)志。殊標(biāo)志。查找表：具有同一類型的數(shù)據(jù)元素組成的集合。查找表：具有同一類型的數(shù)據(jù)元素組成的集合。靜態(tài)查找表包括下列三種基本運(yùn)算：靜態(tài)查找表包括下列三種基本運(yùn)算： 建表建表CREATE(ST), 其作用是生成一個(gè)由用戶給其作用是生成一個(gè)由用戶給定的若干數(shù)據(jù)元素組成

4、的靜態(tài)查找表定的若干數(shù)據(jù)元素組成的靜態(tài)查找表ST。 查找查找SEARCH(ST，K)，若，若ST中存在關(guān)鍵字值中存在關(guān)鍵字值等于等于K的數(shù)據(jù)元素，運(yùn)算結(jié)果為該數(shù)據(jù)元素在的數(shù)據(jù)元素，運(yùn)算結(jié)果為該數(shù)據(jù)元素在ST中中的位置；否則，運(yùn)算結(jié)果為一特殊標(biāo)志。的位置；否則，運(yùn)算結(jié)果為一特殊標(biāo)志。 讀表元讀表元GET(ST，pos)，其運(yùn)算結(jié)果是，其運(yùn)算結(jié)果是ST中中pos位置上的數(shù)據(jù)元素。位置上的數(shù)據(jù)元素。 (靜態(tài)查找表是僅對(duì)查找表進(jìn)行查找操作，而不能靜態(tài)查找表是僅對(duì)查找表進(jìn)行查找操作，而不能被改變的表。被改變的表。) )動(dòng)態(tài)查找表動(dòng)態(tài)查找表 包括包括查找查找讀表元以及下讀表元以及下列三種基本運(yùn)算：列三種基

5、本運(yùn)算：插入插入INSERT(ST，K)，若，若ST中不存在中不存在關(guān)鍵字值等于關(guān)鍵字值等于K的數(shù)據(jù)元素，則將一個(gè)關(guān)鍵的數(shù)據(jù)元素，則將一個(gè)關(guān)鍵字值等于字值等于K的新數(shù)據(jù)元素插入到的新數(shù)據(jù)元素插入到ST中。中。刪除刪除DELETE(ST，K)，當(dāng)，當(dāng)ST中存在關(guān)中存在關(guān)鍵字值等于鍵字值等于K的數(shù)據(jù)元素時(shí)，將其刪除。的數(shù)據(jù)元素時(shí)，將其刪除。初始化初始化INITIATE(ST)，其作用是設(shè)置一，其作用是設(shè)置一個(gè)空的動(dòng)態(tài)查找表個(gè)空的動(dòng)態(tài)查找表ST。 (動(dòng)態(tài)查找表：除了對(duì)查找表進(jìn)行查找操作動(dòng)態(tài)查找表：除了對(duì)查找表進(jìn)行查找操作外，還能向表中插入數(shù)據(jù)元素，或刪除表中外，還能向表中插入數(shù)據(jù)元素，或刪除表中的數(shù)

6、據(jù)元素，因而表可以被改變。的數(shù)據(jù)元素，因而表可以被改變。) )6.2 6.2 靜態(tài)查找表的實(shí)現(xiàn)靜態(tài)查找表的實(shí)現(xiàn)6.2.1 6.2.1 順序表上的查找順序表上的查找 靜態(tài)查找表的順序表的類型定義如下：靜態(tài)查找表的順序表的類型定義如下：#definemaxsize靜態(tài)查找表的表長；靜態(tài)查找表的表長；typedefstructkeytypekey;/*關(guān)鍵字關(guān)鍵字*/./*其它域其它域*/rec;typedefstructrecitemmaxsize+1;intn;/*最后一個(gè)數(shù)據(jù)元素的下標(biāo)最后一個(gè)數(shù)據(jù)元素的下標(biāo)*/sqtable;靜態(tài)查找表中的數(shù)據(jù)元素存放在上述數(shù)組靜態(tài)查找表中的數(shù)據(jù)元素存放在上述

7、數(shù)組的第的第1 1到第到第n n個(gè)單元，第個(gè)單元，第n+1n+1到最后一個(gè)單元為到最后一個(gè)單元為備用區(qū)。不同的是，這里多說明了一個(gè)單元備用區(qū)。不同的是，這里多說明了一個(gè)單元即第即第0 0個(gè)單元，該單元被用于設(shè)置個(gè)單元，該單元被用于設(shè)置 崗哨崗哨 以便以便簡化查找運(yùn)算的實(shí)現(xiàn)。簡化查找運(yùn)算的實(shí)現(xiàn)。在上述存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)查找運(yùn)算的一種直在上述存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)查找運(yùn)算的一種直觀方法是觀方法是 順序查找法順序查找法 ：從表的第：從表的第n n個(gè)位置開個(gè)位置開始，從后往前依次將各個(gè)位置上的數(shù)據(jù)元素始，從后往前依次將各個(gè)位置上的數(shù)據(jù)元素的鍵值與給定值的鍵值與給定值K K比較。若某個(gè)位置上的數(shù)據(jù)比較。若某個(gè)位置上

8、的數(shù)據(jù)元素的鍵值與元素的鍵值與K K相等則查找成功，回送該位置相等則查找成功，回送該位置作為結(jié)果；若所有數(shù)據(jù)元素的鍵值均與作為結(jié)果；若所有數(shù)據(jù)元素的鍵值均與K K不等，不等，回送回送0,0,標(biāo)記查找不成功。標(biāo)記查找不成功。 順序查找算法順序查找算法intsearch-sqtable(sqtableR,keytypeK)R.item0.key=K;/*設(shè)置崗哨設(shè)置崗哨*/i=R.n;/*設(shè)置比較位置初值設(shè)置比較位置初值*/While(R.itemi.key!=K)i-;/*未找到時(shí)修改比較位置繼續(xù)查找未找到時(shí)修改比較位置繼續(xù)查找*/return(i);18714 18 21 23 29 31 3

9、5 38 42 46 49 52012345678910 11 12 13R.nk=18順序查找算法順序查找算法(順序表采用普通數(shù)組形式順序表采用普通數(shù)組形式)intsearch-sqtable(intitem,intn,intk)inti;item0=k;/*在數(shù)組的低端設(shè)置監(jiān)視哨在數(shù)組的低端設(shè)置監(jiān)視哨*/While(itemi!=k)i-;/*從后往前找從后往前找*/returni;/*找不到時(shí)，找不到時(shí)，i為為0*/崗哨崗哨R.item0的作用是：保證的作用是：保證while循環(huán)一定終止循環(huán)一定終止(即使查找不成功、即即使查找不成功、即R中無鍵值等于中無鍵值等于K的數(shù)據(jù)元素，當(dāng)?shù)臄?shù)據(jù)元素

10、，當(dāng)i=0時(shí)時(shí)循環(huán)終止條件循環(huán)終止條件被迫被迫成立成立)。因此，不。因此，不必將必將i0寫入循環(huán)條件從而使循環(huán)條寫入循環(huán)條件從而使循環(huán)條件得到簡化件得到簡化(對(duì)比第對(duì)比第2章定位算法章定位算法locate_sqlist)。有關(guān)測試表明：當(dāng)。有關(guān)測試表明：當(dāng)n1000時(shí)，進(jìn)行一次查找所花費(fèi)的時(shí)時(shí)，進(jìn)行一次查找所花費(fèi)的時(shí)間平均減少約一半。間平均減少約一半。查找運(yùn)算通常以查找運(yùn)算通常以 數(shù)據(jù)元素的鍵值與給定值的比較數(shù)據(jù)元素的鍵值與給定值的比較 作為標(biāo)準(zhǔn)操作，也就是用作為標(biāo)準(zhǔn)操作，也就是用 數(shù)據(jù)元素的鍵值與給定值數(shù)據(jù)元素的鍵值與給定值的比較次數(shù)的比較次數(shù) 來作為查找算法的時(shí)間性能。上述比較來作為查找算

11、法的時(shí)間性能。上述比較次數(shù)稱為次數(shù)稱為 查找長度查找長度 。顯然，查找長度與鍵值等于給。顯然，查找長度與鍵值等于給定值定值K K的元素在順序表中的位置有關(guān)。的元素在順序表中的位置有關(guān)。若順序表中第若順序表中第n n個(gè)元素的鍵值為個(gè)元素的鍵值為K K，則順序查找算法，則順序查找算法的查找長度為的查找長度為1 1；若第；若第1 1個(gè)元素的鍵值為個(gè)元素的鍵值為K K，則查找長，則查找長度為度為n n；若表中無鍵值等于；若表中無鍵值等于K K的元素的元素( (查找不成功查找不成功) )，則，則查找長度為查找長度為n+1n+1?？梢姴顒e很大。較合理的辦法是以?？梢姴顒e很大。較合理的辦法是以 查找成功時(shí)的

12、查找成功時(shí)的平均查找長度平均查找長度(記為記為ASL)ASL)作為查找算法作為查找算法時(shí)間性能的度量，其定義為：時(shí)間性能的度量，其定義為： n nASLASL P Pi iC Ci i i=1i=1順序查找算法的平均查找長度順序查找算法的平均查找長度ASL:查找成功：查找成功：ASL=(n+1)/2查找失敗：查找失?。篈SL=n+1可見，順序查找算法時(shí)間復(fù)雜度為可見，順序查找算法時(shí)間復(fù)雜度為O(n)6.2.2 6.2.2 有序表上的有序表上的查找查找( (二分查找二分查找)有序表：對(duì)于任何一個(gè)順序表，若有序表：對(duì)于任何一個(gè)順序表，若其中的所有數(shù)據(jù)元素按鍵值的某種次其中的所有數(shù)據(jù)元素按鍵值的某種

13、次序序( (升序或降序升序或降序) )排列，則稱為有序表。排列，則稱為有序表。由于有序表中所有元素按鍵值遞增的次序排由于有序表中所有元素按鍵值遞增的次序排列，若將表中任一元素的鍵值列，若將表中任一元素的鍵值R.itemi.keyR.itemi.key與與給定值給定值K K比較，可根據(jù)三種比較結(jié)果區(qū)分出三種比較，可根據(jù)三種比較結(jié)果區(qū)分出三種情況：情況：R.itemi.key=KR.itemi.key=K，查找成功，查找成功，R.itemiR.itemi即為待查元素；即為待查元素；R.itemi.keyKR.itemi.keyK，說明待查元素若在表中，說明待查元素若在表中，則一定排在則一定排在R.

14、itemiR.itemi之前；之前；R.itemi.keyKR.itemi.keyK，說明待查元素若在表中，說明待查元素若在表中，則一定排在則一定排在R.itemiR.itemi之后。之后。因此，在一次比較之后，若沿未找到待查元因此，在一次比較之后，若沿未找到待查元素，則可根據(jù)比較結(jié)果縮小進(jìn)一步查找的區(qū)間。素，則可根據(jù)比較結(jié)果縮小進(jìn)一步查找的區(qū)間。二分查找法的基本思想：首先選取表二分查找法的基本思想：首先選取表中間位置的元素，將其關(guān)鍵碼與給定值進(jìn)行中間位置的元素，將其關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功；若給定值比該比較，若相等，則查找成功；若給定值比該關(guān)鍵碼小，則要找的元素一定在表的左

15、半?yún)^(qū)，關(guān)鍵碼小，則要找的元素一定在表的左半?yún)^(qū)，則繼續(xù)對(duì)左半?yún)^(qū)進(jìn)行折半查找。若給定值比則繼續(xù)對(duì)左半?yún)^(qū)進(jìn)行折半查找。若給定值比該關(guān)鍵碼大，則要找的元素一定在表的右半該關(guān)鍵碼大，則要找的元素一定在表的右半?yún)^(qū)，則繼續(xù)對(duì)右半?yún)^(qū)進(jìn)行折半查找。如此遞區(qū)，則繼續(xù)對(duì)右半?yún)^(qū)進(jìn)行折半查找。如此遞推，直到查找成功或查找區(qū)間長度為推，直到查找成功或查找區(qū)間長度為0(0(查找查找不成功不成功) )為止。為止。二分查找算法中的變量含義：二分查找算法中的變量含義：lowlow : : 查找區(qū)間的下界；查找區(qū)間的下界；highig: : 查找區(qū)間的上界；查找區(qū)間的上界；midmid=(low+hig)/2=(low+hig)/

16、2：區(qū)間的中間位置；：區(qū)間的中間位置；K K ：給定值：給定值 ( ( 如如 K=18 )K=18 )。二分查找算法如下：二分查找算法如下： int binsearch(sqtable R, keytype K)int binsearch(sqtable R, keytype K)low=1; hig=R.n; /low=1; hig=R.n; /* *置查找區(qū)間初值置查找區(qū)間初值* */ / while(low=hig) / while(low=hig) /* *區(qū)間長度不為區(qū)間長度不為0 0時(shí)繼續(xù)查找時(shí)繼續(xù)查找* */ / mid=(low+hig)/2; / mid=(low+hig)/

17、2; /* *找出區(qū)間的中間位置找出區(qū)間的中間位置* */ /switchswitch case K=R.itemmid.key: return mid case K=R.itemmid.key: return mid； case KR.itemmid.key: hig=mid-1; break;case KR.itemmid.key: low=low+1; break case kR.itemmid.key: low=low+1; break / /* *調(diào)整到右半?yún)^(qū)調(diào)整到右半?yún)^(qū)* */ / return(0); return(0); / /* *返回返回0 0，表示查找不成功，表示查找不成

18、功* */ / 15 17 18 22 35 51 60 88 930123456789hig=9low=1mid=5hig=4low=1 mid=2hig=4low=3mid=3K=18 K=18 ( (查找成功的例子查找成功的例子) )15 17 18 22 35 51 60 88 930123456789hig=9low=1mid=5hig=4low=1 mid=2hig=4low=3 mid=3K=20 K=20 ( (查找不成功的例子查找不成功的例子) )low=4hig=4 mid=4hig=3 low=4二分查找算法每進(jìn)行一次鍵值與給定值的二分查找算法每進(jìn)行一次鍵值與給定值的比較

19、，查找區(qū)間的長度至少減小為原來二分比較，查找區(qū)間的長度至少減小為原來二分之一之一(“二分查找二分查找”由此得名由此得名)。由此易推算出。由此易推算出二分查找的查找長度不超過二分查找的查找長度不超過log2n+1。二分查找的平均查找長度為：二分查找的平均查找長度為：ASLblog2(n+1)-1二分查找的時(shí)間復(fù)雜性為：二分查找的時(shí)間復(fù)雜性為：T(n)=O(log2n)由此可見，二分查找的時(shí)間性能比由此可見，二分查找的時(shí)間性能比順序查找好。但二分查找要求以有序順序查找好。但二分查找要求以有序表作為存儲(chǔ)表示。當(dāng)采用的存儲(chǔ)結(jié)構(gòu)表作為存儲(chǔ)表示。當(dāng)采用的存儲(chǔ)結(jié)構(gòu)不是順序表、或者表中元素未按鍵值不是順序表、

20、或者表中元素未按鍵值的次序的次序( (遞增或遞減遞增或遞減) )排列時(shí)，則不能排列時(shí)，則不能進(jìn)行二分查找。而順序查找則無此限進(jìn)行二分查找。而順序查找則無此限制。制。6.2.3 6.2.3 索引順序表上的查找索引順序表上的查找 索引順序表是按索引存儲(chǔ)方式構(gòu)造的一種索引順序表是按索引存儲(chǔ)方式構(gòu)造的一種存儲(chǔ)結(jié)構(gòu)。一個(gè)索引順序表由兩個(gè)部分組成：存儲(chǔ)結(jié)構(gòu)。一個(gè)索引順序表由兩個(gè)部分組成：一個(gè)順序表和一個(gè)索引表。其中的順序表在一個(gè)順序表和一個(gè)索引表。其中的順序表在組織形式上與普通的順序表完全相同；而索組織形式上與普通的順序表完全相同；而索引表本身在組織形式上也是一個(gè)順序表。索引表本身在組織形式上也是一個(gè)順序

21、表。索引順序表的特點(diǎn)表現(xiàn)為以下兩個(gè)方面引順序表的特點(diǎn)表現(xiàn)為以下兩個(gè)方面 ：順序表中的數(shù)據(jù)元素順序表中的數(shù)據(jù)元素“按塊有序按塊有序”；索引表反映了這些索引表反映了這些“塊塊”的有關(guān)特性。的有關(guān)特性。所謂所謂 按塊有序按塊有序 是指：順序表中的數(shù)據(jù)元是指：順序表中的數(shù)據(jù)元素被劃分成一些子表素被劃分成一些子表( (塊塊) )；并且對(duì)其中任意；并且對(duì)其中任意兩個(gè)相鄰表來說，排在前面的子表中的任一兩個(gè)相鄰表來說，排在前面的子表中的任一數(shù)據(jù)元素的鍵值小于排在后面的子表中的所數(shù)據(jù)元素的鍵值小于排在后面的子表中的所有數(shù)據(jù)元素的鍵值。有數(shù)據(jù)元素的鍵值。圖圖6-16-1中的順序表被分成三塊中的順序表被分成三塊:(

22、22:(22，1212，1313，8 8，9 9，20)20)，(33(33，4242，4444，3838，2424，4848，) )，(60(60，5858，7474，4747，8686，53)53)，并且，并且它們中的數(shù)據(jù)元素是按塊有序的它們中的數(shù)據(jù)元素是按塊有序的( (但每一塊但每一塊中的數(shù)據(jù)元素不要求有序中的數(shù)據(jù)元素不要求有序) )。224886171322 12 138920 33 42 44 38 24 48 60 58 74 47 86 5312345678910 11 12 13 14 15 16 17 18圖圖6-16-1 索引順序表示例索引順序表示例 索引表索引表塊內(nèi)最大鍵

23、值塊內(nèi)最大鍵值塊起始位置塊起始位置 索引順序表上的查找分兩個(gè)階段：索引順序表上的查找分兩個(gè)階段：確定待查元素所在的塊；確定待查元素所在的塊；在塊內(nèi)查找待查的元素。在塊內(nèi)查找待查的元素。以以6-16-1所示的索引順序?yàn)槔?。假如給定所示的索引順序?yàn)槔＜偃缃o定K=24K=24，應(yīng)先將應(yīng)先將K K與索引表中的各個(gè)塊內(nèi)最大鍵值比較，與索引表中的各個(gè)塊內(nèi)最大鍵值比較，得知只能在第二塊，然后在第二塊中進(jìn)行查找。得知只能在第二塊，然后在第二塊中進(jìn)行查找。第二階段只能采用順序查找法，而第一階段既第二階段只能采用順序查找法，而第一階段既可采用順序查找法，也可采取二分查找法可采用順序查找法，也可采取二分查找法(

24、(索索引表中的索引項(xiàng)按引表中的索引項(xiàng)按 塊內(nèi)最大鍵值塊內(nèi)最大鍵值 域的值有域的值有序序) )。索引順序表上的上述查找方法稱為分塊查找。索引順序表上的上述查找方法稱為分塊查找。 6.3 6.3 樹表樹表 前面所述的靜態(tài)查找表所含數(shù)據(jù)元素前面所述的靜態(tài)查找表所含數(shù)據(jù)元素(在檢索在檢索階段內(nèi)階段內(nèi))是固定不變的。而動(dòng)態(tài)查找表則不然，是固定不變的。而動(dòng)態(tài)查找表則不然，其所含數(shù)據(jù)元素可以經(jīng)插入、刪除運(yùn)算而不斷其所含數(shù)據(jù)元素可以經(jīng)插入、刪除運(yùn)算而不斷的改變。動(dòng)態(tài)查找表的這種動(dòng)態(tài)特性要求我們的改變。動(dòng)態(tài)查找表的這種動(dòng)態(tài)特性要求我們采用靈活的存儲(chǔ)表示方法來組織動(dòng)態(tài)查找表中采用靈活的存儲(chǔ)表示方法來組織動(dòng)態(tài)查找表

25、中的數(shù)據(jù)元素。的數(shù)據(jù)元素。本節(jié)介紹幾種用來表示動(dòng)態(tài)查找表的樹表本節(jié)介紹幾種用來表示動(dòng)態(tài)查找表的樹表(主主要是二叉排序樹和平衡二叉排序樹。要是二叉排序樹和平衡二叉排序樹。6.3.1 6.3.1 二叉排序樹二叉排序樹一棵一棵二叉排序樹二叉排序樹(又稱又稱二叉查找樹二叉查找樹)或者是一棵或者是一棵空樹，或者是一棵同時(shí)滿足下列條件的二叉樹：空樹，或者是一棵同時(shí)滿足下列條件的二叉樹：1若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的鍵值均小于它的根結(jié)點(diǎn)的鍵值；的鍵值均小于它的根結(jié)點(diǎn)的鍵值；2若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的鍵值均大于它的

26、根結(jié)點(diǎn)的鍵值；的鍵值均大于它的根結(jié)點(diǎn)的鍵值；3它的左、右子樹也分別為二叉排序樹。它的左、右子樹也分別為二叉排序樹。37圖圖6-26-2 二叉排序樹示例二叉排序樹示例2151632852333606563559042981067584583例如例如:是二叉排序樹。是二叉排序樹。66不不70二叉排序樹給查找運(yùn)算的實(shí)現(xiàn)提供了二叉排序樹給查找運(yùn)算的實(shí)現(xiàn)提供了便利條件：在表示一棵二叉排序樹的二便利條件：在表示一棵二叉排序樹的二叉鏈表上，要找鍵值比某結(jié)點(diǎn)叉鏈表上，要找鍵值比某結(jié)點(diǎn)X X的鍵值小的鍵值小( (大大) )的結(jié)點(diǎn)，只需通過結(jié)點(diǎn)的結(jié)點(diǎn)，只需通過結(jié)點(diǎn)X X的左指針的左指針( (右指針右指針) )到它

27、的左到它的左( (右右) )子樹中去找。子樹中去找。二叉排序樹具有下述重要性質(zhì)；中二叉排序樹具有下述重要性質(zhì)；中根遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問根遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列是鍵值的遞增有序序列。序列是鍵值的遞增有序序列。 1 1二叉排序樹上的查找二叉排序樹上的查找(1)(1)若查找樹為空，則查找失??；若查找樹為空，則查找失??；(2)(2)若查找樹非空，將若查找樹非空，將給定值與給定值與查找樹的查找樹的根結(jié)點(diǎn)關(guān)鍵碼比較；根結(jié)點(diǎn)關(guān)鍵碼比較；(3)(3)若相等，則查找成功；否則若相等，則查找成功；否則 若給定值小于根結(jié)點(diǎn)關(guān)鍵碼，則繼若給定值小于根結(jié)點(diǎn)關(guān)鍵碼，則繼續(xù)在左子樹上進(jìn)行查找；續(xù)在

28、左子樹上進(jìn)行查找； 若給定值大于根結(jié)點(diǎn)關(guān)鍵碼，則繼若給定值大于根結(jié)點(diǎn)關(guān)鍵碼，則繼續(xù)在右子樹上進(jìn)行查找。續(xù)在右子樹上進(jìn)行查找。50308020908540358832例如例如:二叉排序樹二叉排序樹查找關(guān)鍵碼查找關(guān)鍵碼=50,505035,503040355090,50809095,2 2二叉排序樹的插入二叉排序樹的插入在二叉排序樹上進(jìn)行插入的原則是：在二叉排序樹上進(jìn)行插入的原則是：(1)(1)必須保證插入一個(gè)結(jié)點(diǎn)之后仍為必須保證插入一個(gè)結(jié)點(diǎn)之后仍為一棵二叉排序樹。一棵二叉排序樹。(2)(2)僅當(dāng)二叉排序樹上不存在鍵值等僅當(dāng)二叉排序樹上不存在鍵值等于于 K K 的結(jié)點(diǎn)時(shí)才插入一個(gè)這樣的結(jié)點(diǎn)。的結(jié)點(diǎn)

29、時(shí)才插入一個(gè)這樣的結(jié)點(diǎn)。因此，插入算法必須包含查找過程；因此，插入算法必須包含查找過程；并且當(dāng)查找不成功時(shí)實(shí)施插入新結(jié)點(diǎn)的并且當(dāng)查找不成功時(shí)實(shí)施插入新結(jié)點(diǎn)的操作。操作。在動(dòng)態(tài)查找表的定義中沒有生成運(yùn)算，在動(dòng)態(tài)查找表的定義中沒有生成運(yùn)算，只有初始化運(yùn)算。這是因?yàn)閯?dòng)態(tài)查找表只有初始化運(yùn)算。這是因?yàn)閯?dòng)態(tài)查找表是從空表開始經(jīng)反復(fù)的插入是從空表開始經(jīng)反復(fù)的插入( (及刪除及刪除) )而而動(dòng)態(tài)生成的。另一方面，假如需要的話，動(dòng)態(tài)生成的。另一方面，假如需要的話，可以通過調(diào)用初始化算法和插入算法而可以通過調(diào)用初始化算法和插入算法而實(shí)現(xiàn)生成運(yùn)算。實(shí)現(xiàn)生成運(yùn)算。 63559042981067584583從空樹開始

30、建立二叉排序樹的過程從空樹開始建立二叉排序樹的過程70【例】已知關(guān)鍵碼序列為【例】已知關(guān)鍵碼序列為: : 63,90,70,55,67,42,98,83,10,45,58 63,90,70,55,67,42,98,83,10,45,58建立一棵二叉排序樹的過程建立一棵二叉排序樹的過程3 3二叉排序樹的刪除二叉排序樹的刪除 與插入相反，刪除在查找成功之后進(jìn)與插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。 可分三種情況討論：可分三種情況討論：(1)(1)被刪除的結(jié)點(diǎn)是葉子；被

31、刪除的結(jié)點(diǎn)是葉子；(2)(2)被刪除的結(jié)點(diǎn)只有左子樹或只有右子被刪除的結(jié)點(diǎn)只有左子樹或只有右子樹；樹；(3)(3)被刪除的結(jié)點(diǎn)既有左子樹，也有右子被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。樹。50308020908540358832(1)被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)例如例如:被刪關(guān)鍵碼被刪關(guān)鍵碼=2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”50308020908540358832(2)被刪除的結(jié)點(diǎn)只有左子樹只有左子樹或者只有右子樹只有右子樹其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹或右子樹指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。被

32、刪關(guān)鍵碼被刪關(guān)鍵碼=408050308020908540358832(3)被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹既有左子樹，也有右子樹4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵碼被刪關(guān)鍵碼=50可以證明，在隨機(jī)情況下，含有可以證明，在隨機(jī)情況下，含有n n個(gè)結(jié)個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長度為點(diǎn)的二叉排序樹的平均查找長度為1+4log1+4log2 2n n 其時(shí)間效率很高。同時(shí)，其它運(yùn)算如其時(shí)間效率很高。同時(shí)，其它運(yùn)算如插入和刪除亦易于實(shí)現(xiàn)。相對(duì)而言，有插入和刪除亦易于實(shí)現(xiàn)。相對(duì)而言，有序表上的二分查找效率也很高；但若在序表上的二分查

33、找效率也很高；但若在有序表上進(jìn)行插入和刪除顯然十分不便有序表上進(jìn)行插入和刪除顯然十分不便且低率。且低率。333262321232163233圖圖6-86-8 單支二叉排序樹示例單支二叉排序樹示例 二叉排序的查找效率與樹的形態(tài)有關(guān)。二叉排序的查找效率與樹的形態(tài)有關(guān)。當(dāng)二叉排序樹退化為一棵深度為當(dāng)二叉排序樹退化為一棵深度為n n的單的單支樹時(shí)，查找算法退化為順序查找，平支樹時(shí)，查找算法退化為順序查找，平均查找長度上升為均查找長度上升為(n+1)/2(n+1)/2。為了避免。為了避免出現(xiàn)這種情況，需要在二叉排序樹的動(dòng)出現(xiàn)這種情況，需要在二叉排序樹的動(dòng)態(tài)變化過程中隨時(shí)調(diào)整其形態(tài)，使之保態(tài)變化過程中隨時(shí)

34、調(diào)整其形態(tài)，使之保持持“平衡平衡”。當(dāng)二叉排序樹的形態(tài)比較。當(dāng)二叉排序樹的形態(tài)比較勻稱時(shí)，它的平均查找長度接近于勻稱時(shí)，它的平均查找長度接近于loglog2 2n n。6.3.2 6.3.2 平衡二叉排序樹平衡二叉排序樹 一棵平衡二叉排序樹一棵平衡二叉排序樹( (簡稱簡稱AVLAVL樹樹) )或或者是一棵空樹，或者是一棵任一結(jié)點(diǎn)者是一棵空樹，或者是一棵任一結(jié)點(diǎn)的左子樹與右子樹的高度至多差的左子樹與右子樹的高度至多差1 1的二的二叉排序樹。叉排序樹。 對(duì)于二叉排序樹上的任何結(jié)點(diǎn)，其平衡對(duì)于二叉排序樹上的任何結(jié)點(diǎn)，其平衡因子定義為該結(jié)點(diǎn)左子樹的高度減去該結(jié)因子定義為該結(jié)點(diǎn)左子樹的高度減去該結(jié)點(diǎn)右子

35、樹的高度。易知平衡二叉排序樹上點(diǎn)右子樹的高度。易知平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是任一結(jié)點(diǎn)的平衡因子只可能是 -1-1、0 0、1 1。反之，一棵二叉排序樹上只要有一個(gè)結(jié)點(diǎn)反之，一棵二叉排序樹上只要有一個(gè)結(jié)點(diǎn)的平衡因子不是的平衡因子不是-1-1、0 0或或1 1，則此二叉排序，則此二叉排序樹不是平衡的。樹不是平衡的。 1511112008037121-151-160320760230圖圖6-9(a)AVL樹的例子樹的例子3301521112008037021-151-260320761230圖圖6-9(b)非非AVL樹的例子樹的例子3301411306006.4 6.4 散列表散列表

36、 散列表又名哈希表散列表又名哈希表, ,因其英文單詞因其英文單詞HashHash而得名。而得名。前幾節(jié)討論的查找方法的共同特點(diǎn)是：前幾節(jié)討論的查找方法的共同特點(diǎn)是：數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵碼之間不存在數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵碼之間不存在確定的關(guān)系，查找的過程為給定值依次和確定的關(guān)系，查找的過程為給定值依次和各個(gè)關(guān)鍵碼進(jìn)行比較，查找的效率取決于各個(gè)關(guān)鍵碼進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵碼個(gè)數(shù)。理想的和給定值進(jìn)行比較的關(guān)鍵碼個(gè)數(shù)。理想的情況是依據(jù)關(guān)鍵碼直接得到其對(duì)應(yīng)的數(shù)據(jù)情況是依據(jù)關(guān)鍵碼直接得到其對(duì)應(yīng)的數(shù)據(jù)元素位置。元素位置。 散列表散列表: :按散列存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)按散列存

37、儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱為散列表。散列技術(shù)的核心是散列函數(shù)。稱為散列表。散列技術(shù)的核心是散列函數(shù)。散列函數(shù)散列函數(shù): :是一種將鍵值映射為散列表中是一種將鍵值映射為散列表中的存儲(chǔ)位置的函數(shù)。的存儲(chǔ)位置的函數(shù)。對(duì)任意給定的動(dòng)態(tài)查找表對(duì)任意給定的動(dòng)態(tài)查找表T T，如果選定了某，如果選定了某個(gè)個(gè)“理想的理想的”散列函數(shù)散列函數(shù)H H及相應(yīng)的散列表及相應(yīng)的散列表L L，則，則對(duì)對(duì)T T中的每個(gè)數(shù)據(jù)元素中的每個(gè)數(shù)據(jù)元素X X，函數(shù)值，函數(shù)值 H(X.key) H(X.key)就就是是X X在散列表在散列表L L中的存儲(chǔ)位置。插入中的存儲(chǔ)位置。插入( (或建表或建表) )時(shí)時(shí)數(shù)據(jù)元素?cái)?shù)據(jù)元素X X將被安置在

38、該位置上，并且查找將被安置在該位置上，并且查找X X時(shí)時(shí)也到該位置上去查找。也到該位置上去查找。散列地址散列地址: :由散列函數(shù)決定的數(shù)據(jù)元素在由散列函數(shù)決定的數(shù)據(jù)元素在散列表中的存儲(chǔ)位置稱為散列地址。散列表中的存儲(chǔ)位置稱為散列地址。散列的基本思想散列的基本思想: :通過由散列函數(shù)決定的通過由散列函數(shù)決定的鍵值鍵值(X.key)(X.key)與散列地址與散列地址(H(X.key)(H(X.key)之間的對(duì)之間的對(duì)應(yīng)關(guān)系來實(shí)現(xiàn)存儲(chǔ)組織和查找運(yùn)算。應(yīng)關(guān)系來實(shí)現(xiàn)存儲(chǔ)組織和查找運(yùn)算。在理想的情況下，散列函數(shù)是一個(gè)一一對(duì)應(yīng)，在理想的情況下，散列函數(shù)是一個(gè)一一對(duì)應(yīng)，即每個(gè)鍵值對(duì)應(yīng)于一個(gè)散列地址，且不同的鍵

39、即每個(gè)鍵值對(duì)應(yīng)于一個(gè)散列地址，且不同的鍵值對(duì)應(yīng)不同的散列地址。但在實(shí)際應(yīng)用中，這值對(duì)應(yīng)不同的散列地址。但在實(shí)際應(yīng)用中，這種情況很少出現(xiàn)。在大多數(shù)情況下，出現(xiàn)種情況很少出現(xiàn)。在大多數(shù)情況下，出現(xiàn)“同同義詞義詞”并發(fā)生并發(fā)生“沖突沖突”是不可避免的。是不可避免的。同義詞同義詞: :設(shè)有散列函數(shù)設(shè)有散列函數(shù)H H和鍵值和鍵值k1k1、k2k2，若，若k1k2k1k2且且H(k1)=H(k2)H(k1)=H(k2)，則稱，則稱k1k1、k2k2是是同義詞同義詞。沖突：假如動(dòng)態(tài)查找表中有兩個(gè)數(shù)據(jù)元素沖突：假如動(dòng)態(tài)查找表中有兩個(gè)數(shù)據(jù)元素X1X1、X2X2存入同一個(gè)散列表，而且它們的鍵值是存入同一個(gè)散列表，

40、而且它們的鍵值是同義詞，這種情況稱為同義詞，這種情況稱為沖突沖突。我們希望同義詞盡量少以便減少?zèng)_突。另一我們希望同義詞盡量少以便減少?zèng)_突。另一方面，由于沖突的不可避免性，又必須考慮在方面，由于沖突的不可避免性，又必須考慮在沖突發(fā)生時(shí)的處理辦法。因此，采用散列技術(shù)沖突發(fā)生時(shí)的處理辦法。因此，采用散列技術(shù)時(shí)需要考慮的兩個(gè)問題是：時(shí)需要考慮的兩個(gè)問題是：如何構(gòu)造如何構(gòu)造( (選擇選擇)均勻的均勻的 散列函數(shù)？散列函數(shù)？用什么方法解決沖突？用什么方法解決沖突？沖突：沖突： 通常關(guān)鍵碼的集合比哈希地址集合大得通常關(guān)鍵碼的集合比哈希地址集合大得多，因此經(jīng)過哈希函數(shù)變換后，可能將不多，因此經(jīng)過哈希函數(shù)變換后

41、，可能將不同的關(guān)鍵碼映射到同一個(gè)地址上，這種現(xiàn)同的關(guān)鍵碼映射到同一個(gè)地址上，這種現(xiàn)象稱為象稱為沖突沖突。 同義詞同義詞: : 映射到同一個(gè)地址上的關(guān)鍵碼稱為映射到同一個(gè)地址上的關(guān)鍵碼稱為同義同義詞詞。6.4.1 6.4.1 散列函數(shù)的構(gòu)造法散列函數(shù)的構(gòu)造法 這里介紹幾種常用的構(gòu)造方法。按這這里介紹幾種常用的構(gòu)造方法。按這些方法構(gòu)造出來的散列函數(shù)計(jì)算簡單而些方法構(gòu)造出來的散列函數(shù)計(jì)算簡單而且比較且比較 均勻均勻(即同義詞較少即同義詞較少) )。以下假。以下假定散列地址是自然數(shù)。另外假定鍵值也定散列地址是自然數(shù)。另外假定鍵值也都是自然數(shù)都是自然數(shù)( (事實(shí)上，鍵值通?？偪梢允聦?shí)上，鍵值通?？偪梢赞D(zhuǎn)

42、換為自然數(shù)轉(zhuǎn)換為自然數(shù)) )。 數(shù)字分析法數(shù)字分析法數(shù)字分析法又稱為數(shù)字選擇法數(shù)字分析法又稱為數(shù)字選擇法, ,適用適用于下述場合于下述場合: :事先知道所有可能出現(xiàn)的事先知道所有可能出現(xiàn)的鍵值鍵值, ,并且鍵值的位數(shù)比散列地址的位并且鍵值的位數(shù)比散列地址的位數(shù)多數(shù)多. .在這種情況下可以對(duì)鍵值的各位在這種情況下可以對(duì)鍵值的各位進(jìn)行分析進(jìn)行分析, ,選擇分布較均勻的若干位組選擇分布較均勻的若干位組成散列地址。成散列地址。假定已知可能出現(xiàn)的所有鍵值中的一假定已知可能出現(xiàn)的所有鍵值中的一部分如下：部分如下：0 0 10 0 1 3 3 1 1 9 9 4 4 2 2 1 10 0 1 6 1 8 3

43、 0 90 0 1 6 1 8 3 0 90 0 1 7 3 9 4 3 40 0 1 7 3 9 4 3 40 0 1 6 4 1 5 1 60 0 1 6 4 1 5 1 60 0 1 8 1 6 3 7 80 0 1 8 1 6 3 7 80 0 1 1 4 3 3 9 50 0 1 1 4 3 3 9 50 0 1 2 4 2 3 6 30 0 1 2 4 2 3 6 30 0 1 9 1 5 4 0 90 0 1 9 1 5 4 0 9 ( (左起左起) )前三位分布不均勻，第前三位分布不均勻，第5 5、7 7位亦有很多重位亦有很多重復(fù)，故應(yīng)將這五位丟棄。剩下的第復(fù)，故應(yīng)將這五位丟棄

44、。剩下的第4 4、6 6、8 8、9 9位都位都是分布較均勻的，可考慮它們或它們中的幾位組合是分布較均勻的，可考慮它們或它們中的幾位組合起來作為散列地址。起來作為散列地址。2.除余法除余法( (重點(diǎn)重點(diǎn)) ) 選擇一個(gè)適當(dāng)?shù)恼麛?shù)選擇一個(gè)適當(dāng)?shù)恼麛?shù)p，以鍵值除以，以鍵值除以p所所得的余數(shù)作為散列地址，即令散列函數(shù)得的余數(shù)作為散列地址，即令散列函數(shù)H為為H(key)keymodp這一方法的關(guān)鍵在于這一方法的關(guān)鍵在于p的選取。若選的選取。若選p為為偶數(shù)，則所得的散列函數(shù)總是將奇數(shù)鍵值映偶數(shù)，則所得的散列函數(shù)總是將奇數(shù)鍵值映射成奇數(shù)地址。偶數(shù)鍵值映射為偶數(shù)地址。射成奇數(shù)地址。偶數(shù)鍵值映射為偶數(shù)地址

45、。因而增加了沖突的機(jī)會(huì)。通常選因而增加了沖突的機(jī)會(huì)。通常選p為大于或?yàn)榇笥诨虻扔谏⒘斜砣萘康淖钚∷財(cái)?shù)。等于散列表容量的最小素?cái)?shù)。 【例】【例】 已知已知1111個(gè)元素的關(guān)鍵碼序列個(gè)元素的關(guān)鍵碼序列: : 18,27,1,20,22,6,10,13,41,15,25 18,27,1,20,22,6,10,13,41,15,25 選取關(guān)鍵碼與數(shù)據(jù)元素位置間的函數(shù)為選取關(guān)鍵碼與數(shù)據(jù)元素位置間的函數(shù)為f(key) = key mod 11f(key) = key mod 11(1) (1) 建立散列表：建立散列表：01234567891022113251527618412010(2) (2) 查找時(shí)，

46、對(duì)給定值查找時(shí)，對(duì)給定值 kx kx 通過該函數(shù)計(jì)通過該函數(shù)計(jì)算出地址，再與該地址單元中的元素進(jìn)行算出地址，再與該地址單元中的元素進(jìn)行比較，若相等，查找成功。比較，若相等，查找成功。3.平方取中法平方取中法一個(gè)數(shù)的平方的中間幾位與這個(gè)數(shù)的一個(gè)數(shù)的平方的中間幾位與這個(gè)數(shù)的每一位都有關(guān)。利用這一特點(diǎn)，平方取每一位都有關(guān)。利用這一特點(diǎn)，平方取中法以鍵值平方的中間幾位作為散列地中法以鍵值平方的中間幾位作為散列地址。這一方法計(jì)算簡單且不需要事先掌址。這一方法計(jì)算簡單且不需要事先掌握鍵值的分布情況。又因取平方中能擴(kuò)握鍵值的分布情況。又因取平方中能擴(kuò)大鍵值差別，所得散列地址比較均勻。大鍵值差別，所得散列地址

47、比較均勻。4.4.基數(shù)轉(zhuǎn)換法基數(shù)轉(zhuǎn)換法將鍵值看成另一種進(jìn)制的數(shù)再轉(zhuǎn)換成原來進(jìn)將鍵值看成另一種進(jìn)制的數(shù)再轉(zhuǎn)換成原來進(jìn)制的數(shù)，然后選其中幾位作為散列地址。例如，制的數(shù)，然后選其中幾位作為散列地址。例如，對(duì)于十進(jìn)制鍵值對(duì)于十進(jìn)制鍵值210485210485，先把它看成是十三進(jìn)，先把它看成是十三進(jìn)制的數(shù)，并轉(zhuǎn)換為十進(jìn)制數(shù)：制的數(shù)，并轉(zhuǎn)換為十進(jìn)制數(shù)：21048521048513132 213135 5+1+113134 4+0+013133 3+4+413132 2+8+813+813+87719357719351010然后從中選取幾位作為散列地址。通常要求然后從中選取幾位作為散列地址。通常要求兩個(gè)基數(shù)

48、互素，且新基數(shù)比原基數(shù)大。兩個(gè)基數(shù)互素，且新基數(shù)比原基數(shù)大。5.5.隨機(jī)數(shù)法隨機(jī)數(shù)法選擇一個(gè)隨機(jī)函數(shù)選擇一個(gè)隨機(jī)函數(shù)randomrandom，以鍵值，以鍵值在該函數(shù)下的值作為散列地址：在該函數(shù)下的值作為散列地址：H(key)= random (key)H(key)= random (key)當(dāng)各個(gè)鍵值的位數(shù)不同時(shí)采用此法當(dāng)各個(gè)鍵值的位數(shù)不同時(shí)采用此法較好。較好。6.4.2 6.4.2 動(dòng)態(tài)查找表在開散列表上的實(shí)現(xiàn)動(dòng)態(tài)查找表在開散列表上的實(shí)現(xiàn)(拉鏈法拉鏈法) 采用散列技術(shù)需考慮的第二個(gè)主要問題是如采用散列技術(shù)需考慮的第二個(gè)主要問題是如何何解決解決“沖突沖突”。而處理沖突的方法與散列表。而處理沖突的方法與散列表本身的組織形式有關(guān)。按組織形式的不同，通本身的組織形式有關(guān)。按組織形式的不同，通常有兩類散列表：開散列表與閉散列表。一旦常有兩類散列表：開散列表與閉散列表。一旦選定了散列函數(shù)和散列表的組織形式，就可以選定了散列函數(shù)和散列表的組織形式，就可以確定相應(yīng)的解決沖突的方法，進(jìn)而可以給出動(dòng)確定相應(yīng)的解決沖突的方法，進(jìn)而可以給出動(dòng)態(tài)查找表的一個(gè)具體實(shí)現(xiàn)。態(tài)查找表的一個(gè)具體實(shí)現(xiàn)。 開散列表的組織方式如下。設(shè)選定的散列函開散列表的組織方式如下。設(shè)選定的散列函數(shù)為數(shù)為H ，H的值域的值域(即散列地址的集合即散列地址的集合)為為0.n-1。設(shè)置一個(gè)設(shè)置一個(gè)地址數(shù)組地址數(shù)組pointer