本章知识框架
1.查找的基本概念
- 什么是查找表?
- 什么是关键字
- 什么是查找
- 查找是否成功?
- 查找的目的?
- 查找的分类
- 如何评价查找算法
- 查找过程中我们需要研究什么?
2.线性表的查找
对于这一部分,该视频讲解了顺序查找(线性查找),折半查找(二分或对分查找)和分块查找这三类查找。
顺序查找(线性查找)
- 顺序查找
算法1:
算法2:
算法3:
算法改进:
把待查关键字key存入表头（“哨兵”、”监视哨”)，从后往前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。
对改进算法的时间效率进行分析:
顺序查找的特点:
折半查找(二分或对分查找【查找表必须是有序表】)
什么是折半查找:
非递归算法:
递归算法:
int Search Bin(SSTable ST, KeyType key,int low ,int high){
if(low > high) return 0;
mid = (low + high)/2;
if(key == ST.elem[mid].key) return mid;
else if(key < ST.elem[mid].key)
high = mid - 1;
else
low = mid + 1;
Bin(ST,key,low,high);
}折半查找的性能分析
分块查找(索引顺序查找)
分块查找:
下面查38,先选择块(38大于22并且小于48所以在索引表序号7开始的块中即第二块),再从块内进行查找(通过顺序查找,即可找到38位于序号10)
分块查找性能分析:
分块查找优缺点:
顺序,折半和分块查找的方法比较
3.树表的查找
动态查找表:表结构在查找过程中动态生成
- 二叉排序树
- 平衡二叉树
- 红黑树
- B-树
- B+树
- 建树
二叉排序树
- 什么是二叉排序树
二叉排序树
非二叉排序树
- 二叉排序树的性质
中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。
中序遍历二叉排序树
- 二叉排序树查找操作
查找105,过程红色箭头
二叉排序树的存储结构
二叉排序树算法思想
算法代码描述:
- 二叉排序树的查找分析
二叉排序树的平均查找长度:
最好情况和最坏情况:含有n个结点的二叉排序树的平均查找长度和树的形态有关
- 二叉排序树的插入操作
如果插入的结点为叶子结点
二叉排序树的生成
例子1:
关键字的输入顺序不同，建立的不同二叉排序树:
- 二叉排序树删除操作
(1）被删除的结点是叶子结点:直接删去该结点。
(2)被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它(结点替换)。
(3)被删除的结点既有左子树，也有右子树
例子:
- 平衡二叉树
什么是平衡二叉树?
什么是平衡因子?根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1、0，或1。
例子1(是一个平衡二叉树):
下图是结点为40的平衡因子计算过程:
例子2:
- 失衡二叉排序树的分析和调整
平衡调整的四种类型:
调整（调整原则:1.降低高度;2.保持二叉排序树性质）:
LL型调整:
例子:
RR型调整:
例子:
LR型:
例子:
RL型:
例子:
4.哈希表的查找
- 散列表(哈希表)的基本概念
例1:
例2:
散列表:
散列表的优缺点:
散列方法:
冲突:
- 构造散列函数
使用散列表要解决好二个问题
构造散列函数考虑的因素:
构造的要求和相关构造方法:
直接定址法(一个x对应唯一的Y值):
除留余数法:
- 处理冲突的方法
开放定址法(开地址法)
线性探测法:
例子:
二次探测法:
伪随机探测法:
链地址法(拉链法)
链地址法建立散列表步骤:
链地址法的优点:
- 散列表的查找
例子1(线性探测法):
例子2(链地址法):
- 散列表的查找效率
