首页 数据结构

# 查找的基本概念

# 查找介绍

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

# 查找是否成功

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

# 查找目的

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

# 查找表的分类

  1. 静态查找表：
    1. 仅作查询操作的查找表
  2. 动态查找表
    1. 作插入和删除操作的查找表

# 查找算法评价指标

关键字的平均比较次数，也称为平均查找长度，ASL（Average Search Length）

# 线性表的查找

# 顺序查找（线性查找）

# 普通查找

  1. 每执行一次循环都要比较两次，一次比较值，一次比较索引是否越界
int Search-Seq(SSTable ST,KeyType key){
    for(int i = ST.length; ST.R[i].key != key; --i){
        if(i <= 0){
            break;
        }
        if(i > 0){
            return i;
        } else {
            return 0;
        }
    }
}

# 改进查找（增加哨兵）

  1. 在索引为 0 的位置存储要查找的结果 key
  2. 如果返回结果不为 0，则查找到，如果返回结果为 0，则查找失败
int Search_Seq(SSMTable ST,KeyType key){
    ST.R[0].key = key;
    for(int i = ST.length; ST.R[i].key != key; --i){
        return i;
    }
}

image-20230226194540999

# 时间效率分析（哨兵）

  1. 比较次数与 key 的位置有关
    1. 查找第 i 个元素，需要比较 n-i+1 次
    2. 查找失败，需要比较 n+1 次
  2. 时间复杂第：O(n)O(n)
    1. 查找成功时的平均查找长度，设表中各记录查找概率相等
    2. ASLS(n)=(1+2+...+n)/n=(n+1)/2ASL_S(n)=(1+2+...+n)/n=(n+1)/2
  3. 空间复杂度：一个辅助空间O(1)O(1)

# 折半查找（二分查找）

# 折半查找定义

  1. 每次将待查记录所在区间缩小一半（查找区间内的元素需要有序）
  2. 优点：效率比顺序查找高
  3. 缺点：只适合有序表，且限于顺序存储结构
// 循环查找
int Search_Bin(SSTable ST,KeyType key){
    int low = 1;
    int height = ST.length;
    while(low <= height){
        mid = (low + height) / 2;
        if(ST.R[mid].key == key){
            return mid;
        } else if(key < ST.R[mid].key){
            height = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return 0;
}
// 递归查找
int Search_Bin(SSTable ST,KeyType key,int low,int high){
    if(low < high){
        return 0;
    }
    mid = (low + high) / 2;
    if(key == ST.R[mid].key){
        return mid;
    } else if(key < ST.R[mid].key){
        Search_Bin(ST,key,low,mid - 1);
    } else {
        Search_Bin(ST,key,mid + 1,high);
    }
}

# 折半查找算法分析

# 性能分析 —— 判定树

  1. 查找成功：比较次数 = 节点的层数 = log⁡2n+1\log_2{n} + 1
  2. 查找不成功：比较次数 = 路径上的内部节点数 ≤log⁡2n+1\leq \log_2{n} + 1
  3. 平均查找长度：ASL=(1+2×2+4×3+4×4)÷11=3ASL=(1+2\times2+4\times3+4\times4)\div11=3

image-20230226201833471

  1. 圆形：内节点代表查找成功的情况
  2. 矩形：外节点代表查找不成功的情况

# 分块查找（索引顺序查找）

# 条件

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

查找过程：先确定待查记录所在块（顺序或折半查找），再在块内查找（顺序查找）

image-20230226203219623

# 分块查找性能分析

  1. 查找效率：ASL=Lb+LwASL=L_b+L_w
  2. ASL：ASLbs=log⁡2(n/s)+1+s/2ASL_{bs}=\log_2^{(n/s)+1}+s/2

# 树表的查找

# 二叉排序树

# 定义

  1. 二叉排序树（Binary Sort Tree）又称为二叉搜索树、二叉查找树
  2. 若其左子树非空，则左子树上所有节点的值均小于根节点的值
  3. 若其右子树非空，则右子树上的所有根节点的值均大于等于根节点的值
  4. 其左右子树本身又是一棵二叉排序树

# 性质

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

# 二叉排序树 —— 查找

# 思路

  1. 若查找的关键字等于根节点，成功
  2. 若小于根节点，查其左子树
  3. 若大于根节点，查其右子树
  4. 在左右子树上的操作类似

# 算法思想

  1. 若二叉排序树为空，则查找失败，返回空指针
  2. 若二叉排序树非空，将给定值 key 与根节点的关键字进行比较
    1. 若 key 等于 T->data.key，则查找成功，返回根节点地址
    2. 若 key 小于 T->data.key，则进一步查找左子树
    3. 若 key 大于 T->data.key，则进一步查找右子树

# 算法描述

BSSTree SearchBST(BSTree T,KeyType key){
    if(!T || key == T->data.key){
        return T;
    } else if(key < T->data.key){
        return SearchBST(T->lchild,key);
    } else {
        return SearchBST(T->rchild,key);
    }
}

# 查找算法分析

  1. 比较的关键字次数 = 次节点所在层数
  2. 最多比较次数 = 树的深度
  3. 含有 n 个节点的二叉排序树的平均查找长度和树的形态有关
    1. 最好情况：与折半查找判定树相同：O(log⁡2n)O(\log_2^n)
    2. 最坏情况：与顺序查找情况相同：O(n)O(n)

# 二叉排序树 —— 插入

# 规则

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

# 二叉排序树 —— 删除

# 规则

  1. 被删除的节点是叶子节点：直接删除该节点即可
  2. 被删除的节点只有左子树或者只有右子树，用其左子树或右子树替换它
  3. 被删除的节点既有左子树，又有右子树
    1. 以其中序前驱值替换之，然后再删除该前驱节点，前驱是左子树中的最大节点
    2. 中序遍历的后继节点来替换之，然后再删除该后继节点，后继是右子树中最小的节点

# 平衡二叉树

# 平衡二叉树的定义

  1. 平衡二叉树（blanced binary tree）
    1. 又称 AVL 树（Adelson-Velskii and Landis）
    2. 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树
      1. 左子树与右子树的高度之差的绝对值小于等于 1
      2. 左子树和右子树也是平衡二叉排序树
      3. 平衡因子 = 节点左子树的高度 - 节点右子树的高度

# 平衡调整的四种情况

image-20230227160237627

# 散列表的出擦找

# 散列表的基本概念

# 基本思想

  1. 记录的存储为止与关键字之间存在对应关系，hsah 函数
  2. 优点：查找效率高
  3. 缺点：空间效率低

# 散列方法

  1. 选取某个函数，依该函数按关键字计算元素的存储为止，并按此存放
  2. 查找时，由同一个函数对给定值计算地址，将 k 与地址单元中元素关键码进行比对，确定查找是否成功

# 散列函数

散列方法中使用的转换函数

# 冲突

不同的关键码映射到同一个散列地址

# 散列表的构造方法

# 直接定址法

  1. Hsah(key)=a×key+bHsah(key)=a\times key+b
  2. 优点：以关键码 key 的某个线性函数值为散列地址，不会产生冲突
  3. 缺点：要占用连续地址空间，空间效率低

image-20230227164714770

# 除留余数法

  1. Hash(key)=keymod  pHash(key)=key \mod p
  2. 技巧：设表长为 m，取p≤mp\leq m

image-20230227165331085

# 解决冲突问题

# 基本思想

有冲突时就寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入

# 开放定址法

# 线性探测法

  1. Hi=(Hash(key)+di)mod  mH_i=(Hash(key)+d_i)\mod m
  2. 一旦冲突就找下一个地址，直到找到空地址存入

# 二次探测法

image-20230227170136398

# 伪随机探测法

生成一个随机地址进行存入

# 链地址法

# 基本思想

相同的散列表地址的记录链成一单链表

image-20230227170515353

# 散列表的查找

  1. 给定 key 值
  2. 计算 H (key)
  3. 判断此地址是否为空
    1. 地址为空，查找失败
    2. 地址不为空，判断关键字 == key
      1. 不等于：按处理冲突方式计算
      2. 等于：查找成功
更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

Baozi 微信支付

微信支付

Baozi 支付宝

支付宝

Baozi 微信

微信