寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.分塊查找簡介
2.分塊查找具體實現(xiàn)
3.分塊查找代碼(C語言完整代碼)

1.分塊查找簡介

分塊查找，也叫索引順序查找，算法實現(xiàn)除了需要查找表本身之外，還需要根據(jù)查找表建立一個索引表。

例如下圖，給定一個查找表，其對應的索引表如圖所示：

查找表中共 18 個查找關鍵字，將其平均分為 3 個子表，對每個子表建立一個索引，索引中包含中兩部分內容：該 子表部分中最大的關鍵字 以及 第一個關鍵字在總表中的位置，即該子表的起始位置

建立的索引表要求按照關鍵字進行升序排序，查找表要么整體有序，要么分塊有序。 分塊有序指的是第二個子表中所有關鍵字都要大于第一個子表中的最大關鍵字，第三個子表的所有關鍵字都要大于第二個子表中 的最大關鍵字，依次類推。

塊（子表）中各關鍵字的具體順序，根據(jù)各自可能會被查找到的概率而定。如果各關鍵字被查找到的概率是相等的，那么可以隨 機存放；否則可按照被查找概率進行降序排序，以提高算法運行效率。

2.分塊查找具體實現(xiàn)

所有前期準備工作完成后，開始在此基礎上進行分塊查找。分塊查找的過程分為兩步進行：

• 確定要查找的關鍵字可能存在的具體塊（子表）；
• 在具體的塊中進行順序查找。

以上圖中的查找表為例，假設要查找關鍵字 38 的具體位置。首先將 38 依次和索引表中各最大關鍵字進行比較，因為 22 < 38 < 48，所以可以確定 38 如果存在，肯定在第二個子表中。 由于索引表中顯示第二子表的起始位置在查找表的第 7 的位置上，所以從該位置開始進行順序查找，一直查找到該子表最后一 個關鍵字（一般將查找表進行等分，具體子表個數(shù)根據(jù)實際情況而定）。結果在第 10 的位置上確定該關鍵字即為所找

3.分塊查找代碼(C語言完整代碼)

#include <stdio.h> #include <stdlib.h> struct index { //定義塊的結構int key;int start; } newIndex[3]; //定義結構體數(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};//確認模塊的起始值和最大值 for (i=0; i<3; i++) { newIndex[i].start = j+1; //確定每個塊范圍的起始值j += 6;for (int k=newIndex[i].start; k<=j; k++) {if (newIndex[i].key<a[k]) { newIndex[i].key=a[k];}}} //對結構體按照 key 值進行排序qsort(newIndex,3, sizeof(newIndex[0]), cmp); //輸入要查詢的數(shù)，并調用函數(shù)進行查找printf("請輸入您想要查找的數(shù)：\n");scanf("%d", &key);k = search(key, a); //輸出查找的結果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) { //確定在哪個塊中，遍歷每個塊，確定 key 在哪個塊中i++;}if (i>=3) { //大于分得的塊數(shù)，則返回 0return -1;}startValue = newIndex[i].start; //startValue 等于塊范圍的起始值while (startValue <= startValue+5 && a[startValue]!=key){startValue++;}if (startValue>startValue+5) { //如果大于塊范圍的結束值，則說明沒有要查找的數(shù)return -1;}return startValue; } //運行結果： 請輸入您想要查找的數(shù)： 22 查找成功！您要找的數(shù)在數(shù)組中的位置是：7

4.分塊查找小結

分塊查找算法的運行效率受兩部分影響：查找塊的操作和塊內查找的操作。查找塊的操作可以采用順序查找，也可以采用折半查 找（更優(yōu)）；塊內查找的操作采用順序查找的方式。相比于折半查找，分塊查找時間效率上更低一些；相比于順序查找，由于在 子表中進行，比較的子表個數(shù)會不同程度的減少，所有分塊查找算法會更優(yōu)。 總體來說，分塊查找算法的效率介于順序查找和折半查找之間

本篇博客轉載C語言中文網(wǎng)

總結

以上是生活随笔為你收集整理的分块查找(完整案例与C语言完整代码实现)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。