分块查找算法介绍与实现

点击打开在线编译器,边学边练

1. 算法简介

分块查找是折半查找和顺序查找的一种改进方法,分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况,其核心有二索引表,二是分块处理。

分块查找要求把一个大的线性表分解成若干块,每块中的节点可以任意存放,但块与块之间必须排序。假设是按关键码值非递减的,那么这种块与块之间必须满足已排序要求,实际上就是对于任意的i,第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外,还要建立一个索引表,把每块中的最大关键码值作为索引表的关键码值,按块的顺序存放到一个辅助数组中,显然这个辅助数组是按关键码值费递减排序的。查找时,首先在索引表中进行查找,确定要找的节点所在的块。由于索引表是排序的,因此,对索引表的查找可以采用顺序查找或折半查找;然后,在相应的块中采用顺序查找,即可找到对应的节点。

 

2.  算法具体过程

借助一张来自互联网上的图片说明:

3903.png

假设要查找关键字 38 的具体位置。首先将 38 依次和索引表中各最大关键字进行比较,因为 22 < 38 < 48,所以可以确定 38 如果存在,肯定在第二个子表中。

由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上,所以从该位置开始进行顺序查找,一直查找到该子表最后一个关键字(一般将查找表进行等分,具体子表个数根据实际情况而定)。结果在第 10 的位置上确定该关键字即为所找。

 

3.代码实现

代码仅供参考

#include <stdio.h>
#include <stdlib.h>
 
struct index 
{ 
  //定义块的结构
  int key;
  int start;
 
} newIndex[3];  //定义结构体数组
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);
  //输入要查询的数,并调用函数进行查找
  printf("请输入您想要查找的数:\n");
  scanf("%d", &key);
  k = search(key, a);
  //输出查找的结果
  if (k>0) 
  {
    printf("查找成功!您要找的数在数组中的位置是:%d\n",k+1);
  }
  else
  {
    printf("查找失败!您要找的数不在数组中。\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) 
  { 
    //大于分得的块数,则返回0
    return -1;
  }
  startValue = newIndex[i].start; //startValue等于块范围的起始值
  while (startValue <= startValue+5 && a[startValue]!=key)
  {
    startValue++;
  }
  if (startValue>startValue+5) 
  { 
    //如果大于块范围的结束值,则说明没有要查找的数
    return -1;
  }
 
  return startValue;
}

4. 生活映射

分块查找在现实生活中也很常用。

例如,一个学校有很多个班级,每个班级有几十个学生。给定一个学生的学号,要求查找这个学生的相关资料。显然,每个班级的学生档案是分开存放的,没有任何两个班级的学生的学号是交叉重叠的,那么最好的查找方法实现确定这个学生所在的班级,然后再在这个学生所在班级的学生档案中查找这个学生的资料。上述查找学生资料的过程,实际上就是一个典型的分块查找。


第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记