数据结构第九章检索

《数据结构第九章检索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章检索任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所版权所有，转载或翻印必究9.1基本概念9.2线性表的检索9.3散列表的检索北京大学信息学院版权所有，转载或翻印必究Page基本概念检索：在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程检索的效率非常重要尤其对于大数据量需要对数据进行特殊的存储处理北京大学信息学院版权所有，转载或翻印必究Page基本概念（续）预排序排序算法本身比较费时只是预处

2、理（在检索之前已经完成）建立索引检索时充分利用辅助索引信息牺牲一定的空间从而提高检索效率北京大学信息学院版权所有，转载或翻印必究Page基本概念（续）散列技术把数据组织到一个表中根据关键码的值来确定表中每个记录的位置缺点：不适合进行范围查询一般也不允许出现重复关键码当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法北京大学信息学院版权所有，转载或翻印必究Page平均检索长度(ASL)关键码的比较检索运算的主要操作平均检索长度(AverageSearchLength)检索过程中对关键码需要执行的平均比较次数是衡量检索算法优劣的时间标准北京大学信息学

3、院版权所有，转载或翻印必究Page平均检索长度ASL是存储结构中对象总数n的函数，其定义为：Pi为检索第i个元素的概率Ci为找到第i个元素所需的关键码值与给定值的比较次数北京大学信息学院版权所有，转载或翻印必究Page平均检索长度假设线性表为（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次给定值与表中关键码值的比较才能找到待查元素北京大学信息学院版权所有，转载或翻印必究Page衡量一个检索算法还需要考虑算法所需的存储量算法的复杂性...北京大学信息学院

4、版权所有，转载或翻印必究Page9.1基于线性表的检索9.1.1顺序检索9.1.2二分检索9.1.3分块检索北京大学信息学院版权所有，转载或翻印必究Page9.1.1顺序检索针对线性表里的所有记录，逐个进行关键码和给定值的比较。若某个记录的关键码和给定值比较相等，则检索成功；否则检索失败(找遍了仍找不到)。存储：可以顺序、链接排序要求：无北京大学信息学院版权所有，转载或翻印必究Page顺序检索算法//代码9-1顺序检索的存储结构类型定义templateclassItem{public:Item(Typevalue):key(value

5、){}TypegetKey(){returnkey;}//获取关键码值;voidsetKey(Typek){key=k;}//设置关键码private:Typekey;//关键码域stringother;//其它域};vector*>dataList;北京大学信息学院版权所有，转载或翻印必究Page“监视哨”顺序检索算法位置0用来做监视哨,位置1到length用来存储实际元素检索成功时返回元素位置，检索失败时统一返回0;//代码9-2顺序检索算法templateintSeqSearch(vector

6、pe>*>&dataList,intlength,Typek){inti=length;//将第0个元素设为待检索值//保证while循环一定终止dataList[0]->setKey(k);//从后往前逐个比较while(dataList[i]->getKey()!=k)i--;returni;//返回元素位置}北京大学信息学院版权所有，转载或翻印必究Page顺序检索性能分析检索成功假设检索每个关键码是等概率的，Pi=1/n检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）北京大学信息学院版权所有，转载或翻印必究Page顺序检索性能分析（续）平

7、均检索长度假设检索成功的概率为p，检索失败的概率为q=(1-p)，则平均检索长度为（n+1)/2

8、根据三种比较结果区分出三种情况（以递增