日韩偷拍一区二区,国产香蕉久久精品综合网,亚洲激情五月婷婷,欧美日韩国产不卡

第8章 查找

在數(shù)據(jù)處理過(guò)程中，是否能在最短時(shí)間內(nèi)查找到所需要的數(shù)據(jù)，是一個(gè)相當(dāng)值得信息從業(yè)人員關(guān)心的問(wèn)題。所謂查找(search，或搜索)指的是從數(shù)據(jù)文件中找出滿足某些條件的記錄。用以查找的條件稱為“鍵值”(key)，就如同排序所用的鍵值一樣。

例如聯(lián)系人中找某人的電話號(hào)碼，那么這個(gè)人的姓名就成為在聯(lián)系人中查找電話號(hào)碼的鍵值。通常影響查找時(shí)間長(zhǎng)短的主要因素包括算法的選擇、數(shù)據(jù)存儲(chǔ)的方式和結(jié)構(gòu)。

8-1 常見(jiàn)的查找方法

如果根據(jù)數(shù)據(jù)量的大小，可將查找分為：

1. 內(nèi)部查找：數(shù)據(jù)量較小的文件，可以一次性全部加載到內(nèi)存中進(jìn)行查找。

2. 外部查找：數(shù)據(jù)量大的文件，無(wú)法一次加載到內(nèi)存中處理，而需使用輔助存儲(chǔ)器來(lái)分次處理。

如果從另一個(gè)角度來(lái)看，查找的技巧又可分為“靜態(tài)查找”和“動(dòng)態(tài)查找”兩種。定義如下所示。

1. 靜態(tài)查找：指的是在查找過(guò)程中，查找的表格或文件的內(nèi)容不會(huì)被改動(dòng)。例如符號(hào)表的查找就是一種靜態(tài)查找。

2. 動(dòng)態(tài)查找：指的是在查找過(guò)程中，查找的表格或文件的內(nèi)容可能會(huì)被改動(dòng)，例如在樹(shù)狀結(jié)構(gòu)中所談的B-tree查找就屬于一種動(dòng)態(tài)查找。

至于查找技巧中比較常見(jiàn)的方法有順序法、二分查找法、斐波那契法、插值法、哈希法、m路查找樹(shù)、B-tree等。為了讓大家能確實(shí)掌握各種查找的技巧和基本原理，以便應(yīng)用于日后的各種領(lǐng)域，現(xiàn)將幾個(gè)主要的查找方法分述于后。

8-1-1 順序查找法

順序查找通常用于未經(jīng)組織化的文件，又稱為線性查找。查找的過(guò)程從文件及時(shí)項(xiàng)數(shù)據(jù)開(kāi)始，按序比較每個(gè)鍵值。由于順序查找法是逐項(xiàng)對(duì)比，因此只要一找到數(shù)據(jù)就可以結(jié)束數(shù)據(jù)的查找。以n項(xiàng)數(shù)據(jù)為例，使用順序查找法來(lái)查找數(shù)據(jù)時(shí)，有可能在第1項(xiàng)就找到了，在這種情形下僅需執(zhí)行一次比較操作。如果數(shù)據(jù)在第2項(xiàng)、第3項(xiàng)…第n項(xiàng)，則其需要的比較次數(shù)分別為2、3、4、…、n次。因此，在平均情況下，順序查找法，查找一項(xiàng)數(shù)據(jù)需要的平均比較次數(shù)為 (n 1)/2。

現(xiàn)在以一個(gè)例子來(lái)說(shuō)明，假設(shè)已有數(shù)列74、53、61、28、99、46、88，若要查找28，則需要比較4次；要查找74僅需比較1次；要查找88則需查找7次，這表示當(dāng)查找的數(shù)列長(zhǎng)度n很大時(shí)，利用順序查找是不太適合的，它是一種適用于小數(shù)據(jù)文件的查找方法。

另外，在最差的情況下，逐一對(duì)比后沒(méi)有找到數(shù)據(jù)，則必須花費(fèi)n次，其最壞情況下(Worst Case)的時(shí)間復(fù)雜度為O(n)。也就是說(shuō)，除非可以預(yù)知要查找的數(shù)據(jù)大概位于文件的前端，否則當(dāng)文件的數(shù)據(jù)項(xiàng)數(shù)過(guò)大時(shí)，順序查找法在查找的效率上顯然不如其他的查找法。

線性查找法的優(yōu)點(diǎn)是文件或數(shù)據(jù)事前不需要經(jīng)過(guò)任何的處理與排序，也由于它未考慮到數(shù)據(jù)的特征對(duì)于查找的影響，所以在應(yīng)用上適合于各種情況，其缺點(diǎn)則是查找的速度較慢。

順序查找法的C語(yǔ)言算法如下所示。

while (val!=-1

{

find=0;

printf("請(qǐng)輸入查找鍵值(1-150)，輸入-1離開(kāi)：");

scanf("%d",&val);

for (i=0;i

{

if(data[i]==val

{

printf("在第 %3d個(gè)位置找到鍵值 [%3d]\n",i 1,data[i]);

find ;

}

}

if(find==0 && val !=-1

printf("######沒(méi)有找到 [%3d]######\n",val);

}

8.1.1

請(qǐng)?jiān)O(shè)計(jì)一個(gè)C程序，以隨機(jī)數(shù)生成1~150之間的80個(gè)整數(shù)，然后實(shí)現(xiàn)順序查找法的過(guò)程。

請(qǐng)參考程序CH08_01.c，本范例程序的運(yùn)行結(jié)果如圖8-1所示。

圖8-1 實(shí)現(xiàn)順序查找法的范例程序的運(yùn)行結(jié)果

8-1-2 二分查找法

如果要查找的數(shù)據(jù)已經(jīng)事先排好序了，則可使用二分查找法來(lái)進(jìn)行查找。二分查找法是將數(shù)據(jù)平均分割成兩份，再比較鍵值與中間值的大小，如果鍵值小于中間值，可確定要查找的數(shù)據(jù)在前半段，否則在后半部。如此分割數(shù)次直到找到或確定不存在為止。例如，以下已排序的數(shù)列 2、3、5、8、9、11、12、16、18 ，而所要查找值為11時(shí)：

首先跟第5個(gè)數(shù)值 9 比較，如圖8-2所示。

圖8-2 先和中值比較

因?yàn)?1>9，所以和后半部的中間值 12 比較，如圖8-3所示：

圖8-3 再和后半部的中值比較

因?yàn)?11<12，所以和前半部的中間值 11比較，如圖8-4所示：

圖8-4 再和后半部的前半部中值比較

因?yàn)?11=11，表示查找到了即查找完成，如果不相等則表示沒(méi)有找到。

二分查找法的C語(yǔ)言算法如下所示。

int bin_search(int data[50],int val

{

int low,mid,high;

low=0;

high=49;

printf("查找過(guò)程中......\n");

while(low

{

mid=(low high)/2;

if(val

{

printf("%d 介于位置 %d[%3d]和中間值 %d[%3d]，找左半邊\n",val,low 1, data[low],mid 1,data[mid]);

high=mid-1;

}

else if(val>data[mid]

{

printf("%d 介于中間值位置 %d[%3d] 和 %d[%3d]，找右半邊\n",val,mid 1, data[mid],high 1,data[high]);

low=mid 1;

}

else

return mid;

}

return -1;

}

使用二分法查找要求被查找的數(shù)列事先已排好序，而且數(shù)據(jù)量不能太大，必須要能直接在內(nèi)存中執(zhí)行。此法適合用于不需增刪的靜態(tài)數(shù)據(jù)，因?yàn)槊看蔚牟檎叶紩?huì)比上一次少一半的范圍，所以最多只需要比較log2n 1或log2(n 1) 次，時(shí)間復(fù)雜度為O(log n)。

8.1.2

請(qǐng)?jiān)O(shè)計(jì)一個(gè)C程序，以隨機(jī)數(shù)生成1~150之間的80個(gè)整數(shù)，然后實(shí)現(xiàn)二分查找法的過(guò)程與步驟。

請(qǐng)參考程序CH08_02.c，本范例程序的運(yùn)行結(jié)果如圖8-5所示。

圖8-5 實(shí)現(xiàn)二分查找法的范例程序的運(yùn)行結(jié)果

8-1-3 插值查找法

插值查找法(interpolation search)又叫作插補(bǔ)查找法，是二分查找法的改進(jìn)版。它是按照數(shù)據(jù)位置的分布，利用公式預(yù)測(cè)數(shù)據(jù)所在的位置，再以二分法的方式漸漸逼近。使用插值法是假設(shè)數(shù)據(jù)平均分布在數(shù)組中，而每一項(xiàng)數(shù)據(jù)的差距相當(dāng)接近或有一定的距離比例。插值法的公式為：

Mid = low (( key - data[low] ) / ( data[high] - data[low] )) ( high - low

其中key是要查找的鍵，data[high]、data[low]是剩余待查找記錄中的較大值和最小值，假設(shè)數(shù)據(jù)項(xiàng)數(shù)為n，其插值查找法的步驟如下所示。

? 將記錄從小到大的順序給予1、2、3、…、n的編號(hào)。

? 令low=1，high=n

? 當(dāng)low

? 令Mid = low (( key - data[low] ) / ( data[high] - data[low] )) ( high - low

? 若key

? 若key=keyMid表示成功查找到鍵值的位置

? 若key>keyMid且low≠Mid 1，則令low=Mid 1

二分查找法的C語(yǔ)言算法如下所示。

int bin_search(int data[50],int val

{

int low,mid,high;

low=0;

high=49;

printf("查找過(guò)程中......\n");

while(low

{

mid=low ((val-data[low])(high-low)/(data[high]-data[low]));

/內(nèi)插法公式/

if (val==data[mid]

return mid;

else if (val < data[mid]

{

printf("%d 介于位置 %d[%3d]和中間值 %d[%3d]，找左半邊

\n",val,low 1,data[low],mid 1,data[mid]);

high=mid-1;

}

else if(val > data[mid]

{

printf("%d 介于中間值位置 %d[%3d] 和 %d[%3d]，找右半邊

\n",val,mid 1,data[mid],high 1,data[high]);

low=mid 1;

}

}

return -1;

}

一般而言，使用插值查找法要求數(shù)據(jù)需先經(jīng)過(guò)排序，這樣查找速度才能優(yōu)于順序查找法，而如果數(shù)據(jù)的分布越平均，則查找速度越快，甚至可能及時(shí)次就找到數(shù)據(jù)。此法的時(shí)間復(fù)雜度取決于數(shù)據(jù)分布的情況，平均而言優(yōu)于O(log n)。

8.1.3

請(qǐng)?jiān)O(shè)計(jì)一個(gè)C程序，以隨機(jī)數(shù)生成1~150之間的50個(gè)整數(shù)，然后實(shí)現(xiàn)插值查找法的過(guò)程與步驟。

請(qǐng)參考程序CH08_03.c，本范例程序的運(yùn)行結(jié)果如圖8-6所示。

圖8-6 實(shí)現(xiàn)插值查找法的范例程序的運(yùn)行結(jié)果

8-1-4 斐波那契查找法

斐波那契查找法(fibonacci search)又稱為Fibonacci查找法，此法和二分法一樣都是以分割范圍來(lái)進(jìn)行查找，不同的是斐波那契查找法不以對(duì)半分割而是以斐波那契級(jí)數(shù)的方式來(lái)分割。

斐波那契級(jí)數(shù)F(n)的定義如下所示。

斐波那契級(jí)數(shù)：0、1、1、2、3、5、8、13、21、34、55、89、……。也就是除了第0個(gè)和第1個(gè)元素外，級(jí)數(shù)中的每個(gè)值都是前兩個(gè)值的和。

斐波那契查找法的好處是只用到加減運(yùn)算而不需用到乘除運(yùn)算，這從計(jì)算機(jī)運(yùn)算的過(guò)程來(lái)看效率會(huì)高于前兩種查找法。在尚未介紹斐波那契查找法之前，我們先來(lái)認(rèn)識(shí)斐波那契查找樹(shù)。所謂斐波那契查找樹(shù)是以斐波那契級(jí)數(shù)的特性來(lái)建立的二叉樹(shù)，其建立的原則如下所示。

(1)斐波那契樹(shù)的左右子樹(shù)均為斐波那契樹(shù)。

(2)當(dāng)數(shù)據(jù)個(gè)數(shù)n確定，若想確定斐波那契樹(shù)的層數(shù)k值是多少，必須找到一個(gè)最小的k值，使得斐波那契層數(shù)的Fib(k 1)≥n 1。

(3)斐波那契樹(shù)的樹(shù)根一定是一個(gè)斐波那契數(shù)，且子節(jié)點(diǎn)與父節(jié)點(diǎn)差值的值為斐波那契數(shù)。

(4)當(dāng)k≥2時(shí)，斐波那契樹(shù)的樹(shù)根為Fib(k)，左子樹(shù)為 (k-1) 層斐波那契樹(shù)(其樹(shù)根為Fib(k-1))，右子樹(shù)為 (k-2) 層斐波那契樹(shù)(其樹(shù)根為Fib(k) Fib(k-2))。

(5)若n 1值不為斐波那契數(shù)的值，則可以找出存在一個(gè)m使用Fib(k 1)-m=n 1，m=Fib(k 1)-(n 1)，再按斐波那契樹(shù)的建立原則完成斐波那契樹(shù)的建立，斐波那契樹(shù)的各節(jié)點(diǎn)再減去差值m即可，并把小于1的節(jié)點(diǎn)去掉。

斐波那契樹(shù)建立過(guò)程的示意圖如圖8-7所示。

圖8-7 斐波那契樹(shù)建立過(guò)程的示意圖

也就是說(shuō)當(dāng)數(shù)據(jù)個(gè)數(shù)為n，且找到一個(gè)最小的斐波那契數(shù)Fib(k 1)使得Fib(k 1)>n 1，則Fib(k) 就是這棵斐波那契樹(shù)的樹(shù)根，而Fib(k-2) 則是與左右子樹(shù)開(kāi)始的差值，左子樹(shù)用減的；右子樹(shù)用加的。例如實(shí)際求取n=33的斐波那契樹(shù)。

由于n=33，且n 1=34為一個(gè)斐波那契樹(shù)，并知道斐波那契數(shù)列的3項(xiàng)特性。

Fib(0) = 0

Fib(1) = 1

Fib(k) = Fib(k-1) Fib(k-2

得知 Fib(0) = 0、Fib(1) = 1、Fib(2) = 1、Fib(3) = 2、Fib(4) = 3、Fib(5) = 5、Fib(6) = 8、Fib(7) = 13、Fib(8) = 21、Fib(9) = 34

從上式可得知Fib(k 1) = 34 à k = 8，建立二叉樹(shù)的樹(shù)根為Fib(8) = 21

左子樹(shù)的樹(shù)根為Fib(8-1) = Fib(7) = 13

右子樹(shù)的樹(shù)根為Fib(8) Fib(8-2) = 21 8 = 29

按此原則可以建立如圖8-8所示的斐波那契樹(shù)。

圖8-8 斐波那契樹(shù)

斐波那契查找法是以斐波那契樹(shù)來(lái)查找數(shù)據(jù)，如果數(shù)據(jù)的個(gè)數(shù)為n，而且n比某一個(gè)斐波那契數(shù)小，且滿足如下表達(dá)式。

Fib(k 1)≥n 1

此時(shí)Fib(k) 就是這棵斐波那契樹(shù)的樹(shù)根，而Fib(k-2) 則是與左右子樹(shù)開(kāi)始的差值，若要查找的鍵值為key，首先比較數(shù)組下標(biāo)Fib(k) 和鍵值key，此時(shí)可以有下列3種比較情況。

? 當(dāng)key值比較小，表示所查找的鍵值key落在1到Fib(k)-1之間，故繼續(xù)查找1到Fib(k)-1之間的數(shù)據(jù)。

? 如果鍵值與數(shù)組下標(biāo)Fib(k) 的值相等，表示成功查找到所要的數(shù)據(jù)。

? 當(dāng)key值比較大，表示所找的鍵值key落在Fib(k) 1到Fib(k 1)-1之間，故繼續(xù)查找Fib(k) 1到Fib(k 1)-1之間的數(shù)據(jù)。

斐波那契查找法的C語(yǔ)言算法如下所示。

#define MAX 20

int fib(int n

{

if(n==1 || n==0

return n;

else

return fib(n-1) fib(n-2);

}

int fib_search(int data[MAX],int SearchKey

{

int index=2;

/斐波拉契數(shù)列的查找/

while(fib(index

index ;

index--;

/ index >=2 /

/起始的斐波拉契數(shù)/

int RootNode=fib(index);

/上一個(gè)斐波拉契數(shù)/

int diff1=fib(index-1);

/上兩個(gè)斐波拉契數(shù)即diff2=fib(index-2)/

int diff2=RootNode-diff1;

RootNode--;/這個(gè)表達(dá)式是配合數(shù)組的下標(biāo)是從0開(kāi)始存儲(chǔ)數(shù)據(jù)/

while(1

{

if(SearchKey==data[RootNode]

{

return RootNode;

}

else

{

if(index==2) return MAX; /沒(méi)有找到/

if(SearchKey

{

RootNode=RootNode-diff2;/左子樹(shù)的新斐波拉契數(shù) /

int temp=diff1;

diff1=diff2;/上一個(gè)斐波拉契數(shù)/

diff2=temp-diff2;/上兩個(gè)斐波拉契數(shù)/

index=index-1;

}

else

{

if(index==3) return MAX;

RootNode=RootNode diff2;/右子樹(shù)的新斐波拉契數(shù) /

diff1=diff1-diff2;/上一個(gè)斐波拉契數(shù)/

diff2=diff2-diff1;/上兩個(gè)斐波拉契數(shù)/

index=index-2;

&nb