数据结构分块查找的实现（代码篇）

分块查找又称索引顺序查找，是顺序查找和二分查找的一种改进方法。

分块查找要求把一个数据分成若干块，每一块里面的元素可以是无序的，但对于一个递增的数组来说，第i块的最大元素一定要小于第i+1块的所有元素，分块查找还需要一个索引表，用来限定每一块的范围，在增加、删除、查找元素时都需要用到。

分块1

分块2

分块3

首先，我们看到的索引表是10、20、30，假如现在需要查找的目标值是12，通过二分查找索引表

我们可以确定12是在分块2中

然后在分块2中顺序查找，最后得到12存在于数列中。

代码如下：

#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;

}

int main()

{

int i,j=0,k;

int a[17] = {1,4,6,10,15,12,17,16,20,13,30,28,26,29,22,25};//从小到大的16个数

int key = 12;

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]; //确定每个块范围中元素的最大值

}

k=block_search(key,a); //调用函数进行查找

if(k!=0)

{

printf("查找成功，其位置是：%d\n",k); //如果找到该数，则输出其下标

}

else

{

printf("查找失败!"); //若未找到，则输出提示信息

}

return 0;

}

文章来源：学到牛牛IT培训 www.xuedaon.com

九七分享吧所有文章来源于网络收集整理，如有侵权请联系QQ2387153712删除，如果这篇文章对你有帮助或者还不错的请给小编点个小赞(◠‿◠)，小编每天整理文章不容易(ಥ_ಥ)！！！