数据结构学习笔记（Ⅶ）：查找

目录

1 查找

1.1 定义

1.2 查找操作

1.3 算法评价指标

2 查找算法

2.1 顺序查找

1.算法思想

 2.实现

3.查找效率

4.算法优化

2.2 折半查找

1.算法思想

2.算法实现

3.查找判定树

4.折半查找效率

2.3 分块查找

1.算法思想

2.查找效率分析

3 B树

3.1 B树概念

3.2 B树的插入删除

1.插入

2.删除

3.3 B+树

1.定义

2.查找

3.与B树对比

4 散列查找

4.1 散列查找（上）

1.散列表

2.查找 

3.散列函数

4.2 散列查找（下）

1.开放定址法

2.再散列法

---

1 查找

1.1 定义

查找——在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表（查找结构)——用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成

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

1.2 查找操作

只需查找符合条件的数据元素的操作为静态查找表；同时需要进行插入、删除数据元素的操作为动态查找表

1.3 算法评价指标

查找长度——在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度（ASL, Average Search Length)——所有查找过程中进行关键字的比较次数的平均值

2 查找算法

2.1 顺序查找

1.算法思想

顺序查找又称线性查找，通常用于线性表。其思想即从头到尾（或逆向）查找

 2.实现

3.查找效率

时间复杂度O(n)

4.算法优化

 对于有序表，可以利用查找判定树进行关键字对比。

若被查找概率不相等，被查概率大的可以放在靠前位置。

2.2 折半查找

1.算法思想

仅适用于有序的顺序表，即二分法 

2.算法实现

3.查找判定树

 折半查找判定树一定是平衡二叉树，只有底层是不满的。

失败结点等于n+1

4.折半查找效率

 查找成功与失败的ASL <= h

2.3 分块查找

1.算法思想

2.查找效率分析

3 B树

3.1 B树概念

 为了保证m叉查找树的查找效率，规定除了根节点外，任何结点至少要[m/2]个分叉，即至少[m/2]-1个关键字；对于任何一个结点，其所有子树高度相同。 

3.2 B树的插入删除

1.插入

2.删除

3.3 B+树

1.定义

2.查找

·根结点开始逐层查找

·顺序查找

3.与B树对比

4 散列查找

4.1 散列查找（上）

1.散列表

散列表(Hash Table)，又称哈希表。是一种数据结构，特点是︰数据元素的关键字与其存储地址直接相关。通过哈希函数实现其映射关系。 
若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”

通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”
用链接法处理冲突：将所有同义词存储在一个链表中

2.查找 

查找关键字后查找其链表内容 

装填因子α  = 表中记录数/散列表长度

3.散列函数

4.2 散列查找（下）

1.开放定址法

2.再散列法