第八讲查找表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,何谓查找表,？,查找表是由,同一类型,的数据元素,(,或记录,),构成的,集合,。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,对查找表经常进行的,操作,:,1,）,查询,某个,“特定的”,数据元素是否在查找表中；,2,）,检索,某个,“特定的”,数据元素的各种属性；,3,）在查找表中,插入,一个数据元素；,4,）从查找表中,删去,某个数据元素。,仅作,查询,和,检索,操作的查找表。,静态查找表,有时在查询之后，还需要将“查询”结果为“,不在查找表中,”的数据元素,插入到,查找表中；或者，从查找表中,删除,其“查询”结果为“,在查找表中,”的数据元素。,动态查找表,查找表可分为两类,:,是数据元素（或记录）中某个,数据项,的值，用以,标识,（识别）一个数据元素（或记录）。,关键字,若此关键字可以识别,唯一的,一个记录，则称之谓,“,主关键字,”。,若此关键字能识别,若干,记录，则称,之谓,“,次关键字,”,。,根据给定的某个值，在查找表中,确定一个其关键字等于给定值的数据元素或（记录）。,查找,若查找表中存在这样一个记录，则称“,查找成功,”。查找结果,给出整个记录的信息，或指示该记录在查找表中的位置,；,否则称“,查找不成功,”。查找结果,给出,“空记录”或“空指针”。,9.1,静 态 查 找 表,数据对象,D,：,数据关系,R,：,D,是具有相同特性的数,据元素的集合。,每个数,据元素含有类型相同的,关键字,，可唯一标识数,据元素。,数据元素同属一个集合。,ADT StaticSearchTable,Create(,&,ST,n);,Destroy(,&,ST);,Search(ST,key);,Traverse(ST,Visit();,基本操作,P,：,ADT StaticSearchTable,构造一个含,n,个数据元素,的静态查找表,ST,。,Create(,&,ST,n);,操作结果：,销毁表,ST,。,Destroy(,初始条件：,操作结果：,静态查找表,ST,存在；,若,ST,中存在其关键字等于,key,的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,Search(ST,key);,初始条件：,操作结果：,静态查找表,ST,存在，,key,为和查找表中元素的关键字类型相同的给定值；,按某种次序对,ST,的每个元素调用函数,Visit(),一次且仅一次，一旦,Visit(),失败，则操作失败。,Traverse(ST,Visit();,初始条件：,操作结果：,静态查找表,ST,存在，,Visit,是对元素操作的应用函数；,typedef struct,/,数据元素存储空间基址，建表时,/,按实际长度分配，,0,号单元留空,int,length,;/,表的长度,SSTable;,假设,静态查找表,的,顺序存储结构,为,ElemType,*,elem,;,数据元素类型的定义为,:,typedef struct,keyType key;/,关键字域,/,其它属性域,ElemType;,TElemType;,一、顺序查找表,二、有序查找表,三、静态查找树表,四、索引顺序表,以顺序表或线性链表表示静态查找表,一、,顺序查找表,ST.elem,回顾顺序表的查找过程：,假设给定值,e=64,要求,ST.elemk=e,问,:k=?,k,k,int,location(,SqList L,ElemType,&,e,Status(*compare)(ElemType,ElemType,),k=1;,p=L.elem;,while,(,k=L.length,&,!(*compare)(*p+,e),),k,+,;,if,(k=L.length),return,k;,else return,0;,/location,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,int,Search_Seq(SSTable ST,KeyType key),/,在顺序表,ST,中顺序查找其关键字等于,/key,的数据元素。若找到，则函数值为,/,该元素在表中的位置，否则为,0,。,ST.elem0.key=key;,/“,哨兵”,for,(,i=ST.length;,ST.elemi.key,!=,key;,-,i,);,/,从后往前找,return,i;,/,找不到时，,i,为,0,/Search_Seq,定义：,查找算法的,平均查找长度,(,A,verage,S,earch,L,ength),为确定记录在查找表中的位置，需和给定值,进行比较的关键字个数的期望值,其中,:,n,为表长，,P,i,为查找表中第,i,个记录的概率，,且 ，,C,i,为找到该记录时，曾,和给定,值比较过的关键字的个数。,分析顺序查找的时间性能,在,等概率,查找的情况下，,顺序表查找的平均查找长度,为：,对,顺序表,而言，,C,i,=n-i+1,ASL=nP,1,+(n-1)P,2,+2P,n-1,+P,n,若查找概率无法事先测定，则查找过程采取的改进办法是，,在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上,。,在,不等概率查找,的情况下，,ASL,ss,在,P,n,P,n-1,P,2,P,1,时,取极小值,上述顺序查找表的查找算法简单，,但平均查找长度较大，特别不适用于表长较大的查找表。,二、有序查找表,若以,有序表,表示静态查找表，则查找过程可以基于“,折半,”进行。,ST.elem,ST.length,例如,:,key=64,的查找过程如下：,low,high,mid,low,mid,high,mid,low,指示查找区间的下界,high,指示查找区间的上界,mid,=(low+high)/2,int,Search_Bin(SSTable ST,KeyType key),low=1,;,high=ST.length,;,/,置区间初值,while,(low 50,时，可得近似结果,一般情况下，表长为,n,的折半查找的判定树的深度和含有,n,个结点的完全二叉树的深度相同。,关键字,:,A B C D E,Pi:,0.2 0.3 0.05 0.3 0.15,Ci:,2 3 1 2 3,三、静态查找树表,在,不等概率查找,的情况下，,折半查找,不是,有序表最好的查找方法。,例如,:,此时,ASL=2,0.2+30.3+10.05+20.3+30.15=,2.4,若改变,Ci,的值,2 1 3 2 3,则,ASL=2,0.2+10.3+30.05+20.3+30.15=,1.9,使,达最小的判定树称为,最优二叉树,，,其中,:,定义,:,为计算方便，令,w,i,=,p,i,选择二叉树的根结点，,使 达最小,介绍一种,次优二叉树,的构造方法：,为便于计算，引入累计权值和,并设,w,l,-1,=0,和,sw,l,-1,=0,，,则推导可得,0,2,3,8,11,15,18,23,例如,:,l,h,21,18,12,4,3,10,18,h,9,6,0,8,E,C,2,1,A,h,5,3,l,h,G,3,0,1,3,E,C,G,A,B,D,F,所得次优二叉树如下所示,:,查找比较“总次数”,=3,2,+4,1,+2,5,+3,3,+1,4,+3,3,+2,5,=,52,查找比较“总次数”,=3,2,+2,1,+3,5,+1,3,+3,4,+2,3,+3,5,=,59,和折半查找相比较,D,B,A,C,F,E,G,Status,SecondOptimal(BiTree,&,T,ElemType R,float,sw,int,low,int,high),/,由有序表,Rlow.high,及其累计权值表,sw,/,递归构造次优查找树,T,。,选择最小的,P,i,值,if,(,!,(T=(BiTree),malloc,(,sizeof,(BiTNode),return,ERROR;,T-data=,Ri,;/,生成结点,构造次优二叉树的算法,CONTINUE,if,(,i,=,low,),T-lchild=,NULL,;,/,左子树空,else,SecondOptimal(T-lchild,R,sw,low,i-1);,/,构造左子树,if,(,i,=,high,),T-rchild=,NULL,;,/,右子树空,else,SecondOptimal(T-rchild,R,sw,i+1,high);,/,构造右子树,return,OK;,/SecondOptimal,次优查找树采用二叉链表的存储结构,Status,CreateSOSTre(,SOSTree,&,T,SSTable ST),/,由有序表,ST,构造一棵次优查找树,T,/ST,的数据元素含有权域,weight,if,(ST.length=0)T=,NULL,;,else,FindSW(sw,ST);,/,按照有序表,ST,中各数据元素,/,的,weight,值求累计权值表,SecondOpiamal(T,ST.elem,sw,1,ST.length);,return,OK;,/CreatSOSTree,索引顺序表的查找过程：,1,）由索引确定记录所在区间；,2,）在顺序表的某个区间内进行查找。,注意：索引可以根据查找表的特点来构造。,可见，,索引顺序查找,的过程也是一个,“缩小区间”,的查找过程。,索引顺序查找的平均查找长度,=,查找“索引”的平均查找长度,+,查找“顺序表”的平均查找长度,ADT DynamicSearchTable,抽象数据类型,动态查找表,的定义如下：,数据对象,D,：,数据关系,R,：,数据元素同属一个集合。,D,是具有相同特性的数据元素的集合。,每个数据元素含有类型相同的关键字，可唯一标识数据元素。,InitDSTable(,&,DT),基本操作,P,：,DestroyDSTable(,&,DT),SearchDSTable(DT,key);,InsertDSTable(,&,DT,e);,DeleteDSTable(,&,T,key);,TraverseDSTable(DT,Visit();,ADT DynamicSearchTable,操作结果：,构造一个空的动态查找表,DT,。,InitDSTable(,&,DT);,销毁动态查找表,DT,。,DestroyDSTable(,&,DT);,初始条件：,操作结果：,动态查找表,DT,存在；,若,DT,中存在其关键字等于,key,的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,SearchDSTable(DT,key);,初始条件：,操作结果：,动态查找表,DT,存在，,key,为和关键字类型相同的给,定值；,动态查找表,DT,存在，,e,为待插入的数据元素；,InsertDSTable(,&,DT,e);,初始条件：,操作结果：,若,DT,中不存在其关键字,等于,e.key,的 数据元素，,则插入,e,到,DT,。,动态查找表,DT,存在，,key,为和关键字类型相同的给,定值；,DeleteDSTable(,&,T,key);,初始条件：,操作结果：,若,DT,中存在其关键字等于,key,的数据元素，则删,除之。,动态查找表,DT,存在，,Visit,是对结点操作的应用函数；,TraverseDSTable(DT,Visit();,初始条件：,操作结果：,按某种次序对,DT,的每个结,点调用函数,Visit(),一次且至,多一次。一旦,Visit(),失败，,则操作失败。,9.2,动 态 查 找 树 表,(n),(1),(n),(1),(nlogn),综合上一节讨论的几种查找表的特性：,查找 插入 删除,无序顺序表,无序线性链表,有序顺序表,有序线性链表,静态查找树表,(n),(n),(logn),(n),(logn),(1),(1),(n),(1),(nlogn),1,）从,查找,性能看，最好情况能达,(logn),，此时要求表,有序,；,2,）从,插入,和,删除,的性能看，最好,情况能达,(1),，此时要求存储,结构是,链表,。,可得如下结论：,一、二叉排序树（二叉查找树）,二、二叉平衡树,三、,B-,树,四、,B,+,树,五、键 树,一、二叉排序树,（二叉查找树）,1,定义,2,查找算法,3,插入算法,4,删除算法,5,查找性能的分析,（,1,）若它的左子树不空，则左子树上,所有,结点的值,均小于,根结点的值；,1,定义：,二叉排序树,或者是一棵空树；或者,是具有如下特性的二叉树：,（,3,）它的左、右子树,也都,分别,是二叉,排序树,。,（,2,）若它的右子树不空，则右子树上,所有,结点的值,均大于,根结点的值；,50,30,80,20,90,10,85,40,35,25,23,88,例如,:,是二叉排序树。,66,不,通常，取二叉链表作为,二叉排序树的存储结构,typedef struct,BiTNode,/,结点结构,struct,BiTNode,*l,child,*r,child;,/,左右孩子指针,BiTNode,*,BiTree;,TElemType data;,2,二叉排序树的查找算法：,1,）若给定值,等于,根结点的关键字，则,查找成功,；,2,）若给定值,小于,根结点的关键字，则,继续在左子树上进行查找,；,3,）若给定值,大于,根结点的关键字，则,继续在右子树上进行查找,。,若二叉排序树,为空,，则,查找不成功,；,否则,50,30,80,20,90,85,40,35,88,32,例如,:,二叉排序树,查找关键字,=50,50,50,35,50,30,40,35,50,90,50,80,90,95,从上述查找过程可见，,在查找过程中，生成了一条,查找路径,：,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点,;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,算法描述如下：,Status,SearchBST(BiTree,T,KeyType key,BiTree,f,BiTree,&,p,),/,在根指针,T,所指二叉排序树中递归地查找其,/,关键字等于,key,的数据元素，若,查找成功,，,/,则返回指针,p,指向该数据元素的结点，并返回,/,函数值为,TRUE,;,/SearchBST,否则表明,查找不成功,，返回,/,指针,p,指向查找路径上访问的最后一个结点，,/,并返回函数值为,FALSE,指针,f,指向当前访问,/,的结点的双亲，其初始调用值为,NULL,if,(,!,T),else if,(EQ(key,T-data.key),else if,(LT(key,T-data.key),else,p=f;,return FALSE,;,/,查找不成功,p=T;,return TRUE,;,/,查找成功,SearchBST(T-,l,child,key,T,p),;,/,在左子树中继续查找,SearchBST(T-,r,child,key,T,p),;,/,在右子树中继续查找,30,20,10,40,35,25,23,f,T,设,key=48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,根据动态查找表的定义,，“插入”操作在,查找不成功,时才进行,；,3,二叉排序树的插入算法,若二叉排序树为,空树,，则新插入的结点为,新的根结点,；否则，新插入的结点必为一个,新的叶子结点,，其,插入位置,由查找过程得到。,Status,Insert BST(BiTree,&,T,ElemType e),/,当二叉排序树中不存在关键字等于,e.key,的,/数据元素时，插入元素值为,e,的结点，并返,/回,TRUE;,否则，不进行插入并返回,FALSE,if,(,!,SearchBST(T,e.key,NULL,p),else return FALSE,;,/Insert BST,s=(BiTree),malloc,(,sizeof,(BiTNode);,/,为新结点分配空间,s-data=e;,s-lchild=s-rchild=,NULL,;,if,(,!,p)T=s;,/,插入,s,为新的根结点,else if,(,LT(e.key,p-data.key),),p-lchild=s;,/,插入*,s,为*,p,的左孩子,else,p-rchild=s;,/,插入*,s,为*,p,的右孩子,return TRUE,;,/,插入成功,（,1,）被删除的结点,是叶子,；,（,2,）被删除的结点,只有左子树,或者,只有右子树,；,（,3,）被删除的结点,既有左子树，也有右子树,。,4,二叉排序树的删除算法,可分,三种情况,讨论：,和插入相反，删除在,查找成功,之后进行，并且要求在删除二叉排序树上某个结点之后，,仍然保持二叉排序树的特性,。,50,30,80,20,90,85,40,35,88,32,（,1,）被删除的结点是,叶子结点,例如,:,被删关键字,=20,88,其双亲结点中相应指针域的值改为“空”,50,30,80,20,90,85,40,35,88,32,（,2,）被删除的结点,只有左子树,或者,只有右子树,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字,=40,80,50,30,80,20,90,85,40,35,88,32,（,3,）被删除的结点,既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字,=50,Status,DeleteBST(,BiTree,&,T,KeyType key),/,若二叉排序树,T,中存在其关键字等于,key,的,/,数据元素，则删除该数据元素结点，并返回,/,函数值,TRUE,，否则返回函数值,FALSE,if,(,!T,),return FALSE,;,/,不存在关键字等于,key,的数据元素,else ,/DeleteBST,算法描述如下：,if,(EQ(key,T-data.key),/,找到关键字等于,key,的数据元素,else if,(LT(key,T-data.key),else,Delete(T),;,return TRUE,;,DeleteBST(T-lchild,key);,/,继续在左子树中进行查找,DeleteBST(T-rchild,key);,/,继续在右子树中进行查找,void,Delete(BiTree,&,p),/,从,二叉排序树中删除结点,p,，,/,并重接它的左子树或右子树,if,(,!,p-rchild),else if,(,!,p-lchild),else ,/Delete,其中,删除操作,过程如下所描述：,/,右子树为空树则只需重接它的左子树,q=p;p=p-lchild;free(q);,p,p,/,左子树为空树只需重接它的右子树,q=p;p=p-rchild;free(q);,p,p,q=p;s=p-lchild;,while,(s-rchild),q=s;s=s-rchild;,/s,指向被删结点的前驱,/,左右子树均不空,p-data=s-data;,if,(q,!=,p)q-rchild=s-lchild;,else,q-lchild=s-lchild;,/,重接*,q,的左子树,free(s);,p,q,s,5,查找性能的分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的,ASL,值，显然，由值相同的,n,个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。,由关键字序列,3,，,1,，,2,，,5,，,4,构造而得的二叉排序树，,由关键字序列,1,，,2,，,3,，,4,，,5,构造而得的二叉排序树，,例如：,2,1,3,4,5,3,5,4,1,2,ASL=,（,1+2+3+4+5,）,/5,=3,ASL=,（,1+2+3+2+3,）,/5,=2.2,下面讨论平均情况,:,不失一般性，假设长度为,n,的序列中有,k,个关键字,小于,第一个关键字，则必有,n-k-1,个关键字,大于,第一个关键字,由它构造的二叉排序树：,n-k-1,k,的平均查找长度是,n,和,k,的函数,P(n,k)(0,k n-1),。,假设,n,个关键字可能出现的,n!,种排列的可能性相同，则含,n,个关键字的二叉排序树的平均查找长度：,在,等概率查找,的情况下，,由此,可类似于解差分方程，此递归方程有解：,二、二叉平衡树,何谓“二叉平衡树”？,二叉平衡树的查找性能分析,如何构造“二叉平衡树”,二叉平衡树,是二叉查找树的另一种形式，其特点为：,树中每个结点的,左、右子树深度之差的绝对值不大于,1,。,例如,:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,构造二叉平衡（查找）树的方法是：,在插入过程中，采用平衡旋转技术。,例如,:,依次插入的关键字为,5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转,一次,先向右旋转,再向左旋转,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字,9,在平衡树上进行查找的过程和二叉排序树相同，因此，,查找过程中和给定值,进行比较的关键字的个数,不超过平衡 树的深度。,平衡树的查找性能分析：,问：含,n,个关键字,的二叉平衡树,可能达到的,最大深度,是多少？,n,=0,空树,最大深度为,0,n,=1,最大深度为,1,n,=2,最大深度为,2,n,=4,最大深度为,3,n,=7,最大深度为,4,先看几个具体情况,:,反过来问，,深度为,h,的二叉,平衡树,中所,含结点的最小值,N,h,是多少？,h,=0,N,0,=0,h,=1,h,=2,h,=3,一般情况下,N,1,=1,N,2,=2,N,3,=4,N,h,=,N,h-1,+,N,h-2,+1,利用归纳法可证得,N,h,=,F,h+2,-1,因此，在,二叉平衡树,上进行查找时，,查找过程中和给定值,进行比较的关键字的个数和,log(n),相当,。,由此推得，,深度为,h,的,二叉平衡树,中所,含结点的最小值,N,h,=,h+2,/5-1,。,反之，,含有,n,个结点的二叉平衡树能达到的最大深度,h,n,=log,(5(n+1)-2,。,三、,B-,树,1,定义,2,查找过程,3,插入操作,4,删除操作,5,查找性能的分析,1,B-,树的定义,B-,树是一种,平衡,的,多路,查找,树：,在,m,阶的,B-,树上，每个非终端结点可能含有：,n,个,关键字,K,i,（,1,i,n,）,nm,n,个,指向记录的指针,D,i,（,1in,）,n+1,个,指向子树的指针,A,i,（,0in,）,多叉树的特性,typedef struct BTNode,int,keynum,;/,结点中,关键字个数,，结点大小,struct,BTNode,*,parent;,/,指向,双亲,结点的指针,KeyType,keym+1;,/,关键字（,0,号单元不用）,struct,BTNode,*,ptrm+1;,/,子树,指针向量,Record,*,recptrm+1;,/,记录,指针向量,BTNode,*,BTree;/B,树结点和,B,树的类型,B-,树结构的,C,语言描述如下,:,非叶结点中的,多个关键字,均,自小至大,有序排列，即：,K,1,K,2,keynum;,i=Search(p,K);,/,在,p-key1.keynum,中查找,i,，,p-keyikeyi+1,if,(i0,&,p-keyi=K)found=,TRUE,;,else,q=p;p=p-ptri;,/q,指示,p,的双亲,if,(,found,),return,(p,i,1);/,查找成功,else return,(q,i,0);/,查找不成功,在查找不成功之后，需进行插入。,显然，,关键字,插入,的,位置,必定在,最下,层的非叶结点,，有下列几种情况：,3,插入,1,）,插入后，该结点的关键字个数,nkeynummin,，则只需删去,K,及其右指针,即可使删除操作结束。注意：,min=(m/2)-1,情形二：若,x-keynum=min,，该结点中的关键字个数已是最小值，删,K,及其右指针后会破坏,B-,树的性质,(3),。若*,x,的左,(,或右,),邻兄弟结点*,y,中的关键字数目大于,min,，则将*,y,中的最大,(,或最小,),关键字上移至双亲结点*,parent,中，而将*,parent,中相应的关键字下移至,x,中。显然这种移动使得双亲中关键字数目不变；*,y,被移出一个关键字，故其,keynum,减,1,，因它原大于,min,，故减少,1,个关键字后,keynum,仍大于等于,min,；而*,x,中已移入一个关键字，故删,K,后*,x,中仍有,min,个关键字。移动完成后，删除过程结束,。,情形三：若*,x,及其相邻的左右兄弟中的关键字数目均为最小值,Min,，此时,*,x,和左或右兄弟合并,。设*,x,有右邻兄弟*,y,，在*,x,中删去,K,及其右子树后，将双亲结点,*,parent,中介于*,x,和*,y,之间的关键字,K,，作为中间关键字，与,*x,和*,y,中的关键字一起,“,合并,”,为一个新的结点取代*,x,和*,y,。由于,K,从双亲中移到新结点后，相当于从*,parent,中删去了,K,，若,parent-keynum,原大于,Min,，则删除操作到此结束；否则，同样要通过移动*,parent,的左右兄弟中的关键字或将*,parent,与其 左右兄弟合并的方法来维护,B-,树性质。最坏情况下，合并操作会向上传播至根，当根中只有一个关键字时，合并操作将会使根结点及其两个孩子合并成一个新的根，从而使整棵树的高度减少一层。,是,B-,树的一种变型,四、,B,+,树,1,B,+,树的结构特点：,每个叶子结点中含有,n,个关键字和,n,个指向记录的指针,；并且，所有,叶子,结点彼此相,链接,构成一个,有序链表,，其,头指针指向含最小关键字的结点；,每个非叶结点中的关键字,K,i,即,为,其相应指针,A,i,所指子树中关键字的最大值,；,所有叶子结点都处在,同一层次,上，每个叶子结点中关键字的个数均介于,m/2,和,m,之间。,2,查找过程,在,B,+,树上，既可以进行缩小范围的查,找，也可以进行顺序查找；,在进行缩小范围的查找时，不管成功,与否，都必须查到叶子结点才能结束；,若在结点内查找时，给定值,K,i,，则,应继续在,A,i,所指子树中进行查找。,3,插入和删除的操作,类似于,B-,树进行，即必要时，也需要进行结点的“分裂”或“归并”。,50 96,15 50,62,78,96,71 78,84,89,96,56 62,20 26 43 50,3 8 15,sq,root,五、键 树,1.,键树的结构特点,2.,.,双链树,3.Trie,树,1.,键树的结构特点：,关键字,中的各个符号,分布在从根结点到叶的路径上,，,叶结点内的符号为“结束”的标志符。因此，,键树的深度和关键字集合的大小无关,；,键树,被约定为,是一棵有序树,，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符,$,小于任何其它符号。,H,A,D,$,S,$,V,E,$,E,$,R,$,E,$,I,G,H,$,S,$,例如,:,表示关键字集合,HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS,2.,双链树,以二叉链表作存储结构实现的键树,typedef,enum,LEAF,BRANCH,NodeKind;,/,两种结点：,叶子,和,分支,结点结构,:,first,symbol,next,分支结点,infoptr,symbol,next,叶子结点,指向孩子结点,的指针,指向兄弟结点,的指针,指向记录,的指针,H,A,D,$,HAD,E,$,R,$,$,E,S,$,G,H,$,I,HE,HER,HERE,HIGH,HIS,T,叶子结点,分支结点,含关键字,的记录,typedef struct,DLTNode,char,symbol;,struct,DLTNode,*,next;,/,指向兄弟结点的指针,NodeKind kind;,union,Record,*,infoptr;,/,叶子结点内的记录指针,struct,DLTNode,*,first;,/,分支结点内的孩子链指针,DLTNode,*,DLTree;/,双链树的类型,#define,MAXKEYLEN 16,/,关键字的最大长度,typedef struct,char,chMAXKEYLEN;/,关键字,int,num;/,关键字长度,KeysType;/,关键字类型,在双链树中查找记录的过程,:,假设,:T,为指向双链树根结点的指针，,K.ch0.K.num-1,为待查关键字,(,给定值,),。,则查找过程中的基本操作为进行下列比较,:,K.chi=?p-symbol,其中,:p,指向双链树中某个结点，,0,i K.num-1,初始状态,:,p=T-first;i=0;,若,(,p,&,p-symbol=K.chi,&,ifirst;i+;,若,(,p,&,p-symbol!=K.chi,),则继续在键树的同一层上进行查找,p=p-next;,若,(,p,&,p-symbol=K.chi,&,i=K.num-1,),则 查找成功，,返回指向相应记录的指针,p-infoptr,若,(,p=NULL,),则表明查找不成功，返回“空指针”,;,3.Trie,树,以多重链表作存储结构实现的键树,结点结构,:,分支结点,叶子结点,指向记录,的指针,0 1 2 3 4 5,24 25 26,关键字,指向下层结点的指针,每个域对应一个“字母”,0 1(A)3 4 5(E)9(I),26,8(H),4(D)19(S)22(V)0 18(R)7(G)19,0 5(E),T,HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS,叶子结点,分支结点,指向记录,的指针,typedef struct,TrieNode,NodeKind kind;/,结点类型,union,struct,KeyType K;,Record,*,infoptr,lf,;,/,叶子结点,(,关键字和指向记录的指针,),struct,TrieNode,*,ptr27;,int,num,bh,;,/,分支结点,(27,个指向下一层结点的指针,),TrieNode,*,TrieTree;/,键树类型,结点结构的,C,语言描述,:,在,Trie,树中查找记录的过程,:,假设,:,T,为指向,Trie,树根结点的指针，,K.ch0.K.num-1,为待查关键字,(,给定值,),。,则,查找过程中的基本操作为：,搜索和对应字母相应的指针,:,若,p,不空，且,p,所指为分支结点，,则,p=p-bh.Ptrord(K.Chi);,(,其中,:0,i K.num-1),初始状态,:,p=T;i=0;,若,(p,&,p-kind=BRANCH,&,ibh.ptrord(K.chi);i+;,其中，,ord,为求字符在字母表中序号的函数,若,(p,&,p-kind=LEAF,&,p-lf.K=K),则,查找成功,，,返回,指向相应记录的指针,p-lf.infoptr,反之，,即,(,!p,|p-kind=LEAF,&,p-lf.K!=K,),则,表明,查找不成功,，,返回,“空指针”,;,一、,哈希表是什么？,二、,哈希函数的构造方法,三、,处理冲突的方法,四、,哈希表的查找,五、,哈希表的删除操作,六、,对静态查找表，,9.3,哈 希 表,以上两节讨论的表示查找表的各种,结构,的共同,特点,：,记录在表中的,位置,和它的,关键字,之间,不存在,一个确定的关系，,一、,哈希表是什么？,查找的过程,为,给定值,依次和关键字集合中各个,关键字,进行,比较,，,查找的效率,取决于和给定值,进行比较,的关键字,个数,。,用这类方法表示的查找表，,其平均查找长度都不为零。,不同的表示方法，其,差别仅在于：,关键字和给定值进行比较的顺序不同。,只有一个办法：预先知道所查关键字在表中的位置，,对于频繁使用的查找表，,希望,ASL=0,。,即，要求：,记录在表中位置和其关键字之间存在一种确定的关系,。,若,以下标为,000 999,的顺序表,表示之。,例如：,为每年招收的,1000,名新生建立一张查找表，其关键字为学号，其值的范围为,xx000 xx999(,前两位为年份,),。,则查找过程可以简单进行：取给定值（学号）的后三位，,不需要经过比较,便可直接从顺序表中找到待查关键字。,但是，对于,动态查找表,而言，,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，,以,f(key),作为关键字为,key,的记录在表中的位置,，,通常,称,这个函数,f(key),为哈希函数。,1),表长不确定；,2),在设计查找表时，只知道关键字所,属范围，而不知道确切的关键字。,Z,hao,Q,ian,S,un,L,i,W,u,C,hen,H,an,Y,e,D,ei,例如：,对于如下,9,个关键字,设,哈希函数,f(key)=,(Ord(,第一个字母,)-Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,问题,:,若添加关键字,Z,hou,怎么办？,能否找到,另一个哈希函数？,1),哈希函数是一个,映象,，即：,将关键字的集合映射到某个地址集合上，,它的设置很,灵活,，只要这个,地址集,合的,大小,不超出允许范围,即可；,从这个例子可见：,2),由于哈希函数是一个,压缩映象,，因此，在一般情况下，很容易产生,“冲突”,现象，即：,key1,key2,，而,f(key1)=f(key2),。,3),很难,找到一个不产生冲突的哈希函数。,一般情况下，,只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表”时，除了需要选择一个,“好”,(,尽可能少产生冲,突,),的哈希函数之外；还需要找到,一种,“处理冲突”,的方法,。,哈希表的定义：,根据设定的,哈希函数,H(key),和所选中的,处理冲突的方法,，将一组关键字,映象到,一个有限的、地址连续的地址集,(,区间,),上，并以关键字在地址集中的“象”作为相应记录在表中的,存储位置,，如此构造所得的查找表称之为“,哈希表,”。,二、,构造哈希函数的方法,对,数字,的关键字可有下列构造方法：,若是,非数字关键字,，则,需先,对其,进行,数字化处理,。,1.,直接定址法,3.,平方取中法,5.,除留余数法,4.,折叠法,6.,随机数法,2.,数字分析法,哈希函数为关键字的线性函数,H(key)=key,或者,H(key)=a,key+b,1.,直接定址法,此法仅适合于：,地址集合的大小,=,关键字集合的大小,此方法仅适合于：,能,预先估计出,全体关键字的,每一位上,各种,数字出现的频度,。,2.,数字分析法,假设关键字集合中的每个关键字都是由,s,位数字组成,(u,1,u,2,u,s,),，分析关键字集中的全体，并,从中提取分布均匀的若干位,或,它们的组合,作为地址。,以,关键字的平方值的中间几位,作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。,3.,平方取中法,此方法适合于,:,关键字中的每一位都有某些数字重复出现频度很高的现象。,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。,有两种叠加处理的方法：,移位叠加,和,间界叠加,。,4.,折叠法,此方法适合于,:,关键字的数字位数特别多。,5.,除留余数法,设定哈希函数为,:,H(ke