第八章查找8.1查找的基本概念8.3基于樹的查找法8.2基于線性表的查找法8.4計(jì)算式查找---哈希法8.1查找的基本概念1、

列表(查找表):是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合,可由任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。2、關(guān)鍵字:數(shù)據(jù)元素中某數(shù)據(jù)項(xiàng)的值,用以標(biāo)識(識別)一個(組)數(shù)據(jù)元素(記錄)。

若關(guān)鍵字可以唯一的識別一個記錄，則稱之為“主關(guān)鍵字”；若關(guān)鍵字識別的記錄不唯一，則稱之為“次關(guān)鍵字”。3、查找

根據(jù)某個給定值,在列表中確定其關(guān)鍵字等于給定值的數(shù)據(jù)元素(記錄)的過程稱為查找。

若列表中存在待查記錄,則稱“查找成功”。查找結(jié)果給出整個記錄的信息,或指示該記錄在列表中的位置；

若列表中不存在待查紀(jì)錄,則稱“查找不成功”.查找結(jié)果給出“空記錄”或“空指針”。4、查找表的分類1)靜態(tài)查找表:僅作查詢和檢索操作的列表。2)動態(tài)查找表:不僅作查詢和檢索操作，還經(jīng)常進(jìn)行插入和刪除操作的列表。

在查找算法中要用到三類參量，即：①查找對象K（找什么）②查找范圍L（在哪找）③查找的結(jié)果（K在L中的位置）其中①②為輸入?yún)⒘?，在函?shù)中不可缺少；③為輸出參量，可用函數(shù)返回值表示。5、平均查找長度

為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。

對于長度為n的列表，查找成功時的平均查找長度為：nASL=P1C1+P2C2+…+PnCn

=

i=1PiCi其中：Pi為查找列表中第i個數(shù)據(jù)元素的概率，

Ci為找到列表中第i個數(shù)據(jù)元素時，已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。6、查找的基本方法：查找方法：比較式查找法計(jì)算式查找法－HASH(哈希)查找法基于線性表的查找法基于樹的查找法8.2基于線性表的查找法有順序查找、折半查找和分塊查找法三種一、順序查找法

順序查找的特點(diǎn)是：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。存儲結(jié)構(gòu)：順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)數(shù)據(jù)元素類型的定義為:typedef

struct{

keyType

key;//關(guān)鍵字域

……

//其它屬性域}

ElemType;1、順序結(jié)構(gòu)數(shù)據(jù)類型定義：假設(shè)靜態(tài)查找表的順序存儲結(jié)構(gòu)為typedef

struct{

elem[MaxSize];//數(shù)據(jù)元素存儲空間基址，建表時

//按實(shí)際長度分配，0號單元留空

int

length;//表的長度}

SSTable;ElemType順序查找過程示例：或ii假設(shè)給定值k=64,要求elem[i].key=k,問:i=?結(jié)果:i=72137881992

5

6456807513…

901234567891011

niiiiiii2、順序查找算法int

SeqSearch（SSTablel,KeyTypek）{i=l.length;while(i>=1&&l.elem[i].key!=k)i--;if(i>=1)return（i）elsereturn(0);}循環(huán)條件i>=1判斷查找是否越界。設(shè)置監(jiān)視哨的順序查找算法int

SeqSearch（SSTablel,KeyTypek）{l.elem[0].key=k;i=l.length;while(l.elem[i].key!=k)i--;return（i）;}l.r[0]為監(jiān)視哨，可以防止越界。例：2137881992

5

6456807513…

901234567891011

niik=562137881992

5

6456807513…

901234567891011

n56結(jié)果:i=8iik=6060結(jié)果:i=03、順序查找的時間復(fù)雜度分析?i=1PiCiASL=n

因?yàn)椋簩樞虮矶裕篊i=n-i+1在等概率查找的情況下：順序表查找成功的平均查找長度為：順序表查找不成功的平均查找長度為：

ASLus=n+1所以，順序表查找的時間復(fù)雜度為:O(n)二、折半查找法（二分搜索法）條件：要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。查找方法：由于列表是按關(guān)鍵字有序排列，所以可以基于“折半確定區(qū)間”的思想進(jìn)行查找。優(yōu)點(diǎn)：比較次數(shù)少，查找速度快;缺點(diǎn)：要求表為有序表，插入、刪除困難。1、概念例如:nk=64

的查找過程如下：lowhighmid

mid

midlow

：指示查找區(qū)間的下界high：指示查找區(qū)間的上界mid=(low+high)/2:每次比較、劃分區(qū)間的“點(diǎn)”lowhigh0123456789101105131921375664758088922、折半查找算法int

BinSrch

（SqListl,KeyTypek）{low=1;high=l.length;/*置區(qū)間初值*/while(low<=high){mid=(low+high)/2;

if(k==l.elem[mid].key)return（mid）;

/*找到待查元素*/

elseif(k<l.elem[mid].key)high=mid-1;

/*繼續(xù)在前半?yún)^(qū)間查找*/

elselow=mid+1;

/*繼續(xù)在后半?yún)^(qū)間查找*/}return(0);}先看一個具體的情況，假設(shè)：n=11判定樹i1234567891011Ci342341342343149671028115找到有序表中任一記錄的過程就是走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑，給定值進(jìn)行比較的關(guān)鍵字個數(shù)恰是該結(jié)點(diǎn)在判定樹上的層次數(shù)。ASLsuccss=(1

1+2

2+4

3+4

4)/11=33/11ASLunsucc=(4

4+8

5)/12=56/12折半查找的判定樹是唯一的。3、折半查找時間復(fù)雜度分析

一般情況,表長為n的折半查找判定樹的深度和含有n個結(jié)點(diǎn)的完全二叉樹的深度相同。假設(shè)n=2h-1并且查找概率相等則ASLbs?log2(n+1)-1

所以，折半查找的時間復(fù)雜度為:O(logn)最壞情況查找長度為二叉樹的深度：log2n+1

查找不成功時的比較次數(shù)最多也為：log2n+2當(dāng)n>50時近似為三、分塊查找法(索引順序表查找)分塊查找要將列表組織成以下索引順序結(jié)構(gòu)：★首先將列表分成若干個塊(子表),一般情況下塊的長度均勻,最后一塊可以不滿。每塊中元素任意排列(塊內(nèi)無序)，但塊與塊之間有序。★構(gòu)造一個索引表,其中每個索引項(xiàng)對應(yīng)一個塊,

記錄每塊的起始位置及每塊中的最大關(guān)鍵字

(或最小關(guān)鍵字)。索引表按關(guān)鍵字有序排列。

整個表由兩部分組成：基本塊表與索引表。例：224886

1

6

12索引表各塊最大關(guān)鍵字

各塊起始地址221213

8

9

3342382448287449…12345678910111213…

分塊查找過程1)由索引確定記錄所在的塊(折半或順序查);2)在塊內(nèi)進(jìn)行查找(順序查)。索引可以根據(jù)查找表的特點(diǎn)來構(gòu)造?？梢?

索引順序表查找的過程也是一個“縮小區(qū)間”的查找過程。

分塊查找時間復(fù)雜度分析分塊查找的平均查找長度=

查找“索引”的平均查找長度

+“塊內(nèi)”查找的平均查找長度

若n個記錄分為b塊，每塊含s個記錄，則等概率情況下,順序查找索引時：

ASL=(b+1)/2+(s+1)/2=(n/s+s)/2+1

可以證明：當(dāng)s=√n時,ASL取最小值√n+1折半查找索引時：ASL=log2(n/s+1)+s/2.8.3基于樹的查找法

一、二叉排序樹二、平衡二叉排序樹（略）

8.3.1二叉排序樹（二叉查找樹）一、定義二、查找三、插入四、刪除（略）五、性能分析一、定義：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；二叉排序樹：或者是一棵空樹，或者是具有如下特性的二叉樹：（3）左、右子樹也分別為二叉排序樹。（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；例如:是二叉排序樹。不50308020901085403525238866*中序遍歷一個二叉排序樹,可以得到一個遞增有序序列。

typedef

structnode{KeyTypekey;/*關(guān)鍵字的值*/

……

structnode*lchild,*rchild;/*左右指針*/}bstnode,*BSTree;

通常用二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)二叉排序樹的存儲結(jié)構(gòu)二、查找根據(jù)二叉排序樹的特點(diǎn)，查找過程如下：（1）k=t：則查找成功，返回根結(jié)點(diǎn)地址；（2）k<t：則進(jìn)一步查左子樹；（3）k>t：則進(jìn)一步查右子樹。

顯然這是一個遞歸過程，可用遞歸算法實(shí)現(xiàn)查找。

若二叉排序樹為空，則查找不成功；否則將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較，如果：例如:50308020908540358832二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095從上述查找過程可見：在查找過程中，生成了一條查找路徑：

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止?！檎页晒Α檎也怀晒θ?、插入1、若二叉排序樹為空樹，則s成為二叉排序樹的根；2、若二叉樹排序樹非空，則將key與二叉樹排序樹根結(jié)點(diǎn)的值t進(jìn)行比較，如果:

已知關(guān)鍵字值為Key的結(jié)點(diǎn)由指針s指示，將其插入二叉排序樹的過程為：（1）key=t：不進(jìn)行插入；（2）key<t：則將s插入左子樹；（3）key>t：則將s插入右子樹。

顯然，可以用遞歸算法實(shí)現(xiàn)插入。fT設(shè)key=48fTfT22pfTfTTTTfffp30201040352523二叉排序樹的生成給定一個元素序列，將二叉排序樹初始化為一棵空樹，然后逐個讀入元素，每讀入一個元素，就將新元素插入到當(dāng)前已生成的二叉排序樹中，直至元素序列插入完畢。例如：

元素輸入序列為：45,24,53,12,28,90,按上述算法生成的二叉排序樹的過程：空樹45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90

對同樣一組元素值，如果輸入的順序不同，所建的二叉排序樹形態(tài)也不同。241228539045如將上述關(guān)鍵字順序變?yōu)?24,53,90,12,28,45,則生成的二叉排序樹為：所以，二叉排序樹的形態(tài)完全由一個輸入序列決定，一個無序序列可以通過構(gòu)造一棵二叉排序樹而得到一個有序序列五、二叉排序樹的查找性能

對于一組相同的關(guān)鍵字序列，關(guān)鍵字插入的先后次序不同，所構(gòu)成的二叉排序樹的形態(tài)及深度也不同。二叉排序樹的平均查找長度ASL與二叉排序樹的形態(tài)有關(guān)：二叉排序樹的各分支越均衡,樹的深度越淺，其平均查找長度ASL越小。例如：452412375393(a)輸入關(guān)鍵字序列為{45,24,53,12,37,93}時的二叉排序樹12122437455393(b)輸入關(guān)鍵字序列為{12,24,37,45,53,93}時的二叉排序樹

假設(shè)每個元素的查找概率相等，則它們的平均查找長度分別是：ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6

由此可見，在二叉排序樹上進(jìn)行查找時的平均查找長度和二叉排序樹的形態(tài)有關(guān)。

若考慮把n個結(jié)點(diǎn)，按各種可能的次序插入到二叉排序樹中，則有n！棵二叉排序樹（其中有的形態(tài)相同）,可以證明，這些二叉排序樹的平均查找長度仍然是O(log2n)。已知長度為12的表：(Jan,

Feb,

Mar,

Apr,

May,

June,

July,

Aug,

Sep,

Oct,

Nov,

Dec)。例：試按表中元素的順序建立二叉排序樹，并求其在等概率情況下查找成功的平均查找長度。若對表中元素先進(jìn)行排序構(gòu)成有序表，再求在等概率情況下對此有序表進(jìn)行折半查找時查找成功的平均查找長度。Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecASLsuss=(1+2＊2+3＊3

+3＊4+2＊5+6)/12

=42/12=3.5JanFebMarAprJuneMayAugJulySepDecOctNovApr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,SepASLsuss=(1+2＊2+4＊3+5＊4)/12

=37/121234567891011123154967112812108.3.2平衡二叉排序樹

對于二叉排序樹,高度越低查找速度就越快。為此可在構(gòu)造二叉排序樹的過程中進(jìn)行樹形的優(yōu)化，即平衡化處理,使其成為平衡二叉排序樹。

樹中每個結(jié)點(diǎn)的左、右子樹深度之差的絕對值不大于1，。1、定義：平衡二叉樹(AVL樹)或是一顆空樹，或者是具有如下特性的二叉排序樹：例如：5472是平衡樹不是平衡樹547218結(jié)點(diǎn)的平衡因子：結(jié)點(diǎn)的左子樹的深度減去它的右子樹的深度。

平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是-1、0、1，否則不是平衡二叉樹。8.4計(jì)算式查找---哈希法

一、哈希表的定義二、哈希函數(shù)的構(gòu)造方法三、處理沖突的方法四、哈希表的查找五、哈希法性能分析8.4.1哈希表的定義以上討論的各種查找表的共同特點(diǎn)為：

記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系，查找的過程是“基于”比較。查找的效率取決于和給定值進(jìn)行比較的次數(shù),這類方法的平均查找長度為O(logn)---O(n)。對頻繁使用的查找表,希望ASL---〉0。能否做到？能！

只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。若以下標(biāo)為000~999的順序表表示之。如：為招收的1000名新生建立一張查找表,

其關(guān)鍵字為學(xué)號,其值的范圍為xx000~xx999(前兩位為年份)。

則查找過程可以簡單進(jìn)行：取給定學(xué)號的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。

另例：1、各年齡人口信息統(tǒng)計(jì)表；

2、解放后各年國民經(jīng)濟(jì)信息統(tǒng)計(jì)表。上述幾例的特點(diǎn)為：

記錄在表中的位置與其關(guān)鍵字之間存在一種確定的對應(yīng)關(guān)系,按此對應(yīng)關(guān)系可根據(jù)關(guān)鍵字的值尋址，從而獲得待查紀(jì)錄。這種查找表稱為哈希表，關(guān)鍵字與記錄地址間的對應(yīng)關(guān)系稱為哈希函數(shù)f(key)

。{Zi,Qi,Su,Li,Wu,Ci,He,Ye,Du}

又例：對于如下9個關(guān)鍵字設(shè)

哈希函數(shù)f(key)=

(Ord(第一個字母)-Ord('A')+1)/2

CiZiQiSuLiWuHeYeDu問題:

若需添加關(guān)鍵字Zh,怎么辦？此類問題稱為“沖突”，如何解決？

0123

4567

8

9

10

11

12

13從上述例子可見：哈希表的構(gòu)造、使用中有兩個問題有待研究：1、如何根據(jù)關(guān)鍵字集合的特點(diǎn)，選擇合適的哈希函數(shù)，使關(guān)鍵字均勻的散列到表中？2、當(dāng)不同的關(guān)鍵字所得的哈希函數(shù)值相同時，即f(k1)=f(k2),如何有效的處理這類“沖突”現(xiàn)象（碰撞），使建表、查找均能有效地進(jìn)行？

根據(jù)選定的函數(shù)H(key)

和處理沖突的方法,將一組關(guān)鍵字映象到一個有限的、連續(xù)的地址集(區(qū)間)上，并以每個關(guān)鍵字在地址集中的“映象”作為相應(yīng)記錄在表中的存儲位置，由此構(gòu)造所得的查找表稱為“哈希表”(散列表、雜湊表),所選擇的函數(shù)H(key)稱為哈希函數(shù)。哈希表的定義：

若是非數(shù)字關(guān)鍵字，則需先對其進(jìn)行數(shù)字化處理。1.

直接定址法3.平方取中法5.除留余數(shù)法4.分段疊加法6.隨機(jī)數(shù)法2.數(shù)字分析法

“好的”哈希函數(shù)應(yīng)該是“均勻”的，對數(shù)字型關(guān)鍵字，一般有下列哈希函數(shù)的構(gòu)造方法：二、構(gòu)造哈希函數(shù)的方法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key

或者

H(key)=a

key+b

其中a和b為常數(shù)(此哈希函數(shù)稱為自身函數(shù)),所得的地址集合的大小等于關(guān)鍵字集合的大小,這種哈希函數(shù)不會發(fā)生沖突。1.

直接定址法此方法僅適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。

假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體,去掉數(shù)字重復(fù)出現(xiàn)頻度很高的位,提取數(shù)字均勻分布的若干位或它們的組合作為地址。2.

數(shù)字分析法

以關(guān)鍵字平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”,平方值的中間幾位與整個關(guān)鍵字中的每一位數(shù)字都相關(guān)。

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。3.平方取中法

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。

此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多，且每一位的數(shù)字分布大致均勻。4.分段疊加法設(shè)定哈希函數(shù)為:

H(key)=keyMODp其中：p≤m

(表長)

也可對2,3,4種方法的結(jié)果取模。

這是一種簡單且適用范圍很廣的哈希函數(shù)，但要求：1、P不能取關(guān)鍵字基數(shù)的冪；

2、P應(yīng)盡可能的取質(zhì)數(shù)，或不包含小于20的質(zhì)因數(shù)的合數(shù)；

3、P應(yīng)盡可能的接近m。5.除留余數(shù)法設(shè)定哈希函數(shù)為:

H(key)=Random(key)其中，Random為偽隨機(jī)函數(shù)

通常，此方法用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。6.隨機(jī)數(shù)法

實(shí)際造表時,采用何種方法來構(gòu)造哈希函數(shù),考慮的因素有：建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài)),哈希表的大小,哈希函數(shù)計(jì)算時間和查找頻率。總的原則是:減少集聚現(xiàn)象,在關(guān)鍵字取值范圍內(nèi),使哈希函數(shù)值盡量均勻散列在函數(shù)值范圍內(nèi),從而使產(chǎn)生沖突的可能性盡量減小。為產(chǎn)生沖突的關(guān)鍵字尋找下一個哈希地址。1.開放定址法2.鏈地址法

除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”

的方法。其含義是：3.建立公共溢出區(qū)三、處理沖突的方法

為產(chǎn)生沖突的關(guān)鍵字H(key)求得一個探測地址序列(在其中逐個探測空哈希地址)：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+

di

)MODm

di

為探測增量有三種，i=1,2,…,m-1

1.開放定址法(1)線性探測再散列

di=c

i

最簡單的情況

c=1(2)平方探測再散列

di=12,-12,22,-22,…,(3)隨機(jī)探測再散列

di

是一組偽隨機(jī)數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)探測增量序列

di

的三種取法：即：產(chǎn)生的Hi

均不相同,且m-1個Hi值能覆蓋

哈希表中所有地址。則要求：

注意：增量di

應(yīng)具有“完備性”※

隨機(jī)探測時的m

和di

應(yīng)沒有公因子；※

平方探測時的表長

m

應(yīng)為形如4j+3

的素?cái)?shù)（如:7,11,19,23,…等）；※

避免二次聚集。012345678910例如哈希表長m=11，現(xiàn)有關(guān)鍵字集合：

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11

190123145568(1)采用線性探測再散列處理沖突1182361121362510123456789101901231468(2)采用二次探測再散列處理沖突55118236112121412ASL=22/9ASL=15/9設(shè)：H2(key)=(3key)MOD10+1

di=i×H2(key)190123145568118236211121214ASL=15/9012345678910(3)采用雙散列函數(shù)探測線性探測處理沖突時：ASL=雙散列探測處理沖突時：ASL=22/915/9二次探測處理沖突時：ASL=15/9本例不同的處理沖突方法的ASL為：將所有哈希地址相同的記錄都鏈接在同一鏈表中。

012345614

0136198223116855

ASL=(6×1+2×2+3)/9=13/9設(shè)哈希函數(shù)為：H(key)=keyMOD7顯然不會發(fā)生二次聚集2.鏈地址法：

按哈希函數(shù)的值域的范圍設(shè)立向量為基本表,另設(shè)立同樣大小的向量為公共溢出區(qū),將所有發(fā)生沖突的記錄都順序存放在公共溢出區(qū)中。

3.建立公共溢出區(qū)

哈希表的查找過程和造表過程一致。

對于給定值K，計(jì)算哈希地址i=H(K)若r[i]=NULL則查找不成功若r[i].key=K則查找成功否則“求下一地址Hi”，直至

r[Hi]=NULL(查找不成功)

或

r[Hi].key=K(查找成功)為止。

采用開放定址處理沖突，則查找過程為：四、哈希表的查找決定哈希表查找ASL的因素：

(1)選用的哈希函數(shù)；

(2)選用的處理沖突的方法；

(3)哈希表飽和的程度，即裝載因子α=n/m

值的大?。╪—記錄數(shù)，m—表的長度）

從查找過程得知，哈希表查找的平均查找長度實(shí)際上并不等于零。五、哈希法性能分析

一般情況下，可以認(rèn)為選用的哈希函數(shù)是“均勻”的，則在討論ASL時，可以不考慮它的因素。

因此，哈希表的ASL是處理沖突方法