查找结构

数据结构 › C
,
·本篇:2.7k字 大约需要: 10分钟

前言

查找概论

  • 查找表（Search Table）是由同一类型的数据元素(或记录)构成的集合
  • 关键字（Key）是数据元素中某个数据项的值
  • 若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）
  • 对于那些可以识别多个数据元素（或记录）的关键字，称为次关键字（Secondary Key）
  • 查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）

查找分类

  • 查找表按照操作方式来分有两种：静态查找表和动态查找表

  • 静态查找表（Static Search Table）：只作查找操作的查找表

    • 查询某个“特定的”数据元素是否在查找表中
    • 检索某个“特定的”数据元素和各种属性

  • 动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

  • 查找时插入数据元素

  • 查找时删除数据元素

这种面向查找操作的数据结构称为查找结构

顺序表查找

定义

  • 顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果知道最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功

顺序表查找算法

1
2
3
4
5
6
7
8
9
10
11
12
13
//a为数组，n为要查找的数组长度，key为要查找的关键字
int SequentialSearch(const int *a, int n, int key)
{
    int ans = -1;
    for(int i = 0; i < n; i++)
    {
        if(a[i] == key)
        {
            ans = i;
        }
    }
    return ans;
}

顺序表查找优化

1
2
3
4
5
6
7
8
9
10
11
int SequentialSearch1(int *a, int n, int key)
{
    int i;
    a[0] = key; // 设置a[0]为哨兵
    i = n;
    while(a[i] != key)
    {
        i--;
    }
    return i; // 返回0说明查找失败
}

比较

  • 这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大
  • “哨兵”不一定要在数组头，也可以在末端

总结

  • 时间复杂度O(n)
  • 顺序查找有很大的缺点，数据量很大时，查找效率极为低下，不过优点是这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的

有序表查找

折半查找

  • 折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常是从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 数组a从小到大排序，n为数组长度，target为要查找的目标
int BinarySearch(const int *a, int n, int target)
{
    int ans = -1; // 未找到则返回-1
    int low = 0, high = n - 1;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(a[mid] < target)
            low = mid + 1;
        else if(a[mid] > target)
            high = mid - 1;
        else
        {
            ans = mid;
            break;
        }
    }
    return ans;
}

插值查找

  • 插值查找（Interpolation Search）是根据要查找的关键字key与查找表中的最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式( key - a[low]) / (a[high] - a[low] )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int InterpolationSearch(const int *a, int n, int target)
{
    int ans = -1;
    int low = 0, high = n - 1;
    while(low <= high)
    {
        int mid = low + (high - low) * (target - a[low]) / (a[high] - a[low]);
        if(a[mid] < target)
            low = mid + 1;
        else if(a[mid] > target)
            high = mid - 1;
        else
        {
            ans = mid;
            break;
        }
    }
    return ans;
}

斐波那契查找

  • 斐波那契查找（Fibonacci Search），它是利用了黄金分割原理来实现的
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
#define MAXSIZE 20 // 斐波那契数列数组的长度大于或等于要查找的表长
int F[MAXSIZE] = {1, 1};
static void Fibonacci()
{
    for(int i = 2; i < MAXSIZE; i++)
        F[i] = F[i - 1] + F[i - 2];
}

// 斐波那契查找
int FibonacciSearch(int *a, int n, int target)
{
    // a[N] = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99}
    Fibonacci();
    int ans = -1;
    int low = 0, high = n - 1;
    int k = 0;
    while(n > F[k] - 1) // 计算n位于斐波那契数列的位置
        k++;
    for(int i = n; i < F[k] - 1; i++) // 将不满的数值补全
        a[i] = a[n];
    while(low <= high)
    {
        int mid = low + F[k - 1] - 1; // 计算当前分割的下标
        if(target < a[mid])
        {
            high = mid - 1;
            k--;
        }
        else if(target > a[mid])
        {
            low = mid + 1;
            k -= 2;
        }
        else
        {
            if(mid <= n)
            {
                ans = mid;
                break;
            }
            else // 若mid > n说明是补全数值, 返回n
            {
                ans = n;
                break;
            }
        }
    }
    return ans;
}
  • 当target = a[mid]时，查找就成功
  • 当target < a[mid]时，新范围是第low个到第mid - 1个，此时范围个数为F[k - 1] - 1个
  • 当target > a[mid]时，新范围是第mid + 1个到第high个，此时范围个数为F[k - 2] - 1个

比较

  • 折半查找

    • 折半查找最好情况查找次数为1次，最坏情况查找次数为logn + 1，所以时间复杂度为O(logn)
    • 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法比较好。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用

  • 插值查找

    • 时间复杂度为O(logn)
    • 对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的性能要比折半查找要好得多

  • 斐波那契查找

  • 时间复杂度为O(logn)

    • 就平均性能来说，斐波那契查找要优于折半查找，但如果是最坏情况，比如这里target = 1，那么始终都处于左侧长半区查找，则查找效率要低于折半查找

总结

  • 折半查找时进行加法与除法运算（ mid = (low + high) / 2 ），插值查找进行复杂的四则运算（ mid = low + ( high - low) * (key - a[low]) / (a[high] - a[low]) ），而斐波那契查找只是最简单加减法运算（ mid = low + F[k - 1] - 1 ），并且需要额外的空间来保存斐波那契数列，在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率
  • 三种有序表的查找本质上是分割点的选择不同，各有优劣

线性索引查找

索引概念

  • 数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构
  • 索引就是把一个关键字与它对应的记录相关联的过程
  • 一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息
  • 索引技术是组织大型数据库以及磁盘文件的一种重要技术
  • 索引按照结构可以分为线性索引、树形索引和多级索引

线性索引

  • 线性索引就是将索引项集合组织为线性结构，也称为索引表

稠密索引

  • 稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项
  • 对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列
  • 索引表有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐波那契等有序查找算法

分块索引

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件

  • 块内无序

    • 即每一块内的记录不要求有序

  • 块间有序

    • 即后一块所有记录的关键字都要大于前一块所有记录的关键字

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引

结构描述

分块索引的索引项结构分为三个数据项

  • 最大关键码，它存储每一块的最大关键字
  • 存储块中的元素个数，以便循环时使用
  • 指向块首数据元素的指针，便于开始对这一块中的记录进行遍历

在分块索引表中查找，就是分两步进行

  • 在分块索引表中查找要查关键字所在的块，由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果
  • 根据首指针找到相应的块，并在块中顺序查找关键码，因为块中可以是无序的，所以只能顺序查找

平均查找长度

  • 设n个记录的数据集被平均分成m块，每个块中有t条记录，显然n = m * t，或者说m = n / t。假设Lb为查找索引表的平均长度，因最好与最差的等概率原则，所以Lb的平均长度为(m + 1) / 2。Lw为块中查找记录的平均查找长度，同理可知它的平均长度为(t + 1) / 2

  • 这样分块索引查找的平均查找长度为：ASLw = Lb + Lw

  • 最佳的情况就是分的块数m与块中的记录数t相同，此时意味着n = m * t = t^2^，即ASLw = t + 1 = $\sqrt{n}$ + 1

倒排索引

  • 索引项的通用结构

    • 次关键码
    • 记录号表

  • 其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）

  • 这样的索引方法就是倒排索引（inverted index）