国家级精品课程—《数据结构与算法》 第10章检索 张铭、赵海燕、王腾蛟、宋国杰、高军 http:/www.ipk.pku.edu.cn/pkuipk/courselsig 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔:张铭 版权所有,转载或翻印必究
国家级精品课程—《数据结构与算法》 张铭、赵海燕、王腾蛟、宋国杰、高军 http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 北京大学信息科学与技术学院 “数据结构与算法”教学小组 本章主笔：张铭 ©版权所有，转载或翻印必究 第10章 检索
主要内容 基本概念 101线性表的检索 102集合的检索 103散列表的检索 小结 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。2
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 2 ◼ 基本概念 ◼ 10.1 线性表的检索 ◼ 10.2 集合的检索 ◼ 10.3 散列表的检索 ◼ 小结 主要内容
基本概念 检索 ■在一组记录集合中找到关键码 值等于给定值的某个记录,或 者找到关键码值符合特定条件 的某些记录的过程 检索的效率非常重要 口尤其对于大数据量 口需要对数据进行特殊的存储处理 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。3
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 3 基本概念 ◼ 检索 ◼ 检索的效率非常重要 ❑ 尤其对于大数据量 ❑ 需要对数据进行特殊的存储处理 ◼ 在一组记录集合中找到关键码 值等于给定值的某个记录，或 者找到关键码值符合特定条件 的某些记录的过程
提高检索效率的方法 预排序 ˇ算法在盐比较糞 隐樊樅蝎命栗‖忌缭盛 建立索引 檢黨时充分利用辅助索引信息 散列技术 ■牺侏适容窬嗯围查洵 面撮屯椽案瀣现重复关键码 当散列方法不适合于基于磁盘的应用程序 时,我们可以选择B树方法 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。4
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 4 提高检索效率的方法 ◼ 预排序 ◼ 建立索引 ◼ 散列技术 ◼ 当散列方法不适合于基于磁盘的应用程序 时，我们可以选择B树方法 ◼ 排序算法本身比较费时 ◼ 只是预处理（在检索之前已经完成） ◼ 检索时充分利用辅助索引信息 ◼ 牺牲一定的空间 ◼ 从而提高检索效率 ◼ 把数据组织到一个表中 ◼ 根据关键码的值确定表中记录的位 置 ◼ 缺点： ◼不适合进行范围查询 ◼一般也不允许出现重复关键码
平均检索长度(ASL) 关键码的比较:检索运算的主要操作 平均检索长度 Average Search Length) 口检索过程中对关键码的平均比较次数 口衡量检索算法优劣的时间标准 4SL=∠FC i=1 ■ASL是存储结福中;为检■第;找到第i个元 对象总数n的郾欻素的概赣所需的关键码值与 给定值的比较次数 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。5
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5 平均检索长度（ASL） ◼ 关键码的比较：检索运算的主要操作 ◼ 平均检索长度(Average Search Length) ❑ 检索过程中对关键码的平均比较次数 ❑ 衡量检索算法优劣的时间标准 ◼ ASL是存储结构中 对象总数n的函数 ◼ Pi 为检索第 i 个 元素的概率 ◼ Ci 为找到第 i 个元 素所需的关键码值与 给定值的比较次数 1 n i i i ASL PC = =