《数据结构》课程教学资源：第八章 检索结构

第8章检索结构

1 第 8 章 检索结构

§8.1概述 §8.1.1检索的概念 ·检索也称査找 检索是指在数据元素(记录)集合中求出满足某给定条件的 记录 数据元素(记录)中确定某特定数据字段的值与给定值相匹 配的记录 ·关键字字段(简称关键字) 检索成功与不成功 在某此问题中,当检索不成功时要插入不存在的数据 记录,或在某种情况下删除所找到的记录 2

2 §8.1 概述 • 检索也称查找 – 检索是指在数据元素（记录）集合中求出满足某给定条件的 记录 – 数据元素（记录）中确定某特定数据字段的值与给定值相匹 配的记录 • 关键字字段（简称关键字） • 检索成功与不成功 • 在某此问题中，当检索不成功时要插入不存在的数据 记录，或在某种情况下删除所找到的记录 §8.1 .1 检索的概念

§81.1检索的概念 检索算法(方法) 按检索操作是否全部在内存进行: 内检索 ·外检索 按是否增删元素 静态检索 ·动态检索

3 • 检索算法（方法） : – 按检索操作是否全部在内存进行： • 内检索 • 外检索 – 按是否增删元素 • 静态检索 • 动态检索 §8.1 .1 检索的概念

§81.1检索的概念 检索算法(方法) 按是否进行比较操作 比较式检索 ·非比较式检索 按关键字是否变化 原词检索 ·变词检索

4 • 检索算法（方法） : – 按是否进行比较操作 • 比较式检索 • 非比较式检索 – 按关键字是否变化 • 原词检索 • 变词检索 §8.1 .1 检索的概念

§8.1.2检索结构 为了提高检索效率,要专门为检索操作设置数 据结构 若按数据元素集合中元素间结构关系分类 线性结构(含线性链结构) 线性索引结构 树形结构 散列(杂凑)结构

5 • 为了提高检索效率，要专门为检索操作设置数 据结构 • 若按数据元素集合中元素间结构关系分类 – 线性结构（含线性链结构） – 线性索引结构 – 树形结构 – 散列（杂凑）结构 §8.1 .2 检索结构

§8.1.2检索结构 按检索结构中数据元素是否会增加或减少分类 静态检索结构:操作中不增加或减少元素 动态检索结构:操作中可能增加元素或减少元素

6 • 按检索结构中数据元素是否会增加或减少分类 – 静态检索结构：操作中不增加或减少元素 – 动态检索结构：操作中可能增加元素或减少元素 §8.1 .2 检索结构

§8.13检索算法的时间与空间复杂 度分析 检索算法的空间复杂度分析 在现有结构上进行检索的算法 实现检索算法而构造专门的数据结构的算法 检索算法的时间复杂度分析 以关键字的比较次数为主度量算法的时间复杂度

7 • 检索算法的空间复杂度分析 – 在现有结构上进行检索的算法 – 实现检索算法而构造专门的数据结构的算法 • 检索算法的时间复杂度分析 – 以关键字的比较次数为主度量算法的时间复杂度 §8.1 .3 检索算法的时间与空间复杂 度分析

§8.13检索算法的时间与空间复杂 度分析 待査关键字的位置对算法本身而言是个随机量, 所以要综合测定算法的检索次数,需使用检索 次数的数学期望 ·将检索算法的检索次数的数学期望称为平均检 索长度ASL( Average Search Length) ·对检索成功(关键字在表中)情况其计算式为: ASL=∑pc i=1

8 • 待查关键字的位置对算法本身而言是个随机量， 所以要综合测定算法的检索次数，需使用检索 次数的数学期望 • 将检索算法的检索次数的数学期望称为平均检 索长度ASL（Average Search Length） • 对检索成功（关键字在表中）情况其计算式为： ASL= §8.1 .3 检索算法的时间与空间复杂 度分析 = n i i i p c 1

§8.13检索算法的时间与空间复杂 度分析 ·检索不成功的情况(关键字不在数据元素集 中),平均检索长度即为检索失败对应的比较 次数。 ·检索算法的总的平均检索长度应为检索成功与 失败两种情况的平均检索长度的数学期望

9 • 检索不成功的情况（关键字不在数据元素集 中），平均检索长度即为检索失败对应的比较 次数。 • 检索算法的总的平均检索长度应为检索成功与 失败两种情况的平均检索长度的数学期望。 §8.1 .3 检索算法的时间与空间复杂 度分析

§8.1.4检索算法的判定树 ·判定树中每个结点表示被查数据元素集中的一个元素 (常用元素编号表示) 从树根到某一结点的路径,就表示检索该结点所经历 的过程,路径上各结点为检索中测试(比较)过的结 点 树结点的各个儿子,表示从该结点起下步检索的各选 择分枝 对无儿子结点,表示检索过程进行到它(即与它比较) 后,不能继续进行,应终止

10 • 判定树中每个结点表示被查数据元素集中的一个元素 （常用元素编号表示） • 从树根到某一结点的路径，就表示检索该结点所经历 的过程，路径上各结点为检索中测试（比较）过的结 点 • 树结点的各个儿子，表示从该结点起下步检索的各选 择分枝 • 对无儿子结点，表示检索过程进行到它（即与它比较） 后，不能继续进行，应终止 §8.1.4 检索算法的判定树