基本介紹
- 中文名：分塊查找
- 別名：索引順序查找
- 釋義：順序查找的一種改進方法
- 套用領域：C語言
簡介,方法描述,操作步驟,平均查找長度,
簡介
分塊查找是折半查找和順序查找的一種改進方法，折半查找雖然具有很好的性能，但其前提條件時線性表順序存儲而且按照關鍵碼排序，這一前提條件在結點樹很大且表元素動態變化時是難以滿足的。而順序查找可以解決表元素動態變化的要求，但查找效率很低。如果既要保持對線性表的查找具有較快的速度，又要能夠滿足表元素動態變化的要求，則可採用分塊查找的方法。
分塊查找的速度雖然不如折半查找算法，但比順序查找算法快得多，同時又不需要對全部節點進行排序。當節點很多且塊數很大時，對索引表可以採用折半查找，這樣能夠進一步提高查找的速度。
分塊查找由於只要求索引表是有序的，對塊內節點沒有排序要求，因此特別適合於節點動態變化的情況。當增加或減少節以及節點的關鍵碼改變時，只需將該節點調整到所在的塊即可。在空間複雜性上，分塊查找的主要代價是增加了一個輔助數組。
需要注意的是，當節點變化很頻繁時，可能會導致塊與塊之間的節點數相差很大，沒寫快具有很多節點，而另一些塊則可能只有很少節點，這將會導致查找效率的下降。
方法描述
分塊查找要求把一個大的線性表分解成若干塊，每塊中的節點可以任意存放，但塊與塊之間必須排序。假設是按關鍵碼值非遞減的，那么這種塊與塊之間必須滿足已排序要求，實際上就是對於任意的i，第i塊中的所有節點的關鍵碼值都必須小於第i+1塊中的所有節點的關鍵碼值。此外，還要建立一個索引表，把每塊中的最大關鍵碼值作為索引表的關鍵碼值，按塊的順序存放到一個輔助數組中，顯然這個輔助數組是按關鍵碼值費遞減排序的。查找時，首先在索引表中進行查找，確定要找的節點所在的塊。由於索引表是排序的，因此，對索引表的查找可以採用順序查找或折半查找；然後，在相應的塊中採用順序查找，即可找到對應的節點。
分塊查找在現實生活中也很常用。例如，一個學校有很多個班級，每個班級有幾十個學生。給定一個學生的學號，要求查找這個學生的相關資料。顯然，每個班級的學生檔案是分開存放的，沒有任何兩個班級的學生的學號是交叉重疊的，那么最好的查找方法實現確定這個學生所在的班級，然後再在這個學生所在班級的學生檔案中查找這個學生的資料。上述查找學生資料的過程，實際上就是一個典型的分塊查找。
操作步驟
step1 先選取各塊中的最大關鍵字構成一個索引表；
step2 查找分兩個部分：先對索引表進行二分查找或
順序查找，以確定待查記錄在哪一塊中；
然後，在已確定的塊中用順序法進行查找。
在C語言中：
#include <stdio.h>
struct index /*定義塊的結構*/
{
int key;
int start;
int end;
} index_table[4]; /*定義結構體數組*/
int block_search(int key, int a[]) /*自定義實現分塊查找*/
{
int i, j;
i = 1;
while (i <= 3 && key > index_table[i].key) /*確定在那個塊中*/
i++;
if (i > 3) /*大於分得的塊數，則返回0*/
return 0;
j = index_table[i].start; /*j等於塊範圍的起始值*/
while (j <= index_table[i].end && a[j] != key) /*在確定的塊內進行查找*/
j++;
if (j > index_table[i].end) /*如果大於塊範圍的結束值，則說明沒有要查找的數,j置0*/
j = 0;
return j;
}
main()
{
int i, j = 0, k, key, a[16];
printf("please input the number:\n");
for (i = 1; i < 16; i++)
scanf("%d", &a[i]); /*輸入由小到大的15個數*/
for (i = 1; i <= 3; i++)
{
index_table[i].start = j + 1; /*確定每個塊範圍的起始值*/
j = j + 1;
index_table[i].end = j + 4; /*確定每個塊範圍的結束值*/
j = j + 4;
index_table[i].key = a[j]; /*確定每個塊範圍中元素的最大值*/
}
printf("please input the number which do you want to search:\n");
scanf("%d", &key); /*輸入要查詢的數值*/
k = block_search(key, a); /*調用函式進行查找*/
if (k != 0)
printf("success.the position is :%d\n", k); /*如果找到該數，則輸出其位置*/
else
printf("no found!"); /*若未找到則輸出提示信息*/
}
平均查找長度
分塊查找的平均查找長度由兩部分組成，一個是對索引表進行查找的平均查找長度，一個是對快內節點進行查找的平均查找長度，總的平均查找長度為E(n)=+。線性表中共有n個節點，分成大小相等的b塊，每塊有s=n/b個節點。假定讀索引表也採用順序查找，只考慮查找成功的情況，並假定對每個節點的查找機率是相等的，則對每塊的查找機率是1/b，對快內每個節點的查找機率是1/s。如圖
上式實際上也給出了分塊查找算法時對全部節點如何進行分塊的原則。
