第九章 查找 由于查找运算的使用效率很高，几乎在任意一个计算由于查找运算的使用效率很高，几乎在任意一个计算机系统软件和应用软件中都会涉及到，所以当问题所涉及机系统软件和应用软件中都会涉及到，所以当问题所涉及的数据量相当大时，查找方法的效率就显得格外重要。的数据量相当大时，查找方法的效率就显得格外重要。 在一些实事查询系统中尤其如此。因此，本章将系统在一些实事查询系统中尤其如此。因此，本章将系统地讨论各种查找方法，并通过对它们的效率分析来比较各地讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。种查找方法的优劣。7/21/20241第九章 查找9.1静态查找表9.2动态查找表9.3哈希表7/21/20242查找的基本概念查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（search table）。在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。7/21/20243对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。7/21/20244查找表操作及分类操作： (1)查询某个“特定的”数据元素是否在查找表中； (2)某个“特定的”数据元素的各种属性； (3)在查找表中插入一个数据元素； (4)从查找表中删去某个数据元素。分类： 若对查找表只作(1)和(2)两种操作，则称此类查找表为静态查找表。 若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。7/21/202459.1 静态查找表抽象数据类型静态查找表的定义：ADTStaticSearchTable数据对象D:D是具有相同属性的数据元素的集合。数据关系R:数据元素同属一个集合。基本操作P:Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit();ADTStaticSearchTable7/21/20246 一、顺序查找顺序查找的基本思想是：顺序查找的基本思想是：顺序查找的基本思想是：顺序查找的基本思想是：从线性表的一端开始，依次将扫描到得结点关键字和给定值K相比较。若当前扫描到得结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。顺序查找的存储结构要求：顺序查找的存储结构要求：顺序查找的存储结构要求：顺序查找的存储结构要求：顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作为存储结构时，扫描必须从第一个结点开始），顺序查找对数据在表中存放的先后次序没有任何要求。在表的组织方式中，线性表是最简单的一种。顺序查找是一种最简单的查找方式。7/21/20247顺序查找的线性表定义如下：typedefstructElemType*elem;intlength;每个结点包含两部分每个结点包含两部分内容：内容：Key 和和info其他其他信息信息7/21/20248（2）算法的实现：算法的实现：技巧：技巧：把待查关键字把待查关键字keykey存入表头或表尾（俗称存入表头或表尾（俗称“哨兵哨兵”），），这样可以加快执行速度。这样可以加快执行速度。例：例：若将待查找的特定值若将待查找的特定值keykey存入存入顺序表的顺序表的首部首部（如（如0 0号单元）号单元），则顺序查找的实现方案为：，则顺序查找的实现方案为：从后向前从后向前逐个比较！逐个比较！int Search_Seq( SSTable ST , KeyType key ) /在顺序表在顺序表STST中，查找关键字与中，查找关键字与keykey相同的元素；若成功，返回其位相同的元素；若成功，返回其位置信息，否则返回置信息，否则返回0 0 ST.elem0.key =key; /设立哨兵，可免去查找过程中每一步设立哨兵，可免去查找过程中每一步都要检测是否查找完毕，都要检测是否查找完毕，0单元被当作监视哨，用来判断表是否查单元被当作监视哨，用来判断表是否查找完毕（技巧）找完毕（技巧）。当。当n1000n1000时，查找时间将减少一半。时，查找时间将减少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i0; - -i) if(ST.elem i .key=key) return i;使使用用了了监监视视哨哨，在在查查找找过过程程中中，不不用用每每一一步步都都去去判判断断是是否否查查找找结结束束。0单单元元被被当当作作监监视视哨哨，用用来来判判断断表表是是否否查查找找完完毕毕（技技巧巧）。当当n1000n1000时时，查查找找时时间将减少一半。间将减少一半。找找到到：返返回回元元素素在在线线性表中的存储位置；性表中的存储位置；未找到：返回未找到：返回0。7/21/202410 查找效率怎样计算？查找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论平均查找长度：平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度(Average Search Length)。7/21/202411平均查找长度平均查找长度（ASLASL：average search lengthaverage search length）。）。其中：其中：n是文件记录个数；是文件记录个数；P Pi i是查找第是查找第i i个记录的查找概率（通常取等概率个记录的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i个记录时所经历的比较次数。个记录时所经历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义：物理意义：假设每一元素被查找的概率相同，则查找每假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为一元素所需的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 7/21/202412讨论讨论如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未考虑查找不成功的未考虑查找不成功的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元素的平均查找次数，还应当除以n（等概率），等概率），即：即： ASL（1n）/2 ，时间效率为时间效率为 O(n)7/21/202413u如果查找不成功的情况不能忽略时：ASL的计算步骤：查找成功的概率为1/2；那么查找成功时第i个记录的概率pi=1/2n，所以查找成功时的ASL=(ni+1)=(n+1)ni=112n4112_查找不成功的概率为1/2；所以查找不成功时的ASL=(n+1)所以所以所以所以：ASLss=3/4(n+1)7/21/202414顺序查找算法分析顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当n较大时，查找效率较低，不宜采用。7/21/202415二、有序表的查找(折半查找)折半查找(Birary search)也称为二分查找，它的查找速度比顺序查找快，但它要求数据在线性表中数据在线性表中数据在线性表中数据在线性表中按查找的关键字域有序排列。按查找的关键字域有序排列。按查找的关键字域有序排列。按查找的关键字域有序排列。设n个数据存放于数组r中，且已经过排序，按由小到大递增的顺序排列。采用二分查找，首先用要查找的给定值k与表正中间元素的关键值相比较，此元素的下标：7/21/202416比较结果有三种可能： 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界high=m-1，继续对数组的前半部分进行二分查找； 如果rm.keyk，说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界low=m+1，继续对数组的后半部分进行二分查找； 如果rm.key=k，查找成功，m所指的记录就是查找到的数据。7/21/202417重复上述过程，查找范围每次缩小1/2，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为key的记录不存在。二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为O(log2n)，对于较大的n显然较顺序查找速度快得多。7/21/202418查找查找23和和79的过程如下图：的过程如下图：mid=(low+high)/2不进位取整不进位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid7/21/202419折半查找的折半查找的c语言算法程序：语言算法程序：int Search_Bin( SSTable ST , int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if(STmid.key= = key) return (mid); /*查找成功查找成功*/ else if( key50n50n50n50时，可得近似结果时，可得近似结果时，可得近似结果时，可得近似结果ASLbs2(n+1)17/21/202422二分查找的性能分析具体例子(11个元素)查找过程可用判定树 描述查找成功时进行比较的 关键字个数最多不超过 树的深度log2n +1 当n较大时，平均查找长度为 ASLbs= log2( n+1) 163194710258117/21/202423三、静态树表的查找u 当有序表中各记录的查找概率相等时，按照判定树描述的查找过程来进行折半查找，性能最优； 有序表中各记录的查找概率不等时，二分查找性能不一定最优。u 可由具体例子说明。u 静态最优查找树和次优查找树方法可解决这一问题。7/21/202424例如例如关键字：ABCDEci：23123此时：ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变ci的值：21323则：ASL=20.2+10.3+30.05+20.3+30.15=1.9不是中间的比，而是根据概率值得不同具体选择。不是中间的比，而是根据概率值得不同具体选择。不是中间的比，而是根据概率值得不同具体选择。不是中间的比，而是根据概率值得不同具体选择。CADB12345pi：0.20.30.050.30.15E7/21/202425在概率不等的情况下：在概率不等的情况下：在概率不等的情况下：在概率不等的情况下：如何能够使平均查找长度最小？如何能够使平均查找长度最小？如何能够使平均查找长度最小？如何能够使平均查找长度最小？查找概率大的查找路径要短查找概率大的查找路径要短判定树该如何设计判定树该如何设计判定树该如何设计判定树该如何设计PH=wihini=1其中，wi=cpi，c为常量，pi为结点i的查找概率，hi为结点所在的层次，称PH值最小的判定二叉树为静态最优查找树。（这里只考虑查找成功的情况）如果只考虑查找成功的情况，则使查找性能达到最佳的判定树是其带全路径长度之和PH值取最小的二叉树7/21/202426 构建静态最优查找树的代价很高，这里介绍一种构建静态最优查找树的代价很高，这里介绍一种构建静态最优查找树的代价很高，这里介绍一种构建静态最优查找树的代价很高，这里介绍一种构造近似最有树的算法构造近似最有树的算法构造近似最有树的算法构造近似最有树的算法 次优查找树。次优查找树。次优查找树。次优查找树。二、次优查找树的构造二、次优查找树的构造二、次优查找树的构造二、次优查找树的构造已知一个序列：（rl,rl+1,，rh)，递增有序其中：rl.keyrl+1.keydata=k)return(b);7/21/202438二叉排序树查找递归算法if(kdata)return(search(bleft,k);elsereturn(search(bright,k);7/21/202439非递归算法btree*treesearch(btree*b,intk)btree*p;p=b;while(p!=NULL);if(pdata=k)return(p);elseif(kdata)p=pleft;elsep=pright;return(NULL);7/21/202440二叉排序树的插入二叉排序树是一种动态树表。特点是树的结构不是一次生成，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。7/21/202441二叉排序树的插入(续)从空树出发，经过一系列的查找插入操作之后，可生成一棵二叉排序树。设查找的关键字序列为45,12,53,3,37,50,98,1,8,43,60，则生成的二叉排序树如下中序遍历二叉排序树可得到一个关键字的有序序列。插入时，不必移动结点。45123533750988431607/21/202442二叉排序树的删除一般二叉树删除存在的问题。如何在二叉排序树上删除结点？设在二叉排序树上被删结点为*p,其双亲结点为*f，又*p是*f的左孩子。若*p为叶子结点，其左右子树为空。此时只需修改*f的指针。若*p只有左子树PL或只有右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树即可。7/21/202443二叉排序树的删除(续)若*p的左子树PL和右子树PR均不空。根据图示可知，在删去*p之前，中序遍历该二叉树得到的序列为CLCQLQSLSPPRF,在删去*p之后，仍应保持其它元素的相对位置不变，方法一是令*p的左子树为*f的左子树，而*p的右子树为*s的右子树；方法二是令*p的直接前驱（或直接后继）替代*p，然后再从二叉排序树中删去它的直接前驱（或直接后继）。7/21/202444二叉排序树的删除图示FPfpPLPRFPfpCLPRfCQSQLSLFCfcCLPRfQSQLSLc7/21/202445在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到所查找结点的路径；若查找不成功，则是从根结点出发走了一条从根结点到某个终端叶子结点的路径。与二分查找类似，和关键字比较的次数不超过二叉排序树的深度。但是，含有n个结点的二叉树不是唯一的，由于对其结点插入的先后次序不同，所构成的二叉树的形态和深度也可能不同。例如，下页图是按不同插入次序得到的两个二叉排序树。二叉排序树查找分析7/21/202446两个二叉排序树在查找失败的情况下，在这二个树上所进行的关键字比较次数分别为3和6次。7/21/202447二叉排序树查找分析(续)树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为log2n，最坏情况下查找时间为O(logn)，与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于n，最坏情况下查找时间为O(n)，与顺序查找属于同一数量级。为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树。7/21/202448平衡树平衡树(Balancedtree)也称为AVL树，是由阿德尔森维尔斯基和兰迪斯(Adelsonvelskiiandlandis)于1962年首先提出的。这是一种附加了一定限制条件的二叉树。我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（Balancefactor），所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是+1，0或1，即任一结点的左、右子树高度之差不超过1。如下页图所示，图中数字为该结点的平衡因子。7/21/202449平衡树平衡二叉树不平衡二叉树不平衡二叉树 7/21/202450假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加1，我们可能会遇到以下三种情况：(1)如果原来其左子树高度hl与右子树高度hr相等，即原来此结点的平衡因子等于0,插入新结点后将使平衡因子变成+1，但仍符合平衡树的条件，不必对其加以调整；如果原来hlhr，即原来此结点的平衡因子等于+1,插入新结点后将使平衡因子变成+2，破坏了平衡树的限制条件，需对其加以调整；如果原来hlhr，即原来此结点的平衡因子等于1，插入新结点后将使平衡因子变成0，平衡更加改善，不必加以调整。7/21/202451如果给平衡树某结点的右子树插入一个结点，且设此新结点使右子树的高度增加1，则也会遇到与之相对应的三种情况。以下页图所示的树为例，设原已有关键字为51，29，72，11和46这五个结点，原树符合平衡树条件，图中各结点旁所标数字为该结点的平衡因子。7/21/202452平衡树插入结点7/21/202453插入新结点破坏了平衡树条件的情况分为两类，仍以向左子树插入新结点为例，这两类情况分别如下页图（a）和(c)所示。图中矩形表示子树，矩形的高度表示子树的高度，带阴影线的方形则表示插入新结点后造成的子树高度加1，各结点旁所标数字为该结点的平衡因子。7/21/202454平衡树的调整图7/21/2024557/21/202456平衡树以二叉链表作为存储结构,每个结点还要增加一个平衡因子域。平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。在插入新结点时，当确定了新结点应插入的位置后，需向回寻找有关平衡因子变为+2或-2的祖先，如有这种结点，则取其中层数居最低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修改。7/21/202457B-树前面介绍的查找方法，均适用于查找存储在内存中的数据，统称为内查找方法，它们适用于较小的表，而对较大的、存储在外存储器上的文件就不合适了。B-树是一种多路平衡查找树，这是一种适用于外查找的方法的数据结构。B树的定义： 一棵m（m3）阶的B-树，或者为空树，或者是满足如下条件的m叉树： 7/21/202458(1)树中每个非终端结点至少包含以下数据项： （n,A0,K1,A1,K2,Kn,An） 其中，n为关键字总数，Ki（1in）是关键字，Ai是指向子树根结点的指针。关键字是递增有序的：K1K20)if(i=m)i=1;elsei+;/*i未到达表末端则后移一个单元进行线性探测，否则返回到表首端继续探测，直至找到待查关键字k或者遇到开放地址为止*/7/21/202481查找算法续if(Ai=0)Ai=k;return(i);7/21/202482例1设有一组关键字19,01,23,14,55,20,84,27,68,11,10,77，采用哈希函数：H（k）=kmod13。采用开放地址的线性探测法解决冲突，试在018的散列地址空间中，对该关键字序列构造散列表。解：依题意m=19，得到线性探测法对应的探查地址序列计算公式为：di=(H(k)+j)mod19;j=1,2,18其计算函数如下：H(19)=19mod13=6H(01)=01mod13=17/21/202483H(23)=23mod13=10H(14)=14mod13=1(冲突)H(14)=(1+1)mod19=2H(55)=55mod13=3H(20)=20mod13=7H(84)=84mod13=6(冲突)H(84)=(6+1)mod19=7(冲突)H(84)=(6+2)mod19=8H(27)=27mod13=1（冲突）H(27)=(1+1)mod19=2(冲突)7/21/202484H(27)=(1+2)mod19=3(冲突)H(27)=(1+3)mod19=4H(68)=68mod13=3(冲突)H(68)=(3+1)mod19=4(冲突)H(68)=(3+2)mod19=5H(11)=11mod13=11H(10)=10mod13=10(冲突)H(10)=(10+1)mod19=11(冲突)H(10)=(10+2)mod19=12H(77)=77mod13=12(冲突)H(77)=(12+1)mod19=137/21/202485例地址分配7/21/202486查找效率分析哈希表的查找效率仍以平均查找长度量度。其中平均查找长度为每个元素的查找长度之和除以所有元素的个数。比较次数取决于下列三个因素：哈希函数、处理冲突的方法和哈希表的装填因子。哈希表的装填因子定义为=表中填入的记录数/哈希表的长度最好在0.60.9之间。7/21/202487查找效率分析（续）线性探测再散列的哈希表查找成功时的平均查找长度为Snl(1+1/(1)/2随机探测再散列、二次探测再散列和再哈希的哈希表查找成功时的平均查找长度为Snrln(1)/链地址法处理冲突的哈希表查找成功时的平均查找长度为Snc1+/2哈希表在查找不成功时的讨论略7/21/202488查找的应用实例“口令”或“密码”的查找计算机病毒的检测技术在“电信通话记录”中的查找7/21/202489第九章 小结查找顺序查找二分查找分块查找树型查找平衡树散列法处理冲突的方法开放地址法链地址法7/21/202490练习题1若对大小为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列二种情况下分别讨论在等概率时的平均查找长度是否相同？（1）查找不成功；（2）查找成功。2画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。7/21/202491练习题3已知如下所示长度为12的表(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)试按表中元素顺序依次插入一棵初始为空的二叉排序树，请画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此表进行折半查找时查找成功时的平均查找长度。(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。7/21/202492练习题4.设关键字集合为27,49,79,5,37,1,56,65,83，散列函数为：H（k）=kmod7，散列表长度m=10，起始地址为0，分别用线性探测和链地址法来解决冲突。试画出对应的散列表。7/21/202493