查找

查找表

关键字：用来标识一个数据元素（或记录）的某个数据项的值

• 主关键字：可以唯一标识一个记录的关键字是主关键字
• 次关键字：可以用来标识若干记录的关键字是次关键字

查找是否成功？

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）

• 若查找表中存在这样一个记录，则称为“查找成功”
  • 查找结果给出整个记录的信息，或指示该记录在查找表中的位置
• 否则称为”查找不成功“
  • 查找结果给出"空记录"或“空指针”

查找的目的是什么？

1. 查找某个“特定的”数据元素是否在查找表中
2. 检索某个“特定的”数据元素的各种属性
3. 在查找表中插入一个数据元素
4. 删除查找表中的某个数据元素

查找表怎么分类？

分为两类：

1. 静态查找表：仅作”查询“（检索）操作的查找表
2. 动态查找表：作”插入“和”删除“操作的查找表

如何评价查找算法？

线性表的查找

顺序查找

改进：设置监视哨，把要查找的关键字存储到下标为0的位置。这样就能减少比较的次数，不用再比较下标i>0。

折半查找

前提条件：有序

折半查找：每次将待查找记录在区间缩小一半。

查找过程：

1. mid = (low + high) / 2
2. key < mid 则：high = mid - 1，即如果要查找的值比中间的值要小，那么移动high指针到mid - 1的位置。
3. key > mid 则：low = mid + 1，即如果要查找的值大于中间的值，那么移动low指针到mid + 1的位置。
4. key == mid，即要找的值刚好在指针mid指向的位置上。
5. high < low，结束。

折半查找的非递归算法

折半查找的递归算法

折半查找的性能分析（判定树）

经过多少个结点，就查找了多少次。

折半查找的优点：效率比顺序查找高。

折半查找的缺点：只适用于有序表，且限于顺序存储结构（对线性链表无效）。

分块查找

树表的查找

二叉排序树

二叉排序树（Binary Sort Tree）又称为二叉搜索树，二叉查找树

二叉排序树的查找分析

二叉排序树的操作

插入

生成

从空树出发，经过一系列的查找、插入操作之后，可以生成一棵二叉排序树。

一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。

插入的结点均为叶子结点，故无需移动其它结点。相当于在有序序列上插入记录而无需移动其它记录。

注意：关键字的输入顺序不同，建立的二叉排序树不同。

删除

从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删除该结点，并且还应该保证删除后所得的二叉树仍然满足二叉排序树的性质不变。

由于中序遍历二叉排序树可以得到一个递增有序的序列，那么，在二叉排序树中删除一个结点相当于删除去有序序列中的一个结点。

将因删除结点而断开的二叉链表重新链接起来。

防止重新链接后树的高度增加。

1. 被删除的结点是叶子结点：直接删除该结点。

2. 被删除的结点只有左子树或只有右子树，用其左子树或右子树替换它（结点替换）。

   

   其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。

3. 被删除的结点既有左子树，也有右子树。

   

   

以左子树的最大值替换被删除的关键字或以右子树的最小值替换被删除的关键字。

平衡二叉树

平衡调整的四种类型

哈希表的查找

散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系。

优点：查找效率高

缺点：空间效率低

散列方法（杂凑法）：选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值K计算地址，将K与地址单元中元素关键码进行比较，确定查找是否成功。

散列函数（杂凑函数）：散列方法中使用的转换函数。

散列表（杂凑表）：按照上述思想构造的表。

冲突：不同的关键码映射到同一个散列地址。

同义词：具有相同函数值的多个关键字。

散列函数的构造方法

使用散列表要解决好两个问题：

1. 构造好的散列函数
   • 所选函数尽可能简单，以便提高转换速度；
   • 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。
2. 制定一个好的解决冲突的方案
   • 查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

解决地址冲突的方法

开放定址法（开地址法）

线性探测法

二次探测法

伪随机探测法

链地址法（拉链法）

链地址法的优点：

• 非同义词不会冲突，无“聚集”现象。
• 链表上结点空间动态申请，更适合于表长不确定的情况。

散列表的查找及性能分析

Q.E.D.