????????簡(jiǎn)介：查找，顧名思義，是我們處理數(shù)據(jù)時(shí)常用的操作之一。大概就是我們從表格中去搜索我們想要的東西，這個(gè)表格，就是所謂的查找表（存儲(chǔ)數(shù)據(jù)的表）。而我們?cè)趺丛O(shè)計(jì)查找，才可以讓計(jì)算機(jī)更快的去找到篩選我們所需要的信息呢，因此，關(guān)于怎么設(shè)計(jì)查找，就有了很多道道了。
????????比如，單純的掰著手指頭去算，一個(gè)一個(gè)查，這是順序查找；又比如，我知道了一個(gè)有序數(shù)據(jù)的最大最小的下標(biāo)，我直接每次看這組數(shù)據(jù)中間的值，就跟數(shù)字爆炸一樣，1和10，我猜5，猜大了，那我就從6和10中間再說他們的中間值8，這樣每次可以省一半的時(shí)間，這是折半查找；再者數(shù)據(jù)特別大，我每次查找要么挨個(gè)算，要么每次省一半，所需時(shí)間還很長(zhǎng)，這時(shí)候我們就需要分塊查找了，它用的時(shí)索引結(jié)構(gòu)。索引，也就相當(dāng)于書的目錄，我們?nèi)プx一本書想讀的內(nèi)容，首先先去目錄去找它在第幾章，隨后在在那一章的第一頁(yè)開始往下找。分塊查找就是這樣的，它顯示分成塊，每一塊的第一個(gè)下標(biāo)為該塊在索引表的標(biāo)記，分塊查找的特點(diǎn)就是，索引表中是有序的，但塊間無序的。
????????
目錄
一、順序查找
? ? ? ? 1.1簡(jiǎn)介：
?1.2代碼：
? ? ? ? 1.3實(shí)現(xiàn)
二、折半查找
? ? ? ? 2.1簡(jiǎn)介：
? ? ? ? 2.2折半思想代碼：
? ? ? ? 2.3.折半的判斷樹
三、分塊查找
? ? ? ? 3.1簡(jiǎn)介
一、順序查找
? ? ? ? 1.1簡(jiǎn)介：
順序查找，一般在線性表中進(jìn)行查找。查找對(duì)象的存儲(chǔ)結(jié)構(gòu)適用于順序表和鏈表。
線性表的順序表中，分為有序和無序兩種情況。
? ? ? ? 哨兵思想：就是在數(shù)組的開頭第一個(gè)位置，或結(jié)尾第一個(gè)位置，不存放數(shù)據(jù)，從下標(biāo)1開始存放，給每次需要對(duì)比的數(shù)據(jù)，放在哨兵位置，即下標(biāo)0處，與之對(duì)比。這樣可以避免越界。
????????無序的話，則是從頭到尾挨個(gè)遍歷因此時(shí)間復(fù)雜度為O（n）。
????????平均查找長(zhǎng)度：
???????? 查找成功：
?*???=
，前面是查找每一個(gè)數(shù)時(shí)的查找次數(shù)的總數(shù)，是個(gè)等差數(shù)列，后面乘上每個(gè)數(shù)被查找的概率，一般都是,即平分。
? ? ? ? 查找失敗：就是給數(shù)組遍歷，遍歷到數(shù)據(jù)的下一位時(shí)發(fā)現(xiàn)找不到了，所以為n+1即可。
? ? ? ? 有序的話，類似于二叉排序樹，它可以減少查找失敗時(shí)的時(shí)間，因?yàn)橛行颍?dāng)我找的值，遍歷到比前一個(gè)大，比后一個(gè)小時(shí)，那么就查找失敗了，后面不用再看了。
????????平均查找長(zhǎng)度：
? ? ? ? ? 查找成功：與無序一樣，
? ? ? ? ? ?查找失敗：（
=
,
，長(zhǎng)方形為不存在的數(shù)據(jù)范圍，查找這些范圍，就算失敗，后面就不用找了。如圖，失敗總次數(shù)為：1+2+3+3，1+2+3為等差數(shù)列，后面再加個(gè)3為結(jié)尾處無窮的情況。? ? ? ?
?1.2代碼：
這里實(shí)現(xiàn)了順序表的順序查找
主要順序查找思想：
//查找
int SeqSearch(SSTable* s,int key)
{
//哨兵處，放進(jìn)需要對(duì)比的值
s->data[0]=key;
int i;
//隨后，從表尾進(jìn)行遍歷對(duì)比
i=s->tabLen;
//不等于key的時(shí)候就一直遞減
while(s->data[i]!=key)
{
i--;
}
//如果找到了，則返回i，如果沒找到，即最后i=0，跟哨兵坐標(biāo)相等了，則失敗
return i;
}#include <stdio.h>
#include <string.h>
#include <malloc.h>
//順序查找結(jié)構(gòu)體
typedef struct
{
int *data; //動(dòng)態(tài)一維數(shù)組
int tabLen;//表長(zhǎng)度
}SSTable;//順序查找表
//初始化順序查找表
void InitSSTable(SSTable *s)
{
printf("輸入表長(zhǎng)\n");
int k;
scanf("%d",&k);
s->tabLen=k;
s->data=(int*)malloc(sizeof(int)*s->tabLen);
}
//查找
int SeqSearch(SSTable* s,int key)
{
s->data[0]=key;
int i;
i=s->tabLen;
while(s->data[i]!=key)
{
i--;
}
return i;
}
void CreatSSTable(SSTable *s)
{
printf("表長(zhǎng)為%d\n",s->tabLen);
int i=1;
printf("請(qǐng)給數(shù)組賦值\n");
while(i<s->tabLen)
{
int x;
scanf("%d",&x);
s->data[i]=x;
i++;
}
}
int main()
{
SSTable s;
InitSSTable(&s);
CreatSSTable(&s);
int pos;
int key;
printf("請(qǐng)輸入要查找的值\n");
scanf("%d",&key);
pos=BinarySearch(s,key);
if(pos!=0)
printf("%d在表中的下標(biāo)為%d\n",key,pos);
else
printf("表中沒有你要找的數(shù)據(jù)\n");
return 0;
} ? ? ? ? 1.3實(shí)現(xiàn)
????????
二、折半查找
? ? ? ? 2.1簡(jiǎn)介：
? ? ? ? 折半查找，又叫二分查找，它僅適用于有序的順序表，注意兩個(gè)特點(diǎn)：1.有序；2.順序表，進(jìn)行隨機(jī)存取操作時(shí)。折半字面意思，紙每次對(duì)折一半，就跟數(shù)字爆炸一樣，每次我猜數(shù)字都從范圍內(nèi)的中間值猜，猜大猜小，再去另一個(gè)區(qū)域去猜。
? ? ? ? 2.2折半思想代碼：
? ? 就是對(duì)有序的一維數(shù)組，進(jìn)行折半劃分。先定義兩個(gè)標(biāo)記遍歷。low和high，low在數(shù)據(jù)最左側(cè)開始，high在數(shù)據(jù)最右側(cè)，high和low為數(shù)組下標(biāo)，因此high=n-1；數(shù)組長(zhǎng)度減1.隨后進(jìn)行while循環(huán)，循環(huán)為low<=high,隨后進(jìn)入循環(huán)，開始，先給mid跟新值，mid=（low+high）/2,我們通過mid去看數(shù)組中mid處的值，與key對(duì)比，如果相等，則返回，如果小于key，說明找的mid偏小了，所以在右區(qū)域去找，此時(shí)更新low即可，low=mid+1;同理如果大于key，說明大了，更新high=mid-1；
//二分查找
int BinarySearch(SSTable s,int key)
{
int low=0;
int high=s.tabLen-1;
int mid=0;
while(low <= high)
{
printf("mid=%d\n",mid);
mid=(low+high)/2;
if(s.data[mid]==key)
return mid;
else if(s.data[mid]<key)
{
low=mid+1;
}
else
high=mid-1;
}
return 0;
} ? ? ? ? 2.3.折半的判斷樹
? ?判斷樹，顧名思義，就是一個(gè)二叉樹，通過二分法，去不斷化分成兩塊。每個(gè)結(jié)點(diǎn)為mid處的值。先后順序?yàn)椋扔涗沴ow和high的初始值，當(dāng)low<=high時(shí)，隨后進(jìn)行折半查找，先更新mid值,然后看數(shù)組mid處的值，與我們查找數(shù)對(duì)比，大或者小，進(jìn)行high或low的更新即可。注：每次更新mid時(shí)，所得的運(yùn)算結(jié)果，就是代碼思想時(shí)所得結(jié)果，即3/2=1,? 5/3=1，只保留整數(shù)位，
此外，做題的時(shí)候，要看好數(shù)據(jù)的下標(biāo)，初始化時(shí)low永遠(yuǎn)都在數(shù)據(jù)第一個(gè)位置的下標(biāo)處，high在數(shù)據(jù)最右側(cè)。
直接上圖：
樹中，每個(gè)結(jié)點(diǎn)為數(shù)組mid下標(biāo)處的數(shù)值。每次左右更新的時(shí)候，更新相應(yīng)的變量。一個(gè)變一個(gè)不變。每個(gè)結(jié)點(diǎn)下面，寫一下mid的值，方便計(jì)算下一個(gè)情況。藍(lán)色區(qū)域?yàn)槭〉膮^(qū)域。
三、分塊查找
? ? ? ? 3.1簡(jiǎn)介
? ? ? ? 分塊查找，僅適用于線性表順序存儲(chǔ)，是對(duì)順序查找和分塊查找的優(yōu)化，它有兩個(gè)表，一個(gè)查找表（正常存儲(chǔ)數(shù)據(jù)的表），一個(gè)索引表（給查找表中的數(shù)據(jù)分成n塊，包含該塊最大值，和該塊其實(shí)下標(biāo)）。分塊查找，索引表有序，查找表可以無序，即塊內(nèi)無序，塊間有序。
????????它用的是索引結(jié)構(gòu)。索引，也就相當(dāng)于書的目錄，我們?nèi)プx一本書想讀的內(nèi)容，首先先去目錄去找它在第幾章，隨后在在那一章的第一頁(yè)開始往下找。分塊查找就是這樣的，它顯示分成塊，每一塊的第一個(gè)下標(biāo)為該塊在索引表的標(biāo)記，分塊查找的特點(diǎn)就是，索引表中是有序的，但塊間無序的。
? ? ? ? 先通過對(duì)比索引表中的值，若在在某個(gè)塊之間，則通過下標(biāo)，取查找表中遍歷即可。
? 平均查找長(zhǎng)度：
? ? ? ? 索引表采用折半查找，查找表采用順序查找：折半查找相當(dāng)于樹，其樹的高度，為平均查找長(zhǎng)度不會(huì)超過樹搞，即log(n)+1即樹高的計(jì)算公式。順序查找，則是遍歷一遍。即長(zhǎng)度為n的表通過劃分為b塊，每塊為a個(gè)數(shù)據(jù)所以n=b*a;
所以總的平均查找為：
log(b)+1+
索引表采用折半查找，查找表也采用折半查找：log(b)+1+log(b)+1=log(b)+log(a)+2,其實(shí)也就是整個(gè)查找表都是有序的，直接對(duì)全部進(jìn)行二分，所以為log(n)+2;文章來源：http://www.zghlxwxcb.cn/news/detail-705055.html
查找效率最高時(shí)：即默認(rèn)n=ba時(shí)，b=a=時(shí)，索引表和查找表都時(shí)有序的，都采用二分查找，效率最高。平均查找長(zhǎng)度最小。文章來源地址http://www.zghlxwxcb.cn/news/detail-705055.html
到了這里，關(guān)于17-數(shù)據(jù)結(jié)構(gòu)-查找-（順序、折半、分塊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
