数据结构篇_知识点板块_第七章查找

• 数据结构篇为本人考研时所写笔记，包括知识点和编程思想两大板块，笔记内容依据王道数据结构考研书所写，但比书本上知识更加生动形象，愿本篇章能对您有所帮助

七、查找

（一）基本查找方法

1. 基本概念：

①　查找表（又称查找结构）：用于查找的数据集合

②　 静态查找表（顺序查找，折半查找，分块查找）：不需要进行动态插入或删除的查找表

③　 动态查找表（二叉排序树，二叉平衡树，B-，B+）：与上反之（不要被动态静态误导了，并不是链表和顺序表的意思）

④　关键字：数据元素中唯一标识该元素的某个数据项的值，基于关键字查找结果是唯一的

⑤　一次查找长度：需要比较的关键字次数

⑥　平均查找长度（ASL）：所有查找过程中进行关键字比较次数的平均值

1. 一般线性表顺序查找：

①　哨兵：将值a赋给查找表中最后一个元素，则在for循环中中间判断条件是判断是否等于a而不必判断数组是否会越界

②　 哨兵好处：避免很多不必要的判断语句，从而提高程序的效率

③　ASL:

(1) 查找成功时平均长度：

(2) 查找成功时平均长度（等概率时）：ASL=（n+1）/2

(3) 查找不成功时平均长度：n+1

④　注意对线性的链表只能进行顺序查找

⑤　顺序表查找指的是在顺序存储结构上进行查找（错）（顺序存储指的就是数组之的数据结构,但是 顺序表并不一定是用数组实现的,例如链表即也可在链式存储结构上实现）

1. 有序线性表顺序查找(一般线性表顺序查找的一种优化)：

①　概念：查找之前知道表的关键字（数值）是有序的

②　有序线性表的判定树：

(1) 树中圆形结点：有序线性表中存在的元素

(2) 树中矩形结点：失败结点；若有n个结点，则相应有n+1个查找失败结点（即类似于二叉数查找失败时所画的空结点）

③　时间复杂度：O（n）

④　ASL:

(1) 查找成功时平均长度与一般线性表一样

(2) 查找不成功时平均长度（等概率时）：n/2 + n/(n+1)（到达失败结点的长度等于父结点所在层数）

1. 一般线性表顺序查找的另一种优化：当被查概率不等时把被查概率大的放在靠前的位置（类似于哈夫曼编码的思想），但这会时ASL_不成功增大，故怎么优化还应依情况而定

2. 折半查找（二分查找）：

①　折半查找判定树（二叉数）：

(1) 判定树：将折半查找过程用二叉树来描述（折半查找的性能分析可以用二叉判定树来衡量）

(2) 判定树是一颗平衡二叉树

(3) 圆形结点：表示一个记录

(4) 结点中的值：该记录的关键字值

(5) 方形结点：树最下面的叶结点，表示查找不成功的情况

(6) 查找成功时：查找长度为根节点到目标结点

查找失败时：查找长度为根节点到对应失败结点的父结点

(7) 左结点值<根值<右结点值（同二叉排序树）

(8) 若有序序列有n个元素，则对应判定树有n个圆形非叶结点和n+1个方形叶结点

(9) 注意：

​(1 当向下取整（mid=(low+high)/2）：判定树必须右子树结点数-左子树结点数=0/1

​(2 当向上取整（mid=(low+high)/2）：判定树必须左子树结点数-右子树结点数=0/1（考试时看清是向上还是向下取整）

(10) 在查找不成功时和给定值进行关键字的比较次数最多为树的高度

②　要求必须是顺序存储结构且元素按关键字有序排列

③　时间复杂度：O（log_2 n）

④　ASL：

(1) 查找成功时：
(h不包括失败结点)

1. K分查找：

2. 分块查找（索引顺序查找）：

①　基本思想：将查找表分为若千子块。块内的元素可以无序，但块之间是有序的,即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列

②　分块查找的过程分为两步:

(1) 第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表

(2) 第二步是在块内顺序查找（因为可能无序故只能顺序查找）

③　ASL:

(1) ASL=索引查找平均长度（L_I）+块内查找平均长度（L_S）

(2) 长度为n的查找表均匀地分为b块，每块有s个记录：

​(1 等概率都使用顺序查找：
（若s=
,则min(ASL)=
+1（求导取极值得出的）)

​(2 索引表用折半查找：

​(3 当都用折半查找时效率最高，具体数据看题（时间效率介于顺序查找和二分查找之间）

1. 若查找表是动态表，则一般用链式存储较方便

（二）B树（多路平衡查找树）和B+树

考前结合王道选择看一下

1）B树

1. 阶：B树（可以为空树）中所有结点的孩子个数最大值

2. B树为满足下列特性的m叉树：

①　树中每个结点至多有m棵子树，即至多含有m-1个关键字。

②　若根结点不是终端结点，则至少有两棵子树（保证绝对平衡，即没高度差）

③　除根结点外的所有非叶结点至少有向上取整（m/2）棵子树，即至少含有向上取整（m/2）-1个关键字

④　综上：

（1) 根结点的子树数∈[2,m]

（2) 关键字数∈[1,m-1]

（3) 其他结点的子树数∈[向下取整（m/2）,m]

（4) 关键字数∈[向下取整（m/2）-1,m-1]

⑤　结点中的关键字是有序的，且结点满足：子树0<关键字1<子树1<关键字2...(即左结点值<根值<右结点值）

⑥　所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的杳找失败结点，实际上这些结点不存在，指向这些结点的指针为空)

⑦　对于任一结点，所有子树高度都相同

⑧　n个关键字的B树必有n+1个叶子结点

⑨　综上所述B树是所有结点的平衡因子均等于0的多路平衡查找树，与③都是为了保证查找效率

（外部结点又称叶子结点/失败结点，外部结点上面一层的结点又称终端结点）

1. 计算B树高度时应注意是否包括最后的叶子结点

2. 对于n>=1，包含n个关键字，高度为h，阶数为m的B树：

①　

②　

2）B+树

1. B+树需满足以下条件：

①　每个分支结点最多有m棵子树(孩子结点)

②　非叶根结点至少有两棵子树，其他每个分支结点至少有向下取整（m/2）棵子树

③　结点的子树个数与关键字个数相等

④　所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列并且相邻叶结点按大小顺序相互链接起来

⑤　所有分支结点（可视为索引的索引）中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针

1. 无论查找成功与否，每次查找都是一条从根结点到叶结点的路径（即都要走到最小面），因为只有底层结点才包含信息，故对于B+树而言只有查找到最下面一层结点才是成功的

3）B-树（多路平衡查找树）

1. 适合在磁盘等直接存取设备上组织动态的查找表

（三）散列表

1. 典型的空间换时间的算法

2. 基本概念：

①　散列函数（又称哈希函数）：一个把查找表中的关键字映射成该关键字对应的地址的函数

②　散列表(又称哈希表)：根据关键字而直接进行访问的数据结构（散列表建立了关键字和存储地址之间的一种直接映射关系）

③　冲突：当两个或两个以上不同关键字映射到同一地址（解决冲突的常用方法是：线性探测法，多重散列法，链地址法）

④　冲突解决技术可以分为两类：开散列方法(也称为拉链法/链地址法)和闭散列方法(也称为开地址方法)。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内

⑤　线性探测是出现冲突后开始向后探测一个位置，所以从第二个关键字若和第一个冲突时映射时要做1次探测

⑥　同义词：发现碰撞的不同关键字

1. 时间复杂度（理想情况）：O(1)（哈希表的查找效率主要取决于哈希表造表时所选取的哈希函数和处理冲突的方法）

2. 散列表和索引表的区别：

（1) 散列存储是直接将关键字的值做一个映射到存储地址

（2) 索引存储则是另外使用关键字来构建一个索引表

A. 散列函数的构造

1. 构造散列函数需注意：

①　散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。

②　散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生

③　散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址

1. 散列函数选择两条标准：简单和均匀

2. 一些函数分析：

①　：不能当作散列函数，因为该函数的返回值不确定，这样无法进行正常的查找（并不是随机就是好)

②　：能够作为散列函数，但不是一个好的散列函数，因为所有关键字都映射到同一位置，造成大量的冲突机会。

a. 直接地址法

1. 直接取关键字的某个线性函数值为散列地址，散列函数为

2. 适合关键字的分布基本连续的情况；若关键字分布不连续，空位较多，则会造成存储空间的浪费

b. 除数余数法

1. 一般取不大于表长但最接近或等于表长的质数p（又称素数（不能被除自身和1外的数整除）（合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数）），散列函数为

2. 此方法关键是取好P

c. 数字分析法

1. 设关键字是r进制数（如十进制数)，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些,每种数码出现的机会均等:而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址

2. 这种方法适合于己知的关键字集合,若更换了关键字，则需要重新构造新的散列函数

d. 平方取中法

1. 取关键字的平方值的中间几位作为散列地址，具体取几位视情况而定

2. 适合用于数据量过大的情况

B. 处理冲突方法

1. 要完全（不是安全）避免冲突需满足：

①　关键字集合U不大于散列表长m

②　选择合适的散列函数（例如选择
就不合适）

a. 开放地址法

1. 数学递推公式：
   （)

2. di一般有四种取法：

①　di中i表示当前元素H(key)冲突后依次H(key)+di（从0开始）比较后的冲突次数，如若分别与H(key)+0、1、-1位置冲突共冲突三次则下一次即为H(key)+d3=H(key)+4(以平方探测法为例)

②　线性探测法：

（1) di=0,1,2...

（2) 空位置的判断也要算成一次比较

（3) 缺点：易造成大量元素的散列地址“聚集”（或堆积（由同义词之间或非同义词之间发生冲突（不是仅同义词之间）））（对存储效率、散列函数、装填因子均不会有影响，但会直接影响平均查找长度）起来，减低查找效率

（4)

③　平方探测法（二次探测法）：（2021考了）

（1) di=0,1,-1,4,-4...

（2)

④　再散列法（双散列法、再哈希法）

（1) 除了原始散列函数H(key)外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止

⑤　伪随机序列法：

（1) di=伪随机序列

1. 注意：在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此,要删除一个元素时，可给它做一个删除标记,进行逻辑删除。但这样做的副作用是:执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

b. 拉链法（链接法，chaining）

1. 将所有同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识

2. 适用于经常进行插入和删除的情况

3. 若限定在链首插入，则插入任一个元素的时间是相同的

5. 注意：有的教材会把“空指针”的判断算作一次比较，具体参考真题是怎么计算的

C.散列查找及性能分析

1. 散列表的查找效率取决于三个因素:散列函数、处理冲突的方法和装填因子

2. 装填因子（一般记为α）：定义一个表的装满程度（)

3. 散列表的平均查找长度依赖于散列表的装填因子α，而不直接依赖于n或m

4. α越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小

（四）ASL综述

1. 设一个查找集合中已有n个数据元素，每个元素的查找概率为p_i,查找成功的数据比较次数为G (i=1, 2,…, n);不在此集合中的数据元素分布在由这n个元素的间隔构成的n+1个子集合内，每个子集合元素的查找概率为q_j,查找不成功的数据比较次数为c_j(j=0, 1,…,n)。因此，对某一特定查找算法的查找成功的ASL和查找失败的ASL，是综合考虑还是分开考虑呢?

答：

1. 上述两种考虑的计算结果是不同的,考试中一定要仔细阅读题目的要求，以免失误

2. 散列表平均查找成功长度除以排序个数，平均查找失败长度除以散列表长度