第八章：查找

这是一个关于第八章：查找的思维导图，涵盖了查找的基本概念、顺序查找、折半查找、分块查找、散列查找等重要知识点，适合用于课程学习、复习备考等场景，帮助读者深入掌握各种查找方法的原理、特点和应用。

第八章查找

• 分块查找（索引顺序查找）
  • 适用情况
    • 既适合于快速查找，又能适应动态变化的要求。
  • 查找思想
    • ①先查索引表（顺序／折半）
    • ②再进入块内顺序查找。
  • 查找特点
    • ①前提条件：查找表被分为若干字块。（数据分块存储）
    • ②重要要求：
      • 块间有序
      • 块内无序
    • ③建立索引表
      • 索引表特征
        • 索引表按关键字有序（由小到大）排列。
      • 索引表元素
        • 含有各块的最大关键字。
        • 含有各块中第一个元素的地址。
• 散列查找（哈希查找）
  • 基本概念
    • 查找表
      • 存储关键字的表
      • 长度为n
    • 散列函数（哈希函数）
      • H（key）称为哈希函数。
    • 散列地址（哈希地址）
      • 利用哈希函数计算出的存储位置称为哈希地址。
    • 散列表（哈希表）
      • ①散列表又称哈希表。 ②散列表是一种用哈希函数计算出的存储位置的数据结构 ③散列表其特点是数据元素的关键字与其存储地址直接相关。
      • 长度为m m≥n
    • 同义词
      • ①不同的关键字，通过散列函数，映射到同一个元素则称它们为同义词。 ②哈希地址相同的关键字称为同义词。
    • 冲突
      • 通过散列函数确定的位置已经存放了其他元素，则称这种情况为冲突。
  • 哈希查找思想
    • ①用哈希函数求出关键字key的哈希地址。
    • ②如果key的哈希地址对应哈希表中的存储单元有数据，则查找成功，读取该位置的数据即可。 ③如果key的哈希地址对应哈希表中的存储单元无数据，则查找失败。
  • 哈希函数构造方法
    • 构造目的
      • 构造哈希函数的目的：是使哈希地址尽可能均匀的分布在哈希表中，同时应使计算尽量简单，以节约计算时间。
    • 构造时考虑因素
      • ①执行速度
      • ②关键字的长度
      • ③散列表的大小
      • ④关键字的分布情况
      • ⑤查找频率
    • 构造方法
      • ①直接地址法
        • 方法
          • 直接地址法使用关键字的线性函数来计算哈希地址，所使用的哈希函数为H（key）＝a×key+b（a和b为常数）
        • 特点
          • 不会出现冲突，不同关键字的哈希地址不相同。
        • 适用
          • 该方法适用于关键字的分布基本连续的情况。
      • ②数据分析法
        • 方法
          • 数字分析法选用关键字中某些取值较分散的数字位构成哈希地址。
      • ③平方取中法
        • 方法
          • 平方取中法是取关键字平方的中间几位作为哈希地址。
      • ④折叠法
        • 方法
          • 折叠法是按照哈希表的地址码位数，将关键字分割成位数相同的几段，然后将这几部分相加得到的和即为哈希地址。
      • ⑤随机数法
        • 方法
          • 随机数法是取关键字的随机函数值作为哈希地址。
      • ⑥除留余数法⭐️
        • H（key）＝key%p（p为关键字的个数+1）
        • m是哈希表长度，P为不大于m但最接近于m或等于m的质数。
  • 处理冲突的方法
    • （1）链地址法
      • 主要思想
        • ①链地址法的主要思想是将关键字为同义词的记录存放在同一个单链表中。 ②没有单链表的存储空间写空符号。 ③一共需要哈希函数求余的数个单链表
      • 平均查找长度
        • （成功）平均查找长度
          • 查找每个关键字成功过程中对比关键字的总次数／关键字个数
        • （失败）平均查找长度
          • 哈希表每个单元格查找为空过程中对比关键字的总次数／哈希函数中对几求的余
      • 查找成功长度
        • ①根据哈希（散列）函数算出某个关键字的哈希地址。
        • ②找到关键字的哈希地址在哈希表中对应的位置
        • ③（1）在此位置往下和单链表每个元素比较一次，找到了key，则查找成功。（比较次数为此单链表第一个元素开始到key的总数。）
        • ④计算在③中找关键字key时比较关键字的次数，即为查找长度。
      • 查找失败长度
        • ①根据哈希（散列）函数算出某个关键字的哈希地址。
        • ②找到关键字的哈希地址在哈希表中对应的位置
        • ③（1）这个位置位置为空，则查找失败。（比较次数为0次） ③（2）在此位置往下和单链表每个元素比较一次未找到，则查找失败。（比较次数为单链表元素个数）
        • ④计算在③中找空比较关键字的次数，即为查找长度。
    • （2）再哈希法
      • 主要思想
        • 当存储某个记录发生冲突时，先算h1，若h1还冲突再算h2，直到某个hk不再冲突为止。
    • （3）开放定址法
      • 方法
        • 线性探测再散列
          • k个关键字，最少探测：k（1+k）／2
          • 关键字的存放
            • ①根据哈希（散列）函数算出某个关键字的哈希地址。
            • ②找到关键字的哈希地址在哈希表中对应的位置。
            • ③（1）如果对应的位置中没有存储数据，则将关键字存入此区域。 ③（2）如果对应的位置中已经有了数据，则将关键字从此位置开始往后找，填到第一个空白处。
          • 关键字的查找长度
            • 平均查找长度
              • （查找成功）平均查找长度
                • 查找每个关键字成功过程中对比关键字的总次数／关键字个数
              • （查找失败）平均查找长度
                • 哈希表每个单元格查找为第一个空白格过程中对比关键字的总次数／哈希函数中对几求的余
            • 查找成功长度
              • ①根据哈希（散列）函数算出某个关键字的哈希地址。
              • ②找到关键字的哈希地址在哈希表中对应的位置
              • ③（1）这个位置找到了key，则查找成功。 ③（2）在此位置有关键字，但不是key，则从这个位置开始，一直往右找，直到找到了key，则查找成功。
              • ④计算在③中找关键字key时比较关键字的次数，即为查找长度。
            • 查找失败长度
              • 空白处的判断也算一次比较
              • ①根据哈希（散列）函数算出某个关键字的哈希地址。
              • ②找到关键字的哈希地址在哈希表中对应的位置
              • ③（1）这个位置为空白，则查找失败。（比较次数为1次） ③（2）在此位置有关键字但不是key，往右和有元素的格子里每个元素比较一次，最后没找到key，找到了第一个空白，则查找失败。（比较次数为计算出的存储位置开始到第一个空白格的总个数。）
              • ④计算在③中找空白处时比较关键字的次数，即为查找长度。
        • 二次探测再散列（平方探测法）
          • 关键字的存放
            • ①根据哈希（散列）函数算出某个关键字的初始哈希地址。
            • ②找到关键字的哈希地址在哈希表中对应的位置。
            • ③（1）如果对应的位置中没有存储数据，则将关键字存入此区域。 ③（2）如果对应的位置中已经有了数据，则计算关键字新的哈希地址h1＝（初始哈希地址+di）%哈希表长度 如果h1还冲突就计算h2，直到找到空白处存入数据为止。
  • 影响冲突的因素
    • ①采用的哈希函数
    • ②采用的处理冲突的方法
    • ③哈希表的填满程度
  • 使用哈希表要解决好的问题
    • ①采用好的哈希函数。所选函数应该尽可能的使得计算出的存储地址均匀的分布在哈希表中，所选函数应尽可能简单，以节约计算时间。
    • ②制定一个好的处理冲突的方法。以便关键字之间发生冲突时，能够很好的处理，有规律的查询到相关单元。
  • 平均查找的时间复杂度
• 折半查找（二分查找）
  • 适用情况
    • ①适合静态查找。 ②使用静态查找表。（线性表中有序的顺序表） ③每次将待排序序列长度缩短一半。
  • 查找思想
    • ①求三初始值
      • 设置low和high初始值 low＝1 high＝表尾元素下标
    • ②比较值
      • m＝（low+high）／2 将m对应下标的值和key值作比较。
    • ③找新区
      • key＜m，左边作为新区域（小左），high＝m-1 key＞m，右边作为新区域（大右）， low＝m+1 key＝m，找到了，m即为找的位置。
    • ④确定三新值
      • low更新／high更新 m＝（low+high）／2
    • ⑤重复②③④，直到找到／或high＜low为止
  • 查找算法
    • low＝1； high＝ST.length； while（low＜＝high） ｛ m＝（low+high）／2； if（k＝＝ST.elem［m］.key）return m; else if（k＜ST.elem［m］.key）high＝m-1; else low＝m+1; ｝ return 0;
  • 时间复杂度
  • 查找特点
    • 通过构造判定树进行查找
      • 构造过程
        • 以初始m作为根节点，并且分出左右子树，然后再找左右子树的根结点和左右子树。
      • 构造特性
        • 别名
          • ①折半查找判定树是平衡二叉树。
        • 结点
          • 折半查找判定树左子树结点数k，右子树结点树k或k+1
          • 折半查找判定树只有最后两层可能出现叶子结点
        • 查找长度
          • 折半查找判定树中某结点的查找长度就是该结点对应在树中的层数。
          • （成功）平均查找长度
            • n个结点，查找成功的关键字有n个。
            • 每个结点所在的层次数之和／结点个数
          • （失败）平均查找长度
            • n个结点，查找失败的区域有n+1个
            • ［（每个虚拟结点所在的层次数-1）的和］／（结点个数+1）
              • 虚拟结点是：每个已知结点都变换成度为二的结点这个过程中添加出的结点就是虚拟结点
• 顺序查找（线性查找）
  • 适用情况
    • ①适合静态查找。 ②使用静态查找表。（线性表中的顺序表）
      • 静态查找表顺序表的定义
        • SSTable ST；
      • 静态查找表顺序表中元素表示
        • 地址
          • ST.elem［i］（元素地址）
            • i＝0，第0分量不储存数据，在保留。
          • ST.elem［i］.key（元素中关键字地址）
        • 表长
          • ST.length（表长度）
            • length＝n时，需分配n+1个结点。
  • 查找思想
    • ①在下标为0的元素里设置哨兵
    • ②从后到前查找
    • ③循环条件无需判断下标是否越界
  • 查找算法
    • for（i＝ST.length；i＞＝1；--i） if（ST.elem［i］.key＝＝k）return 1； return 0；
    • for（i＝ST.length；i＞＝1&&ST.elem［i］.key！＝K；--i）； if（i＞0）return i； else return 0；
    • ST.elem［0］.key＝K； for（i＝ST.length；ST.elem［i］.key！＝k；--i）; return i；
  • 查找特点
    • 被查元素
      • 被查找元素有序或无序都可以。
    • 平均查找长度
    • 时间复杂度
    • 时间复杂度
• 基本概念
  • 概念
    • 查找→查找表→关键字
      • 查找
        • 查找就是指在查找表中确定一个关键字等于给定值的数据元素／记录的过程。
      • 查找表
        • ①用于查找的数据集合称为查找表。 ②它由同一类型的数据元素（此时的这个数据元素包含多个数据项，也叫做记录）组成。
      • 关键字（key）（唯一性）
        • 用于数据元素中唯一标识该元素的某个数据项的值。
  • 类型和放向
    • 类型
      • 静态查找
        • 只需要查找操作。
      • 动态查找
        • 除了查找，还需要插入删除的操作。
    • 方向
      • 从前往后查找
      • 从后往前查找
  • 查张长度
    • 查找长度
      • 在查找中，对比关键字的次数。
    • 平均查找长度（ASL）
      • 衡量查找算法效率的主要标准⭐️
      • 平均查找长度与哈希表长度无关
      • 分类
        • （查找成功）的平均查找长度（和查找表中关键字有关）
          • 所有查找成功的过程中进行关键字比较次数的平均值。 （查找每个关键字成功过程中对比关键字的总次数／关键字个数
        • （查找失败）的平均查找长度（和哈希函数有关）
          • 所有查找失败的过程中进行关键字比较次数的平均值。 （查找为空（空指针）／查找第一个空白格（空区域）过程中对比关键字的总次数／（哈希函数中求余的值）
    • ASL的数量级反映了查找算法的时间复杂度