考研数据结构 08 查找

一、顺序查找和折半查找

1.1 一般线性表顺序查找

  查找方法大家都会的，下面是性能分析。
  查找成功时的平均长度：

当每个元素的查找概率相等，即P_i=1/n时，ASL_success=(n+1)/2。

1.2 有序表的顺序查找

  下面我们讨论在有序表中的查找。在一般线性表中，查找失败的长度为n+1，而在有序表中查找失败的平均长度为：

其中P_i为到达第i个节点失败的概率，在概率相等的情况下，他是1/(n+1)；l_j是第j个节点所在的层数。当n=6时，ASL_fail = 6/2 + 6/7 = 3.86.

1.3 折半查找

  这也是大家很熟悉的查找，但值得注意的是：需要注意查找时的边界处理。

int Binary_Search(List list, Element ele)
{
    // 默认返回值为 -1
    int re { -1 };

    // 用于确定上下边界的“指针”
    int lower { 0 }, upper { list.size() };

    while (lower < upper)
    {
        // 查找中间位置
        int mid = (upper + lower) / 2;

        //查找成功 则返回当前位置
        if (list[mid].element = ele)
        {
            re = mid;
            break;
        }
        // 若小于当前值，则从前部分开始查找
        else if (list[mid].element < ele)
        {
            upper = mid - 1;
        }
        // 若大于当前值，则从后部分开始查找
        else if (list[mid].element > ele)
        {
            lower = mid + 1;
        }
    }

    return re;
}

1.4 分块查找

  将数组分成若干份，每份内按排序准则排序，份与份之间可以不遵循排序准则。查找思路为多次使用二分查找。

二、散列表

2.1 地址构造方法

2.1.1 直接构造法

H(key) = constValA * key + constValB;

  通过两个常量与key计算出地址，key不同的情况下地址不会重复。适合关键字连续的情况，如果关键字不连续（空位多），则会造成空间的浪费。

2.1.2 除留余数法

H(key) = key % p;

  我们可以通过余数p来控制散列表的大小，但是这种方法存在地址冲突的问题。
  其他的构造方法这里不再赘述。

2.2 地址冲突解决方法

2.2.1 开放地址法

Hi = (H(key +di) % m;
// Hi为第i个元素的位置，d为增量序列，m为散列表长度

  对于增量序列d有如下几种选择方法：

1. 线性探测法：d = 0、1、2、3……m-1。这种方法的特点是：遇到冲突查找下一个节点，直到找到一个空单元，或是查遍全表。
2. 平方探测法：d = 0²、1²，-1²、2²……-k²、k²，其中k < m/2。m必须是可以表示成4k + 3的素数。优点：避免堆积；缺点：不能查找到散列表的所有单元，但至少能查找到一半单元。
3. 再散列法：当H(key)冲突时，使用第二个函数：Hi = (H(key) + i*H2(key)) % m；
4. 伪随机序列法：di为伪随机数。

2.2.2 拉链法

  此时我们的Hi位置不在存放元素，而是存放链表，用以存储相同下标的元素。

2.3 查找与性能分析

2.3.1 查找方法

  Hash的查找方法：

1. 查找H(key)位置是否有元素，如果无元素则查找失败。有元素则比较，相等则返回查找结果；不相等就查找下一个位置是否有元素，直到找到元素、或查无元素。

2.3.2 性能分析

  影响性能的因素：

1. 哈希函数
2. 冲突处理方法
3. 填装因子，填装因子 = 元素记录数 / 散列表长度