🔑数据结构_第七章：查找

一、基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找；
查找表（查找结构）：查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成；
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是
唯一的。
对查找表的常见操作：
- 仅查找符合条件的数据元素——静态查找表——仅关注查找速度即可；
- 插入、删除某个数据元素——动态查找表——除了查找速度，还要注意插/删操作是否方便实现。
查找算法的评价指标：
- 查找长度：在查找运算中，需要对比关键字的次数称为查找长度；
- 平均查找长度(ASL,Average Search Length)：所有查找过程中进行关键字的比较次数之和的平均值。ASL的数量级反映了查找算法的时间复杂度。
- 评价一个查找算法的效率时，通常考虑查找成功/查找失败两种情况的ASL。
- 通常认为查找任何一个元素的概率都相同。

二、顺序查找

（一）算法思想

顺序查找，又叫线性查找，通常用于线性表。
算法思想：从头到 jio 挨个找 (或者反过来也OK)。就是遍历对比。

（二）代码实现

方法1

//要查找的顺序表
typedef struct{
	ElemType *elem;		//动态数组基址
    int TableLen;		//表的长度
}SSTable;

//顺序查找——查找表ST中关键字为key的元素，返回其数组下标
int Search_Seq(SSTable ST, ElemType key){
    //标记查到的元素下标
    int i;
    //循环遍历查找
    for(i=0; i<ST.TableLen && ST.elem[i]!=key; i++);
    //循环结束，查找成功则返回查到的元素的数组下标i，没查到则返回-1
    return i==ST.TableLen? -1 : i;
}

方法2

//查找表的0号元素默认不存储数据，查找时使其等于key，然后从尾到头遍历，查找失败则返回0
int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0]=key;
    int i;
    for(i=ST.Table; ST.elem[i]!=key; i--);
    return i;
}

（三）性能分析

ASL_成功 = (1+2+3+…+n)/n = (n+1)/2;

ASL_失败 = n+1;

时间复杂度为：O(n)。

（四）优化（对有序表）

三、二分查找（折半查找）

仅适用于有序的顺序表！！！

（一）算法思想

二分法，没什么好说的。

（二）代码实现

//待查找的有序表
typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;

//折半查找——从表L中查找等于key的数组元素，返回数组下标
int Binary_Search(SSTable L, ElemType key){
    //定义左中右三个位置的标识
    int low=0, high=L.TableLen-1, mid;
    //循环查找
    while(low<=hile){
        mid=(low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high=mid-1;
        else
            low=mid+1;
    }
    //当low>high时循环结束，未查找到，返回-1
    return -1;
}

（三）性能评估

四、索引查找（分块查找）

（一）算法思想

查找表里存储的元素为分块的规律，块有序，块内元素无序。
按照块的规律给查找表建立索引表，查找数据时先将数据与索引表对比，确定查找范围，再在查找表里按此范围顺序查找。
默认分块是按从小到大的顺序排列的。

//定义索引表
typedef struct{
    //最大关键字
    ElemType maxValue;
    int low, high;
    //int mid;		//折半查找需要的mid变量
}

//顺序表存储实际待查找元素
ElemType List[];

关键字先在索引表中查找：
- 可以顺序查找对比
  
  1.判断关键字是否小于索引表中第一个分块的maxValue；
  
  （1）小于，说明key就在该分块内，接下来去查找表中该分块的[low, high]区间内查找即可。
  
  （2）不小于，说明key在后面的分块内，那么向后找到下一个分块，重复执行步骤（1）（2）即可。
- 也可以折半查找
  
  1.初始化索引表：mid = (low + high) / 2;
  
  2.判断key和mid 的大小关系：
  
  key < mid
  
  high = mid - 1; mid = (low + high) / 2;
  
  此时如果low>high，那么直接跳到步骤3；
  
  重复步骤2；
  
  key > mid
  
  low = mid + 1; mid = (low + high) / 2; `
  
  此时如果low>high，那么直接跳到步骤3；
  
  重复步骤2；
  
  key = mid
  
  直接去当前mid所指的块内查找即可；
  
  3.说明key就在low所指的分块内，接下来去查找表中查找该分块对应的范围即可。
在查找表中查找

顺序遍历即可。
当索引表low > high时，查找元素必定在low所指分块内的原因：

（二）性能评估

1、查找效率分析——ASL

对于顺序查找索引表：

当有n个元素时，将其分为√n个块，每块有√n个元素，这样ASL会达到最小值：ASL=√n+1。
对于折半查找索引表：

不重要。。。
扩展与优化

五、二叉排序树的定义及运算

（一）概念

二叉排序树：

左子树上结点总是小于根，右子树上结点总是大于根。

即：左孩子 < 根结点 < 右孩子的二叉树，根据这个特点对其中序遍历，得到的序列一定是大小递增的序列。

（二）查找

//二叉排序树结点
typedef struct BSTNode{
    int data;//数据域
    struct BSTNode *lchild, *rchild;//左右孩子指针
}BSTNode, *BSTree;

//查找算法——在二叉排序树中寻找值为key的结点
//循环方式实现
BSTNode *BST_Search(BSTree T, int key){
    while(T!=NULL && key!=T->data){//若树空或者等于根节点值，则循环结束
        if(key < T->data)//小于
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}

//递归方式实现——王道官方
BSTNode BST_Search(BSTree T, int key){
    if(T==NULL)
        return NULL;
    if(T->data==key)
        return T;
    else if(key < T->data)
        return BSTSearch(T->lchild, key);//在左子树中找
    else
        return BSTSearch(T->rchild, key);//在右子树中找
}

//递归方式实现——自己写
BSTNode BST_Search(BSTree T, int key){
    if(T==NULL || T->data==key)
        return T;
    if(key > T->data)
        T=T->rchild;
    else
        T=T->lchild;
    Bst_Search(T, key);
}

（三）插入

若原二叉排序树为空，则直接插入结点；
否则，判断，若关键字k小于根结点值，则插入到左子树；若关键字k大于根结点值，则插入到右子树。

//王道官方——递归实现
//给二叉排序树插入k
int BST_Insert(BSTree &T, int k){
    //若原树为空或定位到了合适的插入位置，则以k为data创建结点插入
    if(T==NULL){
        T=(BSTree)malloc(sizeof(BSTNode));
        T->data=k;
        T->lchild=T->rchild=NULL;
        return 1;//返回1，插入成功
    }
    else if(k==T->data)//树中存在相同值结点，插入失败返回0
        return 0;
    else if(k < T->data)
        return(BST_Insert(T->lchild));
    else
        return(BST_Insert(T->rchild));
}

//给二叉排序树插入k——循环实现
int BST_Insert(BSTree &T, int k){
    //先判断树空，空则直接插入
    if(T==NULL){
        T=(BSTree)malloc(sizeof(BSTNode));
        T->lchild=T->rchild=NULL;
        T->data=k;
        return 1;
    }
    //不空，循环找位置插入：
    while(!T==NULL){
		if(k==T->data)
			//存在相同的数，插入失败，返回0
			return 0;
		else if(k < T->data)
        	T=T->lchild;
    	else
			T=T->rchild;
    }
    //找到了合适的位置，插入
	T=(BSTree)malloc(sizeof(BSTNode));
	T->lchild=T->rchild=NULL;
	T->data=k;
    //T->father->xchild=T
	return 1;
}

（四）二叉排序树的构造

设有序列str={......}，数据元素个数为n，以此构建二叉排序树：

void Creat_BST(BSTree &T, int str[], int n){
    T=NULL;
    for(int i=0; i<n; i++){
        BST_Insert(T, str[i]);
    }
}

同一序列，若数据元素顺序不同，构造出来的二叉树可能相同也可能不同！

（四）删除

分三种情况：

删除的是叶子结点，那么直接删即可；
删除的结点只有左子树或只有右子树，那么之间删除结点再让其左/右子树连上来即可；
删除的结点既有左子树又有右子树：

先找到目标元素的直接前驱或直接后继，用这个元素的值替换掉要删除元素的值；

再在其右子树中删除其直接前驱或直接后继即可。

（五）性能评估

查找的性能分析：

空间复杂度：
- 循环方法：O(1)；
- 递归方法：O(h)；//h为树的高度
时间复杂度：
- 最坏情况为树的高度：O(h)；
- 平均查找长度：O(log₂n+1);
查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。

（六）平衡二叉树

1、平衡二叉树的构造

定义：平衡二叉树(Balanced Binary Tree)，简称平衡树(AVL树)，树上任一结点的左子树和右子树的高度之差不超过1。
结点平衡因子 = 左子树高 - 右子树高。

在平衡二叉树中插入结点，有可能会导致不平衡，通常插入操作分为以下四种情况：

（1）LL情况

在左子树的左结点插入新结点：

（2）RR情况

（3）LR

（4）RL

（5）查找效率分析

2、平衡二叉树的删除

六、散列查找

（一）散列表（哈希表）

散列表 (Hash Table)，又称哈希表，是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关。
我们通过散列函数/哈希函数建立关键字与存储地址的联系。

若不同的关键字通过散列函数映射到同一个值，则称它们为同义词；
通过散列函数确定的位置已经存放了其他元素，则称这种情况为冲突。
处理冲突的方法之一——拉链法：

用拉链法（又称链接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中：
- PS：将链表变成有序链表，效率会进一步提高！

（二）查找逻辑

先用哈希函数计算关键字的对应存储地址，查找到后再去哈希表里查找，例如图中；

性能评估
- 查找成功
  
  总之，冲突越多，查找效率越低，而哈希函数越优秀，产生的冲突越少。
  
  理论上，散列查找的最优时间复杂度可达到O(1)。
- 查找失败
装填因子：

$α$ = 表中记录数 / 散列表长度

（三）常见哈希函数/散列函数

1、除留余数法

$H (k e y) = k e y$ ：

散列表长m，取一个不大于m但最接近或等于m的质数p。

一定得是质数，才能尽可能的让更多的元素分布均匀！

当然，考试标准答案是质数，但在实际业务场景中还得根据实际情况选择！

2、直接定址法

$H (k e y) = k e y$ 或 $H (k e y) = a \times k e y + b$ ：

其中，a和b是常数。这种方法计算最简单，且不会产生冲突。

它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

3、数字分析法

4、平方取中法

取关键字的平方值的中间几位作为散列地址。

具体取多少位要视实际情况而定。

这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

总之，散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

（四）常见冲突处理方法

1、拉链法

处理冲突的方法之一——拉链法：

用拉链法（又称链接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中：

PS：将链表变成有序链表，效率会进一步提高！

2、开放定址法

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

其数学递推公式为：
$H_{i} = (H (k e y) + d_{i})$
其中 $i = 0, 1, 2, \dots, k (k \leq m - 1)$ ， $m$ 表示散列表表长， $d_{i}$ 为增量序列， $i$ 可理解为“第 $i$ 次发生冲突”。

关于 $d_{i}$ 的确定有三种方法：

线性探测法—— $d_{i} = 0, 1, 2, \dots, m - 1$ ：

即发生冲突时，每次往后探测相邻的下一个位置是否为空。

空则存储在下位置，不空则重复检测下一个，直到存下为止。
- 缺点：线性探测法很容易造成同义词、非同义词的“聚集 (堆积)”现象，严重影响查找效率。
  
  产生原因——冲突后再探测一定是放在某个连续的位置。
平方探测法—— $d_{i} = 0^{2}, 1^{2}, (- 1)^{2}, 2^{2}, (- 2)^{2}, \dots, k^{2}, (- k)^{2}$ ：

又称二次探测法，其中 $k \leq \frac{m}{2}$ 。

非重点小坑：采用此方法处理时，前提条件是哈希表的表长必须为 $4 j + 3$ ，这样才能使得所有单元格都能被探测到！否则只会重复检测其中的某些位置！
- 查找：也是此方法查找即可。
伪随机序列法：

就是让 $d_{i}$ 等于一个你自己确定的具体序列。
总结
- 查找：进行查找时同样也是这样操作，直到遇到空位表示查找失败。
- ❗删除：若是直接删掉元素会导致空位出现从而影响查找，所以应该用自定义的删除标识标记此处为已删除！