数据结构之索引查找（分块查找）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之索引查找（分块查找）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

活动地址：CSDN21天学习挑战赛

作者简介：大家好我是小唐同学(๑>؂<๑），为梦想而奋斗的小唐，让我们一起加油！！！

个人主页：小唐同学(๑>؂<๑）的博客主页

系列专栏：数据结构

博友们如果也是新手入门数据结构我希望大家可以多加练习数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里

牛客网支持ACM模式哦，刷算法题也很推荐哦！！！

下面上文章------》

刷题图示：

索引查找介绍：

索引查找的核心思想：

索引查找代码实现：

复杂度：

时间复杂度：

刷题图示：

索引查找介绍：

索引查找也称为分块查找，也是顺序查找的一种改进方法，在索引查找法中，除表本身之外还需要建立一个索引表。由分块查找可知，它要分开进行，块内元素之间无大小关系，块与块之间有大小关系（比如说：第二块中的元素肯定要比第一块中大，第三块中元素肯定要比前两块中的元素大）所以索引表是有序的，可以进行二分查找进行查找由于要有索引所以要用到结构体。

索引查找的核心思想：

准备工作：

本文索引查找是在一定条件下使用（给索引表开值为3，所以查找表中元素个数要是3的倍数），则每个块中的元素个数为n/3,则在每个块中找出块中最大值，赋值给索引表，在对索引表的关键字进行比较排序

索引查找是先找到确定的块（这个过程可以进行二分也可以进行顺序查找（下边代码实现的是顺序查找））

确定块之后在块中进行顺序查找

索引查找代码实现：

# include <stdio.h>
# include <stdlib.h>
struct Lnode
{
	int start;
	int key;
}index_table[3];
int cmp(const void *a,const void *b)
{
	return (*(struct Lnode*)a).key> (*(struct Lnode*)b).key?1:-1;
}
int fenkuai(int key,int a[],int n)//传参  给出关键字和数组  n是来确定块的大小 
{
	int i,j;
	i=0;
	while(i<3&&key>index_table[i].key)
	{
		i++;
	 } 
	 if (i>3)
	 {
	 	return 0; 
	 } 
	  j=index_table[i].start;
	   for(j=index_table[i].start;j<index_table[i].start+n/3;j++)
	   {
	   if(a[j]==key)
	   {
	   	return j;
	   }
	   }
	   return 0;
}
int main()
{
	 int i,j=0,k;
   int n;
   printf("请输入3的倍数的个数") 
   scanf("%d",&n);
    int a[n];
   for(i=0;i<n;i++)
{
scanf("%d",&a[i]);   	
} 
    int key;
    printf("请输入要查找的值"); 
    scanf("%d",&key);
    for(i=0;i<3;i++)
    {
    	index_table[i].start=j;
    	j+=n/3;
   	 	for(int k=index_table[i].start;k<=j;k++)
   	 	{
   	 	if(index_table[i].key<a[k])
			{
			index_table[i].key=a[k];	
			}	
		}
	
	}
	qsort(index_table,3,sizeof(index_table[0]),cmp);
//	printf("请输入你想查找的数");
	k= fenkuai(key,a,n);
	if(k>0)
	{
		printf("查找成功下标为： %d ",k);
	}
	else
	printf("失败"); 
	return 0; 
}

复杂度：

时间复杂度：

查找索引表时采用顺序查找：

ASL=L1+LS=（b+1）/2+（s+1）/2=(s^2+2*s+n)/2*s

对索引表进行折半查找时：

ASL=L1+LS=⌈log2(b+1)⌉+(s+1)/2文章来源地址https://www.toymoban.com/news/detail-786230.html

到了这里，关于数据结构之索引查找（分块查找）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！