索引顺序查找（分块查找）
索引顺序查找又叫分块查找，它是介于顺序查找和折半查找之间的一种查找方法。折半查找虽然具有很好的性能，但其前提条件是线性表顺序存储而且按照关键字排序，这一前提条件在结点数很大且表元素动态变化时难以满足。而顺序查找虽然可以解决表元素动态变化的要求，但查找效率很低。如果既要保持查找效率，又要能够满足表元素动态变化的需求，则可采用索引顺序查找的方法。
在此查找方法中，除查找表外还需要为查找表建立一个“索引表”，索引表是分段有序的。将查找表分为若干个子表，为每一个子表建立一个索引项存储在索引表中，索引项包括两项内容：关键字项和指针项。例如现有一个查找表，为其建立一个索引表，如图1所示。
图1 查找表及其索引表
在索引表中关键字项存储的是子表中的最大值，指针项存储的是子表的地址。索引顺序查找的基本思想就是：（1）首先根据给定的关键字key，在索引表中查找以确定key所在的子表；（2）然后再在子表中查找关键字为key的元素，如果找到，则查找成功；否则查找失败。
索引表是有序表，则既可进行顺序查找也可进行折半查找，以确定待查元素所在子表；而子表可能是无序的，因此只能用顺序查找。
例如给定key=59，则索引表中查找得出结果：22<key<90，因为22是第一个子表中的最大值，所以59应该是在第二个子表中。在索引项中得知，第二个子表是从地址005开始，则从此处开始顺序查找此子表，直到找到值为59的元素。查找之后发现，此子表中没有值为59的元素，则查找失败。
索引顺序查找的实现相比前面所学的几种查找算法要难一些，但理解了其查找原理，实现起来也相对容易，为了让读者更好的体会查找过程，接下来我们通过一个案例来展示索引顺序查找，具体如例1所示。
例1
1 #define _CRT_SECURE_NO_WARNINGS
2 #include <stdio.h>
3 #include <stdlib.h>
4 //索引顺序查找（分块查找）
5 struct indexBlock //定义块的结构
6 {
7 int max;
8 int start;
9 int end;
10 } indexBlock[4]; //定义索引表，里面有4个struct对象
11
12 int blockSearch(int key, int a[])
13 {
14 int i = 0;
15 int j;
16
17 while (i<3 && key>indexBlock[i].max) //确定在哪个子表中
18 i++;
19
20 if (i >= 3) //大于分的块数，则返回-1,找不到该数
21 return -1;
22
23 j = indexBlock[i].start; //j等于块范围的起始值
24
25 while (j <= indexBlock[i].end && a[j] != key) //在确定的块内进行查找
26 j++;
27
28 if (j > indexBlock[i].end) //如果大于块范围的结束值，则说明没有要查找的数，j置为-1
29 j = -1;
30
31 return j;
32 }
33
34 int main()
35 {
36 int j = -1;
37 int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; //查找表
38 printf("已知查找表:\n");
39 for (int i = 0; i < 15; i++)
40 printf("%d ", a[i]);
41
42 printf("\n");
43
44 for (int i = 0; i < 3; i++)
45 {
46 indexBlock[i].start = j + 1; //确定每个块范围的起始值
47 j = j + 1;
48
49 indexBlock[i].end = j + 3; //确定每个块范围的结束值
50 j = j + 3;
51
52 indexBlock[i].max = a[j]; //确定每个块范围中元素的最大值
53 }
54
55 printf("请输入你要查找的数：\n");
56 int key;
57 scanf("%d", &key);
58 int index = blockSearch(key, a);
59
60 if (index >= 0) {
61 printf("查找成功！你要查找的数查找表中的位置是：%d\n", index);
62 }
63 else{
64
65 printf("查找失败！你要查找的数不在查找表中。\n");
66 }
67
68 system("pause");
69 return 0;
70 }运行结果如图2所示。
图2 例1运行结果
在例1中，代码5-10行定义了一个索引表，代码44-53行确定了索引表对应的每个子表的大小及每个子表中的最大值。代码12-32行的函数就是实现的索引顺序查找的算法：代码17-18行确定要查找的关键字在哪个子表中，确定了子表后，代码第25-26行在子表中查找，如果查找到就返回其角标，如果没找到则查找失败。
隐藏目录
