1. 算法簡(jiǎn)介

分塊查找是折半查找和順序查找的一種改進(jìn)方法，分塊查找由于只要求索引表是有序的，對(duì)塊內(nèi)節(jié)點(diǎn)沒有排序要求，因此特別適合于節(jié)點(diǎn)動(dòng)態(tài)變化的情況，其核心有二索引表，二是分塊處理。

分塊查找要求把一個(gè)大的線性表分解成若干塊，每塊中的節(jié)點(diǎn)可以任意存放，但塊與塊之間必須排序。假設(shè)是按關(guān)鍵碼值非遞減的，那么這種塊與塊之間必須滿足已排序要求，實(shí)際上就是對(duì)于任意的i，第i塊中的所有節(jié)點(diǎn)的關(guān)鍵碼值都必須小于第i+1塊中的所有節(jié)點(diǎn)的關(guān)鍵碼值。此外，還要建立一個(gè)索引表，把每塊中的最大關(guān)鍵碼值作為索引表的關(guān)鍵碼值，按塊的順序存放到一個(gè)輔助數(shù)組中，顯然這個(gè)輔助數(shù)組是按關(guān)鍵碼值費(fèi)遞減排序的。查找時(shí)，首先在索引表中進(jìn)行查找，確定要找的節(jié)點(diǎn)所在的塊。由于索引表是排序的，因此，對(duì)索引表的查找可以采用順序查找或折半查找；然后，在相應(yīng)的塊中采用順序查找，即可找到對(duì)應(yīng)的節(jié)點(diǎn)。

2.  算法具體過程

借助一張來(lái)自互聯(lián)網(wǎng)上的圖片說(shuō)明：

假設(shè)要查找關(guān)鍵字 38 的具體位置。首先將 38 依次和索引表中各最大關(guān)鍵字進(jìn)行比較，因?yàn)?22 < 38 < 48，所以可以確定 38 如果存在，肯定在第二個(gè)子表中。

由于索引表中顯示第二子表的起始位置在查找表的第 7 的位置上，所以從該位置開始進(jìn)行順序查找，一直查找到該子表最后一個(gè)關(guān)鍵字（一般將查找表進(jìn)行等分，具體子表個(gè)數(shù)根據(jù)實(shí)際情況而定）。結(jié)果在第 10 的位置上確定該關(guān)鍵字即為所找。

3.代碼實(shí)現(xiàn)

代碼僅供參考

#include <stdio.h>
#include <stdlib.h>
 
struct index 
{ 
　　//定義塊的結(jié)構(gòu)
　　int key;
　　int start;
 
} newIndex[3];  //定義結(jié)構(gòu)體數(shù)組
int search(int key, int a[]);
 
int cmp(const void *a,const void* b)
{
　　return (*(struct index*)a).key>(*(struct index*)b).key?1:-1;
}
 
int main()
{
　　int i, j=-1, k, key;
　　int a[] = {33,42,44,38,24,48, 22,12,13,8,9,20, 60,58,74,49,86,53};
　　//確認(rèn)模塊的起始值和最大值
　　for (i=0; i<3; i++) 
　　{
　　　　newIndex[i].start = j+1; //確定每個(gè)塊范圍的起始值
　　　　j += 6;
　　　　for (int k=newIndex[i].start; k<=j; k++) 
　　　　{
　　　　　　if (newIndex[i].key<a[k]) 
　　　　　　{
　　　　　　　　newIndex[i].key = a[k];
　　　　　　}
　　　　}
　　}
　　//對(duì)結(jié)構(gòu)體按照 key 值進(jìn)行排序
　　qsort(newIndex,3, sizeof(newIndex[0]), cmp);
　　//輸入要查詢的數(shù)，并調(diào)用函數(shù)進(jìn)行查找
　　printf("請(qǐng)輸入您想要查找的數(shù)：\n");
　　scanf("%d", &key);
　　k = search(key, a);
　　//輸出查找的結(jié)果
　　if (k>0) 
　　{
　　　　printf("查找成功！您要找的數(shù)在數(shù)組中的位置是：%d\n",k+1);
　　}
　　else
　　{
　　　　printf("查找失?。∧业臄?shù)不在數(shù)組中。\n");
　　}
 
　　return 0;
}
 
int search(int key, int a[])
{
　　int i, startValue;
　　i = 0;
　　while (i<3 && key>newIndex[i].key) 
　　{ 
　　　　// 確定在哪個(gè)塊中，遍歷每個(gè)塊，確定key在哪個(gè)塊中
　　　　i++;
　　}
　　if (i>=3) 
　　{ 
　　　　//大于分得的塊數(shù)，則返回0
　　　　return -1;
　　}
　　startValue = newIndex[i].start; //startValue等于塊范圍的起始值
　　while (startValue <= startValue+5 && a[startValue]!=key)
　　{
　　　　startValue++;
　　}
　　if (startValue>startValue+5) 
　　{ 
　　　　//如果大于塊范圍的結(jié)束值，則說(shuō)明沒有要查找的數(shù)
　　　　return -1;
　　}
 
　　return startValue;
}

4. 生活映射

分塊查找在現(xiàn)實(shí)生活中也很常用。

例如，一個(gè)學(xué)校有很多個(gè)班級(jí)，每個(gè)班級(jí)有幾十個(gè)學(xué)生。給定一個(gè)學(xué)生的學(xué)號(hào)，要求查找這個(gè)學(xué)生的相關(guān)資料。顯然，每個(gè)班級(jí)的學(xué)生檔案是分開存放的，沒有任何兩個(gè)班級(jí)的學(xué)生的學(xué)號(hào)是交叉重疊的，那么最好的查找方法實(shí)現(xiàn)確定這個(gè)學(xué)生所在的班級(jí)，然后再在這個(gè)學(xué)生所在班級(jí)的學(xué)生檔案中查找這個(gè)學(xué)生的資料。上述查找學(xué)生資料的過程，實(shí)際上就是一個(gè)典型的分塊查找。