物联网
您现在所在的位置:首页>企业动态>物联网

分块查找

编辑:学到牛牛IT培训    发布日期: 2022-03-10 14:42:01  

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

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

分块查找 

分块1

分块查找

分块2


分块查找

分块3

图片35.png

 

分块查找

 

首先,我们看到的索引表是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 ",k);    //如果找到该数,则输出其下标

    }

    else

    {

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

    }

    return 0;

}


免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都高新西区西芯大道4号

  • 学到牛牛在线咨询

    扫一扫,免费咨询

  • 学到牛牛公众号

    微信公众号

学一流技术,找高薪工作

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问