第十六天、分块查找

题目 采用分块查找的方法查找有序表，有序表个数为15，要求用户输入有序表各元素，程序输出查找结果，若成功，显示出元素在有序表中的位置。
1、程序分析
    step1先选取各块中的最大关键字构成一个索引表；
    step2查找分为两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
2、程序实现

 <stdlib.h>
/*声明分块查找函数*/
int block_search(int iKey,int iArr[]);

/*定义块的结构体*/
struct index
{ int iKey; //关键字 int iStart; //起始位置 int iEnd; //结束位置
}index_table[4]; //结构体数组

/**********************************
*函数名称：block_search
*参数说明：iKey 查询的关键字
* iArr 有序数列保存的数组
*说明： 分块查找
***********************************/
int block_search(int iKey,int iArr[])
{ int i = 1,j; while((i < 4) && (iKey > index_table[i].iKey))  //确定要查找的元素在哪个块里 { i++; } if(i > 3) //当大于最大块数的时候表明没有查找到，返回0 { return 0; } else { j = index_table[i].iStart; //j为块范围的起始位置 while((j <= index_table[i].iEnd) && (iArr[j] != iKey)) { j++; } if(j > index_table[i].iEnd) //超出块的范围 { return 0; } return j; }
}

void main(void)
{ int i,j = 0,iRet,iKey,iArr[16]; printf("请输入15个有序数："); for(i = 1;i < 16;i++) scanf("%d",&iArr[i]); for(i = 0;i < 3;i++) { index_table[i].iStart = j + 1; //确定每个块范围的起始位置 j = j + 1; index_table[i].iEnd = j + 4; //确定每个块范围的结束位置 j = j + 4; index_table[i].iKey = iArr[j]; //确定每个块范围的元素最大值 } printf("请输入您要查询的数字："); scanf("%d",&iKey); iRet = block_search(iKey,iArr); if(iRet != 0) printf("查找成功，其位置是：%d\n",iRet); else printf("查找失败!\n");
}
  

 

  
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
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

3、显示结果

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

原文链接：jackcui.blog.csdn.net/article/details/51131485