数据结构与算法分析之查找技术

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第9,章,章,查,查,找,找,技,技,术,术,9.1,顺,顺,序,序,查,查,找,找,9.2,有,有,序,序,表,表,的,的,对,对,分,分,查,查,找,找,9.3,分,分,块,块,查,查,找,找,9.4,二,二,叉,叉,排,排,序,序,树,树,查,查,找,找,9.5,hashing,技,术,术,9.1,顺,顺,序,序,查,查,找,找,9.1.1,线,线,性,性,表,表,在,在,顺,顺,序,序,存,存,储,储,下,下,的,的,顺,顺,序,序,查,查,找,找,9.1.2,线,线,性,性,链,链,表,表,的,的,顺,顺,序,序,查,查,找,找,9.1,顺,顺,序,序,查,查,找,找,9.1.1,线,线,性,性,表,表,在,在,顺,顺,序,序,存,存,储,储,下,下,的,的,顺,顺,序,序,查,查,找,找,(1),如,如,果,果,线,线,性,性,表,表,为,为,无,无,序,序,表,表,（,（,即,即,表,表,中,中,元,元,素,素,的,的,排,排,列,列,是,是,无,无,序,序,的,的,）,）,，,，,则,则,不,不,管,管,是,是,顺,顺,序,序,存,存,储,储,结,结,构,构,还,还,是,是,链,链,式,式,存,存,储,储,结,结,构,构,，,，,都,都,只,只,能,能,用,用,顺,顺,序,序,查,查,找,找,。,。,(2),即,即,使,使,是,是,有,有,序,序,线,线,性,性,表,表,，,，,如,如,果,果,采,采,用,用,链,链,式,式,存,存,储,储,结,结,构,构,，,，,也,也,只,只,能,能,用,用,顺,顺,序,序,查,查,找,找,。,。,9.1,顺,顺,序,序,查,查,找,找,线,性,性,表,表,在,在,顺,顺,序,序,存,存,储,储,结,结,构,构,下,下,的,的,顺,顺,序,序,查,查,找,找,输,入,入,：,：,线,线,性,性,表,表,长,长,度,度,n,以,及,及,线,线,性,性,表,表,的,的,存,存,储,储,空,空,间,间,V,；,；,被,查,查,找,找,的,的,元,元,素,素,x,。,。,输,出,出,：,：,被,被,查,查,找,找,元,元,素,素,x,在,线,线,性,性,表,表,中,中,的,的,序,序,号,号,k,。,。,如,果,果,在,在,线,线,性,性,表,表,中,中,不,不,存,存,在,在,元,元,素,素,x,，,，,则,输,输,出,出,k,1,。,。,PROCEDURESERCH(V,，,，n,，,，x,，,，k),k,1,WHILE(k,n)and(V(k),x)DOk,k,1,IF(k,n,1)THENk,1,RETURN,9.1,顺,顺,序,序,查,查,找,找,/*,函,函,数,数,返,返,回,回,被,被,查,查,找,找,元,元,素,素,x,在,线,线,性,性,表,表,中,中,的,的,序,序,号,号,，,，,如,果,果,在,在,线,线,性,性,表,表,中,中,不,不,存,存,在,在,元,元,素,素,值,值,x,，,，,则,返,返,回,回,1*/,intserch(v,，,，n,，,，x),intn,；,；,ETv,，,，x,；,；/*ET,为,线,线,性,性,表,表,数,数,据,据,类,类,型,型*/,intk,；,；,k,0,；,；,while(k,n)&(vk,x)k,k,1,；,；,if(k,n)k,1,；,；,return(k),；,；,9.1,顺,顺,序,序,查,查,找,找,9.1.2,线,线,性,性,链,链,表,表,的,的,顺,顺,序,序,查,查,找,找,9.1,顺,顺,序,序,查,查,找,找,线,性,性,表,表,在,在,链,链,式,式,存,存,储,储,结,结,构,构,下,下,的,的,顺,顺,序,序,查,查,找,找,输,入,入,：,：,线,线,性,性,链,链,表,表,头,头,指,指,针,针,HEAD,以,及,及,存,存,储,储,空,空,间,间,V,、,、NEXT,；,；,被,查,查,找,找,的,的,元,元,素,素,x,。,。,输,出,出,：,：,被,被,查,查,找,找,元,元,素,素,x,的,结,结,点,点,在,在,线,线,性,性,链,链,表,表,中,中,的,的,存,存,储,储,序,序,号,号,k,。,。,如,果,果,在,在,线,线,性,性,链,链,表,表,中,中,不,不,存,存,在,在,元,元,素,素,值,值,为,为,x,的,结,结,点,点,，,，,则,输,输,出,出,k,1,。,。,PROCEDURELSERCH(V,，,，NEXT,，,，HEAD,，,，x,，,，k),k,HEAD,WHILE(k,0)and(V(k),x)DOk,NEXT(k),IF(k,0)THENk,1,RETURN,9.1,顺,顺,序,序,查,查,找,找,structnode,ETd,；,；structnode*next,；,；,；,；,/*,函数,返,返回,被,被查,找,找元,素,素,x,所在,结,结点,的,的存,储,储地,址,址，,如果,在,在线,性,性链,表,表中,不,不存,在,在元,素,素值,为,为,x,的结,点,点，,则,则返,回,回,NULL*/,structnode*lserch(head,，,，x),structnode*head；,ETx；/*ET,为线,性,性链,表,表中,值,值域,的,的数,据,据类,型,型*/,structnodek；,khead,；,；,while(k,NULL)&(k,dx)k,k,next,；,；,return(k)；,9.2,有,有,序,序表,的,的对,分,分查,找,找,设有,序,序线,性,性表,的,的长,度,度为,n，,被查,元,元素,为,为,x。,将,x,与线,性,性表,的,的中,间,间项,进,进行,比,比较,：,：,若中,间,间项,的,的值,等,等于,x，,则说,明,明查,到,到，,查,查找,结,结束,；,；,若,x,小于,中,中间,项,项的,值,值，,则,则在,线,线性,表,表的,前,前半,部,部分,（,（即,中,中间,项,项,以前,的,的部,分,分）,以,以相,同,同的,方,方法,进,进行,查,查找,；,；,若,x,大于,中,中间,项,项的,值,值，,则,则在,线,线性,表,表的,后,后半,部,部分,（,（即,中,中间,项,项,以后,的,的部,分,分）,以,以相,同,同的,方,方法,进,进行,查,查找,。,。,这个,过,过程,一,一直,进,进行,到,到查,找,找成,功,功或,子,子表,长,长度,为,为0(说,明,明线,性,性,表中没有,这,这个元素)为止。,在最坏情,况,况下，对,分,分查找只,需,需要比较,log,2,n,次，,而顺序查,找,找需要比,较,较,n,次。,9.2,有,有序表,的,的对分查,找,找,有序线性,表,表在顺序,存,存储结构,下,下的对分,查,查找,输入：有,序,序线性表,长,长度,n,以及线性,表,表的存储,空,空间,V；,被查找的,元,元素,x。,输出：被,查,查找元素,x,在有序线,性,性表中的,序,序号,k。,如果在线,性,性表中不,存,存,在元素,x，,则输出,k1,。,。,PROCEDURE BSERCH(V，n，x，k),i1；jn,WHILE (i,j)DO, k(ij)/2,IF (V(k),x)THENRETURN,IF (V(k),x)THENjk1；,ELSEik1；,IF(ij) THENk1,RETURN,9.2,有,有序表,的,的对分查,找,找,intbserch(v，n，x) /*,函数返回,被,被查找元,素,素,x,在线性表,中,中的序号,如果在线,性,性表中不,存,存在元素,值,值,x，,则返回1 */,intn；,ETx，v；, int i,，,，j，k,；,；,i1；jn,；,；,while (i,j), k(ij)/2；,if (vk1x)return(k,1)；,if (vk1x) j,k1,；,；,elseik,1；,return(1)；,9.3,分,分块查,找,找,分块有序,表,表,将长度为,n,线性表分,成,成,m,个子表，,各,各子表的,长,长度可以,相,相,等，也可,以,以互相不,等,等，但要,求,求后一个,子,子表中的,每,每一个,元素均大,于,于前一个,子,子表中的,所,所有元素,。,。,分块有序,表,表的结构,可,可以分为,两,两部分：,(1)线,性,性表本身,采,采用顺序,存,存储结构,。,。,(2)再,建,建立一个,索,索引表。,在,在索引表,中,中，对线,性,性表的每,个,个子表建,立,立一个索,引,引结点，,每,每个结点,包,包括两个,域,域：一是,数,数据域，,用,用于存放,对,对应子表,中,中的最大,元,元素值；,二,二是指针,域,域，用于,指,指示对应,子,子表的第,一,一个元素,在,在整个线,性,性表中的,序,序号。,9.3,分,分块查,找,找,structindnode, ETkey；/*,数据域，,存,存放子表,中,中的最大,值,值，,其类型与,线,线性表中,元,元素的数,据,据类,型相同*/,intk；/*,指针域，,指,指示子表,中,中第一个,元,元素,在线性表,中,中的序号*/,；,9.3,分,分块查,找,找,9.3,分,分块查,找,找,(1)首,先,先查找索,引,引表，以,便,便确定被,查,查元素所,在,在的子表,。,。由于索,引,引表数据,域,域中的数,据,据是有序,的,的，因此,可,可以采用,对,对分查找,。,。,(2)然,后,后在相应,的,的子表中,用,用顺序查,找,找法进行,具,具体的查,找,找。,分块查找,输入：长,度,度为,n,的线性表,L,的存储空,间,间,V(1：n)；,索引表中,的数据域,存,存储空间,KEY(1：m),与指针域,存,存储空间,K(1：m)；,被查元素,x。,输出：被,查,查元素,x,在线性表,L,中的序号,j（,即使,L(j),x,的,j）。,如果,x,不在线性,表,表,L,中，则置,j1,。,。,9.3,分,分块查,找,找,PROCEDURE INSERCH(V,，,，n，KEY，K,，,，m，x,，,，j),i1；jm,WHILE (j,i1) DO,对分查找,索,索引表,t(i,j)/2,IF (xKEY(t) THENjt,ELSEit,IF (ij)and(xKEY(i) THENij,jK(i)；tn,IF (im)THENtK(i1),1,确定顺序,查,查找的终,点,点,WHILE (j,t)and(V(j)x)DOjj1,顺序查找,子,子表,IF (jt)THENj1,RETURN,9.3,分,分块查,找,找,在分块查,找,找中，为,了,了找到被,查,查元素,x,所在的子,表,表，需要,对,对分查找,索,索引,表，在最,坏,坏情况下,需,需要查找,log,2,(m1),次。,在相应子,表,表中用顺,序,序查找法,查,查找元素,x，,在最坏情,况,况下需要,查,查找,n/m,（,假设各子,表,表长度相,等,等）次；,而,而在平均,情,情况下需,要,要查找,n/(2m),次。,因此，分,块,块查找的,工,工作量为,：,：,在最坏情,况,况下需要,查,查找,log,2,(m1)n/m,次，,平均情况,下,下大约需,要,要查找,log,2,(m1)n/(2m),次。,当,mn,时，线性,表,表,L,即为有,序,序表，,分,分块查,找,找即为,对,对分查,找,找,当,m1,时，线,性,性表,L,为一般,的,的无序,表,表，分,块,块查找,即,即为顺,序,序查找,。,。,分块查,找,找的效,率,率介于,对,对分查,找,找和顺,序,序查找,之,之间。,9.3,分,分,块,块查找,structindnode, ETkey,；,；/*,数据域,，,，存放,子,子表中,的,的最大,值,值，,其类型,与,与线性,表,表中元,素,素的数,据,据类型,相,相同*/,intk,；,； /*,指针域,，,，指示,子,子表中,第,第一个,元,元素在,线,线性表,中,中的序,号,号*/,；,/*函,数,数返回,被,被查找,元,元素,x,在线性,表,表中的,序,序号，,如果在,线,线性表,中,中不存,在,在元素,值,值,x，,则返回,1*/,intinserch(v，n，s,，,，m，x),intn，m；,ETx，v,；,；,structindnodes,；,；,9.3,分,分,块,块查找,inti,，,，j，t；,i1,；,； j,m；,while(ji1)/*,对分查,找,找索引,表,表*/,t(ij)/2,；,；,if(x,st.key)jt,；,；,else i,t；,if(i!j)&(xsi.key)ij,；,；,jsi.k；tn；,if(i!,m)t,si1.k,1；/*,确定顺,序,序查找,的,的终点*/,while(j,t)&(Vj!x)jj1,；,；/*,顺序查,找,找子表*/,if (j,t)j1；,return(j)；,9.4,二,二叉排序树,查,查找,9.4.1,二,二叉排,序,序树及其构,造,造,9.4.2,二,二叉排,序,序树查找,9.4,二,二叉排序树,查,查找,9.4.1,二,二叉排,序,序树及其构,造,造,(1)左子,树,树上的所有,结,结点值均小,于,于根结点值,；,；,(2)右子,树,树上的所有,结,结点值均不,小,小于根结点,值,值；,(3)左、,右,右子树也满,足,足上述两个,条,条件。,9.4,二,二叉排序树,查,查找,9.4,二,二叉排序树,查,查找,9.4,二,二叉排序树,查,查找,依次读入给,定,定序列中的,每,每一个元素,：,：,(1)若当,前,前的二叉排,序,序树为空，,则,则读入的元,素,素为根结点,；,；,(2)若读,入,入的元素值,小,小于根结点,值,值，则将元,素,素插入到左,子,子树中；,(3)若读,入,入的元素值,不,不小于根结,点,点值，则将,元,元素插入到,右,右子树中。,无论是插入,到,到左子树还,是,是右子树，,同,同样按照上,述,述方法处理,。,。,9.4,二,二叉排序树,查,查找,9.4,二,二叉排序树,查,查找,9.4,二,二叉排序树,查,查找,插入元素68,9.4,二,二叉排序树,查,查找,插入元素71,9.4,二,二叉排序树,查,查找,插入元素77,9.4,二,二叉排序树,查,查找,插入元素88,9.4,二,二叉排序树,查,查找,二叉排序树,的,的另一种形,态,态,9.4,二,二叉排序树,查,查找,由无序序列,构,构造二叉排,序,序树,输入：长度,为,为,n,的无序序列,A(1：n)。,输出：二叉,排,排序树的头,指,指针,BT。,PROCEDUREINBSORT(A,，,，n，BT),BT0,FORk1TO nDO, NEW(p),取得一个新,结,结点,V(p)A(k)；L(p),0； R(p)0,jBT,IF (j0)THENBTp,若二叉排序,树,树为空,ELSE,二叉排序树,不,不空,9.4,二,二叉排序树,查,查找,WHILE(L(j)p)and(R(j)p)DO,未到叶子结,点,点,IF (A(k)V(j)THEN,插入到左子,树,树,IF (L(j)0) THEN j,L(j),ELSEL(j),p,ELSE,插入到右子,树,树,IF (R(j)0) THEN j,R(j),ELSER(j),p,RETURN,9.4,二,二叉排序树,查,查找,#,include stdlib.h/* malloc,函数需要包,含,含头文件,stdlib.h*/,struct btnode/*,定义结点类,型,型*/,ET d,；,；/*,数据域*/,struct btnode*lchild；/*,左指针域*/,struct btnode*rchild；/*,右指针域*/,；,struct btnode*inbsort(a，n)/*,函数返回二,叉,叉排序树头,指,指针*/,intn；,ET a；, structbtnode *p,，,， *q，*bt；,intk；,btNULL；,9.4,二,二叉排序树,查,查找,for (k0；kn；k), p(struct btnode*)malloc(sizeof(struct btnode)；,pdak；plchild,NULL,；,； prchildNULL；,/*,置新结点的,数,数据域与左,、,、右指针域*/,qbt；,if (q,NULL) btp；/*,二叉排序树,为,为空*/,else/*,二叉排序树,不,不空*/,while(qlchild!p)&(q,rchild!p), if(ak,qd) /*,插入到左子,树,树*/,if (q,lchild!NULL)qq,lchild；,elseqlchild,p；,9.4,二,二叉排序树,查,查找,else/*,插入到右子,树,树*/,if (q,rchild!NULL)qq,rchild；,elseqrchild,p；,return(bt),；,； /*,返回二叉排,序,序树头指针*/,9.4,二,二叉排序树,查,查找,9.4.2,二,二叉排,序,序树查找,从二叉排序,树,树的根结点,开,开始与被查,值,值进行比较,：,：,(1)若被,查,查值等于根,结,结点值，查,找,找成功，查,找,找过程结束,。,。,(2)若被,查,查值小于根,结,结点值，则,到,到左子树中,去,去查找。,(3)若被,查,查值大于根,结,结点值，则,到,到右子树中,去,去查找。,在左、右子,树,树中查找时,也,也采用上述,方,方法。,查找过程直,到,到查找成功,或,或所考虑的,子,子树已空为,止,止。,9.4,二,二叉排序树,查,查找,二叉排序树,查,查找,输入：二叉,排,排序树头指,针,针,BT,以及存储空,间,间；被查元,素,素,x。,输出：被查,元,元素,x,在二叉排序,树,树空间中的,存,存储结点序,号,号,p,PROCEDURE BSTSERCH(BT，x,，,，p),PBT,WHILE (p,0)and(V(p)x)DO, IF(xV(p) THENpL(p),沿左子树,查,查找,ELSEpR(p),沿右子树,查,查找,RETURN,9.4,二,二叉排,序,序树查找,structbtnode/*,定义结点,类,类型*/,ETd；/*,数据域*/,structbtnode*lchild；/*,左指针域*/,structbtnode*rchild；/*,右指针域*/,；,9.4,二,二叉排,序,序树查找,/*函数,返,返回被查,值,值,x,所在结点,的,的存储地,址,址*/,structbtnode*bstserch(bt,，,，x),structbtnode*bt；,ETx；, structbtnode*p,；,；,pbt,；,；,while (p!NULL)&(p,d!,x), if(xpd) p,plchild；/*,沿左子树,查,查找*/,elsepprchild；/*,沿右子树,查,查找*/,return(p)；,9.5,Hash,表技术,9.5.1,Hash,表的基本,概,概念,9.5.2 几,种,种常用的,Hash,表,9.5.1,Hash,表的基本,概,概念,9.51.1,直,直接查找,技,技术,9.51.2,Hash,表,9.51.3,Hash,码的构造,9.51,Hash,表的基本,概,概念,9.51.1,直,直接查找,技,技术,设表的长,度,度为,n。,如果存在,一,一个函数,ii(k)，,对于表中,的任意一,个,个元素的,关,关键字,k，,满足以下,条,条件：,(1)1,in；,(2),对于任意,的,的元素关,键,键字,k,1,k,2,，,恒存在,i(k,1,)i(k,2,)。,则称此表,为,为直接查,找,找表。其,中,中函数,ii(k),称为关键,字,字,k,的映象函,数,数。,9.51,Hash,表的基本,概,概念,1.直接,查,查找表的,填,填入,要将关键,字,字为,k,的元素填,入,入到直接,查,查找表，,只,只需做以,下,下两,步：,(1)计,算,算关键字,k,的,映,映,象,象,函,函,数,数,i,i(k),；,；,(2),将,关,关,键,键,字,字,k,及,有,有,关,关,元,元,素,素,信,信,息,息,填,填,入,入,到,到,表,表,的,的,第,第,i,项,。,。,9.51,Hash,表,的,的,基,基,本,本,概,概,念,念,2.,直,直,接,接,查,查,找,找,表,表,的,的,取,取,出,出,要,在,在,直,直,接,接,查,查,找,找,表,表,中,中,取,取,出,出,关,关,键,键,字,字,k,的,元,元,素,素,，,，,也,也,只,只,需,需,做,做,以,以,下,下,两,两,步,：,：,(1),计,计,算,算,关,关,键,键,字,字,k,的,映,映,象,象,函,函,数,数,i,i(k),；,；,(2),检,查,查,表,表,中,中,第,第,i,项,：,：,若,第,第,i,项,为,为,空,空,，,，,则,则,说,说,明,明,表,表,中,中,没,没,有,有,关,关,键,键,字,字,为,为,k,的,元,元,素,素,；,；,否,则,则,取,取,出,出,第,第,i,项,中,中,的,的,元,元,素,素,即,即,可,可,。,。,9.51,Hash,表,的,的,基,基,本,本,概,概,念,念,9.51.2,Hash,表,9.51,Hash,表,的,的,基,基,本,本,概,概,念,念,例,将,关,关,键,键,字,字,序,序,列,列(09,，,，31,，,，26,，,，19,，,，01,，,，13,，,，02,，,，11,，,，27,，16,，,，05,，,，21),依,依,次,次,填,填,入,入,长,长,度,度,为,为,n,12,的,表,表,中,中,。,。,设,设,映,映,象,象,函,函,数,为,为,i,INT(k/3),1,。,。,9.51,Hash,表,的,的,基,基,本,本,概,概,念,念,设,表,表,的,的,长,长,度,度,为,为,n,。,。,如,果,果,存,存,在,在,一,一,个,个,函,函,数,数,i,i(k),，,，,对,于,于,表,表,中,中,的,任,任,意,意,一,一,个,个,元,元,素,素,的,的,关,关,键,键,字,字,k,，,，,满,足,足1,i,n,，,，,则,称,称,此,此,表,表,为,Hash,表,。,。,其,其,中,中,函,函,数,数,i,i(k),称,为,为,关,关,键,键,字,字,k,的,Hash,码,。,。,(1),构,构,造,造,合,合,适,适,的,的,Hash,码,，,，,以,以,便,便,尽,尽,量,量,减,减,少,少,表,表,中,中,元,元,素,素,冲,冲,突,突,的,的,次,次,数,。,。,即,即,Hash,码,的,的,均,均,匀,匀,性,性,要,要,比,比,较,较,好,好,。,。,(2),当,当表中,元,元素发,生,生冲突,时,时，要,进,进行适,当,当的处,理,理。,9.51,Hash,表的基,本,本概念,9.51.3,Hash,码的构,造,造,(1),使,使各关,键,键字尽,可,可能均,匀,匀地分,布,布在,Hash,表中，,即,即,Hash,码,的均匀,性,性要好,，,，以便,减,减少冲,突,突发生,的,的机会,。,。,(2),Hash,码的计,算,算要尽,量,量简单,。,。,9.51,Hash,表的基,本,本概念,1.截,段,段法,2.分,段,段叠加,法,法,3.除,法,法,imod(k，n),4.,乘法,imod(k*,，,，n),一般取0.618033988747，,或,或0.6125423371，,或0.6161616161。,9.52,几,几种常,用,用的,Hash,表,9.52.1,线,线,性,性,Hash,表,9.52.2,随,随,机,机,Hash,表,9.52.3,溢,溢,出,出,Hash,表,9.52.4,拉,拉,链,链,Hash,表,9.52.5,指,指,标,标,Hash,表,9.52,几,几种常,用,用的,Hash,表,9.52.1,线,线,性,性,Hash,表,开放法,9.52,几,几种常,用,用的,Hash,表,1.线,性,性,Hash,表的填,入,入,将关键,字,字,k,及有关,信,信息填,入,入线性,Hash,表的步,骤,骤如下,：,：,(1),计,计算关,键,键字,k,的,Hash,码,ii(k),。,。,(2),检查表,中,中第,i,项的内,容,容：,若第,i,项为空,，,，则将,关,关键字,k,及有关,信,信息填,入,入该项,；,；,若第,i,项不空,，,，则令,imod(i1,，,，n),，,，,转(2)继续,检查。,只要,Hash,表尚未,填,填满，,最,最终总,可,可以找,到,到一个,空,空项，,将,将关,键字,k,及有关,信,信息填,入,入到,Hash,表中。,9.52,几,几种常,用,用的,Hash,表,2.,线,线性,Hash,表的取,出,出,要在线,性,性,Hash,表中取,出,出关键,字,字,k,的元素,，,，其步,骤,骤如下,：,：,(1),计,计算关,键,键字,k,的,Hash,码,ii(k),。,。,(2),检查表,中,中第,i,项的内,容,容：,若第,i,项登记,着,着关键,字,字,k，,则取出,该,该项元,素,素即可,；,；,若第,i,项为空,，,，则表,示,示在,Hash,表中没,有,有该关,键,键字的,信息；,若第,i,项不空,，,，且登,记,记的不,是,是关键,字,字,k，,则令,imod(i1,，,，n),，,，,转(2)继续,检,检查。,9.52,几,几种常,用,用的,Hash,表,例,将关键,字,字序列(09,，,，31,，,，26,，,，19,，,，01,，,，13,，,，02,，,，11,，,，27,，,，,16，05，21),依,依次填,入,入长度,为,为,n12,的线性,Hash,表中。,设,设,Hash,码为,iINT(k/3)1,。,。,9.52,几,几种常,用,用的,Hash,表,缺点：,(1),在,在线性,Hash,表填入,的,的过程,中,中，当,发,发生冲,突,突时，,首,首先考,虑的是,下,下一项,，,，因此,，,，当,Hash,码的冲,突,突较多,时,时，在,线,线,性,Hash,表中会,存,存在“,堆,堆聚”,现,现象，,即,即许多,关,关键字,被,被连续,登记在,一,一起，,从,从而会,降,降低查,找,找效率,。,。,(2),在,在线性,Hash,表的填,入,入过程,中,中，处,理,理冲突,时,时会带,来,来新的,冲突。,9.52,几,几种常,用,用的,Hash,表,9.52,几,几种常,用,用的,Hash,表,9.52.2,随,随,机,机,Hash,表,9.52,几,几种常,用,用的,Hash,表,1.随,机,机,Hash,表的填,入,入,将关键,字,字,k,及有关,信,信息填,入,入随机,Hash,表的步,骤,骤如下,：,：,(1),计,计算关,键,键字,k,的,Hash,码,i,0,i(k)。,且令,ii,0,。,(2),伪随机,数,数序列,初,初始化,，,，令,j1,（,（,即将取,随,随机数,指,指针指,向伪随,机,机数序,列,列中的,第,第1个,随,随机数,）,）。,(3),检,检查表,中,中第,i,项的内,容,容：,若第,i,项为空,，,，则将,关,关键字,k,及有关,信,信息填,入,入该项,；,；,若第,i,项不空,，,，则令,imod(i,0,RN(j),，,，n),，,，,并令,jj,1（,即将取,随,随机数,指,指针指,向,向下一,个,个随机,数,数），,转(3)继续,检,检查。,其,其中,RN(j),表示伪,随,随机数,序,序列,RN,中的,第,j,个随机,数,数。,9.52,几,几种常,用,用的,Hash,表,伪随机,数,数序列,RN,按下,列,列方,法,法产,生,生：,R1,FORj,1TOnDO,Rmod(5*R，4n),RN(j)INT(R/4),9.52,几,几种,常,常用,的,的,Hash,表,例,将关,键,键字,序,序列(09，31,，,，26，19,，,，01，13,，,，02，11,，,，27,，16，05,，,，21),依,依次,填,填入,长,长度,为,为,n2,4,16,的随,机,机,Hash,表,中。,设,设,Hash,码为,iINT(k/3),1,。,。,伪随,机,机数,序,序列,为,为：1，6，15,，,，12，13,，,，2,，,，11，8，9，,14,，,，7,，,，4,，,，5,，,，10，3，0。,9.52,几,几种,常,常用,的,的,Hash,表,2.,随,随,机,机,Hash,表的,取,取出,要在,随,随机,Hash,表中,取,取出,关,关键,字,字,k,的元,素,素，,其,其步,骤,骤如,下,下：,(1)计,算,算关,键,键字,k,的,Hash,码,i,0,i(k)。,且令,ii,0,。,(2),伪随,机,机数,序,序列,初,初始,化,化，,令,令,j1（,即将,取,取随,机,机数,指,指针,指,指,向伪,随,随机,数,数序,列,列中,的,的第1个,随,随机,数,数）,。,。,(3)检,查,查表,中,中第,i,项的,内,内容,：,：,若第,i,项登,记,记着,关,关键,字,字,k，,则取,出,出该,项,项元,素,素即,可,可；,若第,i,项空,，,，则,表,表示,在,在,Hash,表中,没,没有,该,该关,键,键字,信,信息,；,；,若第,i,项不,空,空，,且,且登,记,记的,不,不是,关,关键,字,字,k，,则令,imod(i,0,RN(j),，,，n)，,并令,jj1（,即将,取,取随,机,机数,指针,指,指向,下,下一,个,个随,机,机数,）,），,转,转(3),继,继续,检,检查,。,。其,中,中,RN(j),表示伪随,机,机数序列,RN,中的第,j,个随机数,。,。,9.52,几,几种,常,常用的,Hash,表,9.52,几,几种,常,常用的,Hash,表,9.52.3,溢,溢出,Hash,表,溢出,Hash,表包括,Hash,表和溢出,表,表两部分,。,。,在,Hash,表的填入,过,过程中，,将,将冲突的,元,元素顺序,填,填入溢出,表,表,，而当查,找,找过程中,发,发现冲突,时,时，就在,溢,溢出表中,进,进行顺序,查找。,溢出表是,一,一个顺序,查,查找表。,9.52,几,几种,常,常用的,Hash,表,1.溢出,Hash,表的填入,将关键字,k,及有关信,息,息填入溢,出,出,Hash,表的步骤,如,如下：,(1)计,算,算关键字,k,的,Hash,码,ii(k)。,(2),检查表中,第,第,i,项的内容,：,：,若第,i,项为空，,则,则将关键,字,字,k,及有关信,息,息填入该,项,项；,若第,i,项不空，,则,则将关键,字,字,k,及有关信,息,息依次填,入,入溢出,表中的自,由,由项。,9.52,几,几种,常,常用的,Hash,表,2. 溢,出,出,Hash,表的取出,要在溢出,Hash,表中取出,关,关键字,k,的元素，,其,其步骤如,下,下：,(1)计,算,算关键字,k,的,Hash,码,ii(k)。,(2),检查表中,第,第,i,项的内容,：,：,若第,i,项登记着,关,关键字,k，,则取出该,项,项元素即,可,可；,若第,i,项为空，,则,则表示在,Hash,表中没有,该,该关键字,信息；,若第,i,项不空，,且,且登记的,不,不是关键,字,字,k，,则转入在,溢,溢出,表中进行,顺,顺序查找,。,。,9.52,几,几种,常,常用的,Hash,表,例,将关键字,序,序列(09，31,，,，26，19，01，13,，,，02，11，27,，16，05，21)依次,填,填入长度,为,为,n12,的溢出,Hash,表中。,设,Hash,码为,iINT(k/3)1,。,。,9.52,几,几种,常,常用的,Hash,表,9.52.4,拉,拉链,Hash,表,拉链,Hash,表又分为,外,外链,Hash,表与内链,Hash,表。,9.52,几,几种,常,常用的,Hash,表,1.外链,Hash,表的填入,将关键字,k,及有关信,息,息填入外,链,链,Hash,表的步骤,如,如下：,(1)计,算,算关键字,k,的,Hash,码,ii(k)。,(2),取得一个,新,新结点,p，,并将关键,字,字,k,及有关信,息,息填入,结点,p。,(3),将结点,p,链入以,H(i),为头指针,的,的链表的,链,链头。,9.52,几,几,种,种,常,常,用,用,的,的,Hash,表,例,将,将,关,关,键,键,字,字,序,序,列,列(09,，,，31,，,，26,，,，19,，,，01,，,，13,，,，02,，,，11,，,，27,，,，16,，,，,05,，,，21),依,依,次,次,填,填,入,入,长,长,度,度,为,为,n,12,的,外,外,链,链,Hash,表,中,中,。,。,设,Hash,码,为,为,i,INT(k/3),1,。,。,9.52,几,几,种,种,常,常,用,用,的,的,Hash,表,2.,外,外,链,链,Hash,表,的,的,取,取,出,出,要,在,在,外,外,链,链,Hash,表,中,中,取,取,出,出,关,关,键,键,字,字,k,的,元,元,素,素,，,，,其,其,步,步,骤,骤,如,如,下,下,：,：,(1),计,计,算,算,关,关,键,键,字,字,k,的,Hash,码,i,i(k),。,。,(2),在,以,以,H(i),为,头,头,指,指,针,针,的,的,链,链,表,表,中,中,顺,顺,序,序,查,查,找,找,关,关,键,键,字,字,为,为,k,的,结,结,点,。,。,若,若,找,找,到,到,，,，,则,则,从,从,结,结,点,点,中,中,取,取,出,出,该,该,元,元,素,素,。,。,9.52,几,几,种,种,常,常,用,用,的,的,Hash,表,9.52.5,指,指,标,标,Hash,表,指,标,标,Hash,表,包,包,括,括,指,指,标,标,表,表,与,与,内,内,容,容,表,表,两,两,部,部,分,分,。,。,9.17answer,/,SearchforanddeletetherecordwithKeyK(p311),template,boolhashdict:,hashDelete(constKey&K,Elem&e)const,inthome;/HomepositionforK,intpos=home=h(K);/Initialpositonprobesequence,for(inti=1;!KEComp:eq(K,HTpos)i+),/Nextonprobesequence,pos=(home+p(K,i)%M;,if(KEComp:eq(K,HTpos)/Foundit,e=HTpos;,HTpos=TOMBSTONE;/Deleteit(p320),returntrue;,elsereturnfalse;/Knotinhashtable,/InserteintohashtableHT(p311),template,boolhashdict:,hashInsert(const Elem& e),int home;/ Home position fore,int pos =home= h(getkey(e);/ Init probe sequence,for (int i=1; (!(EEComp:eq(EMPTY,HTpos) i+) ,pos =(home + p(getkey(e),i)% M;/ Followprobes,if (EEComp:eq(e, HTpos) returnfalse;/ Dup,HTpos =e;/ Inserte,return true;,The searchfunctionneednot be changedat all, since tombstone slotsshould betreated asthough they are full.,