第9章检索 >检索的基本概念 >线性表的检索 二叉排序树 >丰满树和平衡树 >最佳二叉排序树和 Huffman树 >B- 树 散列表检索
第9章 检索 ➢检索的基本概念 ➢ 线性表的检索 ➢最佳二叉排序树和Huffman树 ➢散列表检索 ➢二叉排序树 ➢B-树 ➢丰满树和平衡树
91检索的基本概念 检索是确定数据元素集合中是否存在数据元素 等于特定元素或是否存在元素满足某种给定特征的 过程。 要进行检索,必须知道待检索对象的特征,也 就是要知道待检索数据元素的关键字。 我们将能唯一标识一个数据元 素的关键字称为主关键字,而 其它关键字称为辅助关键字或 从关键字
9.1 检索的基本概念 检索是确定数据元素集合中是否存在数据元素 等于特定元素或是否存在元素满足某种给定特征的 过程。 要进行检索，必须知道待检索对象的特征，也 就是要知道待检索数据元素的关键字。 我们将能唯一标识一个数据元 素的关键字称为主关键字，而 其它关键字称为辅助关键字或 从关键字
静态检索表:检索的前后不会改变查找表的内容。 动态检索表:检索过程中可能会改变数据元素的存储 位置。 检索算法的评价标准:平均查找长度ASL( Average Search Length),也就是为确定某一结点在数据集 合中的位置,给定值与集合中的结点关键字所需进行 的比较次数 对于具有n个数据元素的集合,查找某元素成功的平 均查找长度为 ASL= ∑
静态检索表：检索的前后不会改变查找表的内容。 动态检索表：检索过程中可能会改变数据元素的存储 位置。 检索算法的评价标准：平均查找长度ASL（Average Search Length），也就是为确定某一结点在数据集 合中的位置，给定值与集合中的结点关键字所需进行 的比较次数。 对于具有n个数据元素的集合，查找某元素成功的平 均查找长度为： = n i Pi Ci 1 ASL＝
92线性表的检索 线性结构是数据元素间最常见的数据结构,基 于线性表的检索运算在各类程序中应用非常广氵 本节介绍三种在线性表上进行检索的方法,它们分 别是顺序检索、二分法检索与分块检索。为简化问 题,本节所介绍的检索方法均视为是基于静态查找 表上的操作
9.2 线性表的检索 线性结构是数据元素间最常见的数据结构，基 于线性表的检索运算在各类程序中应用非常广泛， 本节介绍三种在线性表上进行检索的方法，它们分 别是顺序检索、二分法检索与分块检索。为简化问 题，本节所介绍的检索方法均视为是基于静态查找 表上的操作
921顺序检索 从表的一端开始,顺序(逐个)扫描线性表, 依次将扫描到的结点关键字和给定值Key相比较,若 当前扫描到的结点关键字与Key相等,则检索成功; 若扫描结束后,仍未找到关键字等于Key的结点,则 检索失败。 存储结构:顺序存储或链式存储 本节介绍基于顺序表的顺序检索算法
9.2.1顺序检索 从表的一端开始，顺序（逐个）扫描线性表， 依次将扫描到的结点关键字和给定值Key相比较，若 当前扫描到的结点关键字与Key相等，则检索成功； 若扫描结束后，仍未找到关键字等于Key的结点，则 检索失败。 存储结构：顺序存储或链式存储 本节介绍基于顺序表的顺序检索算法