数据结构 第七章教学课件

,单击此处编辑母版文本样式,第二级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,单击此处编辑母版标题样式,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据结构 第七章教学课件,第七章 查找,数据结构,目录,4,1,2,3,查找,静态查找表,动态查找表,哈希表,5,小结,第七章,查找,总体要求,掌握顺序查找、折半查找的实现方法；,掌握动态查找表（包括：二叉排序树、二叉平衡树、,B-,树）的构造和查找方法；,掌握哈希表、哈希函数冲突的基本概念和解决冲突的方法。,7.1,基本概念,1,、数据项,数据项是具有独立含义的标识单位，是数据不可分割的,最小单位,。,2,、数据元素,数据元素是由若干数据项构成的数据单位，是在某一问题中作为整体进行考虑和处理的,基本单位,。,数据元素,数据项,(,值,),数据项,(,名,),3,、关键字,关键字是数据元素中某数据项的值，用该值可以标识一个数据元素。,4,、查找,根据给定的某个值，在查找表中寻找一个其关键字等于给定值的数据元素。（成功或失败）,主关键字,次关键字,5,、查找表（,search table,）,由同一类型的数据元素构成的集合。查找表有如下四种基本操作：,(1),判定数据元素是否存在,(2),查找数据元素各属性值,(3),插入一个元素（在插入元素前表中不能存在有相同主关键字的记录）,(4),删除一个元素（在删除元素前表中必须存在该记录）,静态查找表,动态查找表,7.2,静态查找表,静态查找表一般以线性表表示。,线性表结构可以是顺序表结构，也可以是单链表结构。,7.2.1,顺序查找,从静态查找表的一端开始，将给定记录的关键字与表中各记录的关键字逐一比较。,找,64,public class ElemType ,T key;/,关键字域,/.,其它域,public ElemType(),key=null;,public ElemType(T data),key=data;,顺序查找的线性表数据元素定义如下：,public class SeqTable ,protected ArrayList elem;,/,数据元素存储空间基址,protected int length; /,表长度,publicSeqTable(T data,int n) ,/,用数组,data,中的前,n,个元素初始化顺序表,public int Search_Seq(T key),/,顺序查找,顺序查找的线性表结构定义如下：,【,算法,7-1】,初始化顺序表,publicSeqTable(T data,int n),elem=new ArrayList();,ElemType e;,for(int i=0;in;i+),e=new ElemType(datai);,elem.add(i, e);,length=n;,【,算法,7-2】,顺序查找,public int Search_Seq(T key) /,顺序查找,int i;,ElemType e=new ElemType(key);,elem.add(length,e); /“,哨兵”,for (i=0;elem.get(i)pareTo(key)!=0;+i) ;,if(ilength)return i;,else return -1;,找,60,监视哨,找到第,i,个记录,需比较的次数。,对含有,n,个记录的表，查找,成功,时：,第,i,个记录被,查找的概率。,1 2 3 4 5 6 7 8 9 10 11,顺序查找的平均查找长度：,ASL,=,P,1,+ 2,P,2,+ (n-1),P,n,-1,+n,P,n,假设每个记录的查找概率相等：,P,i,=1/,n,则：,ASL=1/n*(1+2+3.+n)=(n+1)/2,时间复杂度：,O(n,）,顺序查找优点：,算法简单，适应面广。,顺序查找缺点：,平均查找长度大。,7.2.2,折半查找（二分查找）,有序、顺序存储,折半查找,查找过程：,0 1 2 3 4 5 6 7 8 9 10,5 13 19 21 37 56 64 75 80 88 92,找,21,low,mid,high,0 1 2 3 4 5 6 7 8 9 10,5 13 19 21 37 56 64 75 80 88 92,找,63,low,high,mid,high low,【,算法,7-3】,折半查找,public int Search_Bin(T key),int low,high,mid;,low =0; high=length-1;/,置区间初值,while (low = high),mid = (low + high) / 2;if(pareTo(elem.get(mid).key)=0),return mid; /,找到待查元素,else if (pareTo(elem.get(mid).key)0),high = mid - 1;,else low = mid + 1;,return -1;,性能分析：,0 1 2 3 4 5 6 7 8 9 10,5 13 19 21 37 56 64 75 80 88 92,1,2,2,3,3,3,3,4,4,4,4,C,i,i,5,2,8,0,3,6,9,1,4,7,10,判定树,查找,37,比较次数,=,路径上的结点数,比较次数,=,结点,4,的层数,比较次数,树的深度,log,2,n, +1,查找成功：,查找不成功：,比较次数,=,路径上的内部结点数,比较次数 ,log,2,n, +1,平均查找长度,ASL,（成功时）：,第,j,层的每个结点要比较的次数,第,j,层,结点数,第,j,层要比较的总次数,折半查找,优点,：效率比顺序查找高。,折半查找,缺点,：只适用于,有序表,，限于,顺序存储结构,1,),1,(,log,1,),1,(,log,1,2,1,1,2,2,1,1,1,1,-,+,-,+,+,=,=,=,=,=,-,=,=,n,n,n,n,j,n,c,n,c,p,ASL,h,j,j,n,i,i,n,i,i,i,bs,7.3,动态,查找表,7.3.1,二叉排序树,二叉排序树上查找某关键字等于给定值的结点过,程，其实就是走了一条从根到该结点的路径。,30,80,20,90,85,40,35,88,32,50,35,比较的关键字次数,此结点所在层次数,最多的比较次数,树的深度,=,=,查找关键字：,35,二叉排序树的平均查找长度：,45,24,12,37,53,93,(45, 24, 53, 12, 37, 93),二叉排序树,插入的,n,个元素从一开始就有序，,变成单支树的形态！,此时树的深度为,n,; ASL = (,n,+ 1) / 2,查找效率与顺序查找情况相同。,含有,n,个结点的二叉排序树的平均查找长度和树的形态有关,形态比较均衡树的深度为：,log,2,n, + 1;,45,24,12,37,53,93,45,24,12,37,53,93,最坏情况,最好情况,有,n,个关键字的二叉排序树的平均查找长度,设每种树态出现概率相同，查找每个关键字也是等概率的，,则二叉排序树的,由此可见，在,随机,的情况下，二叉排序树的,ASL,和,log,2,n,是,等数量级,的。,问题：,如何提高形态不均衡的二叉排序树的查找效率？,平衡二叉树,解决办法：,做“,平衡化,”处理，即尽量让二叉树的形状均衡！,7.3.2,平衡二叉树,平衡二叉树,（,Balanced Binary Tree,），它或者是一棵空树，或者是具有如下特性的二叉排序树：,(1),左子树和右子树的深度之差的绝对值不超过,1,；,(2),它的左、右子树也分别是平衡二叉树。,平衡因子,=,该结点左子树与右子树的深度差,。任一结点的平衡因子只能取：,-1,、,0,或,1,；,希望二叉排序树的形态均匀,!,图,7.4,平衡与非平衡二叉树,平衡二叉树上任何结点的左、右子树的深度之差都不超过,1,，它的平均查找长度是和,log,2,n,+1,同数量级的。,非平衡 二 叉树,例：判断下列二叉树是否,AVL,树？,1,-1,0,0,-1,1,0,平 衡 二 叉 树,0,0,1,2,-1,0,假设在一棵 二叉排序树上插入一个新结点后造成失衡，则必须,重新调整树的结构,，使之恢复平衡。,我们称此调整平衡的过程为,平衡旋转,。,平衡旋转的类别,单右平衡旋转,单左平衡旋转,先左后右平衡旋转,先右后左平衡旋转,若在,C,的,左子树的左子树上插入,结点，使,C,的平衡因子从,1,增加,至,2,， 需要进行一次,顺时针旋转,。,(,以,B,为旋转轴）,A,若在,A,的,右子树的右子树上插入,结点，使,A,的平衡因子从,-1,改变,为,-2,，需要进行一次,逆时针旋转,。,(,以,B,为旋转轴）,2),单左平衡旋转：,C,1),单右平衡旋转：,C,B,C,A,B,A,若在,C,的,左子树的右子树上插入,结点，使,C,的平衡因子从,1,增加 至,2,， 需要,先进行逆时针旋转，,再顺时针旋转。,(,以插入的结点,B,为旋转轴）,B,3),先左旋转，后右旋转 平衡旋转：,C,A,A,B,C,C,A,B,若在,A,的,右子树的左子树上插入,结点，使,A,的平衡因子从,-1,改变为,-2,，需要,先进行顺时针旋转，再逆时针旋转。,(,以插入的结点,B,为旋转轴）,4),先右旋转，后左旋转 平衡旋转：,B,调整必须保证二叉排序树的特性不变,A,C,B,A,C,C,B,A,0,13,0,37,0,24,例：,请将下面序列构成一棵平衡二叉排序树：,(13, 24, 37, 90, 53),0,13,0,37,-1,13,0,24,-1,24,-2,13,0,90,-1,24,-1,37,0,53,1,90,-2,37,需要 单左平衡旋转,(,绕,24,逆转，,24,为根,),需要,RL,平衡,旋转（绕,53,先顺后逆）,-2,24,0,37,0,90,0,53,0,53,0,37,0,90,-1,24,7.3.3 B-,树,一种平衡的,多路查找树,一棵,m,阶的,B-,树的定义如下：,(1),树中每个结点最多有,m,棵子树；,(2),若根结点不是叶子结点，则至少有两棵子树；,(3),除根之外的所有非终端结点至少有,m/2,棵子树,(4),所有的非终端结点中包含下列信息数据,(n,p,0,k,1,p,1,k,2,p,2,.p,n,k,n,),k,i,是关键字,k,i,k,i+1,且 ，,p,i,为指向子树根结点的指针，且,p,i,所指子树中所有结点的关键字均小于,k,i+1,且大于,k,i,，,n,为关键字的个数。,一棵,m,阶的,B-,树的定义如下：,(5),所有的叶子结点都出现在同一层次上，并且不带信息。,一棵深度为,4,的,4,阶,B-,树,2,、,B-,树的查找,查找关键字：,47,B-,树的查找是从根结点出发，沿指针搜索结点（纵向查找）和在结点内进行顺序（或折半）查找（横向查找）两个过程交叉进行。,3,、,B-,树的插入,(a)3,阶,B-,树,(b),插入结点,60,(c),插入结点,90,(d),插入结点,30,4,、,B-,树的删除,3,阶,B-,树删除结点,61,3,阶,B-,树删除结点,50,B-,树插入、删除时易于平衡，外部查找效率高，适合于组织磁盘文件的动态索引结构。在文件系统中很有用。,7.4,哈希表,查找操作要完成什么任务？,待查值,k,确定,k,在存储结构中的位置,学过哪些查找技术？这些查找技术的共性？,顺序查找、折半查找、二叉排序树查找等。,由于记录的存储位置与关键字之间不存在确定的关系，故查找时要进行一系列对关键字的查找比较，查找效率由比较一次缩小的查找范围决定。,7.4.1,哈希表的概念,在记录的存储位置和它的关键字之间建立一个确定的对应关系 ，以 作为关键字为 的记录在表中的位置。,设哈希函数：,则构建的哈希表如下所示：,表示字符的次序，,A,的次序为,1,如果要查找给定关键字为“,Qian”,的记录，,H(Qian,）,=8,，即可从地址为,8,的表中取得该记录。,7.4.2,哈希表函数的构建,1,、直接定址法,哈希函数为关键字的线性函数，即：,H(key) = akey + b,（,a,，,b,为常数）,2,、数字分析法,对各个关键字的各个码位进行分析，取关键字中某些取值较分散的数字位作为哈希地址的方法。,3,、平方取中法,以关键字的平方值的中间几位作为存储地址。,4,、折叠法,将关键字分割成位数相同的几部分,(,最后一部分的位数可以不同,),，然后取它们的叠加和,(,舍去进位,),为哈希地址。,5,、除留余数法,除留余数法是用模（,%,）运算得到的方法，其哈希函数,H(key)=key %p,，,pm,其中,m,为存储单元数。,4,、折叠法,将关键字分割成位数相同的几部分,(,最后一部分的位数可以不同,),，然后取它们的叠加和,(,舍去进位,),为哈希地址。,14,7,14,14,7,0,14,散列地址,56,49,42,35,28,21,14,关键字,例：,p,21,p,= 8,散列地址,6 5 4 3 2 1 0,7.4.3,处理冲突,开放定址法（,Open Addressing,）,定义：就是一旦产生了冲突，即该地址已经存放了其它数据元素，就去寻找另一个空的散列地址。,若发生了第,i,次冲突，试探的下一个地址将增加,d,i,h,i,(key) = (h(key)+d,i,) mod TableSize ( 1 i TableSize ),线性探测、 二次探测、 双散列,d,i,= i,d,i,= i,2,d,i,= i*h,2,(key),1.,线性探测法（,Linear Probing,）,例,设关键词序列为,47,7,29,11,9,84,54,20,30,散列表表长,TableSize =11,，,散列函数为：,H(key) = key mod 11,。,用,线性探测法,处理冲突，列出依次插入后的散列表，,并估算查找性能。,ASL s=,（,4*1+2+3+4+5+8,）,/ 9 = 26/9,2.89,“一次聚集（,Primary Clustering,）”现象：需要经过很多次冲突才找到空位置。,关键词,(key),47,7,29,11,9,84,54,20,30,散列地址,h(key),3,7,7,0,9,7,10,9,8,冲突次数,0,0,1,0,0,3,2,4,7,例：设关键字序列为,47, 7, 29, 11, 16, 92, 22, 8, 3;,散列函数取为：,H(key) = key %11,。,2.,链接法,因查找成功的,ASL,s=,（,6+3*2,）,/ 9,1.3,7.4.4,哈希表的查找及其分析,平均查找长度（,ASL,）用来度量散列表查找效率。,另一方面,，关键词的比较次数，取决于产生冲突的多少。,影响产生冲突多少有以下三个因素,：,（,1,）散列函数是否均匀；,（,2,）处理冲突的方法；,（,3,）散列表的装填因子,。,主要分析后两者对,查找效率的影响。,可以证明，线性探查法的期望平均查找长度满足下列公式：,1.,线性探查法的查找性能,所有地址链表的平均长度定义成装填因子,，,有可能超过,1,。平均查找次数为：,2.,链接法的查找性能,装填因子是指散列表中已有的元素个数,n,与散列表空间大小,m,的比值，即,=n/m,。,本章小结,3,、,折半查找,又称为二分查找，它是一种效率较高的查找方法，时间复杂度为,O(log,2,n),但要求线性表必须采用顺序存储结构，且表中元素必须按关键字有序（升序或降序均可）。,1,、查找表按照实施的操作可以分为：,静态查找表和动态查找表,。,2,、,顺序查找,方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构，但是查找效率较低，时间复杂度为,O(n),。,4,、,二叉排序树,查找最好情况下的查找时间与折半查找是同数量级的，即,O(log,2,n),。,6,、,B-,树,是一种平衡的多路查找树，插入、删除时易于平衡，外部查找效率高。,5,、二叉排序树的查找效率与二叉排序树的形态有关，故希望二叉排序树的形态均匀，引入了,平衡二叉树,。,7,、通过哈希函数可以确定记录在表中位置和其关键字之间的关系,-,哈希表,。,