青岛大学数据结构与算法——第7章

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

  • 查找基本概念
  • 线性表的查找
  • 树表的查找
  • 哈希表的查找

二 查找基本概念

  • 哪里查找
  • 查找什么
  • 查找成功？
  • 查找算法评估：ASL

三 线性表的查找

3.1 顺序查找(线性查找)

  • 应用范围
  • Search_Seq
  • 改进(哨兵/监视哨)
  • 性能分析(时间复杂度(O(1)+空间复杂度(O(1)))

3.2 折半查找(二分或对分查找)

  • 概念：缩小一半
  • 折半查找(Search_Bin)

3.3 分块查找/索引顺序查找

  • 条件—分块/有序

四 树表的查找

  • 二叉排序树
  • 平衡二叉树AVL
  • B-树
  • B+树

五 哈希表的查找

5.1 示例

学生编号存入对应单元

5.2 散列表冲突

不同关键码映射同一个散列

5.3 散列构造

  • 直接定址法
  • 除留余数法

5.4 解决

  • 开放定址法：线性探测法、二次探测法、伪探测法
  • 链地址法(拉链法)
  • 双散列函数法
  • 建立公共溢出区

六 图示