数据结构与算法基础（青岛大学-王卓）(8)

哎呀呀，sorry艾瑞波地，这次真的断更一个月了，又发生了很多很多事情，秋风开始瑟瑟了，老父亲身体查出肿瘤了，有病请及时就医，愿每一个人都有一个健康的身体，God bless U and FAMILY.
直接上货了 😃

文章目录

- 查找
- - 概念
  - 线性表的查找
  - - 顺序查找(线性)
    - - 应用范围：
      - 表示方法：
      - 算法：
      - 算法7.2时间效率分析：
      - 讨论
      - 优缺点：
    - 折半查找(对半/二分)
    - - 算法思路
      - 二分查找效率分析 - 判定树
      - 平均查找长度ASL(成功时)
      - 优缺点
    - 分块查找(索引顺序查找)
    - - 条件
      - 性能分析
      - 优缺点
  - 树表的查找
  - - 二叉排序树 (Binary Sort Tree）
    - - 二叉排序树定义
      - 二叉排序树的性质
      - 二叉排序树查找
      - 二叉排序树的插入
      - 二叉排序树的生成
      - 二叉排序树的删除
      - 平衡二叉树
  - 散列表的查找
  - - 散列表术语
    - 散列函数构造方法
    - - 直接定址法
      - 除留余数法
    - 处理冲突的方法
    - - 开放地址法
      - 链地址法
    - 散列表查找

查找

内容回顾：
在这里插入图片描述

概念

查找表是由同一类型的数据元素（或记录）构成的集合。由于"集合"中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
查找 – 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录），查找成功返回该记录信息或者位置，查找不成功则给出空记录或者空指针。
关键字：用来标识一个数据元素（或记录）的某个数据项的值。分为 主关键字(可唯一地标识一个记录的关键字) 和 次关键字(用以识别若干记录的关腱字)。
对查找表的操作：查询记录，检索属性，插入数据元素，删除数据元素。
查找表分类：
- 静态(仅查询)
- 动态(可插入，删除)
查找算法的评价指标 – 平均查找长度(关键字的平均比较次数) – ASL(Average Search Length)
查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的。为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为地加上某种确定的约束关系。

线性表的查找

顺序查找(线性)

应用范围：

顺序表或线性链表表示的静态查找表
表内元素之间无序

表示方法：

// 数据元素的类型定义
typedef struct {KeyType key; //关键字域......       //其他域
} ElemType;// 顺序表结构类型定义
typedef struct {ElemType *R; // 表基址int length; //表长
} SSTable; //Sequential Search Table//定义一个顺序表ST
SSTable ST;

算法：

在这里插入图片描述

// 算法7.1
int Search_Seq(SSTable ST, KeyType key) {// 如成功则返回位置信息，不成功返回0for(i=ST.length; i>=1; --i) {if (ST.R[i].key == key) return i;return 0;}
}

// 算法改1
int Search_Seq(SStable ST, KeyType key) {for(i=ST.length; ST.R[i].key != key; --i)if (i<=0) break;if (i>0) return i;else return 0;
}// 算法改2
inti Search_Seq(SStabl ST, KeyType key) {for(i=ST.length; ST.R[i].key != key&&i>0; --i);if (i>0) return i;else return 0;
}

上面的算法的每一次循序都需要进行两次比较，能否改进？

查找的值是否相等
i的值是否越界

改进：

把待查关键字 key 存入表头（"哨兵、“监视哨”) 从后往前个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。(如果找不到在表头[0]位置也一定会找到)。

当ST.length较大时，此改进能使进行一次查找所需的平均时间几乎减少一半。

在这里插入图片描述

// 改进算法7.2
int Search_Seq(SSTable ST, KeyType key) {ST.R[0].key = key;for (i=ST.length; ST.R[i].key != key; --i);return i;}
}

算法7.2时间效率分析：

在这里插入图片描述

时间复杂度：O(n)

查找成功时的平均查找长度，设表中各记录查找概率相等(注意这里是指的是查找成功时所以不算哨兵位置)

ASL_s(n)=(1 + 2 +…+ n)/n = (n+1)/2

空间复杂度：O(1) — 辅助空间用于哨兵位置

讨论

1 、记录的查找概率不相等时如何提高查找效率？

查找表存储记录原则按照查找概率高低存储：1 ）查找概率越高，比较次数越少；2 ）查找概率越低，比较次数较多。

2 、记录的查找概率无法测定日日何提高查找效率？

方法 – 按查找概率动态调整记录顺序．1 ）在每个记录中设一个访问频度域；2 ）始终保持记录按非递增有序的次序排列；3 ）每次查找后均将刚查到的记录直接移至表头。

优缺点：

优点：算法简单，逻辑次序无要求，且不同存储结构均适用。

缺点：ASL 太长，时间效率太低。

折半查找(对半/二分)

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

在这里插入图片描述

算法思路

非递归算法

设表长为n，low、high 和 mid 分别指向待查元素所在区间的上界、下界和中点， key 为给定的要查找的值．
初始时，令low = 1，high=n, mid=$\lfloor(low+high)/2\rfloor $
让 k 与 mid 指向的记录比较
- 若key == R[mid].key 查找成功
- 若key < R[mid].key, 则 high=mid-1
- 若 key > R[mid].key, 则 low=mid+1
重复上述操作，直至 low>high 时，查找失败

// 二分查找(非递归)
int Search_Bin(SSTabl ST, KeyType key) {low = 1;high = ST.length; // 初始化置区间值while (low <= high) { mid = (low + high) / 2;if (ST.R[mid].key == key) return mid; // 找到元素else if (ST.R[mid].key < key) {  // 缩小区间low = mid + 1; // 继续在后半区查找} else high = mid -1; // 继续在前半区查找}return 0; // 表中不存在待查元素
} // Search_Bin// 二分查找(递归)
int Search_Bin(SSTable ST, KeyType key, int low, int high) {if (low > high) return 0; // 查找不到时返回0mid = (low + high)/2if (ST.R[mid].key == key) return mid;else if (ST.R[mid].key > key) {Search_Bin(ST, key, low, mid-1);} else {Search_Bin(ST, key, mid+1, high);}
}

二分查找效率分析 - 判定树

在这里插入图片描述

平均查找长度ASL(成功时)

在这里插入图片描述

优缺点

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

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

分块查找(索引顺序查找)

条件

将表分成几块，且表或者有序，或者分块有序；若i < j，则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字。
建立"索引表"（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）。

查找过程：找38 --> 目标在索引48的块中 --> 顺序/折半在块内查找–> 找到38

性能分析

在这里插入图片描述

优缺点

优点：插入和删除比较容易，无需进行大量移动。

缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。

适用情况如果线性表既要快速查找又经常动态变化，则可采用分块查找。

在这里插入图片描述

树表的查找

动态查找表 – 几种特殊的树, 用来解决插入，删除频繁操作但需要维护表的有序性情况。

表结构在查找过程中动态生成对于给定值 key若表中存在，则成功返回；否则，插入关字等于 key 的记录

分类：

二叉排序树
平衡二叉树
红黑树
B- 树
B+ 树
键树

二叉排序树 (Binary Sort Tree）

又称为二叉搜索树、二叉查找树

二叉排序树定义

二叉排序树或是空树，或是满足如下性质的二叉树：

若其左子树非空，则左子树上所有结点的值均小于根结点的值；
若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；
其左右子树本身又各是一棵二叉排序树

二叉排序树的性质

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

如上图就是 3 12 24 37 45 53 61 78 90 100

二叉排序树查找

算法

在这里插入图片描述

typedef struct {KeyType key;  //关键字项infoType otherinfo;  //其他数据域
}ElemType;typedef stuct BSTNode {ElemType data;  //数据域struct BSTNode *lchild, *rchild;  //左右孩子指针
}BSTNode, *BSTree;BSTree T;  //定义二叉排序树T

在这里插入图片描述

BSTree SearchBST(BSTree T, KeyType key) {if (!T) || (key == T->data.key) return T; //表为空或者表不为空且找到了都返回一个指针T(BSTree类型)else if (key < T->data.key)   // 判断key在左右子树的位置return SearchBST(T->lchild, key); //继续在左子树上找else return SearchBST(T->rchild, key);  //继续在右子树上找
}//SearchBST

平均查找长度

在这里插入图片描述

二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。

在这里插入图片描述

总结：含有 n 个结点的二叉排序树的平均查找长度和树的形态有关

在这里插入图片描述

二叉排序树的插入

若二叉排序树为空，则插入结点作为根结点插入到空树中
否则，继续在其左、右子树上查找
- 树中已有，不再插入
- 树中没有
  - 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
插入的元素一定在叶结点

在这里插入图片描述

二叉排序树的生成

从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。
一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。(插入的结点均为叶子结点，故无需移动其他结点)
关键字的输入顺序不同，建立的不同二叉排序树。

二叉排序树的删除

从二叉排序树中删除一个结点，不能把以该结点为根的子树都删掉，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。(中序遍历二叉树得到递增有序的序列)

被删除的结点是叶子结点：直接删去该结点。
被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它（结点替换）。

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

以其中序前趋值替换之（值替换），然后再删除该前趋结点。前趋是左子树中最大的结点。

也可以用其后继替换之，然后再除该后继结点。后继是右子树中最小的结点。
总结图：