計(jì)算機(jī)軟件基礎(chǔ)課件：查找技術(shù)

查找技術(shù)BasicsofComputerSoftware答辯人：XXX目錄順序查找表1折半查找2二叉排序樹3哈希查找45索引表的查找順序查找表PART1查找的概念靜態(tài)查找表動態(tài)查找表哈希表查找數(shù)據(jù)結(jié)構(gòu)：查找01020304檢索檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性刪除元素從查找表中刪去某個(gè)數(shù)據(jù)元素查詢查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中插入元素在查找表中插入一個(gè)數(shù)據(jù)元素查找的概念查找表：由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。靜態(tài)查找表動態(tài)查找表1僅作查詢和檢索操作的查找表2在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素查找表的分類：是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識（識別）一個(gè)數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以識別唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字”。若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。關(guān)鍵字查找的定義根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。若查找表中存在這樣一個(gè)記錄，則稱“查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置。查找成功否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”查找失敗查找方法評價(jià)查找速度ASL：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值對有n個(gè)記錄的表：其中：pi為查找表中第i個(gè)元素的概率

ci為找到表中第i個(gè)元素所需比較次數(shù)平均查找長度ASL占用的存儲空間算法的復(fù)雜程度

以順序表表示靜態(tài)查找表，則Search函數(shù)可用順序查找來實(shí)現(xiàn)。其順序存儲結(jié)構(gòu)定義如下：typedefstruct{ElemTypeelem[maxsize];

intlength;}SSTable;靜態(tài)表的查找回顧：順序表的查找intFind(SeqListL,ListDatax){inti=0;while(i<L.length&&L.data[i]!=x)i++;if(i<L.length)returni;elsereturn-1;}回顧：順序表的按值查找查找第n個(gè)元素：

1查找第n-1個(gè)元素：2……….查找第1個(gè)元素：

n查找第i個(gè)元素：

n+1-i查找失敗：

n+1增加監(jiān)視哨的按值查找intSearch_Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。ST.elem[0]=key;//設(shè)置“哨兵”

i=ST.length;//設(shè)置開始查詢位置while（ST.elem[i]!=key）i--;//從后往前找returni;//找不到時(shí)，i為0}//Search_Seq增加監(jiān)視哨的查找算法查找算法的平均查找長度：

對順序表而言，Ci=n-i+1

又∵在等概率查找的情況下，∴順序表查找的平均查找長度為：

順序表查找的時(shí)間復(fù)雜度為：O(n)順序查找性能分析在不等概率查找的情況下，ASLss在

Pn≥Pn-1≥……≥P2≥P1時(shí)取最小值。表中記錄可按查找概率由小到大重新排列,以提高查找效率。 若查找概率無法事先測定，則查找過程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。順序查找性能分析有序表的查找PART2

順序表的查找算法簡單，但平均查找長度較大，不適用于表長較大的查找表。 若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半。適用條件：采用順序存儲結(jié)構(gòu)的有序表。有序表的查找lowhigmid123456789101111513192137566475808892找21例如:在有序表中查找key=21的查找過程mid=(low+high)/2hig=mid-1low=mid+1折半查找midlowhig123456789101111513192137566475808892找20例如:在表中查找key=20的查找過程mid=(low+high)/2hig=mid-1low=mid+1Low>hig,查找失敗折半查找—查找失敗的情況1.設(shè)表長為n，low、hig和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn),k為給定的待查元素。

2.令mid=(low+hig)/2

讓k與mid指向的記錄比較

若k==r[mid]，查找成功

若k<r[mid]，則hig=mid-1

若k>r[mid]，則low=mid+1

3.重復(fù)2，直至low>hig時(shí)，查找失敗。折半查找的算法描述開始low?higlow=上界hig=下界K=r[mid]K<r[mid]查找成功hig=mid-1low=mid+1結(jié)束查找失敗hig=mid-1yesyesyesintSearch_Bin(SSTableST,KeyTypekval){low=1;hig=ST.length;//置區(qū)間初值

while(low<=hig){mid=(low+hig)/2;if（kval==ST.elem[mid])returnmid;//找到待查元素

elseif(kval<ST.elem[mid])hig=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

}return0;//順序表中不存在待查元素}//Search_Bin折半查找算法6391425781011判定樹：描述折半查找過程的二叉樹。有n個(gè)結(jié)點(diǎn)的判定樹的深度為

log2n+1折半查找在查找過程中進(jìn)行的比較次數(shù)最多不超過log2n+1位置1234567891011元素513192137566475808892次數(shù)34234134234折半查找算法的時(shí)間復(fù)雜度為：O(log2n)折半查找的性能分析順序表有序表表的特性無序有序存儲結(jié)構(gòu)順序或鏈?zhǔn)巾樞虿鍎h操作易于進(jìn)行需移動元素ASL的值大小順序表和有序表的比較二叉排序樹PART3動態(tài)查找表的特點(diǎn)表結(jié)構(gòu)本身是在查找過程中動態(tài)生成若表中存在其關(guān)鍵字等于給定值key的記錄,則查找成功否則插入關(guān)鍵字等于key的記錄動態(tài)查找表二叉排序樹（二叉查找樹）定義：二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：(1)若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；(2)若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;(3)它的左、右子樹也都分別是二叉排序樹。66先序序列：后序序列：中序序列：50302010252340358070908588102325203540307088859080501020232530354050708085889050308020901085403525238870二叉排序樹這是一棵二叉排序樹這不是一棵二叉排序樹有序序列typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;structBiTNode*lchild,*rchild;//左右指針

}BiTNode,*BiTree;二叉排序樹的存儲結(jié)構(gòu)以二叉鏈表形式存儲查找85查找35查找2850308020901085403525238870二叉排序樹的查找過程若二叉排序樹為空，則查找不成功；否則

1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；

2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；

3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。二叉排序樹的查找算法描述{if(T==nil)returnnil;//查找不成功elseif(T->data==key)returnT;//查找成功elseif(key<T->data)returnSearchBST(T->lchild,key);//在左子樹中查找elsereturnSearchBST(T->rchild,key);//在右子樹中查找BiTreeSearchBST(BiTreeT,KeyTypekey)}//SearchBST二叉排序樹的查找算法實(shí)現(xiàn)輸入序列3，1，2，5，4→輸入序列：1，2，3，4，5

→同一組數(shù)據(jù)，輸入順序不同，構(gòu)造的二叉排序樹不同，查找效率也不同2134535412其ASL=(1+2+3+4+5)/5=3其ASL=(1+2+3+2+3)/5=2.2輸入順序和構(gòu)建的二叉排序樹之間的關(guān)系哈希查找PART4哈希表的相關(guān)定義哈希函數(shù)的構(gòu)造方法處理沖突的方法哈希表的查找哈希表的插入哈希查找分析哈希表的查找哈希查找的概念基本思想存在的問題1哈希查找哈希查找又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程2基本思想在記錄的存儲地址和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。3存在的問題但是存儲地址和它的關(guān)鍵字之間不一定是一一對應(yīng)關(guān)系，因此一般還要進(jìn)行比較，只是盡量減少比較次數(shù)。哈希表的相關(guān)定義地址元素:357元素2:478元素4:1028元素3:1280元素1:元素1元素4元素2元素3HashFunction哈希函數(shù)圖示哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象。 可寫成，addr(ai)=H(ki)其中：ai是表中的一個(gè)元素

addr(ai)是ai的存儲地址

ki是ai的關(guān)鍵字哈希表的相關(guān)定義哈希表：根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。地址元素:357元素2:478元素4:1028元素3:1280元素1:元素1元素4元素2元素3HashFunction哈希表哈希表的相關(guān)定義哈希函數(shù)的構(gòu)造方法直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機(jī)數(shù)法

以數(shù)據(jù)元素關(guān)鍵字key本身或它的線性函數(shù)作為它的哈希地址，即：

H(key)=k

或

H(key)=a×key+b

；

(其中a,b為常數(shù))地址A1A2……A99A100年齡12……99100人數(shù)980800……495107

例如，有一個(gè)人口統(tǒng)計(jì)表，記錄了從1歲到100歲的人口數(shù)目，其中年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字本身，如圖所示：哈希函數(shù)的構(gòu)造方法：直接定址法取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法。例：構(gòu)造一個(gè)長為100的哈希表?，F(xiàn)給出其中8個(gè)關(guān)鍵字進(jìn)行分析，8個(gè)關(guān)鍵字如下：K1=61317602

K2=61326875

K3=62739628

K4=61343634K5=62706815

K6=62774638

K7=61381262

K8=61394220分析上述8個(gè)關(guān)鍵字可知，關(guān)鍵字從左到右的第1、2、3、6位取值比較集中，不宜作為哈希地址，剩余的第4、5、7、8位取值較均勻，可選取其中的兩位作為哈希地址。設(shè)選取最后兩位作為哈希地址，則這8個(gè)關(guān)鍵字的哈希地址分別為：哈希地址：2，75，28，34，15，38，62，20。哈希函數(shù)的構(gòu)造方法：數(shù)字分析法關(guān)鍵字關(guān)鍵字的平方哈希函數(shù)值1234152275622721434592449924413217073424734321410329796297哈希函數(shù)的構(gòu)造方法：平方取中法原理02方法01先取關(guān)鍵字的平方，然后根據(jù)可使用空間的大小，選取平方數(shù)中間幾位為哈希地址。通過取平方擴(kuò)大差別，平方值的中間幾位和這個(gè)數(shù)的每一位都相關(guān)，則對不同的關(guān)鍵字得到的哈希函數(shù)值不易產(chǎn)生沖突，由此產(chǎn)生的哈希地址也較為均勻。哈希函數(shù)的構(gòu)造方法：折疊法適用范圍02方法01將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和。關(guān)鍵字位數(shù)較多，而且關(guān)鍵字中每一位上數(shù)字分布大致均勻的情況。當(dāng)哈希表長為1000時(shí)，關(guān)鍵字key=110108331119891，允許的地址空間為三位十進(jìn)制數(shù)，則采用三位折疊法有：

H(key)=

1

1

0

+1

0

8+

3

3

1+1

1

9+

8

9

1

=

5

5

9（舍去進(jìn)位），例我們就可以用關(guān)鍵字做為隨機(jī)種子數(shù)，那么針對相同的關(guān)鍵字就會產(chǎn)生相同的隨機(jī)數(shù)，所以說計(jì)算機(jī)中的隨機(jī)函數(shù)都是偽隨機(jī)函數(shù)哈希函數(shù)的構(gòu)造方法：隨機(jī)數(shù)法主要原因02方法01選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即H(key)=random(key),其中random為隨機(jī)函數(shù)。通常用于關(guān)鍵字長度不等時(shí)采用此法。計(jì)算機(jī)中的隨機(jī)函數(shù)都是偽隨機(jī)函數(shù)，只要設(shè)定的隨機(jī)種子數(shù)相同，會產(chǎn)生相同的隨機(jī)數(shù)的設(shè)定哈希函數(shù)為:H(key)=keyMODp(p≤m)其中：m為表長；p為不大于m的素?cái)?shù)，或是不含20以下的質(zhì)因子，稱為模除留余數(shù)法不僅可以對關(guān)鍵字直接取模，也可以在折疊、平方取中等運(yùn)算后取模。理論研究表明，除留余數(shù)法的模p取不大于表長且最接近表長m的素?cái)?shù)時(shí)效果最好。哈希函數(shù)的構(gòu)造方法：除留余數(shù)法給定一組關(guān)鍵字為:12,39,18,24,33,21若取p=9，則他們對應(yīng)的哈希函數(shù)值將為:3,3,0,6,6,3可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能若取p=11,則他們對應(yīng)的哈希函數(shù)值將為:1，6，7，2，0，10哈希函數(shù)的構(gòu)造方法：除留余數(shù)法對p加以限制？例為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。哈希查找處理沖突的方法開放地址法再哈希法鏈地址法010203處理沖突的含義為產(chǎn)生沖突的地址H（key）

求得一個(gè)地址序列：H1,H2,…,Hs1≤s≤m-1Hi=（H（key）+di

）MODm其中：i=1,2,…,s H(key)為哈希函數(shù)；m為哈希表長；di為增量序列，有下列三種取法：處理沖突的方法：開放地址法對沖突的地址序列：Hi=(H(key)+di)MODm中的增量di的三種取法：線性探測再散列二次探測再散列隨機(jī)探測再散列1di=c

i，c為常量，最簡單的情況c=12di=12,-12,22,-22,…,3di

是一組偽隨機(jī)數(shù)列：這個(gè)數(shù)列是隨機(jī)產(chǎn)生的固定數(shù)處理沖突的方法：開放地址法某哈希表表長為11，哈希函數(shù)為H(key)=keyMOD11，分別填入關(guān)鍵字為17，60，29和38的4個(gè)記錄，按三種處理沖突的方法，將它填入表中若采用：線性探測再散列，則H1=(5+1)MOD11=6有沖突H2=(5+2)MOD11=7有沖突H3=(5+3)MOD11=8不沖突若采用：二次探測再散列，則H1=(5+12)MOD11=6有沖突H2=(5-12)MOD11=4不沖突若采用：隨機(jī)探測再散列設(shè)偽隨機(jī)數(shù)序列為9，4，3……，則：H1=(5+9)MOD11=3不沖突012345678910383838（1）H(17)=17MOD11=6不沖突（2）H(60)=60MOD11=5不沖突（3）H(29)=29MOD11=7不沖突（4）H(38)=38MOD11=5有沖突601729處理沖突的方法：開放地址法舉例例012345678910給定關(guān)鍵字集合構(gòu)造哈希表{19，12，25，14，55，69，82，31}設(shè)定哈希函數(shù)為H(key)=keyMOD11，若采用線性探測再散列處理沖突1912145569821112

3

2112531

012345678910191214556982321543213212531

哈希查找表的建立和查找舉例例查找成功時(shí)的比較次數(shù)查找失敗時(shí)的比較次數(shù)

下面我們用除留余數(shù)法的線性探測再散列，對開放地址法的哈希查找做個(gè)小結(jié)：

哈希函數(shù)：H(key)=keyMODp

產(chǎn)生沖突時(shí)的地址序列：Hi=(H(key)+di)MODm，其中di=i；

元素個(gè)數(shù)：n則：計(jì)算ASL成功時(shí)，其每個(gè)元素的查找概率Pi=1/n，ci是比較次數(shù)計(jì)算ASL失敗時(shí)，其每個(gè)哈希地址的查找概率Pi=1/p，ci是從哈希地址到下一個(gè)空位置的位置個(gè)數(shù)

另外，我們前面的例子中，模值p是等于表長m的，如果表長m大于模值p時(shí)，該如何處理？請同學(xué)們考慮開放地址法的哈希查找小結(jié)將所有哈希地址相同的記錄都鏈接在同一鏈表中

關(guān)鍵字{19,01,23,14,55,68,11,82,36}哈希函數(shù)為H(key)=keyMOD70123456

1436

01

23

116819

82

55ASL成功=（1×6+2×2+3×1）/9=13/9ASL失敗=（1×4+2×1+3×1）/7=10/7處理沖突的方法：鏈地址法例141276819230123456789101112

^^^^^^^79^55^84^20^10^11^處理沖突的方法：鏈