数据结构第七章-查找（1.基础内容）

注：在一轮复习的时候花了快一周学校这一章，是因为这章的题目难度在初学时，还算比较复杂，对于各种查找的过程，要比较清楚。

总知识框架：
 

复习：本章是考研的重点。对于折半查找，应掌握折半查找的过程、构造判定树、分析平均查找长度等。对于二叉排序树、二叉平衡树和红黑树，要了解它们的概念、性质和相关操作等。B树和B+树是本章的难点。对与B树，考研大纲要求掌握插入、删除和查找的操作过程；对于B+树，仅要求了解其基本概念和性质。对于散列查找，应掌握散列表的构造、冲突处理方法（各种方法处理过程）、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。

基于上述，对于过程，自己要很熟悉，最好的办法是，自己一定要一个一个步骤来，逐步的显示，对比操作，进行自我检验。

注：再二轮开始复习之前，可以自己先按照自己的复习方式迅速过一遍。

注：为什么自己要写一遍，不直接拍，还是想自己在打字的时候可以对这一章的知识点的内容记忆更再次复盘一次。这一章自己学的兴趣还是比较大的，对于B树，是有点复杂，听课听烦了，我就直接去对着书中的题和答案，自己摸索这个过程，效果还好，做了几个之后继续听课，然后听完了，再自己重新做一遍。

1.查找的基本概念

• 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合中找到满足条件的数据元素；二是查找失败。
• 查找表(查找结构)：用于查找的由同一类型的数据元素(或记录)构成的集合。查找表本质是表中记录之间仅存在"同属一个集合”这个逻辑的集合结构。为此，我们在数据元素之间人为地加上一些关系，以便按照某种规则查找，即用另一种数据结构来表示查找表。
• 对查找表进行的操作一般有四种：①查询某个特定的数据元素是否在查找表中；②检索满足条件的某个特定的数据元素的各自属性； ③在查找表中插入一个数据元素；④在查找表中删除某个数据元素。只作前两种查找操作的查找表为静态查找表；可以作上述四种操作，即在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素的为动态查找表。
• 关键字：数据元素中可以标识元素的某个数据项的值。主关键字可以唯一标识一个记录，次关键字可以识别若干记录。使用基于主关键字的查找，查找结果应该是唯一的。
• 平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值：
• 

补充：按分类：静态查找表、动态查找表。

适合静态查找（仅关注查找速度即可）的方式：顺序查找、折半查找、散列查找等。

适合动态查找（除直线速度，也要关注插/删除操作是否方便）的方式：二叉排序树的查找、散列查找等。

2.表格类比复习

注：（相对于二刷）重点强调一下，为以后做铺垫。

重点：关注表的分类

查找算法的评价指标：

 查找算法的评价指标（举例）:相对于回顾一遍

成功：

 失败：