10-数据结构与算法-北京大学2008-张铭-检索

数据结构与算法第10章检索本章由张铭主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。第十章检索基本概念10.1线性表的检索10.2集合的检索10.3散列表的检索10.4总结“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念检索检索的效率非常重要尤其对于大数据量需要对数据进行特殊的存储处理在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。提高检索效率的方法预排序建立索引散列技术当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法排序算法本身比较费时只是预处理（在检索之前已经完成）检索时充分利用辅助索引信息牺牲一定的空间从而提高检索效率把数据组织到一个表中根据关键码的值确定表中记录的位置缺点：不适合进行范围查询一般也不允许出现重复关键码“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。平均检索长度（ASL）关键码的比较：检索运算的主要操作平均检索长度(AverageSearchLength)检索过程中对关键码的平均比较次数衡量检索算法优劣的时间标准1niiiASLPCASL是存储结构中对象总数n的函数Pi为检索第i个元素的概率Ci为找到第i个元素所需的关键码值与给定值的比较次数“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.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次给定值与表中关键码值的比较才能找到待查元素“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。检索算法评估的几个问题衡量一个检索算法还需要考虑算法所需的存储量算法的复杂性...“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。10.1基于线性表的检索10.1.1顺序检索10.1.2二分检索10.1.3分块检索“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。10.1.1顺序检索针对线性表里的所有记录，逐个进行关键码和给定值的比较。若某个记录的关键码和给定值比较相等，则检索成功；否则检索失败(找遍了仍找不到)。存储：可以顺序、链接排序要求：无“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。顺序检索算法templateclassTypeclassItem{private:Typekey;//关键码域//…//其它域public:Item(Typevalue):key(value){}TypegetKey(){returnkey;}//取关键码值voidsetKey(Typek){key=k;}//置关键码};vectorItemType*dataList;“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。“监视哨”顺序检索算法检索成功返回元素位置，检索失败统一返回0;templateclassTypeintSeqSearch(vectorItemType*&dataList,intlength,Typek){inti=length;//将第0个元素设为待检索值dataList[0]-setKey(k);//设监视哨while(dataList[i]-getKey()!=k)i--;returni;//返回元素位置}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。顺序检索性能分析检索成功假设检索每个关键码是等概率的：Pi=1/n检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）Piniinnniininin·()()01101121“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。顺序检索平均检索长度假设检索成功的概率为p，检索失败的概率为q=(1-p)（n+1)/2ASL(n+1)1ASL(1)21(1)(1)2(1)(1/2)npqnnppnnp“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。顺序检索优缺点优点：插入元素可以直接加在表尾Θ(1)缺点：检索时间太长Θ(n)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。10.1.2二分检索法将任一元素dataList[i].Key与给定值K比较三种情况：（1）Key=K，检索成功，返回dataList[i]（2）KeyK，若有则一定排在dataList[i]]前（3）KeyK，若右则一定排在dataList[i]后缩小进一步检索的区间“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二分法检索算法templateclassTypeintBinSearch(vectorItemType*&dataList,intlength,Typek){intlow=1,high=length,mid;while(low=high){mid=(low+high)/2;if(kdataList[mid]-getKey())high=mid-1;//右缩检索区间elseif(kdataList[mid]-getKey())low=mid+1;//左缩检索区间elsereturnmid;//成功返回位置}return0;//检索失败，返回0}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。关键码18low=1high=935123456789152251608893lowmidhigh1817第一次：l=1,h=9,mid=5;array[5]=3518第二次：l=1,h=4,mid=2;array[2]=1718第三次：l=3,h=4,mid=3;array[3]=18＝18“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二分法检索性能分析最大检索长度失败的检索长度是或在算法复杂性分析中logn是以2为底的对数其他底，算法量级不变）（1log2n）（1log2n）（1log2n151822517892134886093351756“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。二分法检索性能分析（续）成功的平均检索长度为：(n50)优缺点优点：平均与最大检索长度相近，检索速度快缺点：要排序、顺序存储，不易更新(插/删)11ASL(2)11log(1)12log(1)12jiininnnn“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。10.1.3分块检索顺序与二分法的折衷既有较快的检索又有较灵活的更改“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索思想“按块有序”设线性表中共有n个数据元素，将表分成b块•不需要均匀•每一块可能不满每一块中的关键码不一定有序但前一块中的最大关键码必须小于后一块中的最小关键码“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。索引表索引表各块中的最大关键码及各块起始位置可能还需要块中元素个数（每一块可能不满）索引表是一个递增有序表由于表是分块有序的“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索——索引顺序结构link:Key:012345678910111213141516172212139833424424486080744986530612224886556块内最大关键码块起始位置块内有效元素个数count:“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索性能分析分块检索为两级检索先在索引表中确定待查元素所在的块；•设在索引表中确定块号的时间开销是ASLb然后在块内检索待查的元素。•在块中查找记录的时间开销为ASLwASL(n)=ASLb+ASLw“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索性能分析(续2)假设在索引表中用顺序检索，在块内也用顺序检索当s=时，ASL取最小值，ASL=+1≈1ASL2bb1ASL2sw211ASL122212bsbsnssnnn“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索性能分析(续3)当n=10,000时顺序检索5,000次二分法检索14次分块检索100次如果数据块（子表）存放在外存时，还会受到页块大小的制约此时往往以外存一个Ｉ/Ｏ读取的数据（一页）作为一块“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索性能分析(续4)若采用二分法检索确定记录所在的子表，则检索成功时的平均检索长度为ASL=ASLb+ASLwlog2(b+1)-1+(s+1)/2log2(1+n/s)+s/2“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分块检索的优缺点优点：插入、删除相对较易没有大量记录移动缺点：增加一个辅助数组的存储空间初始线性表分块排序当大量插入/删除时，或结点分布不均匀时，速度下降“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。10.2集合的检索用位向量来表示集合对于密集型集合（数据范围小，而集合中有效元素个数比较多）01234567891011121314150011010100010100“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。例：计算0到15之间所有的奇素数奇数：素数：奇素数：11111111000000001111110000000000011101100000000013579111315024681012143571113219150468101214357111319150246810121413579111315357111323571113&=“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。例：集合的无符号数表示全集元素个数N=40的集合，集合{35,9,7,5,3,1}表示为0000000000000000000000000000100000000000000000000000001010101010不够一个ulong,左补0“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。10.3散列检索10.3.0散列中的基本问题10.3.1散列函数碰撞的处理