【数据结构】查找

查找的基本概念

1. 查找：在数据集合中查找满足某种条件的数据元素的过程【成功/失败】
2. 查找表（查找结构）：用于查找的数据集合，由同一类型的数据元素（或者记录）组成的
3. 操作（一般有四个）：1⃣️查询某数据是否在表中2⃣️检索满足条件的某个特定元素的各种属性 3⃣️在查找表中插入一个数据元素4⃣️从查找表中删除某个数据元素
4. 静态查找表：只涉及操作1和2
5. 适合静态查找表的查找方法有：顺序查找、折半查找、散列查找等
6. 适合动态查找表的查找方法：二叉排序树的查找、散列查找等
   二叉平衡树和B树都是二叉排序树的改进
7. 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果唯一。
8. 平均查找长度（ASL）：【一次查找长度是需要比较的关键字次数】而平均查找长度是所有查找过程中进行关键字比较次数的平均值
   
   其中，n是查找表的长度，Pi是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即Pi=1/n，Ci是找到第i个数据元素所需进行的比较次数。
   ASL是衡量查找算法效率的最主要的指标

顺序查找法

顺序查找（线性查找）

1. 适用范围：顺序表和链表都可以
   1.1 顺序表：通过数组下标递增来顺序扫描每个元素
   1.2 链表【只能进行顺序查找】：通过指针next来依次扫描每个元素
2. 区分：对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找

对一般的无序线性表的顺序查找

对按关键字有序的线性表的顺序查找

分块查找法

折半查找法

树形查找

二叉搜索树

二叉平衡树

红黑树

B树及其基本操作、B+树的基本概念

散列（Hash）表

查找算法的分析与应用