国家级精品课程—《数据结构与算法》 第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 = =
平均检索长度的例子 假设线性表为(a,b,c)检索a、b、c的概 率分别为04、0.1、0.5 口顺序检索算法的平均检索长度为 0.4×1+0.1×2+05×3=2.1 口即平均需要21次给定值与表中关键码值的 比较才能找到待查元素 “十一五”国家级规划教材。张铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,B0.6。6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 6 平均检索长度的例子 ◼ 假设线性表为（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次给定值与表中关键码值的 比较才能找到待查元素
检索算法评估的几个问题 衡量一个检索算法还需要考虑 口算法所需的存储量 口算法的复杂性 “十一五”国家级规划教材。铭,王腾蛟,赵海燕,《数据结构与算法》,高教社,208.6。7
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 7 检索算法评估的几个问题 ◼ 衡量一个检索算法还需要考虑 ❑ 算法所需的存储量 ❑ 算法的复杂性 ❑
10.1基于线性表的检索 1011顺序检索 中1012二分检索 1013分块检索 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10.1 基于线性表的检索 ◼ 10.1.1 顺序检索 ◼ 10.1.2 二分检索 ◼ 10.1.3 分块检索
10.11顺序检索 针对线性表里的所有记录,逐个进行 关键码和给定值的比较。 口若某个记录的关键码和给定值比较相等, 则检索成功; 口否则检索失败(找遍了仍找不到)。 存储:可以顺序、链接 排序要求:无 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 10.1.1 顺序检索 ◼ 针对线性表里的所有记录，逐个进行 关键码和给定值的比较 。 ❑ 若某个记录的关键码和给定值比较相等， 则检索成功 ； ❑ 否则检索失败(找遍了仍找不到)。 ◼ 存储：可以顺序、链接 ◼ 排序要求：无
顺序检索算法 template class Item i private Type key; ∥关键码域 其它域 public: Item(Type value): key (value)t ype getKeyo{ return key;}∥取关键码值 void setKey( Type k){key=k;}∥置关键码 vector*> datalist “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 顺序检索算法 template class Item { private: Type key; //关键码域 //… //其它域 public: Item(Type value):key(value) {} Type getKey() {return key;} //取关键码值 void setKey(Type k){ key=k;} //置关键码 }; vector*> dataList;