2022年数据结构与算法分析之查找技术(共74张PPT).pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第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，,则输出,k1。,PROCEDURE SERCH(V，n，x，k),k1,WHILE(kn)and(V(k)x)DO kk1,IF(kn1)THEN k1,RETURN,9.1 顺序查找,/*函数返回被查找元素,x,在线性表中的序号，,如果在线性表中不存在元素值,x，,则返回1*/,int serch(v，n，x),int n；,ET v，x；/*ET,为线性表数据类型*/,int k；,k0；,while (kn)&(vkx)kk1；,if(kn)k1；,return(k)；,9.1 顺序查找,9.1.2 线性链表的顺序查找,9.1 顺序查找,线性表在链式存储结构下的顺序查找,输入：线性链表头指针,HEAD,以及存储空间,V、NEXT；,被查找的元素,x。,输出：被查找元素,x,的结点在线性链表中的存储序号,k。,如果在线性链表中不存在元素值为,x,的结点，,则输出,k1。,PROCEDURE LSERCH(V，NEXT，HEAD，x，k),kHEAD,WHILE(k0)and(V(k)x)DO kNEXT(k),IF(k0)THEN k1,RETURN,9.1 顺序查找,struct node,ET d；struct node *next；,/*,函数返回被查找元素,x,所在结点的存储地址，,如果在线性链表中不存在元素值为,x,的结点，则返回,NULL*/,struct node *lserch(head，x),struct node *head；,ET x；/*ET,为线性链表中值域的数据类型*/,struct node k；,khead；,while (kNULL)&(kdx)kknext；,return(k)；,2 几种常用的Hash表,若第i项为空，则说明表中没有关键字为k的元素；,52 几种常用的Hash表,return(k)；,if(qrchild!NULL)qqrchild；,ET d；,若x大于中间项的值，则在线性表的后半部分（即中间项,将关键字序列(09，31，26，19，01，13，02，11，27,在元素x，则输出k1。,以前的部分）以相同的方法进行查找；,WHILE(p0)and(V(p)x)DO,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(ij)DO,k(ij)/2,IF(V(k)x)THEN RETURN,IF(V(k)x)THEN jk1；,ELSE ik1；,IF (ij)THEN k1,RETURN,int home;/Home position for e,HTpos=e;/Insert e,要在外链Hash表中取出关键字k的元素，其步骤如下：,输入：线性表长度n以及线性表的存储空间V；,即Hash码的均匀性要比较好。,struct indnode,(1)首先查找索引表，以便确定被查元素所在的子表。,(2)在以H(i)为头指针的链表中顺序查找关键字为k的结,(3)检查表中第i项的内容：,51 Hash表的基本概念,无论是插入到左子树还是右子树，同样按照上述方法处理。,将关键字序列(09，31，26，19，01，13，02，11，27,表中没有这个元素)为止。,则称此表为直接查找表。,52 几种常用的Hash表,9.2 有序表的对分查找,int bserch(v，n，x)/*,函数返回被查找元素,x,在线性表中的序号,如果在线性表中不存在元素值,x，,则返回1*/,int n；,ET x，v；,int i，j，k；,i1；jn；,while(ij),k(ij)/2；,if(vk1x)return(k1)；,if(vk1x)jk1；,else ik1；,return(1)；,9.3 分块查找,分块有序表,将长度为,n,线性表分成,m,个子表，各子表的长度可以相,等，也可以互相不等，但要求后一个子表中的每一个,元素均大于前一个子表中的所有元素。,分块有序表的结构可以分为两部分：,(1)线性表本身采用顺序存储结构。,(2)再建立一个索引表。在索引表中，对线性表的每个子表建立一个索引结点，每个结点包括两个域：一是数据域，用于存放对应子表中的最大元素值；二是指针域，用于指示对应子表的第一个元素在整个线性表中的序号。,9.3 分块查找,struct indnode,ET key；/*,数据域，存放子表中的最大值，,其类型与线性表中元素的数据类,型相同*/,int k；/*,指针域，指示子表中第一个元素,在线性表中的序号*/,；,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(ji1)DO ,对分查找索引表,t(ij)/2,IF(xKEY(t)THEN jt,ELSE it,IF(ij)and(xKEY(i)THEN ij,jK(i)；tn,IF(im)THEN tK(i1)1 ,确定顺序查找的终点,WHILE(jt)and(V(j)x)DO jj1 ,顺序查找子表,IF(jt)THEN j1,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 分块查找,struct indnode,ET key；/*,数据域，存放子表中的最大值，,其类型与线性表中元素的数据类型相同*/,int k；/*,指针域，指示子表中第一个元素在线性表中的序号*/,；,/*函数返回被查找元素,x,在线性表中的序号，,如果在线性表中不存在元素值,x，,则返回1*/,int inserch(v，n，s，m，x),int n，m；,ET x，v；,struct indnode s；,if(qlchild!NULL)qqlchild；,有序线性表在顺序存储结构下的对分查找,/Search for and delete the record with Key K (p311),否则取出第i项中的元素即可。,prchildNULL；,(3)将结点p链入以H(i)为头指针的链表的链头。,2 几种常用的Hash表,其中RN(j)表示伪随机数序列RN中的,t(ij)/2；,，16，05，21)依次填入长度为n12的溢出Hash表中。,52 几种常用的Hash表,/*函数返回被查值x所在结点的存储地址*/,struct node,9.3 分块查找,int i，j，t；,i1；jm；,while(ji1)/*,对分查找索引表*/,t(ij)/2；,if(xst.key)jt；,else it；,if(i!j)&(xsi.key)ij；,jsi.k；tn；,if(i!m)tsi1.k1；/*,确定顺序查找的终点*/,while(jt)&(Vj!x)jj1；/*,顺序查找子表*/,if(jt)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。,PROCEDURE INBSORT(A，n，BT),BT0,FOR k1 TO n DO,NEW(p),取得一个新结点,V(p)A(k)；L(p)0；R(p)0,jBT,IF (j0)THEN BTp ,若二叉排序树为空,ELSE ,二叉排序树不空,9.4 二叉排序树查找,WHILE(L(j)p)and(R(j)p)DO ,未到叶子结点,IF(A(k)V(j)THEN ,插入到左子树,IF(L(j)0)THEN jL(j),ELSE L(j)p,ELSE ,插入到右子树,IF(R(j)0)THEN jR(j),ELSE R(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)/*,函数返回二叉排序树头指针*/,int n；,ET a；,struct btnode *p，*q，*bt；,int k；,btNULL；,9.4 二叉排序树查找,for(k0；kn；k),p(struct btnode *)malloc(sizeof(struct btnode)；,pdak；plchildNULL；prchildNULL；,/*,置新结点的数据域与左、右指针域*/,qbt；,if(qNULL)btp；/*,二叉排序树为空*/,else /*,二叉排序树不空*/,while(qlchild!p)&(qrchild!p),if(akqd)/*,插入到左子树*/,if(qlchild!NULL)qqlchild；,else qlchildp；,9.4 二叉排序树查找,else /*,插入到右子树*/,if(qrchild!NULL)qqrchild；,else qrchildp；,return(bt)；/*,返回二叉排序树头指针*/,9.4 二叉排序树查找,9.4.2 二叉排序树查找,从二叉排序树的根结点开始与被查值进行比较：,(1)若被查值等于根结点值，查找成功，查找过程结束。,(2)若被查值小于根结点值，则到左子树中去查找。,(3)若被查值大于根结点值，则到右子树中去查找。,在左、右子树中查找时也采用上述方法。,查找过程直到查找成功或所考虑的子树已空为止。,9.4 二叉排序树查找,二叉排序树查找,输入：二叉排序树头指针,BT,以及存储空间；被查元素,x。,输出：被查元素,x,在二叉排序树空间中的存储结点序号,p,PROCEDURE BSTSERCH(BT，x，p),PBT,WHILE(p0)and(V(p)x)DO,IF(xV(p)THEN pL(p),沿左子树查找,ELSE pR(p),沿右子树查找,RETURN,9.4 二叉排序树查找,struct btnode /*,定义结点类型*/,ET d；/*,数据域*/,struct btnode *lchild；/*,左指针域*/,struct btnode *rchild；/*,右指针域*/,；,9.4 二叉排序树查找,/*函数返回被查值,x,所在结点的存储地址*/,struct btnode *bstserch(bt，x),struct btnode *bt；,ET x；,struct btnode *p；,pbt；,while(p!NULL)&(pd!x),if(xpd)pplchild；/*,沿左子树查找*/,else pprchild；/*,沿右子树查找*/,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,的映象函数,ii(k)；,(2),将关键字,k,及有关元素信息填入到表的第,i,项。,9.51,Hash,表的基本概念,2.直接查找表的取出,要在直接查找表中取出关键字,k,的元素，也只需做以下两,步：,(1)计算关键字,k,的映象函数,ii(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)依次填入长度为,n12,的表中。设映象函,数为,iINT(k/3)1。,9.51,Hash,表的基本概念,设表的长度为,n。,如果存在一个函数,ii(k)，,对于表中,的任意一个元素的关键字,k，,满足1,in，,则称此表,为,Hash,表。其中函数,ii(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.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)，,并令,jj1（,即将取随机数指针指向下一个随机数），,转(3)继续检查。其中,RN(j),表示伪随机数序列,RN,中的,第,j,个随机数。,9.52 几种常用的,Hash,表,伪随机数序列,RN,按下列方法产生：,R1,FOR j1 TO n DO,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)依次填入长度为,n12,的外链,Hash,表中。,设,Hash,码为,iINT(k/3)1。,9.52 几种常用的,Hash,表,2.外链,Hash,表的取出,要在外链,Hash,表中取出关键字,k,的元素，其步骤如下：,(1)计算关键字,k,的,Hash,码,ii(k)。,(2),在以,H(i),为头指针的链表中顺序查找关键字为,k,的结,点。若找到，则从结点中取出该元素。,9.52 几种常用的,Hash,表,9.52.5 指标,Hash,表,指标,Hash,表包括指标表与内容表两部分。,9.17 answer,/,Search for and delete the record with Key K (p311),template,bool hashdict:,hashDelete(const Key&K,Elem&e)const,int home;,/Home position for K,int pos=home=h(K);,/Initial posit on probe sequence,for(int i=1;!KEComp:eq(K,HTpos)i+),/Next on probe sequence,pos=(home+p(K,i)%M;,if(KEComp:eq(K,HTpos),/Found it,e=HTpos;,HTpos=TOMBSTONE;,/Delete it(p320),return true;,else return false;,/K not in hash table,/Insert e into hash table HT(p311),template,bool hashdict:,hashInsert(const Elem&e),int home;,/Home position for e,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;,/Follow probes,if(EEComp:eq(e,HTpos)return false;,/Dup,HTpos=e;,/Insert e,return true;,The search function need not be changed at all,since tombstone slots should be treated as though they are full.,