学科分类
目录
数据结构

索引顺序查找(分块查找)

索引顺序查找又叫分块查找,它是介于顺序查找和折半查找之间的一种查找方法。折半查找虽然具有很好的性能,但其前提条件是线性表顺序存储而且按照关键字排序,这一前提条件在结点数很大且表元素动态变化时难以满足。而顺序查找虽然可以解决表元素动态变化的要求,但查找效率很低。如果既要保持查找效率,又要能够满足表元素动态变化的需求,则可采用索引顺序查找的方法。

在此查找方法中,除查找表外还需要为查找表建立一个“索引表”,索引表是分段有序的。将查找表分为若干个子表,为每一个子表建立一个索引项存储在索引表中,索引项包括两项内容:关键字项和指针项。例如现有一个查找表,为其建立一个索引表,如图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行在子表中查找,如果查找到就返回其角标,如果没找到则查找失败。

点击此处
隐藏目录