DS08-查找.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基本概念,线性表的查找,树表的查找,散列,(Hash),技术,第八章 查找,8.1,查找的基本概念,查找（,Searching,）,的定义是：给定一个关键字值,K,，在含有,n,个结点的表中找出关键字等于给定值,K,的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息,。,查找表的数据结构表示,若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为,动态查找表,（,Dynamic Search Table,）。否则称之为,静态查找表,(Static Search Table),。,若整个查找过程都在内存进行，则称之为,内查找,；反之，若查找过程中需要访问外存，则称之为,外查找,平均查找长度,ASL,（,Average Search Length,）,定义为,：,ASL=,其中：,1,、,n,是结点的个数；,2,、,Pi,是查找第,i,个结点的概率。若不特别声明 ，认为每个结点的查找概率相等，即,pl=p2=,pn,=1/n,3,、,ci,是找到第,i,个结点所需进行的比较次数。,顺序查找,(Sequential Search),基本思想是：,从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值,K,相比较。若当前扫描到的结点关键字与,K,相等，则查找成功；若扫描结束后，仍未找到关键字等于,K,的结点，则查找失败。,8.2,线性表的查找,基于顺序结构的顺序查找算法,类型说明,typedef,struct,KeyType,key,；,/*,KeyType,由用户定义*,/,InfoType,otherinfo,；,/*,此类型依赖于应用*,/,NodeType,；,typedef,NodeType,Seqlistn+1,；,/*,多出,0,号单元用作监视哨*,/,具体算法,int,SeqSearch(Seqlist,R,，,KeyType,K),/*,在顺序表,R1.n,中顺序查找关键字为,K,的结点，,成功时返回找到的结点位置，失败时返回,0*/,int,i,；,R0.key=K,；,/*,设置监视哨*,/,for(i,=n,；,Ri.key,!=,K;i,-),；,/*,从表后往前找*,/,return i,；,/*,若,i,为,0,，表示查找失败，否则,Ri,为要找的结点*,/,/*,SeqSearch,*/,算法分析,生成林成功时的顺序查找的平均查找长度：,ASL=pi =np1+(n-1)p2+2pn-1+pn,（式,8.2,）,在等概率情况下，,pi=1/n(1in),，故成功的平均查找长度为,(n+2+1)/n=(n+1)/2,即查找成功时的平均比较次数约为表长的一半。,顺序查找的优点,算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。,顺序查找的缺点,查找效率低。,二分查找,又称,折半查找,，它是一种效率较高的查找方法。,二分查找要求,：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。,二分查找,二分查找的基本思想是：,（,1,）首先确定该区间的中点位置：,mid=,（,2,）然后将待查的,K,值与,Rmid.key,比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。,二分查找算法,int,BinSearch(SeqList,R,，,KeyType,K),int,low=1,，,high=n,，,mid,；,while(low,K),high=mid-1;,else,low=mid+1,；,return 0,；,例：,设算法的输入实例中有序的关键字序列为：,05,，,13,，,19,，,21,，,37,，,56,，,64,，,75,，,80,，,88,，,92,查找的关键字,K=21,第一步：,05,，,13,，,19,，,21,，,37,，,56,，,64,，,75,，,80,，,88,，,92,第二步：,05,，,13,，,19,，,21,，,37,，,56,，,64,，,75,，,80,，,88,，,92,第三步：,05,，,13,，,19,，,21,，,37,，,56,，,64,，,75,，,80,，,88,，,92,此时,Rmid.key,K,，,return mid,4,。,二分查找判定树,二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的,判定树,(Decision Tree),或,比较树,(Comparison Tree),。,二分查找判定树的组成,圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。,外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。,当查找时找到外部节点时，表示查找的值没有在该有序表中,二分查找的平均查找长度,二分查找成功时的平均查找长度为：,ASLbnlg(n+1)-1,二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：,二分查找的优点和缺点,虽然二分查找的效率高，但是要将表按关键字排序。,二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。,分块查找,分块,查找表,存储结构,分块,查找表由,分块有序,的线性表,和,索引表,组成。,分块查找的,基本思想,：,首先查找索引表,索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。,然后在已确定的块中进行顺序查找,由于块内无序，只能用顺序查找。,查找,关键字等于给定值,K=24,的结点,(,见,P199),因为索引表小，不妨用顺序查找方法查找索引表。即首先将,K,依次和索引表中各关键字比较，直到找到第,1,个关键宇大小等于,K,的结点，由于,K48,，所以关键字为,24,的结点若存在的话，则必定在第二块中；然后，由,ID2.addr,找到第二块的起始地址,7,，从该地址开始在,R7.12,中进行顺序查找，直到,R11.key=K,为止。,算法分析,分块查找是两次查找过程。整个查找过程的平均查找长度是两次查找的平均查找长度之和。,以二分查找来确定块，分块查找成功时的平均查找长度,ASLblk,=ASLbn+ASLsqlg(b+1)-1+(s+1)/2lg(n/s+1)+s/2,以顺序查找确定块，分块查找成功时的平均查找长度,ASLblk,=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s),分块查找的优点,在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。,因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。,8.3,树表的查找,1,、二叉排序树的,定义,二叉排序树,(Binary Sort Tree),又称,二叉查找,(,搜索,),树,(Binary Search Tree),。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：,（,1,）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；,（,2,）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；,（,3,）左、右子树本身又各是一棵二叉排序树。,二叉排序树的特点,（,1,）二叉排序树中任一结点,x,，其左,(,右,),子树中任一结点,y(,若存在,),的关键字必小,(,大,),于,x,的关键字。,（,2,）二叉排序树中，各结点关键字是惟一的。,（,3,）按中序遍历该树所得到的中序序列是一个递增有序序列。,二叉排序树的存储结构,typedef,int,KeyType,；,typedef,struct,node,KeyType,key,；,InfoType,otherinfo,；,struct,node*,lchild,，*,rchild,；,BSTNode,；,typedef,BSTNode,*,BSTree,；,二叉排序树插入新结点的过程,在二叉排序树中插入新结点，要保证插入后仍满足,BST,性质。其插入过程是：,1),若二叉排序树,T,为空，则为待插入的关键字,key,申请一个新结点，并令其为根；,2),若二叉排序树,T,不为空，则将,key,和根的关键字比较：,(a),若二者相等，则说明树中已有此关键字,key,，无须插入。,(b),若,key,Tkey,，则将它插入根的右子树中。,二叉排序树插入新结点的算法,void,InsertBST(BSTree,*,Tptr,，,KeyType,key),BSTNode,*f,，*,p=*,TPtr,；,while(p,),if(p,-key=,key,)return,；,f=p,；,p=(key,key)?p,-,lchild,：,p-,rchild,；,p=(,BSTNode,*),malloc(sizeof(BSTNode,),；,p-key=,key,；,p-,lchild,=p-,rchild,=NULL,；,if(*,TPtr,=NULL),*,Tptr,=p,；,else,if(key,key),f-,lchild,=p,；,else f-,rchild,=p,；,二叉排序树的生成,是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插入到当前已生成的二叉排序树中。,BSTree,CreateBST(void,),BSTree,T=NULL,；,KeyType,key,；,scanf,(,d,，,&key),；,while(key,),InsertBST(&T,，,key),；,scanf,(,d,，,&key),；,return T,；,生成二叉排序树的算法,见右边,输入实例,(5,，,3,，,7,，,2,，,4,，,8),，根据生成二叉排序树算法,生成二叉排序树的过程,5,5,3,2,5,3,7,5,3,7,2,5,3,7,4,2,5,3,7,4,8,二叉排序树的删除,从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，并且还要保证删除后所得的二叉树仍然满足,BST,性质。,删除操作的,一般步骤,1),进行查找 查找时，令,p,指向当前访问到的结点，,parent,指向其双亲,(,其初值为,NULL),。若树中找不到被删结点则返回，否则被删结点是*,p,。,2),删去*,p,。,删*,p,时，应将*,p,的子树,(,若有,),仍连接在树上且保持,BST,性质不变。按*,p,的孩子数目分三种情况进行处理。,删除*,p,结点的三种情况,1)*p,是叶子,(,即它的孩子数为,0),无须连接*,p,的子树，只需将*,p,的双亲*,parent,中指向*,p,的指针域置空即可。,2)*p,只有一个孩子*,child,只需将*,child,和*,p,的双亲直接连接后，即可删去*,p,。,3)*p,有两个孩子,先令,q=p,，将被删结点的地址保存在,q,中；然后找*,q,的中序后继*,p,，并在查找过程中仍用,parent,记住*,p,的双亲位置。*,q,的中序后继*,p,一定是*,q,的右子树中最左下的结点，它无左子树。因此，可以将删去*,q,的操作转换为删去的*,p,的操作，即在释放结点*,p,之前将其数据复制到*,q,中，就相当于删去了*,q,。,二叉排序树删除算法,void,DelBSTNode(BSTree,*,Tptr,，,KeyType,key),BSTNode,*parent=,NUll,，*,p=*,Tptr,，*,q,，*,child,；,while(p,),if(p,-key=,key,)break,；,parent=p,；,p=(key,key)?p,-,lchild,：,p-,rchild,；,if(!p,)return,；,q=p,；,if(q,-,lchild&q,-,rchild,),for(parent,=q,，,p=q-,rchild,；,p-,lchild,；,parent=p,，,p=p=-,lchild,),；,child=(p-,lchild)?p,-,lchild,：,p-,rchild,；,if(!parent,),*,Tptr,=child,；,else,if(p,=parent-,lchild,),parent-,lchild,=child,；,else parent-,rchild,=child,；,if(p,!=q),q-key=p-key,；,free(p,),；,二叉排序树上的查找,在二叉排序树上进行查找，和二分查找类似，也是一个逐步缩小查找范围的过程。,递归的查找算法：,BSTNode,*,SearchBST(BSTree,T,，,KeyType,key),if(T,=,NULL|key,=T-key),return T,；,if(key,key),return,SearchBST(T,-,lchild,，,key),；,else,return,SearchBST(T,-,rchild,，,key),；,在二叉排序树上进行查找时的,平均查找长度和二叉树的形态有关：,(a),在最坏情况下，二叉排序树是通过把一个有序表的,n,个结点依次插入而生成的，此时所得的二叉排序树蜕化为一棵深度为,n,的单支树，它的平均查找长度和单链表上的顺序查找相同，也是,(n+1)/2,。,(b),在最好情况下，二叉排序树在生成的过程中，树的形态比较匀称，最终得到的是一棵形态与二分查找的判定树相似的二叉排序树，此时它的平均查找长度大约是,lgn,。,(c),插入、删除和查找算法的时间复杂度均为,O(lgn,),。,二叉排序树和二分查找的比较,就平均时间性能而言，二叉排序树上的查找和二分查找差不多。,就维护表的有序性而言，二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作，且其平均的执行时间均为,O(lgn,),，因此更有效。二分查找所涉及的有序表是一个向量，若有插入和删除结点的操作，则维护表的有序性所花的代价是,O(n,),。当有序表是静态查找表时，宜用向量作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其存储结构。,-,树,B-,树的定义,一棵,m(m3),阶的,B-,树是满足如下性质的,m,叉树：,(1),每个结点至少包含下列数据域：,(n,，,P0,，,Kl,，,P1,，,K2,，,，,Ki,，,Pi),其中：,n,为关键字总数,Ki(1ij),是关键字，关键字序列递增有序：,K1 K2,keynum,；,K,keyi;i,-),；,if(i,0&T-,keyi,=1),*pos=i,；,return T,；,if(!T,-,soni,),return NULL,；,DiskRead(T,-,soni,),；,return,SearchBTree(T,-,Soni,，,k,，,pos),；,查找操作的时间开销,B-,树上的查找有两个基本步骤：,在,B-,树中查找结点，该查找涉及读盘,DiskRead,操作，属外查找；,在结点内查找，该查找属内查找。,查找操作的时间为：,外查找的读盘次数不超过树高,h,，故其时间是,O(h,),；,内查找中，每个结点内的关键字数目,keynum,m(m,是,B-,树的阶数,),，故其时间为,O(nh,),。,B-,树的插入和生成,B-,树的生成是从空树起，逐个插入关键字而得到的。,（,1,）,插入关键字,K,的方法,首先在树中查找,K,，若找到则直接返回,(,假设不处理相同关键字的插入,),；否则查找操作必失败于某个叶子上，然后将,K,插入该叶子中。若该叶子结点原来是非满,(,指,keynum,keynum,Min,，则只需删去,K,及其右指针,(*x,是叶子，,K,的右指针为空,),即可使删除操作结束。,情形二,：若,x-,keynum,=Min,，该叶子中的关键字个数已是最小值，删,K,及其右指针后会破坏,B-,树的性质,(3),。若*,x,的左,(,或右,),邻兄弟结点*,y,中的关键字数目大于,Min,，则将*,y,中的最大,(,或最小,),关键字上移至双亲结点*,parent,中，而将*,parent,中相应的关键字下移至,x,中。,情形三,：若*,x,及其相邻的左右兄弟,(,也可能只有一个兄弟,),中的关键字数目均为最小值,Min,，则上述的移动操作就不奏效，此时须*,x,和左或右兄弟合并。,B,树中删除关键字,6,，,7,的过程,12,6,8,9,7,5,2,15,13,12,7,9,8,5,2,15,13,12,5,8,9,2,15,13,性能分析,n,个结点的平衡的二叉排序的高度,H,（即,lgn,）比,B-,树的高度,h,约大,lgt,倍。,例如,m=1024,，则,lgt,=lg512=9,。此时若,B-,树高度为,4,，则平衡的二叉排序树的高度约为,36,。显然，若,m,越大，则,B-,树高度越小。,若要作为内存中的查找表，,B-,树却不一定比平衡的二叉排序树好，尤其当,m,较大时更是如此。,因为查找等操作的,CPU,计算时间在,B-,树上是,O(mlogtn,)=0(lgn(m/lgt),8.4,散列,(Hash),技术,散列表,(Hash Table),设所有可能出现的关键字集合记为,U(,简称全集,),。实际发生,(,即实际存储,),的关键字集合记为,K,（,|K|,比,|U|,小得多）。,散列方法是使用函数,h,将,U,映射到表,T0.m-1,的下标上（,m=O(|U|),）。这样以,U,中关键字为自变量，以,h,为函数的运算结果就是相应结点的存储地址。从而达到在,O(1),时间内就可完成查找。,其中：,h,：,U0,，,1,，,2,，,，,m-1,，通常称,h,为散列函数,(Hash Function),。散列函数,h,的作用是压缩待处理的下标范围，使待处理的,|U|,个值减少到,m,个值，从而降低空间开销。,T,为散列表,(Hash Table),。,h(Ki)(KiU,),是关键字为,Ki,结点存储地址,(,亦称散列值或散列地址,),。,将结点按其关键字的散列地址存储到散列表中的过程称为,散列,(Hashing),散列表的冲突现象（,1,）冲突,两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突,(Collision),或碰撞。发生冲突的两个关键字称为该散列函数的同义词,(Synonym),。,（,2,）安全避免冲突的条件,最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：,其一是,|,U|m,其二是选择合适的散列函数。,3,）,冲突不可能完全避免,通常情况下，,h,是一个压缩映像。虽然,|,K|m,，但,|U|m,，故无论怎样设计,h,，也不可能完全避免冲突。,（,4,）,影响冲突的因素,冲突的频繁程度除了与,h,相关外，还与表的填满程度相关。,设,m,和,n,分别表示表长和表中填人的结点数，则将,=,n/m,定义为散列表的装填因子,(Load Factor),。,越大，表越满，冲突的机会也越大。通常取,1,。,常用散列函数,平方取中法,具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。,除余法,该方法是最为简单常用的一种方法。它是以表长,m,来除关键字，取其余数作为散列地址，即,h(key,)=key,m,该方法的关键是选取,m,。选取的,m,应使得散列函数值尽可能与关键字的各位相关。,m,最好为素数。,相乘取整法,该方法包括两个步骤：首先用关键字,key,乘上某个常数,A(0A1),，并抽取出,key.A,的小数部分；然后用,m,乘以该小数后取整。即：,该方法最大的优点是选取,m,不再像除余法那样关键,随机数法,选择一个随机函数，取关键字的随机函数值为它的散列地址，即,h(key,)=,random(key,),其中,random,为伪随机函数，但要保证函数值是在,0,到,m-1,之间。,处理冲突的方法,开放地址法解决冲突的方法,用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查,(,亦称探测,),技术在散列表中形成一个探查,(,测,),序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址,(,即该地址单元为空,),为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。,开放地址法的一般形式,开放定址法的一般形式为：,hi=(,h(key)+di,),m 1im-1,（,3,）开放地址法堆装填因子的要求,开放定址法要求散列表的装填因子,l,，实用中取,为,0.5,到,0.9,之间的某个值为宜。,形成探测序列的方法,按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。,线性探查法,(Linear Probing),该方法的基本思想是：,将散列表,T0.m-1,看成是一个循环向量，若初始探查的地址为,d(,即,h(key,)=d),，则最长的探查序列为：,d,，,d+l,，,d+2,，,，,m-1,，,0,，,1,，,，,d-1,即,:,探查时从地址,d,开始，首先探查,Td,，然后依次探查,Td+1,，,，直到,Tm-1,，此后又循环到,T0,，,T1,，,，直到探查到,Td-1,为止。,二次探查法,(,Quadratic Probing),二次探查法的探查序列是：,hi=(,h(key)+i,*i),m 0im-1/,即,di,=i2,即探查序列为,d=,h(key,),，,d+12,，,d+22,，,，等。,该方法的缺陷是不易探查到整个散列空间。,双重散列法,(Double Hashing),该方法是开放定址法中最好的方法之一，它的探查序列是：,hi=(,h(key)+i,*h1(key),m 0im-1/,即,di,=i*h1(key),即探查序列为：,d=,h(key,),，,(d+h1(key),m,，,(d+2h1(key),m,，,，等。,拉链法,解决冲突的方法,拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为,m,，则可将散列表定义为一个由,m,个头指针组成的指针数组,T0.m-1,。凡是散列地址为,i,的结点，均插入到以,Ti,为头指针的单链表中。,T,中各分量的初值均应为空指针。在拉链法中，装填因子,可以大于,1,，但一般均取,1,。,例：,已知一组关键字为（,26,，,36,，,41,，,38,，,44,，,15,，,68,，,12,，,06,，,51,），取表长为,13,，,用拉链法解决冲突构造这组关键字的散列表如右图,0,1,2,3,4,5,8,6,9,7,10,11,12,26,15,41,12,36,68,06,38,44,51,拉链法的优点,(1),拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；,(2),由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；,(3),开放定址法为减少冲突，要求装填因子,较小，故当结点规模较大时会浪费很多空间。而拉链法中可取,1,，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；,(4),在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。,拉链法的缺点,拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。,散列表上的运算,散列表类型说明：,#define NIL-1,#define M 997,typedef,struct,KeyType,key,；,InfoType,otherinfo,；,NodeType,；,typedef,NodeType,HashTablem,；,基于开放地址法的查找算法,散列表的查找过程和建表过程相似。假设给定的值为,K,，根据建表时设定的散列函数,h,，计算出散列地址,h(K,),，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值,K,比较。若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去,开放地址法一般形式的函数表示,int,Hash(KeyType,k,，,int,i),return(h(K)+Increment(i,),m,；,若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的,h(K,),和,Increment(i,),可定义为：,int,h(KeyType,K),return K,m,；,int,Increment(int,i),return i;/,通用的开放定址法的散列表查找算法：,int,HashSearch(HashTable,T,，,KeyType,K,，,int,*pos),int,i=0,；,do,*pos=,Hash(K,，,i),；,if(T,*,pos.key,=K)return l,；,if(T,*,pos.key,=NIL)return 0,；,while(+i,0),printf(duplicate,key!),；,else,Error(hashtableoverflow,!),；,void,CreateHashTable(HashTable,T,，,NodeType,A,，,int,n),int,i,if(n,m),Error(Load,factor1),；,for(i,=0;im,；,i+),Ti.key,=NIL,；,for(i,=0;in,；,i+),Hashlnsert(T,，,Ai,),；,删除,基于开放定址法的散列表不宜执行散列表的删除操作。若必须在散列表中删除结点，则不能将被删结点的关键字置为,NIL,，而应该将其置为特定的标记,DELETED,。,性能分析,插入和删除的时间均取决于查找，故下面只分析查找操作的时间性能。,虽然散列表在关键字和存储位置之间建立了对应关系，理想情况是无须关键字的比较就可找到待查关键字。但是由于冲突的存在，散列表的查找过程仍是一个和关键字比较的过程，不过散列表的平均查找长度比顺序查找、二分查找等完全依赖于关键字比较的查找要小得多。,