考研数据结构 08 查找

发布于 8 天前  46 次阅读


一、顺序查找和折半查找

1.1 一般线性表顺序查找

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

当每个元素的查找概率相等,即Pi=1/n时,ASLsuccess=(n+1)/2。

1.2 有序表的顺序查找

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

其中Pi为到达第i个节点失败的概率,在概率相等的情况下,他是1/(n+1);lj是第j个节点所在的层数。当n=6时,ASLfail = 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 = 02、12,-12、22……-k2、k2,其中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. 填装因子,填装因子 = 元素记录数 / 散列表长度