数据结构 C语言版 教学课件 李云清 第09章_检索.pdfVIP

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