數(shù)據(jù)結(jié)構(gòu)第14講(浙江工業(yè)大學(xué))

1MainIndexContentsSearchAlgorithmsIllustratingtheBinarySearch-Successful

-Unsuccessful

BinarySearchAlg.

HashSearchLecture14–SearchAlgorithms11.SequentialSearchAlgorithmsSearchalgorithmsstartwithatargetvalueandemploysomestrategytovisittheelementslookingforamatch.Iftargetisfound,theindexofthematchingelementbecomesthereturnvalue.23MainIndexContentsSearchAlgorithms34MainIndexContentsSearchAlgorithms

-SequentialSearchAlgorithmintseqSearch(constintarr[],intfirst,intlast,inttarget){ inti=first; while(i!=last&&arr[i]!=target) i++;

returni; } //O(n)42.BinarySearchAlgorithmsCase1. Amatchoccurs.Thesearchiscompleteand midistheindexthatlocatesthetarget. if(midValue==target) //foundmatch returnmid;

5BinarySearchAlgorithmsCase2. Thevalueoftargetislessthanmidvalueandthesearchmust continueinthelowersublist.Repositiontheindexlasttothe endofthesublist(last=mid). //searchthelowersublistif(target<midvalue)

<repositionlasttomid>

<searchsublistarr[first]…arr[mid-1]

6BinarySearchAlgorithmsCase3. Thevalueoftargetisgreaterthanmidvalueandthesearch mustcontinueintheuppersublist.Repositiontheindexfirst tothefrontofthesublist(first=mid+1).//searchuppersublistif(target>midvalue) <repositionfirsttomid+1> <searchsublistarr[mid+1]…arr[last-1]>78MainIndexContentsIllustratingtheBinarySearch

-SuccessfulSearch1. Searchfortarget=23Step1:Indicesfirst=0,last=9,mid=(0+9)/2=4.Sincetarget=23>midvalue=12,step2searchestheuppersublistwithfirst=5andlast=9.89MainIndexContentsIllustratingtheBinarySearch

-SuccessfulSearchStep2: Indicesfirst=5,last=9,mid=(5+9)/2=7.Sincetarget=23<midvalue=33,step3searchesthelowersublistwithfirst=5andlast=7. 910MainIndexContentsIllustratingtheBinarySearch

-SuccessfulSearchStep3: Indicesfirst=5,last=7,mid=(5+7)/2=6.Sincetarget=midvalue=23,amatchisfoundatindexmid=6.10IllustratingtheBinarySearch

-UnsuccessfulSearchSearchfortarget=4.Step1: Indicesfirst=0,last=9,mid=(0+9)/2=4.Sincetarget=4<midvalue=12,step2searchesthelowersublistwithfirst=0andlast=4.11IllustratingtheBinarySearch

-UnsuccessfulSearchStep2: Indicesfirst=0,last=4,mid=(0+4)/2=2.Sincetarget=4<midvalue=5,step3searchesthelowersublistwithfirst=0andlast2.12IllustratingtheBinarySearch

-UnsuccessfulSearchStep3: Indicesfirst=0,last=2,mid=(0+2)/2=1.Sincetarget=4>midvalue=3,step4shouldsearchtheuppersublistwithfirst=2andlast=2.However,sincefirst>=last,thetargetisnotinthelistandwereturnindexlast=9.1314MainIndexContentsBinarySearchAlgorithmintbinSearch(constintarr[],intfirst,intlast,inttarget){ intmid; intmidvalue; intorigLast=last;while(first<last){ mid=(first+last)/2; midvalue=arr[mid]; if(target==midvalue) returnmid;

elseif(target<midvalue) last=mid; else first=mid+1; }returnorigLast; } //O(log2n)1415MainIndexContents二分查找(或折半查找)判定樹(二叉搜索樹)125233-75516331516MainIndexContents3.散列表（Hash）散列查找：支持快速數(shù)據(jù)存儲和提取而設(shè)計(jì)的。散列方法：對數(shù)據(jù)鍵值進(jìn)行散列，即用散列函數(shù)對鍵值進(jìn)行處理，得的計(jì)算結(jié)果為該數(shù)據(jù)在散列表中的位置。（可以理解為將該數(shù)據(jù)映射到一個(gè)散列表中）散列函數(shù)：決定數(shù)據(jù)項(xiàng)i在散列表中位置的函數(shù)h，稱為散列函數(shù)。h(x)=i常用的散列函數(shù)是質(zhì)數(shù)取余法，即mod函數(shù)。

h(x)=xmodk=i其中，k一般為大于或等于數(shù)據(jù)集的質(zhì)數(shù)。16散列函數(shù)/沖突解決h(k)=kmodp，p最好是一個(gè)大素?cái)?shù)。原因：為了盡力避免沖突。一般地說，如果p的約數(shù)越多，沖突的幾率就越大。簡單的證明：假設(shè)p是一個(gè)有較多約數(shù)的數(shù)，同時(shí)在數(shù)據(jù)中存在q滿足gcd(p,q)=d>1，即有p=a*d,q=b*d,則有qmodp=q-p*[bdiva]其中[bdiva]的取值范圍是[0，b]，即[bdiva]的值只有b+1種可能，而p是一個(gè)預(yù)先確定的數(shù)。因此qmodp的值就只有b+1種可能了；雖然mod運(yùn)算之后的余數(shù)仍然在[0，p-1]內(nèi)，但是它的取值僅限于[0,b]

,分布就變得不均勻了。p的約數(shù)越多，發(fā)生這種分布不均勻的情況就越頻繁，沖突幾率越高。質(zhì)數(shù)的約數(shù)最少，因此應(yīng)選用大質(zhì)數(shù)。例如：p=12=3*4,q=21=3*7qmodep=21mode12=21-12*[21/12]=21-12*[7/4]17散列函數(shù)/沖突解決在一般情況下，散列表的空間必須比數(shù)據(jù)的集合大。若散列表的空間大小為M，填入表中的結(jié)點(diǎn)數(shù)為N，則稱N/M為散列表的負(fù)載因子（loadfactor，或“裝填因子”）。若散列函數(shù)對不相等的關(guān)鍵碼計(jì)算出相同的散列地址時(shí)，稱該現(xiàn)象為沖突（collision），發(fā)生沖突的兩個(gè)關(guān)鍵碼稱為該散列函數(shù)的同義詞。采用散列技術(shù)時(shí)需要考慮的兩個(gè)首要問題是：（1）如何構(gòu)造使數(shù)據(jù)分布均勻的散列函數(shù)；（2）一旦發(fā)生沖突，用什么方法來解決；1819MainIndexContentsHashExample1920MainIndexContents1、除余法（除留余數(shù)法）除余法是最簡單的散列方法，散列函數(shù)為：h(x)＝xmodM。2、平方取中法當(dāng)不知道全部關(guān)鍵字時(shí)，可通過求關(guān)鍵碼的平方值作為散列地址。因?yàn)橐粋€(gè)數(shù)平方后中間幾位數(shù)和該數(shù)的每一位都相關(guān)，由此得到的散列地址比較隨機(jī)。3、數(shù)字分析法關(guān)鍵字中某些數(shù)字可能在某些位上分布均勻，在某些位上分布不均勻?？蛇x取其中各種符號分布均勻的若干位作為散列地址，或進(jìn)行疊加后作散列地址，如電話號碼。4、折疊法有時(shí)關(guān)鍵碼所含的位數(shù)很多，則可將關(guān)鍵碼分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和作為散列地址，這方法稱為折疊法。如處理國家標(biāo)準(zhǔn)圖書編號，ISBN9787302023685。常用的有移位疊加、間界疊加(來回折疊)：例如：0-442-20586-4,分割后為0442205864移位疊加：5864間界疊加：5864+4220+0224+04＋04100886092５、隨機(jī)數(shù)法H(key)=random(key)2021MainIndexContents散列沖突2122MainIndexContents散列沖突沖突解決技術(shù)可以分為兩類：開散列方法(openhashing，也稱為鏈地址法，separatechaining)閉散列方法(closedhashing，也稱為開地址方法，openaddressing)。這兩種方法的不同之處：開散列法把發(fā)生沖突的關(guān)鍵碼存儲在散列表主表之外，如存儲于相應(yīng)的鏈表，或桶；閉散列法（開地址法）把發(fā)生沖突的關(guān)鍵碼存儲在表中另一個(gè)槽內(nèi)。2223MainIndexContentsHashTableUsingOpenProbeAddressing

（使用閉散列方法，即開地址探測法）23ChainingwithSeparateLists

（使用開散列法，即鏈地址法）2425MainIndexContents主要探測方法1、線性探查法依次探查地址單元：d+1，d+2，......，M-1，0，1，......，d-1直到找到一個(gè)空閑地址或查找到關(guān)鍵碼為key的結(jié)點(diǎn)為止。2、二次探查法二次探查法的基本思想是：生成的后繼散列地址不是連續(xù)的，而是跳躍式的：d+1,d-1,d+4,d-4,d+9,d-9,….3、隨機(jī)探查法探查序列是散列表位置的一個(gè)隨機(jī)排列。4、雙散列探查法線性探測和二次探測都能消除基本聚集，但如果兩個(gè)關(guān)鍵碼散列到同一個(gè)基地址，那么采用這兩種方法還是得到同樣的探查序列，仍然會產(chǎn)生聚集。這是因?yàn)榫€性探查和二次探查產(chǎn)生的探查序列只是基地址的函數(shù)，而不是原來關(guān)鍵碼值的函數(shù)。這個(gè)問題稱為二級聚集(secondaryclustering)。為了避免二級聚集，應(yīng)使探查序列是原來關(guān)鍵碼值的函數(shù)，而不是基位置的函數(shù)。雙散列探查法利用第二個(gè)散列函數(shù)作為常數(shù)，每次跳過常數(shù)項(xiàng)，做線性探查。2526MainIndexContents雙散列探測方法第一次探測：h1(x)=i第二次探測：h2(x)=k于是，項(xiàng)