考研数据结构与算法（八）查找

一、基本概念 1.1 查找表

用于查找的数据集合称为查找表，它由 同一类型 的数据元素（或记 录〉组成，可以是一个数组或链表等数据类型。

查找表中常用的四种操作

• ①查询某个 特定的数据元素 是否在查找表中
• ②检索满足条件的某个特定的数据元素的其他属性
• ③在查找表中 插入 一个数据元素
• ④从查找表中 删除 某个数据元素

只进行查找（检索）操作（即查找表的前两种操作）的表另称为 静态查找表 ，如果需要进行 删除 或者 插入 操作，那么此表另称为 动态查找表

1.2 关键字

对于一个数据元素，可能是多个值构成的，每一个值都是一个关键字，如果一个关键字在查找表里可以 唯一的标识 一个记录，那么我们称其为 主关键字 ，若不能唯一标识我们则称其为 次关键字

1.3 查找

根据某个给定的值，在查找表寻找满足条件的过程称为查找，查找的结果一般分为两种：

• 查找成功
• 查找失败

1.4 平均查找长度

在查找过程中，一次查找的长度是指需要 比较的关键字次数 ，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，一般来说 这个平均长度是指 平均成功查找长度 因为查找不成功的情况我们一般忽略掉了，但是如果我们不能忽略查找失败的情况，那么某个算法的 平均查找长度=成功平均查找长度 + 失败平均查找长度

1.4.1 成功平均查找长度

注意：这个在所有的查找表的题目中都会考到，后面对于每一个表都会进行分析

我们假设 n n n 是查找表的长度， P i P_i Pi 是查找第 i i i 个数据元素的概率（一般认为每一个数据元素查找的概率相等，即 P i = 1 / n P_i = 1/n Pi=1/n） ， C i C_i Ci 是找到第 i i i 个数据元素所需要进行的比较次数，则其数学定义为：

A S L 成功 = ∑ i = 1 n P i C i ASL_{成功}=\sum_{i=1}^nP_iC_i ASL成功=i=1∑nPiCi

1.4.2 失败平均查找长度

注意：这个只在二叉排序树or哈希表中可能会考到，后面也会一一解析

对于一个查找表来说，假设对于查找某个不存在的元素的概率为 P i P_i Pi ，对每一个不存在的元素查找所需要进行的比较次数为 C i C_i Ci ，假设我们有 m m m 个不存在的元素，那么我们可以得到其数学定义：

A S L 失败 = ∑ i = 1 m P i C i ASL_{失败}=\sum_{i=1}^mP_iC_i ASL失败=i=1∑mPiCi

这里其实不够形象，可以不用在意，后面会具体例子具体解析的~

二、静态查找 2.1 顺序表（顺序查找）

简单理解为，我们将元素存储在一个线性表中，这个线性表可以是数组也可以是链表，反正无论如何我们都是要从头到尾遍历，除非遇到我们需要查找的元素，我们就将元素返回，否则我们就继续往下遍历，最后没找到的话，我们可以返回一个-1或者其他非元素集合下标

关于代码的话一般有两种写法，第一种则是王道书上介绍的 “哨兵” 写法，我们将线性表中第 0 0 0 个位置设定为我们想要找的元素（即线性表中的元素是 [ 1 , n ] [1,n] [1,n] 范围的），然后从线性表的末尾往前查找，即便 [ 1 , n ] [1,n] [1,n] 范围内没有我们需要的元素，也会在第 0 0 0 个位置停止，此时我们对于函数返回的值做判断只要是 0 0 0 那么就说明没找到

typedef struct{／／查找表的数据结构
	ElemType *elem; //元素存储空间基址，建表时按实际长度分配，0 号单元留空 int TableLen; //表的长度 }SSTable; int Search_Seq(SSTable ST , ElemType key) { ST.elem[0]=key; //“哨兵”  for(i = ST.TableLen; ST.elem[i] != key; --i); ／／从后往前找 return i; ／／若表中不存在关键字为 key 的元素，将查找到 i 为 0 时退出 for 循环 } 

当然如果说我们想要元素从 0 0 0 这个位置开始存储的话，可以不不使用 “哨兵” ，代码如下

typedef struct{／／查找表的数据结构
	ElemType *elem; //元素存储空间基址，建表时按实际长度分配 int TableLen; //表的长度 }SSTable; int Search_Seq(SSTable ST , ElemType key) { for(i = ST.TableLen - 1; i >= 0; --i); ／／从后往前找 if(ST.elem[i] == key) return i; ／／表中找到关键字 key return -1;//表中未找到关键字 } 

对于这样的一个查找方法，我们来分析一下它的平均查找长度：

• 对于查找第 i i i 个元素，如果我们逆着查找那么需要比较 n − i + 1 n-i+1 n−i+1 次，顺着看实际上我们就需要比较 i i i 次，不管是顺着还是逆着，当我们求平均的时候结果都是一样的，但是显然顺着的方式比较好求一点
• 又由于每一个元素查找的可能都是一样的即 1 n \frac{1}{n} n1 于是 P i = 1 n P_i = \frac{1}{n} Pi=n1 ，那么对于顺序查找的平均长度就为：

A S L 成功 = ∑ i = 1 n P i i = n + 1 2 ASL_{成功} = \sum_{i=1}^nP_ii = \frac{n+1}{2} ASL成功=i=1∑nPii=2n+1

当然上式子若是逆着查找的话应该这么写：

A S L 成功 = ∑ i = 1 n P i ( n − i + 1 ) = n + 1 2 ASL_{成功} = \sum_{i=1}^nP_i(n-i+1) = \frac{n+1}{2} ASL成功=i=1∑nPi(n−i+1)=2n+1

反正结果是一样的啦~

我们 考虑一下查找失败的情况 ，假设查找失败的概率和查找成功的概率一样，那么对于查找失败的情况来说每一次查找的概率是和已经有元素一样即 P i = 1 2 n P_i = \frac{1}{2n} Pi=2n1 ，而每次匹配的次数都是 n n n 次（ 从头到尾匹配完，这里使用的是非哨兵模式 ），那么失败平均匹配长度为： A S L 失败 = ∑ i = 1 n P i ( n ) = n 2 ASL_{失败} = \sum_{i=1}^nP_i(n) = \frac{n}{2} ASL失败=i=1∑nPi(n)=2n

此时的成功平均匹配长度为： A S L 成功 = ∑ i = 1 n P i i = n + 1 4 ASL_{成功} = \sum_{i=1}^nP_ii = \frac{n+1}{4} ASL成功=i=1∑nPii=4n+1

所以平均匹配长度为：

A S L 平均 = A S L 成功 + A S L 失败 = n + 1 4 + n 2 = 3 n + 1 4 ASL_{平均} = ASL_{成功} + ASL_{失败} = \frac{n+1}{4} + \frac{n}{2} = \frac{3n + 1}{4} ASL平均=ASL成功+ASL失败=4n+1+2n=43n+1

假设我们的顺序表是一个有序表的话，那么我们进行失败匹配的过程中会减少一点，假设我们走到了一个大于查找的key的第一个位置，因为顺序表是一个有序的，那么我们现在就需要停止，那么对于第 i i i 个未查找到的元素我们需要比较 i + 1 i+1 i+1 次，那么对于匹配失败的概率是 1 2 n \frac{1}{2n} 2n1 ，匹配失败的长度为 C i = { i + 1 , if  i < n n , if  i = n C_i = \begin{cases} i+1, & \text{if} \ i