通信原理大綜合課件軟件查找

12.7查找2一、查找的概念1.定義：根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。2.7查找2.平均查找長度ASLASL(AverageSearchLength)

通常把查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)作為衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。

為什么要學(xué)習(xí)查找由于查找運算的使用頻率很高，幾乎在任何一個計算機系統(tǒng)軟件和應(yīng)用軟件中都會涉及到，所以當(dāng)問題所涉及的數(shù)據(jù)量相當(dāng)大時，查找方法的效率就顯得格外重要。32．7．1順序查找思想：對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進行記錄的關(guān)鍵字和K的比較，若相等則表示找到,若線性表中所有的元素都與K不相等,則表示查找失敗.平均查找長度為(n+1)/2intserch(intV[],intn,intx){ intk;k=0; while((k<n)&&(v[k]!=x)) k=k+1;if(k==n)k=-1; returnk;}4intSeqSearch(SeqlistR[]，KeyTypeK)

{//在順序表R[1..n]中順序查找關(guān)鍵字為K的結(jié)點，

inti；

R[0].key=K；//設(shè)置哨兵

for(i=n；R[i].key!=K;i--)；//從表后往前找

returni；

}//SeqSearch

5順序查找的優(yōu)點

算法簡單，且對表的結(jié)構(gòu)無任何要求.

適應(yīng)情況:無序表鏈?zhǔn)酱鎯樞虼鎯?/p>

順序查找的缺點

查找效率低，因此，當(dāng)n較大時不宜采用順序查找

優(yōu)缺點62．7．2折半查找方法:將x與線性表的中間項進行比較,分為三種情況:1.若中間項的值等于x,說明找到,查找結(jié)束.2.若x<中間項,則在線性表的前半部分以相同的方法查找3.若x>中間項,則在線性表的后半部分以相同的方法查找適用范圍:必須在具有順序存儲結(jié)構(gòu)的有序表中進行。思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。7(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)midlowhighlowhigh(08,14,23,37,46,55,68,79,91)midlowmidhigh(08,14,23,37,46,55,68,79,91)midlowhigh(08,14,23,37,46,55,68,79,91)midhighlow(08,14,23,37,46,55,68,79,91)midlowhigh

1234567898intSearch_Bin(intV[],intn,intx){intlow,high,mid;low=1;high=n;while(low<=high){

mid=(low+high)/2;if(v[mid]==x)returnmid;elseif(x<V[mid])high=mid-1;//在前半?yún)^(qū)間繼續(xù)查找

elselow=mid+1;}return0;}9折半查找的優(yōu)點和缺點

折半查找只適用順序存儲結(jié)構(gòu)。折半查找特別適用于那種一經(jīng)建立就很少改動、而又經(jīng)常需要查找的線性表。

鏈表上無法實現(xiàn)折半查找。

在等概率假設(shè)下，二分查找成功時的平均查找長度為：

ASLbn≈lg(n+1)-110#include<stdio.h>typedefstruct{ intno; charname[10];}Sstable;main(){ intno,j; intSearch_Bin(SstableST[],intn,intk); Sstablepp[5]={{0,"0"},{1,"王一"},{2,"王平"},{3,"劉紅"},{4,"張朋"}}; scanf("%d",&no);

j=Search_Bin(pp,4,no);

if(j!=0)printf("Thenameis:%5s",pp[j].name); elseprintf("NoNumber");}

intSearch_Bin(SstableST[],intn,intk){ intlow,high,mid;

low=1;high=n; while(low<=high) { mid=(low+high)/2; if(ST[mid].no==k)returnmid; if(k<ST[mid].no)high=mid-1; elselow=mid+1; } return0;}112.7.3分塊查找

分塊查找的基本思想

（1）首先查找索引表

索引表是有序表，可采用折半查找或順序查找，以確定待查的結(jié)點在哪一塊。

（2）然后在已確定的塊中進行順序查找

12平均查找長度ASL

表R[1..n]均分為b塊，每塊的結(jié)點個數(shù)為s；

s=n/b;b=n/s;

①以二分查找來確定塊，分塊查找成功時的平均查找長度ASLblk=ASLbn+ASLsq≈lg(b+1)-1+(s+1)/2≈lg(n/s+1)+s/2②以順序查找確定塊，分塊查找成功時的平均查找長度ASL'blk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)

分塊查找算法的效率介于順序查找和二分查找之間。13若表中有10000個結(jié)點，則把它分成100個塊，每塊中含

100個結(jié)點。用順序查找確定塊，分塊查找平均需要做多少次比較順序查找平均需做多少次比較折半查找最多需多少次比較。142.7.4散列查找1、

基本概念——哈希函數(shù)，沖突根據(jù)關(guān)鍵字的值，利用某個函數(shù)直接計算出元素所在的位置。這函數(shù)稱為“哈希函數(shù)”，能用散列技術(shù)進行查找的表稱為散列表（哈希表）。哈希表技術(shù)的主要目標(biāo)是提高查找效率。沖突是指存在多個關(guān)鍵字，能計算出相同的存儲位置。發(fā)生沖突的兩個關(guān)鍵字稱為該散列函數(shù)的同義詞.需要解決的問題:構(gòu)造好的哈希函數(shù),使沖突的現(xiàn)象越少越好.

設(shè)計有效的解決沖突的方法.152、

構(gòu)造哈希函數(shù)的常用方法

兩條標(biāo)準(zhǔn)：簡單和均勻

（1）直接定址法——取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址.H（K）=K或H（K）=A*K+B；例如：有一個從1到100歲的人口數(shù)字統(tǒng)計表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。地址0102...252627...100年齡12...252627......人數(shù)30002000...1050...............

16(2)平方取中法具體方法：先通過求關(guān)鍵字的平方值擴大相近數(shù)的差別，然后根據(jù)表長度取中間的幾位數(shù)作為散列函數(shù)值。又因為一個乘積的中間幾位數(shù)和乘數(shù)的每一位都相關(guān)，所以由此產(chǎn)生的散列地址較為均勻?！纠繉⒁唤M關(guān)鍵字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100，1002001，0012321)若取表長為1000，則可取中間的三位數(shù)作為散列地址集：(100，121，201，020，123)。intHash(intkey){//假設(shè)key是4位整數(shù)key*=key；key/=100；//先求平方值，后去掉末尾的兩位數(shù)returnkey％1000；//取中間三位數(shù)作為散列地址返回}17該方法是最為簡單常用的一種方法。該方法的關(guān)鍵是選取p。以p應(yīng)取1.1n至1.7n之間的一個素數(shù)為好。（3）除后余數(shù)法——H（K）=KMODp例:一組關(guān)鍵字為（21，14，19，58，65，32，72）

H(K)=KMOD11假定一個集合S為：

{18,75,60,43,54,90,46}

該集合共包含7個元素，為了散列存儲該集合，假定選取的散列函數(shù)為

h(K)=K%13

183、

處理沖突的方法

（1）

開放定址法設(shè)線性哈希表的長度為n,其查找過程:①計算關(guān)鍵字K的第H(K)項的內(nèi)容②檢查表中的第H(K)項的內(nèi)容若為空,將關(guān)鍵字K填入.

若不為空,則令H(K)=(H(K)+1)MODN

轉(zhuǎn)②繼續(xù)檢查.例如:{9,31,26,19,1,13,2,11,27,16,5,21}哈希函數(shù):H(K)=INT(K/3)+1

表項序號123456789101112H(K)=int(K/3)+101020509131119162627312119(2)鏈地址法鏈地址法解決沖突的方法：把具有相同散列地址的鍵值存放在同一個鏈表中，稱為同義詞鏈表。例一組關(guān)鍵字為（21，14，19，58，65，32，72）

H(K)=KMOD11∧∧∧∧∧

∧

∧012345678910216532∧19∧72∧1458∧20散列存儲的平均查找長度

∧∧∧∧∧

∧

∧012345678910216532∧19∧72∧1458∧（4*1+2*1+3*1）/7在查找每個元素概率相等的情況下，它等于每個元素的查找長度(即比較次數(shù))之和除以所有元素的個數(shù)。21例如，假定一個具有12個元素的數(shù)據(jù)表B為：

B=(18,75,60,43,54,90,46,31,