数据结构上机——分块查找

分块查找，原理上还是非常容易理解的
题目也没出幺蛾子，相比于课本代码，甚至作出了优化
课本代码给出了分块的起始位置，而它还给出了末尾位置
具体思路是：
先用二分查找，查询所在块
再在块中进行顺序查找
代码如下：

//分块查找的程序代码
#include<stdio.h>
//类型定义
typedef int keytype;
typedef struct
{
	keytype key;
	int low,high;
}index;
typedef struct
{
	keytype key;
}record;
const int recN=18;
const int idxN=3;

int blksearch(record[],index[],keytype,int);
int main()
{
	record r[recN]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53};
	index idx[idxN]={{22,0,5},{48,6,11},{86,12,17}};
	keytype key;
	int loc,i;
	printf("待查找的记录关键字表：\n");
	for(i=0;i<recN;i++)
		printf("%5d",r[i]);
	printf("\n");
	printf("输入所要查找记录的关键字：");
	scanf("%d",&key);
	loc=blksearch(r,idx,key,idxN);
	if(loc!=-1) printf("查找到，是第%d个记录。\n",loc+1);
	else printf("记录查找不到！\n");
}

//添加折半查找索引表，块内顺序查找算法
int blksearch(record r[],index idx[],keytype key,int idxN)
{
	int low,high=idxN-1,mid,i,j;
	{
		while(low<=high)
		{
			mid=(low+high)/2;
			if(idx[mid].key>=key) high=mid-1;
			else low=mid+1;
		}
		if(low<idxN)
		{
			i=idx[low].high;
			j=idx[low].low;
			while(r[i].key!=key&&i>=j)i--;
			if(i>=j)return i;
		}
		return -1;
	}
}



  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
 

文章来源: zstar.blog.csdn.net，作者：zstar-_，版权归原作者所有，如需转载，请联系作者。

原文链接：zstar.blog.csdn.net/article/details/111304950