数据结构查找算法

常用的一些数据结构查找算法，包括b树，b+树等，查找是在数据集合中寻找满足某种条件的数据元素的过程，本图希望对你有帮助。

查找

• 查找的基本概念
  • 在数据集合中寻找满足某种条件的数据元素的过程
  • 平均查找长度
    • • n为查找表中元素个数 Pi为查找第i个元素的概率，通常假设每个元素查找概率相同，Pi=1/n Ci是找到第i个元素的比较次数。
• 顺序查找法
  • 一般线性表的顺序查找
  • 有序表的顺序查找
• 折半查找法
  • 有序的顺序表 （数组）
• 分块查找法
  • 折半查找和顺序查找的一种改进方法 要求索引表是有序的，块内节点没有排序要求
    • 1、选取各块中的最大关键字构成一个索引表 2、①先对索引表进行折半查找或顺序查找，确定待查记录在哪一块中 ②已确定的块中用顺序法进行查找
• B树及其基本操作
  • B树（多路平衡查找树）
    • B树的阶（m）：B树中所有结点的孩子结点数的最大值
    • m阶B树
      • 树中每个结点至多有m棵子树（即至多含有m-1个关键字）
      • 若根结点不是终端结点，则至少有两棵子树
      • 除根节点外的所有非叶结点至少含有 ⌈m/2⌉ 棵子树 （即至少含有 ⌈m/2⌉-1 个关键字）
      • 所有的叶结点都出现在同一层次上，且不带任何信息
    • B树的高度
      • n个关键字、高度h、阶数m
  • B树的查找
  • B树的插入
    • 1、定位
    • 2、插入
  • B树的删除
    • 终端结点
    • 非终端结点
• B+树的基本概念
  • ⼀棵m阶的B+树需满⾜下列条件： 1）每个分⽀结点最多有m棵⼦树（孩⼦结点）。 2）⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有 棵⼦树。 3）结点的⼦树个数与关键字个数相等。 4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来。 5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。
• 对比B树与B+树
• 散列表
  • 基本概念
    • 散列表建立了关键字和存储地址之间的一种直接映射关系，把关键字映射成其对应地址的函数称为散列函数
    • 冲突
      • 散列函数把两个或两个以上的不同关键字映射到同一地址
    • 聚集（堆积）
      • 非同义词争夺一个地址
  • 构造方法
    • 直接定址法
    • 除留余数法
    • 数字分析法
    • 平方取中法
      • 取关键字的平方值的中间几位作为散列地址
    • 折叠法
  • 处理冲突的方法
    • 开放定址法
      • 容易产生聚集
      • 方法
        • 线性探测法
        • 平方探测法
        • 再散列法
        • 伪随机序列法
    • 拉链法（链接法，chaining）
      • 适用于经常进行删除和插入的情况
      • 将冲突的值放在线性链表中
      • 不会产生聚集
  • 散列查找及性能分析
    • 填装因子
      • 填装因子=表中记录数n/散列表长度m
• 字符串模式匹配
  • 串的定义
    • 零个或多个字符组成的有限序列
  • 串的存储结构
    • 定常顺序存储表示
    • 堆分配存储表示
    • 块链存储表示
  • 串的基本操作
  • 串的模式匹配
  • KMP