北京大学：《数据结构与算法》课程教学资源（实验班PPT课件）第九章 检索

数据结构与算法 第九章检索 任课教员:张铭 httpi//db.pku.edu.cn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究

数据结构与算法 第九章 检索 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究

第九章检索 令基本概念 9.1线性表的检索 9.2集合的检索 令9.3散列表的检索 9.4总结 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 第九章 检索 „ 基本概念 „ 9.1 线性表的检索 „ 9.2 集合的检索 „ 9.3 散列表的检索 „ 9.4 总结

基本概念 ■检索:在一组记录集合中找到关键码 值等于给定值的某个记录,或者找到 关键码值符合特定条件的某些记录的 过程 检索的效率非常重要 尤其对于大数据量 需要对数据进行特殊的存储处理 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 3

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 基本概念 „ 检索：在一组记录集合中找到关键码 值等于给定值的某个记录，或者找到 关键码值符合特定条件的某些记录的 过程 „ 检索的效率非常重要 „ 尤其对于大数据量 „ 需要对数据进行特殊的存储处理

基本概念(续) 预排序 排序算法本身比较费时 只是预处理(在检索之前已经完成) 建立索引 检索时充分利用辅助索引信息 牺牲一定的空间 从而提高检索效率 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 基本概念（续） „ 预排序 „ 排序算法本身比较费时 „ 只是预处理（在检索之前已经完成） „ 建立索引 „ 检索时充分利用辅助索引信息 „ 牺牲一定的空间 „ 从而提高检索效率

基本概念(续) ■散列技术 把数据组织到一个表中 根据关键码的值来确定表中每个记录的位置 n缺点 不适合进行范围查询 一般也不允许出现重复关键码 当散列方法不适合于基于磁盘的应用程 序时,我们可以选择B树方法 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 5

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 基本概念（续） „ 散列技术 „ 把数据组织到一个表中 „ 根据关键码的值来确定表中每个记录的位置 „ 缺点： „ 不适合进行范围查询 „ 一般也不允许出现重复关键码 „ 当散列方法不适合于基于磁盘的应用程 序时，我们可以选择B树方法

平均检索长度(ASL) 关键码的比较:检索运算的主要操作 平均检索长度( Average Search Length) 检索过程中对关键码的平均比较次数 衡量检索算法优劣的时间标准 ASl PC P为检索第个元素的概率 ci为找到第i个元素所需的关键码值与 给定值的比较次数 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 6

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 平均检索长度（ASL） „ 关键码的比较：检索运算的主要操作 „ 平均检索长度(Average Search Length) „ 检索过程中对关键码的平均比较次数 „ 衡量检索算法优劣的时间标准 1 n i i i A SL P C = = ∑ Pi 为检索第i个元素的概率 Ci 为找到第i个元素所需的关键码值与 给定值的比较次数

平均检索长度的例子 假设线性表为(abc)检索a、 b、c的概率分别为04、01、05 n顺序检索算法的平均检索长度为 04×1+01×2+05×3=21 即平均需要21次给定值与表中关键 码值的比较才能找到待查元素 北京大学信息学院 张铭编写 版权所有,转载或翻印必究

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 平均检索长度的例子 „ 假设线性表为（a, b, c）检索a、 b、c的概率分别为0.4、0.1、0.5 „ 顺序检索算法的平均检索长度为 0.4×1+0.1×2+0.5×3 = 2.1 „ 即平均需要2.1次给定值与表中关键 码值的比较才能找到待查元素

检索算法评估的几个问题 衡量一个检索算法还需要考虑 算法所需的存储量 算法的复杂性 ■■■ 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 8

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 检索算法评估的几个问题 „ 衡量一个检索算法还需要考虑 „ 算法所需的存储量 „ 算法的复杂性 „

9.1基于线性表的检索 9.1.1顺序检索 Q9.1.2二分检索 9.1.3分块检索 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 9

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 9.1 基于线性表的检索 „ 9.1.1 顺序检索 „ 9.1.2 二分检索 „ 9.1.3 分块检索

9.1.1顺序检索 针对线性表里的所有记录,逐个进 行关键码和给定值的比较。 若某个记录的关键码和给定值比较相 等,则检索成功; 否则检索失败(找遍了仍找不到)。 ■存储:可以顺序、链接 排序要求:无 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 10

北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 9.1.1 顺序检索 „ 针对线性表里的所有记录，逐个进 行关键码和给定值的比较 。 „ 若某个记录的关键码和给定值比较相 等，则检索成功 ； „ 否则检索失败(找遍了仍找不到)。 „ 存储：可以顺序、链接 „ 排序要求：无