吉林大学数据结构课件 第八章 查找

第八章查找查找（亦称检索），简言之就是查表。一份表就是一个文件(表通常指小文件，文件一般指大表。一个大的文件通常被称为数据库)一份表包含N个记录，假定每个记录都对应一个关键词。一个查找算法查找或检索一张表的过程，就是对给定的变元K，去找出其关键词域之值等于K的那个记录；查找完成后有两种可能，或者查找成功，已确定出一个其关键词域之值为K的记录之所在，或者查找失败，即确定出关键词域之值为K的记录在表中已无处可寻。在查找失败后，有时还希望把一个关键词域之值为K的新记录插入到表中去，这样的过程被称为查找与插入操作下面我们简要介绍一下查找方法研究中的代表性工作：1946年，JohnMauchly首先提出了对半查找（又称为二分查找，折半查找）的思想。随后人们又在20世纪六、七十年代对其进行了深入研究，提出了一致对半查找算法，费波那契查找算法和插值查找算法等。1952年，A.I.Dumey描述了树插入算法的原始形式。之后人们又研究了二叉查找树、最优二叉查找树、近似最优二叉查找树、平衡树、2-3树、2-3-4树、红黑树、B树及其变形树等树查找方法，并将其广泛应用于数据库、操作系统等领域中。–1962年，两名俄国数学家G.M.Adelson-Velsky和E.M.Landis，对维持一株好的查找树的问题，发现了一个非常漂亮的解，即平衡树，许多学者也将其称之为AVL树，其中AV代表Adelson-Velsky，L代表Landis.1953年，H.P.Luhn提出了散列（Hashing，也译成杂凑、哈希）的思想。从1953年至今，散列技术一直是研究的热点，并被广泛应于数据加密等领域。1980年，C.S.Ellis提出将AVL树并行的思想。之后，直到2004年，人们才分别提出了AVL树、2-3树、红黑树、B树的并行算法，使树的查找、插入和删除等操作，实现了从单处理机上的顺序执行到多处理机上的并行执行的跨越。从上面的发展历程可看出，自上世纪50年代起至今查找技术研究已经历了半个世纪，在这段时间里，人们陆续提出了线性表查找、树结构查找、基于检索结构的查找、数字查找和散列查找等方法。每种查找方法的提出都有其历史背景，且其目的都是要提高查找方法的效率。一个查找算法，主要有以下四个方面的特性：内外有别分内查找和外查找。内查找系指内存能容纳一文件的全部N个记录的情形；外查找系指一文件所包含的记录总数N太大超出了内存的容量。静态动态静态查找时，表（或文件）的内容不变（即一个单纯的查找过程）；动态查找时，频繁地将新记录插入到表（或文件）中，或频繁地从表（或文件）中删除记录，即表（或文件）中的内容不断地变化。8.1顺序查找无序表的顺序查找从起点开始顺着往下查，一直找到正确的关键词为止顺序查找方法从线性表的起始结点开始，逐个检查其后继结点，或者找到关键词KKi，或者iN（i为表中记录的下标，N为线性表的元素个数）查找以失败告终。这个算法可以精确地阐述如下：算法S(N，R，K.i)/*给定包含N个记录R1，R2，…，RN，其对应的关键词分别为K1，K2，…，KN的一个表，S查找一个给定的变元K.这里假定N1.*/S1.[初始化]i1.S2.[比较关键词]如果KKi，则算法成功结束.S3.[推进i]ii1.S4.[iN?]若iN，则返回步骤S2；否则此算法以失败告终.▐序号元素341527861213212428304224查找24●查找成功的平均查找长度：SS●顺序查找的时间复杂度:O(n)＝i=1i=n∑Pi.Ci＝i=1i=n∑Ci1n＝i=1i=n∑i1n＝n+12算法Q(N，R，K.i)//算法Q与S基本相同，区别在于Q之表（或文件）的末尾添加了一个“虚拟”记录RN1.Q1.[初始化]置i1，并置KN1K.Q2.[比较关键词]如果KKi，则转到步骤Q4.Q3.[推进i]置ii1，并返回步骤Q2.Q4.[iN?]如果iN，则算法成功结束；否则以失败告终.//此时有iN1▐算法Q大约比算法S节省百分之二十的运行时间。算法Q还能更快吗？算法Q(N，R，K.i)Q1.[初始化]置i1.KN1K.Q2.[前进两步]置ii2.Q3.[Ki:K]若KiK，则转到步骤Q5.Q4.[Ki1:K]若Ki1K//此时KiK，则返回步骤Q2；否则置ii1.//此时Ki1K，找到了所需记录，其位置为i1Q5.[iN?]若iN，则算法成功结束；否则算法以失败告终.//此时iN1▐算法Q的运行时间比算法S约减少了百分之三十。把经常出现的元素（它的发生概率较大）自动向表的前端移动，把不经常出现的元素自动向表的后端移动，并称以该方式组织的表为自组织表.MOVE-AHEAD-ONEMOVE-TO-FRONT●顺序查找优缺点:优点:算法简单,且适用面广,对表的结构无任何要求.缺点:平均查找长度较大,特别n很大查找效率低.有序表的顺序查找算法T(N，R，K.i)/*设与表中记录R1，R2，…，RN对应的关键词满足K1K2…KN，算法T查找给定变元K，假定有一虚拟记录RN1，其关键词为KN1∞，显然有KN1K.*/T1.[初始化]置i1.KN1∞.T2.[比较]若KKi，则转到步骤T4.T3.[推进i]置iil，并返回步骤T2.T4.[KKi?]若KKi，则算法成功结束；否则算法以失败告终.▐对于成功查找，算法T的平均执行时间基本与算法Q相同；但当查找不成功时，它比算法Q大约快1倍，因为它能更快地确定一个记录不存在当然，如果只需对这个表查找一次，则进行顺序查找比对这个文件进行完整的排序要快K1K2…KN.在这样的表中，比较K和Ki后，我们有:KKi，[不必考虑子表Ri，Ri1，…，RN]KKi，[查找成功结束]KKi，[不必考虑子表R1，R2，…，Ri]使用不同的规则确定i，可得到不同的二分查找方法：对半查找、一致对半查找、斐波那契查找和插值查找等。从只考虑KKi和KKi两种情况，到考虑KKi，KKi和KKi等三种情况；每次比较K和当前被查之子表（文件）的中间记录的关键词Km算法B(N，R，K.i)给定其关键词在递增次序下（即K1K2…KN）包含N个记录R1,R2,,RN的一个表（或曰文件，表（或文件）的一部分亦被称为表（或文件）），本算法查找一个给定变元K.用两个指针s和e分别指出当前被查找之文件中最左边记录（或其关键词）的下标和最右边记录（或其关键词）的下标。算法B(N，R，K.i)B1.[初始化]s1.eN.B2.[取中点]（此时，若知道K在此文件中，则它满足KsKKe）如果es，则该算法以失败告终；否则，置i(s+e)/2（i为此文件的近似中点）。B3.[比较]如果KKi，则转步骤B4；如果KKi，则转步骤B5；如果K=Ki，则算法成功结束。B4.[调整e]ei1，并返回B2.B5.[调整s]si1，并返回B2.▐[例]假定有序表A中10元素的关键字序列为：12，23，26，37，54，60，68，75，82，96当给定值分别为96和58时进行对半查找。查找k=96时对半查找过程(4次比较成功）1234567891012232637546068758296s=1e=10e=1012232637546068758296s=1i=5e=1012232637546068758296s=6i=812232637546068758296s=e=10i=10e=1012232637546068758296s=9i=9查找k=58时对半查找过程(3次比较失败）e=10e=10123456789101223263754606875829612232637546068758296s=1i=512232637546068758296s=6i=812232637546068758296s=6e=512232637546068758296s=6e=7i=6[例]T（1，10）的二叉判定树每个圆圈结点表示关键词比较K:Ki45281369710﹤﹥54758296231226603768﹤﹤﹤﹤﹤﹤﹤﹤﹤==========12232637546068758296●二叉判定树二叉判定树，T（s，e）的递归定义如下：(1)当e-s+10时，T（s，e）为空树；(2)当e-s+10时，二叉判定树的根结点是有序表中序号为(e+s)/2的记录，根结点的左子树是与有序表Rs，Rs+1，…，R(e+s)/2-1相对应的二叉判定树，根结点的右子树是与有序表R(e+s)/2+1，R(e+s)/2+2，…，Re相对应的二叉判定树.●外部结点：树中所有结点的空指针都指向一个方形结点，则称这些方形结点为查找树的外部结点。●内部结点：树中原来那些圆形结点就叫做查找树的内部结点。●增长的二叉树：当原二叉树中的结点没有左子树形和右子树形时，就增加特殊的结点（称外部结点，树中原来的那些结点称内结点），由此生成的二叉树称为增长的二叉树。搜索K=96成功的情况：4528136971054758296231226603768搜索K=58失败的情况：4528136971054758296231226603768[例]T(1,10)查找成功的平均查找长度.4528136971054758296231226603768ASLSUCC＝(1*1+2*2+3*4+4*3)/10＝29/10＝2.9●查找失败的平均查找长度：4528136971054758296231226603768ASLUNSUCC＝En/(n+1)＝(3*5+4*6)/11＝39/11引理8.1如果算法B对N个记录的成功查找是等概率的，且不成功查找也是等概率的，则成功查找关键词的平均比较次数为SN1IN/N，不成功查找关键词的平均比较次数为UNEN/(N1)(其中IN，EN为T(1,N)的内、外路径长)已知外路径长总是比内路径长大2NSN1IN/N，(SN-1)*NIN，UNEN/(N1)，UN*(N+1)EN=IN+2N=SN*N+NSN(11/N)UN1引理8.1如果算法B对N个记录的成功查找是等概率的，且不成功查找也是等概率的，则成功查找关键词的平均比较次数为SN1IN/N，不成功查找关键词的平均比较次数为UNEN/(N1)(其中IN，EN为T(1,N)的内、外路径长)已知外路径长总是比内路径长大2N通过比较进行查找的一种“最好的”方式，是在所有具有N个内结点的二叉树中，具有极小外路径长的树。引理8.1如果算法B对N个记录的成功查找是等概率的，且不成功查找也是等概率的，则成功查找关键词的平均比较次数为SN1IN/N，不成功查找关键词的平均比较次数为UNEN/(N1)(其中IN，EN为T(1,N)的内、外路径长)引理8.2对半查找二叉判定树T(s,e)的高度是log2(e–s2).引理8.3设T(1,N)是N个内结点的二叉查找判定树，如不考虑外结点T(1,N)之高度为k，则T(1,N)之外结点均属于k或k1层.定理8.2在最坏情况下，算法B的关键词比较次数为log2(N1)，且其期望复杂性等于O(log2N).4528136971054758296231226603768一致对半查找–就对半查找算法而言，能否将其所用的指针数量减少，譬如仅使用三个（s，i和e）中的两个–使用当前的位置i和它的变化率δ；在每次不相等的比较之后，可以置iiδδδ/2（近似地）算法U(N，R，K.i)/*给定包含N个记录R1，R2，…，RN，其诸关键词为递增次序K1K2…KN的一张表，本算法查找变元K.若N为偶数，则算法有时将涉及一个虚拟关键词K0，K0被置成∞（或小于K的任意值）.我们假定N1.*/U1.[初始化]置iN/2，