第八章-查找-数据结构.ppt

单击此处编辑母版标题样式,第八章 查找,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,第,八,章 查找,第八章 查找,知 识 点,查找的基本概念,三种基本查找方法：顺序查找、二分查找和分块查找,树型查找的基本概念和查找算法,散列法、散列函数冲突的基本概念和解决冲突方法,难 点,二叉排序树查找,平衡树及平衡树的调整,第八章 查找,要 求,熟练掌握以下内容：,三种基本查找方法的基本思想和算法,二叉排序树查找的基本思想和算法,散列法基本思想、散列函数的常用构造方法及解决冲突方法,了解以下内容：,平衡树及平衡树的调整,B-,树查找,第八章 查找,第八章目录,8.1,查找的基本概念,8.2,基本查找方法,8.3,树型查找,8.4,散列法,8.5,应用举例及分析,小 结,习题与练习,第八章 查找,8.1,查找的基本概念,查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。,在计算机中，被查找的数据对象是由同一类型的记录构成的集合，可称之为查找表（,search table,）。,在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（,key,）。,第八章 查找,对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。,查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数的平均值，作为衡量查找算法好坏的依据。,返回,第八章 查找,8.2.1,顺序查找,顺序查找,(,Sequential search),也称为线性查找，是采用线性表作为数据的存储结构，对数据在表中存放的先后次序没有任何要求。,顺序查找是最简单的查找方法，它的基本思想是：查找从线性表的一端开始，顺序将各单元的关键字与给定值,k,进行比较，直至找到与,k,相等的关键字，则查找成功，返回该单元的位置序号；如果进行到表的另一端，仍未找到与,k,相等的关键字，则查找不成功，返回,0,作为查找失败的信息。,第八章 查找,顺序查找的线性表定义如下：,#,define MAXITEM 100 /*,最多项数*,/,struct,element,keytype,key;,Elemtype,data;,;,typedef struct sqlist,MAXITEM;,这里,keytype,和,ElemType,可以是任何相应的数据类型，如,int,、,float,或,char,等，在算法中我们规定它们缺省是,int,类型。,第八章 查找,顺序查找算法,int sequsearch,(,sqlist,r,int,k,n),/*n,为线性表,r,中元素个数*,/,i=1,while(ri.key!=k&in),i=0;,return(i);,第八章 查找,顺序查找算法分析,此函数的主要运算时间是用于循环语句逐单元进行比较判断,ri.key,是否等于,k,，,因此顺序查找的速度较慢，最坏的情况查找成功需比较,n,次，最好的情况是比较,1,次，如果对每个关键字进行查找的概率相等，则查找成功所需的平均比较次数为,(,n+1)/2,，,而查找失败则需比较,(,n+1),次，时间复杂度为,O,（,n,）。,顺序查找的优点是算法简单、适应面广，且不要求表中数据有序。缺点是平均查找长度较大，特别是当,n,较大时，查找效率较低，不宜采用。,第八章 查找,8.2.2,二分查找,二分查找,(,Birary,search),也称为折半查找，它的查找速度比顺序查找快，但它要求数据在线性表中按查找的关键字域有序排列。,设,n,个数据存放于数组,r,中，且已经过排序，按由小到大递增的顺序排列。,采用二分查找，首先用要查找的给定值,k,与表正中间元素的关键值相比较，此元素的下标 。,第八章 查找,比较结果有三种可能：,如果,rm.keyk,，,说明如果存在欲查找的元素，该元素一定在数组的前半部分，查找范围缩小了一半，修改查找范围的的上界,high=m-1,，,继续对数组的前半部分进行二分查找；,如果,rm.keyk,，,说明如果存在欲查找的元素，该元素一定在数组的后半部分，查找范围缩小了一半，修改查找范围的的下界,low=m+1,，,继续对数组的后半部分进行二分查找；,如果,rm.key=k,，,查找成功，,m,所指的记录就是查找到的数据。,第八章 查找,重复上述过程，查找范围每次缩小,1/2,，当范围不断缩小，出现查找范围的下界大于上界时，则查找失败，确定关键字为,key,的记录不存在。,二分查找是一种效率较高的算法，最好的情况是第一次比较即找到所查元素，即使一次比较没有找到，也把进一步查找的范围了缩小一半。与此类似，每比较一次均使查找范围减半，故最坏的情况所需比较次数为,O(,logn,),，对于较大的,n,显然较顺序查找速度快得多。,第八章 查找,二分查找算法,int binsearch,(,sqlist,r,int,k,n),int,i,low=1,high=n,m,find=0;,/*low,和,high,分别表示查找范围的起始单元下标和终止单元下标，,find,为查找成功的标志变量*,/,while(low=high&!find),m=(low+high)/2;,if(krm.key),第八章 查找,二分查找算法续,low=m+1;,else,i=m;,find=1;,if(!find),i=0;,return(i);,第八章 查找,8.2.3,分块查找,分块查找又称为索引顺序查找，是顺序查找方法的另一种改进，其性能介于顺序查找和二分查找之间。,分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但块与块之间必须按关键字大小有序排列，即前一块中的最大关键字值小于后一块中的最小关键字值。,还需要建立一个索引表，索引表中的一项对应于线性表中的一块，索引项由键域和链域组成，键域存放相应块的最大关键字，链域存放指向本块第一个结点和最末一个结点的指针。索引表按关键字值的递增顺序排列。,第八章 查找,分块查找的算法分两步进行，首先确所查找的结点属于哪一块，即在索引表中查找其所在的块，然后在块内查找待查的数据。由于索引表是递增有序的，可采用二分查找，而块内元素是无序的，只能采用顺序查找。如果块内元素个数较少，则不会对执行速度有太大的影响。,例如线性表中关键字为,:9,22,12,14,35,42,44,38,48,60,58,47,78,80,77,82,其索引如图,8.1,所示。,第八章 查找,图,8.1,线性表与索引表,第八章 查找,索引表的定义,struct indexterm,keytype,key;,int,low,high;,;,typedef struct indexterm,indexMAXITEM;,这里的,keytype,可以是任何相应的数据类型，如,int,、,float,、或,char,等，在算法中，我们规定,keytype,缺省是,int,类型。,第八章 查找,分块查找算法,int blksearch,(,sqlist,r,index,idx,int,k,bn,),/*,bn,为块的个数*,/,int,i,high=,bn,low=1,mid,j,find=0;,while(low=high&!find),/*,二分查找索引表*,/,mid=(low+high)/2;,if(k,idx,mid.key),low=mid+1;,第八章 查找,分块查找算法续,else,find=1;,if(find=1),i=,idx,mid.low;,j=,idx,mid.high;,else if(low,bn,),/*k,小于索引表内最大值*,/,第八章 查找,分块查找算法续,i=,idx,low.low;,j=,idx,low.high;,while(ij),i=0;,return(i);,返回,第八章 查找,8.3.1,二叉排序树查找,将原始数据表示成二叉排序树，树的每个结点对应一个记录，则可利用此二叉排序树进行类似于二分查找思想的数据查找，这也是一个逐步缩小查找范围的过程。这种查找方法称为树型查找,。,基本思想：查找过程从根结点开始，首先将它的关键字与给定值,k,进行比较，如果相等，则查找成功，输出有关的信息；如果不等，若根结点关键字大于给定值,k,，,向左子树继续查找，否则向右子树继续查找。,向子树查找又是树型查找，先以子树的根结点数据与,k,进行比较，如果不相等又转向它的左或右子树继续查找。,第八章 查找,树型查找是一种递归的查找过程。,在二叉排序树上查找关键字为,k,的结点，成功时返回该结点位置，否则返回,NULL,，,递归函数如下：,btree,*search(,btree,*b,int,k),if(b=NULL),return(NULL);,else,if(b-data=k),return(b);,第八章 查找,二叉排序树查找递归算法,if(kdata),return(search(b-left,k);,else,return(search(b-right,k);,第八章 查找,非递归算法,btree,*,treesearch,(,btree,*b,int,k),btree,*p;,p=b;,while(p!=NULL);,if(p-data=k),return(p);,else if(kdata),p=p-left;,else p=p-right;,return(NULL);,第八章 查找,在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根结点到所查找结点的路径；若查找不成功，则是从根结点出发走了一条从根结点到某个终端叶子结点的路径。与二分查找类似，和关键字比较的次数不超过二叉排序树的深度。,但是，含有,n,个结点的二叉树不是唯一的，由于对其结点插入的先后次序不同所构成的二叉树的形态和深度也可能不同。例如，图,8.2,是按不同插入次序得到的两个二叉排序树。,第八章 查找,图,8.2,两个二叉排序树,在,查找失败的情况下，在这二个树上所进行的关键字比较次数分别为,3,和,6,次。,第八章 查找,二叉排序树查找分析,树型查找最坏情况时，需要的查找时间取决于树的高度，当二叉排序树接近满二叉树时，其高度为,log,2,n,，,最坏情况下查找时间为,O(log n),，,与二分查找是同样数量级的；当二叉排序树为只有一个端结点的所谓“退化树”时，其高度等于,n,，,最坏情况下查找时间为,O(n),，,与顺序查找属于同一数量级。,为了保证树型查找有较高的查找速度，我们希望该二叉树接近满二叉树，也就是希望二叉树的每一个结点的左、右子树高度尽量接近平衡，即使按任意次序不断地插入结点，也不要使此树成为退化树,。,第八章 查找,8.3.2,平衡树,平衡树,(,Balanced tree),也称为,AVL,树，是由阿德尔森,维尔斯基和兰迪斯,(,Adelson,-,velskii,and,landis,),于,1962,年首先提出的。,这是一种附加了一定限制条件的二叉树。我们定义二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子（,Balance factor,），,所谓平衡树，是指一个二叉树其任一结点的平衡因子值只能是,+1,，,0,或,-1,，即任一结点的左、右子树高度之差不超过,1,。,如图,8.3,所示，图中数字为该结点的平衡因子。,第八章 查找,平衡树,平衡二叉树,不平衡二叉树,第八章 查找,假设给平衡树某个结点的左子树插入一个新结点，且此新结点使左子树的高度加,1,，我们可能会遇到以下三种情况：,(1),如果原来其左子树高度,hl,与右子树高度,hr,相等，即原来此结点的平衡因子等于,0,插入新结点后将使平衡因子变成,+1,，但仍符合平衡树的条件，不必对其加以调整；,如果原来,hlhr,，,即原来此结点的平衡因子等于,+1,插入新结点后将使平衡因子变成,+2,，破坏了平衡树的限制条件，需对其加以调整；,如果原来,hlhr,，,即原来此结点的平衡因子等于,-1,，插入新结点后将使平衡因子变成,0,，平衡更加改善，不必加以调整。,第八章 查找,如果给平衡树某结点的右子树插入一个结点，且设此新结点使右子树的高度增加,1,，则也会遇到与之相对应的三种情况。,以图,8.4,所示的树为例，设原已有关键字为,51,，,29,，,72,，,11,和,46,这五个结点，原树符合平衡树条件，图中各结点旁所标数字为该结点的平衡因子。,第八章 查找,图,8.4,平衡树插入结点,第八章 查找,插入新结点破坏了平衡树条件的情况分为两类，仍以向左子树插入新结点为例，这两类情况分别如图,8.5,（,a,）,和,(,c),所示。,图中矩形表示子树，矩形的高度表示子树的高度，带阴影线的方形则表示插入新结点后造成的子树高度加,1,，各结点旁所标数字为该结点的平衡因子。,第八章 查找,图,8.5,平衡树的调整,第八章 查找,第八章 查找,平衡树以二叉链表作为存储结构,每个结点还要增加一个平衡因子域。,平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。,在插入新结点时，当确定了新结点应插入的位置后，需向回寻找有关平衡因子变为,+2,或,-2,的祖先，如有这种结点，则取其中层数居最低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修改。,第八章 查找,8.3.3,B-,树,前面介绍的查找方法，均适用于查找存储在内存中的数据，统称为内查找方法，它们适用于较小的表，而对较大的、存储在外存储器上的文件就不合适了。,B-,树,是一种,多路平衡查找树，这是一种适用于外查找的方法的数据结构。,B-,树的定义：,一棵,m,（,m3,）,阶的,B-,树，或者为空树，或者是满足如下条件的,m,叉树：,第八章 查找,(,1),树中每个非终端结点至少包含以下数据项：,（,n,A,0,K,1,A,1,K,2,K,n,A,n,）,其中，,n,为关键字总数，,K,i,（,1in,）,是关键字，,A,i,是指向子树根结点的指针关键字是递增有序的：,K,1,K,2,0),if(i=m),i=1;,else,i+;/*i,未到达表末端则后移一个单元进行线性探测，否则返回到表首端继续探测，直至找到待查关键字,k,或者遇到开放地址为止*,/,第八章 查找,查找,算法续,if(Ai=0),Ai=k;,return(i);,返回,第八章 查找,例,8.1,设有一组关键字,19,01,23,14,55,20,84,27,68,11,10,77,，采用哈希函数：,H,（,k,）,=k mod 13,。,采用开放地址的线性探测法解决冲突，试在,0,18,的散列地址空间中，对该关键字序列构造散列表。,解：依题意,m=19,，,得到线性探测法对应的探查地址序列计算公式为：,di,=(H(k)+j)mod 19;j=1,2,18,其计算函数如下：,H(19)=19 mod 13=6,H(01)=01 mod 13=1,第八章 查找,H(23)=23 mod 13=10,H(14)=14 mod 13=1(,冲突,),H(14)=(1+1)mod 19=2,H(55)=55 mod 13=3,H(20)=20 mod 13=7,H(84)=84 mod 13=6(,冲突,),H(84)=(6+1)mod 19=7(,冲突,),H(84)=(6+2)mod 19=8,H(27)=27 mod 13=1,（,冲突）,H(27)=(1+1)mod 19=2(,冲突,),第八章 查找,H(27)=(1+2)mod 19=3(,冲突,),H(27)=(1+3)mod 19=4,H(68)=68 mod 13=3(,冲突,),H(68)=(3+1)mod 19=4(,冲突,),H(68)=(3+2)mod 19=5,H(11)=11 mod 13=11,H(10)=10 mod 13=10(,冲突,),H(10)=(10+1)mod 19=11(,冲突,),H(10)=(10+2)mod 19=12,H(77)=77 mod 13=12(,冲突,),H(77)=(12+1)mod 19=13,第八章 查找,图,8.11,例,81,地址分配,第八章 查找,例,8.2,编写一个函数，利用二分查找算法在一个有序表中插入一个元素,x,，,并保持表的有序性。,本题的解题思想是，先在有序表,r,中利用二分查找算法查找关键字值等于或小于,x,的结点，,mid,指向正好等于,x,的结点或,low,指向关键字正好大于,x,的结点，然后采用移动法插入,x,结点即可。,第八章 查找,例,8.2,算法,insert(,sqlist,r,int,x,int,n),int,low=1,high=n,mid,i,find=0;,while(low=high&!find),mid=(low+high)/2;,if(xrmid.key),low=mid+1;,else,第八章 查找,例,8.2,算法续,i=mid;,find=1;,if(!find),mid=low;,for(i=n;i=mid;i-),ri+1.key=ri.key;,rmid.key=x;,返回,第八章 查找,小结,查找,顺序查找,二分查找,分块查找,树型查找,平衡树,散列法,处理冲突的方法,开放地址法,链接表法,返回,第八章 查找,习题与练习,一、基础知识题,1.,解释下列名词,(1),查找,(2),树型查找,(3),平衡因子,(4),散列函数,(5),冲突,2.,设有序表为,a,b,c,d,e,f,g,，,请分别画出对给定值,f,g,和,h,进行拆半查找的过程3.,试述顺序查找法、二分查找法和分块查找法对被查找表中元素的要求，每种查找法对长度,为,n,的表的等概率查找长度是多少？,第八章 查找,4.,设散列表长,m=14,，,哈希函数为,H(k)=k mod 11,，,表中一共有,8,个元素,15,27,50,73,49,61,37,60,，试画出采用二次探测法处理冲突的散列表。,5.,线性表的关键字集合为,113,12,180,138,92,67,94,134,252,6,70,323,60,，共有,13,个元素，已知散列函数为：,H,（,k,）,=k mod 13,，,采用链接表处理冲突，试设计这种链表结构。,6.,设关键字集合为,27,49,79,5,37,1,56,65,83,，散列函数为：,H,（,k,）,=k mod 7,，,散列表长度,m=10,，,起始地址为,0,，分别用线性探测和链接表法来解决冲突。试画出对应的散列表。,第八章 查找,二、算法设计题,1.,从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找。,2.,如果线性表中各结点查找概率不等，则可以使用下面的策略提高顺序表的查找效率：如果找到指定的结点，则将该结点和其前趋（若存在）结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法（注意查找时必须从表头开始向后扫描）。,第八章 查找,3.,试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。,4.,设给定的散列表存储空间为,H1m,，,每个单元可存放一个记录，,Hi(1im),的初始值为零，选取散列函数为,H(R.key),，,其中,key,为记录,R,的关键字，解决冲突方法为线性探测法，编写一个函数将某记录,R,填入到散列表,H,中。,返回,第八章 查找,