《数据结构 第2版 教学课件 ppt 作者 宗大华 陈吉人 《数据结构》课件-8》由会员分享，可在线阅读，更多相关《数据结构 第2版 教学课件 ppt 作者 宗大华 陈吉人 《数据结构》课件-8（24页珍藏版）》请在金锄头文库上搜索。
1、第8章 查找,1.,2.,3.,本章讲述内容：,4.,有关查找的基本概念；,各种静态查找算法 ；,基于二叉查找树的动态查找算法 ；,基于散列表的动态查找算法 。,8.1 查找的基本概念,.,查找是最为常见的、使用频率最高的、程序中耗费时间最多的一种数据操作，是实施数据读取、插入、修改、删除等重要操作的基础。,.,所谓“查找”，是要确定具有某个值的元素是否是某个集合中的一个成员的过程。,设集合T里有n条记录：(k1, I1)、(k2, I2)、(k3, I3)、(kn, In)。其中，k1、k2、kn是互不相同的n个关键字值，Ii是与ki相关联的记录信息(1in)。给定某个值K。“查找”就是要在
2、集合T中寻找出一个记录(kj, Ij)，使得有kj =K。查找成功的含义就是在T里找到一个关键字为kj的记录，使得kj=K；查找失败就是在T里找不到记录，使得kj=K。,.,能唯一确定一个记录的数据项，称为是记录的“主关键字”，简称“关键字”；不能唯一确定一个记录的数据项，称为记录的“次关键字”。,.,.,有n条记录的集合T是实施查找的基础。在讨论查找时，常把T称为“查找表”。若查找只为获取是否成功以及相应的记录信息，而不去改变查找表的内容，那么这种查找称为“静态查找”，这时的查找表称为“静态查找表”；若查找会伴随对数据元素的变更，那么这种查找称为“动态查找”，这时的查找表称为“动态查找表”。
3、,.,查找时，用给定值K与各记录的关键字ki(1in)进行比较。若Ci是查找第i个记录需要的比较次数，Pi是查找第i个记录的概率，则查找成功的“平均查找长度(ASL)”为：,ASL = pici,i=1,n,查找表有16个记录，关键字序列为：08、12、15、20 、24、29、32、35、38、44 、48、56、60、66、74、88。现给定K=38，用折半查找法找出哪个记录的关键字等于38。,8.2 静态查找算法,8.2.1 折半查找,若已经根据某种规则对静态查找表中的记录进行了某种排序，那么就可以设计出别的算法来对表元素进行较高效率的查找。,.,所谓“有序表”，是指已经将记录按照关键字
4、的大小顺序进行了排列(由小到大或由大到小)的一种查找表。基于有序表的折半查找算法，具有很高的查找效率。,.,折半查找的基本思想是以有序表的中间记录为准，将表分为左、右两个子表。用给定值K与中间记录的关键字比较，若结果相等，则查找成功；若给定值K小于中间记录的关键字，则取左子表继续这种查找；若给定值K大于中间记录的关键字，则取右子表继续这种查找。不断重复，直到查找成功，或无该记录存在而查找失败。,.,例：,08,12,15,20,24,29,32,35,38,44,48,56,60,66,74,88,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,序号：,初始状态：
5、,右子表,左子表,38,44,48,56,60,66,74,88,9,10,11,12,13,14,15,16,右子表,左子表,38,44,48,9,10,11,38,9,序号：,第1次比较后：,序号：,第2次比较后：,序号：,第3次比较后：,解：,(a),(b),(c),(d),“KArmid.key”时，表示要查找的记录应在当前查找区间的右子表里，因此保持原有high里的值，将low修改成mid+1 ；,“KArmid.key”时，表示要查找的记录应在当前查找区间的左子表里，因此保持原来low里的值，将high修改成mid1；,有序表的折半查找算法,算法8-1,算法描述,(1),算法分析,
6、(2),实施折半查找时，应把查找表顺序存储在一个一维数组里，数组元素的存储结构如图所示。,.,key,data,记录关键字,记录的其他数据项,Bin_Ar(Ar, n, K) low = 1; high = n; while (lowArmid.key) low = mid + 1; else return (mid); return (-1); ,.,算法中三个变量low、high、mid各自的作用是： low存放当前查找区间左端起始记录序号，初始为1； high存放当前查找区间右端终端记录序号，初始为n； mid存放当前查找区间中间记录的序号，其取值由公 式(low+high)/2通过取整
7、运算“ ”求得 。,.,算法的主体是while循环，在“low=high”时，循环一直进行。循环体里的任务是用给定值K与当前比较区间中间记录的关键字进行比较。比较有以下3种情况：,(a),(b),(c),“K=Armid.key”时，表示要查找的记录就是查找区间的中间记录。于是查找成功，返回记录的序号mid，循环结束。,有如下的有序表： 7 14 18 21 23 29 31 35 38 42 46 49 52 要查找关键字为14和22的记录。利用图示说明折半查找时变量low、high、mid的变化。,有序表的(递归)折半查找算法,算法8-2,Bin_Ar1(Ar, K, low, high)
8、 if (lowhigh) return (1 ); else mid = (low+high)/2 ; if (Armid.key = K) return (mid); if (Armid.key K) return Bin_Ar1(Ar, K, low, mid1); else return Bin_Ar1(Ar, K, mid+1, high); ,例：,07,14,18,21,23,29,31,35,38,42,46,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,初始：,low,mid,high,07,14,18,21,23,29,31,35,38,42,46
9、,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,第1次：,low,mid,high,07,14,18,21,23,29,31,35,38,42,46,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,第2次：,low,mid,high,07,14,18,21,23,29,31,35,38,42,46,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,第3次：,low,mid,high,07,14,18,21,23,29,31,35,38,42,46,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,第4
10、次：,low,mid,high,07,14,18,21,23,29,31,35,38,42,46,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,第2次：,low,mid,high,07,14,18,21,23,29,31,35,38,42,46,49,52,1,2,3,4,5,6,7,8,9,10,11,12,13,第3次：,low,mid,high,(a),(b),解：,8.2.2 分块查找,所谓“分块有序表”，是指这样的一种线性表，若把它顺序分为若干部分，每部分称为一“块”，那么每块里面的记录关键字虽然是无序的，但前面块里记录的最大关键字总是小于后面块里的最大关键
11、字。,.,.,比如，将图中所给线性表 划分成3块，,14,22,08,31,18,43,62,49,35,52,88,78,71,83,1,2,3,4,5,6,7,8,9,10,11,12,13,14,第1块,第2块,第3块,这3块里记录的关 键字排列都是无序的。但第一 块里记录的最大关键字小于第二块里记录，第二块里记录的最大关键字小于第三块里记录的最大关键字，因此该表是一个分块有序表。,.,分块查找基于分块有序表。基本思想是：按块的顺序，以每块中记录的最大关键字值建立起索引顺序表。查找时，用给定值K在索引顺序表里通过顺序查找确定出它可能在的块，然后再在该块里实施顺序查找，终获得最终结果：是成
12、功或是失败。,例：,基于图(a)的分块有序表，查找关键字为K=56的记录。,14,22,08,31,18,43,62,49,35,52,88,78,71,83,1,2,3,4,5,6,7,8,9,10,11,12,13,14,查找表：,31,62,88,5,5,4,1,6,11,key:,len:,addn:,索引顺序表,为该查找表建立索引顺序表，如图所示。,解：,每一个表目由三项组成： key该块里记录的最大关键字值； len该块里的记录数； addn该块第1个记录的序号。,对分块有序表实施分块查找时，把查找表存储在一维数组里，元素的存储结构如图(a)所示；,.,key,data,记录关键字
13、,记录的其他数据项,len,addn,块内最大关键字值,块的起始记录序号,key,块内记录个数(长度),基于分块有序表的分块查找算法,算法8-3,算法描述,(1),算法分析,(2),Blk_Ar(Ar, Ib, K, b) i = 1; while (iIbi.key) i+; if (ib) return (1); else j = Ibi.addn; while (jIbi.len+Ibi.addn1) return (1); else return (j); ,算法通过while循环对索引顺序表Ib进行顺序查找，该表里共有b个表目，查找就在1b之间进行。,.,.,根据块号从索引顺序表里得
14、到该块起始记录位置(Ibi.addn)，以及该块最后记录的位置(Ibi.addn+Ibi.len1)。通过while循环 在此范围查找所需的记录。即看哪一个记,录的关键字Arj.key与K相等。如果查到有相等关键字，就表示查找成功，变量j里是该记录在查找表Ar里的序号。,.,这时算法的查找效率将由两个部分确定：一是确定待查记录所在块时，对索引顺序表进行查找的平均查找长度Lb；一是在某块里进行查找的平均查找长度Lw。分块查找的平均查找长度ASLbs= Lb +Lw 。,把索引顺序表存储在一维数组里，元素的存储结构如图(b)所示。,(a),(b),从图中知道，根结点的值是13，它的左子树上有三个结
15、点，其值分别是10、2、12，它们都小于13；它的右子树上有四个结点，其值分别是25、20、31、29，它们都大于13。再随便来看其他任何一个结点，比如25。以它为根结点时，其左子树上有一个结点，值是20，小于25；其右子树上有两个结点，值分别是31、29，它们都大于25。可见，图(a)给出的二叉树，符合二叉查找树的条件，是一棵二叉查找树。,8.3 二叉查找树的动态查找,8.3.1 二叉查找树及查找算法,.,折半和分块查找建立在顺序存储结构上，对表进行插入操作、删除会感到不便和麻烦。它们属于静态查找的范畴。二叉查找树查找，不仅具有较高的查找效率，而且还便于在表中进行数据的插入和删除。它属于动态查找的范畴。,所谓“二叉查找树”，或是一棵空树，或是一棵满足下列条件的二叉树：,.,(1),(2),(3),若它的左子树非空，则左子树上所有结点的值都小于根结点的值；,若它的右子树非空，则右子树上所有结点的值都大于根结点的值；,它的左、右子树本身也是一棵二叉查找树。,图(a)所示为一棵二叉树，它是一棵二叉查找树吗？,例：,10,2,12,25,20,31,13,29,(a),解：,基于二叉查找树的查找算法,算法8-4,算法描述,(1),算法分析,(2),用二叉链表结构存储二叉查找树，实现查找容易。这时结点的存储结构如图所示。,.,Lchild,Rchild,记录关键字,右孩子指
