数据结构与算法第九章检索

《数据结构与算法第九章检索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第九章检索数据结构与算法第九章检索¢基本概念¢9.1线性表的检索任课教员：张铭http://db.pku.edu.cn/mzhang/DS/¢9.2集合的检索mzhang@db.pku.edu.cn¢9.3散列表的检索北京大学信息科学与技术学院网络与信息系统研究所¢9.4总结©版权所有，转载或翻印必究北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2基本概念基本概念（续）¢检索：在一组记录集合中找到关键码¢预排序值等于给定值的某个记录，或者找到¢排序算法本身比较费时关键码值符合特定条件的某些记录的¢只是预

2、处理（在检索之前已经完成）过程¢建立索引¢检索时充分利用辅助索引信息¢检索的效率非常重要¢牺牲一定的空间¢尤其对于大数据量¢从而提高检索效率¢需要对数据进行特殊的存储处理北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4基本概念（续）平均检索长度（ASL）¢散列技术¢关键码的比较：检索运算的主要操作¢平均检索长度(AverageSearchLength)¢把数据组织到一个表中¢检索过程中对关键码的平均比较次数¢根据关键码的值来确定表中每个记录的位

3、置¢衡量检索算法优劣的时间标准¢缺点：n¢不适合进行范围查询ASL=PC¢一般也不允许出现重复关键码∑iii=1¢当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法Pi为检索第i个元素的概率Ci为找到第i个元素所需的关键码值与给定值的比较次数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5北京大学信息学院张铭编写©版权所有，转载或翻印必究Page61平均检索长度的例子检索算法评估的几个问题¢假设线性表为（a,b,c）检索a、¢衡量一个检索算法还需要考虑b、c的概率分别为0.4、0.1、0.5¢

4、算法所需的存储量¢顺序检索算法的平均检索长度为¢算法的复杂性0.4×1+0.1×2+0.5×3=2.1¢...¢即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7北京大学信息学院张铭编写©版权所有，转载或翻印必究Page89.1基于线性表的检索9.1.1顺序检索¢9.1.1顺序检索¢针对线性表里的所有记录，逐个进行关键码和给定值的比较。¢9.1.2二分检索¢若某个记录的关键码和给定值比较相¢9.1.3分块检索等，则检索成功；¢否则检索失败(找遍了

5、仍找不到)。¢存储：可以顺序、链接¢排序要求：无北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10顺序检索算法“监视哨”顺序检索算法templateclassItem{¢检索成功返回元素位置，检索失败统一返回0;public:templateintItem(Typevalue):key(value){}SeqSearch(vector*>&TypegetKey(){returnk

6、ey;}//取关键码值;dataList,intlength,Typek){voidsetKey(Typek){key=k;}//置关键码inti=length;private://将第0个元素设为待检索值Typekey;//关键码域dataList[0]->setKey(k);//设监视哨stringother;//其它域while(dataList[i]->getKey()!=k)i--;};returni;//返回元素位置vector*>dataList;}北京大学信息学院张铭编写©版权

7、所有，转载或翻印必究Page11北京大学信息学院张铭编写©版权所有，转载或翻印必究Page122顺序检索性能分析顺序检索平均检索长度¢检索成功¢假设检索成功的概率为p，检索失败的概率假设检索每个关键码是等概率的，Pi=1/n为q=(1-p)n+1n−11n−1ASL=⋅pq+⋅+(n1)∑Pi·()ni−=−∑()ni2ni=0i=0n+1=pp⋅+(1−+)(n1)nn+12==∑ii=12=+−(1np)(1/2)¢检索失败假设检索失败时都需要比较n+1次（设置了一个¢（n+1)/2

8、北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14顺序检索优缺点9.1.2二分检索法¢将任一元素dataList[i].Key与给定值K¢优点：插入元素可以直接比较加在表尾Θ(1)¢三种情况：（1）Key=K，检索成功，返回dataList[i]¢缺点：检索时间太长Θ(n)（2）Key