彩色PDF讲义(9)

《彩色PDF讲义(9)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、chLength)¢检索过程中对关键码的平均比较次数¢衡量检索算法优劣的时间标准nASL=∑PCiii=1Pi为检索第i个元素的概率Ci为找到第i个元素所需的关键码值与给定值的比较次数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6平均检索长度的例子¢假设线性表为（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次给定值与表中关键码值的比较才能找到待查元素北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7检索算法评估的几个问题¢衡量一个检索算法还需要考虑¢

4、算法所需的存储量¢算法的复杂性¢...北京大学信息学院张铭编写©版权所有，转载或翻印必究Page89.1基于线性表的检索¢9.1.1顺序检索¢9.1.2二分检索¢9.1.3分块检索北京大学信息学院张铭编写©版权所有，转载或翻印必究Page99.1.19.1.1顺序检索顺序检索¢针对线性表里的所有记录，逐个进行关键码和给定值的比较。¢若某个记录的关键码和给定值比较相等，则检索成功；¢否则检索失败(找遍了仍找不到)。¢存储：可以顺序、链接¢排序要求：无北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10顺序检索算法templateclassItem{

5、public:Item(Typevalue):key(value){}TypegetKey(){returnkey;}//取关键码值;voidsetKey(Typek){key=k;}//置关键码private:Typekey;//关键码域stringother;//其它域};vector*>dataList;北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11“监视哨”顺序检索算法¢检索成功返回元素位置，检索失败统一返回0;templateintSeqSearch(vector*>&dataList,

6、intlength,Typek){inti=length;//将第0个元素设为待检索值dataList[0]->setKey(k);//设监视哨while(dataList[i]->getKey()!=k)i--;returni;//返回元素位置}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12顺序检索性能分析¢检索成功假设检索每个关键码是等概率的，Pi=1/nn−11n−1∑Pi·()ni−=−∑()nini=0i=0nn+1==∑i2i=1¢检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）北京大学信息学院张铭编写©版权所有，转载或翻印必究Page1

7、3顺序检索平均检索长度¢假设检索成功的概率为p，检索失败的概率为q=(1-p)n+1ASL=⋅pq+⋅+(n1)2n+1=pp⋅+(1−+)(n1)2=+−(1np)(1/2)¢（n+1)/2