王道数据结构课代表 - 考研数据结构 第七章 查找(B树、散列表) 究极精华总结笔记（C版本）

王道数据结构课代表 - 考研数据结构 第七章 查找(B树、散列表) 究极精华总结笔记（C版本）

本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对数据结构知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！
关于对 “查找” 章节知识点总结的十分全面，涵括了《王道数据结构》课程里的全部要点（本人来来回回过了三遍视频），其中还陆陆续续补充了许多内容，所以读者可以相信本篇博客对于考研数据结构“查找”章节知识点的正确性与全面性；但如果还有自主命题的学校，还需额外读者自行再观看对应学校的自主命题材料。

精准控时：
如果不实际 *** 作代码，只是粗略过一下知识点，需花费 50 分钟左右过一遍
这个50分钟是我在后期冲刺复习多次尝试的时间，可以让我很好的在后期时间紧张的阶段下，合理分配复习时间；
但是刚开始看这份博客的读者也许会因为知识点陌生、笔记结构不太了解，花费许多时间，这都是正常的。
重点！！！学习一定要多总结多复习！重复、重复、再重复！！！

食用说明书：
第一遍学习王道课程时，我的笔记只有标题和截图，后来复习发现看只看图片，并不能很快的了解截图中要重点表达的知识点。
所以再第二遍复习中，我给每一张截图中标记了重点，以及每张图片上方总结了该图片对应的知识点以及自己的思考。
最后第三遍，查漏补缺。
所以 ，我把目录放在博客的前面，就是希望读者可以结合目录结构去更好的学习知识点，之后冲刺复习阶段脑海里可以浮现出该知识结构，做到对每一个知识点熟稔于心！
请读者放心！目录展示的知识点结构是十分合理的，可以放心使用该结构去记忆学习！
注意(⊙o⊙)！，每张图片上面的文字，都是该图对应的知识点总结，方便读者更快理解图片内容。

---

第7章 查找

文章目录

第7章 查找

7.1 查找的基本概念

1、查找2、查找表3、关键字4、静态查找表5、平均查找长度 7.1 查找的基本概念小结7.2 顺序查找和折半查找

7.2.1 顺序查找

1、算法思想2、具体实现3、优化 7.2.1 顺序查找小结7.2.2 折半查找

1、算法思想2、具体实现3、查找效率分析4、折半查找判定树5、拓展思考 7.2.2 折半查找小结7.2.3 分块查找

1、算法思想2、查找效率分析3、拓展思考 7.2.3 分块查找小结 7.3 B树和B+树

7.3.1 B树及其基本 *** 作

1、B树的高度 7.3.1 B树的基本概念小结

2、B树的插入3、B树的删除 7.3.1 B树的基本 *** 作小结7.3.2 B+树的基本概念

1、B+树满足的条件2、B+树的查找3、B+树 VS B树 7.3.2 B+树的小结 7.4 散列表

7.4.1 散列表的基本概念

1、散列查找 7.4.2 散列函数

1、除留余数法2、直接定址法3、数字分析法4、平方取中法 7.4.3 处理冲突的方法

一、开放定址法

1、线性探测法2、平方探测法3、伪随机序列法 二、再散列法 7.4.3 处理冲突的方法小结拉链法的小优化

7.1 查找的基本概念

1、查找 2、查找表 3、关键字

4、静态查找表

5、平均查找长度

7.1 查找的基本概念小结

---

7.2 顺序查找和折半查找 7.2.1 顺序查找 1、算法思想

2、具体实现

3、优化

7.2.1 顺序查找小结

---

7.2.2 折半查找 1、算法思想

2、具体实现

3、查找效率分析

4、折半查找判定树

右子树 - 左子树 = 0/1

5、拓展思考

7.2.2 折半查找小结

---

7.2.3 分块查找 1、算法思想

2、查找效率分析

3、拓展思考

7.2.3 分块查找小结

---

7.3 B树和B+树

不怎么考察代码题

将2叉查找树升级到5叉查找树注意每个区间的范围了解查找失败时，指针会落在哪里去？

例如：下图里表明的“失败结点”，范围在（15，22）的结点都会落到那里

每个结点内关键字太少，导致树变高，查找效率低下

例如下图，5叉查找树退化成2叉查找树 所以为了保证查找的效率，就会规定每个结点内至少需要含有的关键字数量

根结点不要求至少（[m/2]向上取整）个分叉

“不平衡”也不利于查找效率但是参考平衡二叉树的规定，对于m叉查找树又太麻烦了，所以直接规定左、右子树高度要相同

7.3.1 B树及其基本 *** 作

上面逼逼一大堆，关于B树比较重要的规定就是：

1、各子树要平衡（绝对平衡）2、各结点的分叉数有规定 注意！！！下面的终端结点和叶子结点，别混淆了m阶B树，m个分叉，m-1个关键字

k是关键字，p是指针

3个B树关键的性质

1、B树的高度

n+1个叶子结点：n个关键字剋划分出n+1个区域

7.3.1 B树的基本概念小结

2、B树的插入

插入80，导致结点关键字数量超过上限

新结点一定是插入到最底层

根结点可以只有一个关键字

3、B树的删除

终端结点直接删除（但是也要注意结点里关键字的数量）

删除非终端节点，找直接前驱或直接后继

删除终端节点里的关键字，导致结点关键字数量不足

1、兄弟够借

删除终端节点里的关键字，导致结点关键字数量不足

2、兄弟不够借（合并）

7.3.1 B树的基本 *** 作小结

---

7.3.2 B+树的基本概念

​ 考研中B+树不会考的很深，都是考一些基本概念的问题。

1、B+树满足的条件

B树：m-1个关键字对应m个分支，m个子树B+树：m个关键字，对应m个分支，m个子树B+树里，查找信息并不会停留在分支节点上，会一直查找到叶子结点

例如查找9，最后找的是绿色的9，而不是蓝色的9

2、B+树的查找

B+树和B树关于查找的区别看下B+树，B树两个图，B+树关键字会重复，B树不会重复

B+树还可以通过p开始顺序查找

3、B+树 VS B树

7.3.2 B+树的小结

B树只能进行随机查找，而B+树可以进行随机查找和顺序查找

---

7.4 散列表 7.4.1 散列表的基本概念

1、散列查找

7.4.2 散列函数 1、除留余数法

选最大质数 —— 为了让不同的关键字冲突尽可能少

2、直接定址法

3、数字分析法

4、平方取中法

---

7.4.3 处理冲突的方法

之前使用的是拉链法 一、开放定址法

1、线性探测法

哈希函数取模，和冲突函数取模，选的取模值不一定相同，看看下图标识

一个选择13，一个选择16

开发定址法：即可能和同义词发生冲突，也可能和非同义词发生冲突。

注意，此处对于空位置的判断也算作一次比较，和上一小节的拉链法不算空位置有区别

21%13=8，所以下图从84开始找，一旦遇到空（例如，10那个位置），就表明不需要在找下去了

上图里我们说到：越早遇到空位置，就可以越早确认查找失败。可是也有不适应的情况！

下图中假设删除元素1，使得2位置变空。此时若要查找27元素，27%13=1，从1位置（14）开始找，可是此时2位置为空，就无法查找到4位置了元素27了。 针对上诉情况，规定在删除一个元素时不能简单删除元素就完事了，还需要做个删除标记，让查找时可以此处是因删除而空，而不是没有初始元素才空的。还需要接着往后找。

下面的看似表很满，实际真实数据并不多，也是开放定址法的一个弊端。

查找成功的效率分析

查找失败的效率分析

只有位置为空，才比较1次，不然就得一直遍历到13这个位置，才能确认失败。

为什么查找效率低：同义词、非同义词聚集堆积聚集是因选取不当的处理冲突的方法造成的

2、平方探测法

d是针对初始位置 *** 作的，例如：元素32的位置就是6-1，而不是上一个位置7-1。

平法探测法对于散列表的长度有要求：4*j+3

3、伪随机序列法

二、再散列法

7.4.3 处理冲突的方法小结

---

拉链法的小优化

保持冲突的同义词的链表，进行有序链接

---

考研人加油！！！