资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 查找表,查找表是由同一类型的数据元素,(,或记录,),构成的集合。,由于,“,集合,”,中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,何谓查找表 ？,对查找表经常进行的,操作,:,查询,某个,“特定的”,数据元素是否在查找表中；,检索,某个,“特定的”,数据元素的各种属性；,在查找表中,插入,一个数据元素；,从查找表中,删去,某个数据元素。,仅作,查询,和,检索,操作的查找表。,静态查找表,有时在查询之后，还需要将“查询”结果为“,不在查找表中,”的数据元素,插入到,查找表中；或者，从查找表中,删除,其“查询”结果为“,在查找表中,”的数据元素。,动态查找表,查找表可分为两类,:,是数据元素（或记录）中某个,数据项,的值，用以,标识,（识别）一个数据元素（或记录）。,关键字,若此关键字可以识别,唯一的,一个记录，则称之谓,“主关键字”,。,若此关键字能识别,若干,记录，则称,之谓,“次关键字”,。,根据给定的某个值，在查找表中,确定一个其关键字等于给定值的数据元素或（记录）,查找,若查找表中存在这样一个记录，则称“,查找成功,”，查找结果：,给出整个记录的信息，或指示该记录在查找表中的位置,；,否则称“,查找不成功,”，查找结果：,给出,“空记录”或“空指针”。,由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。,为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，,用另外一种结构来表示查找表,。,查找的方法取决于查找表的结构。,如何进行查找？,9.1,静态查找表,9.2,动态查找树表,9.3,哈希表,9.1,静 态 查 找 表,数据对象,D,：,数据关系,R,：,D,是具有相同特性的数,据元素的集合。,每个数,据元素含有类型相同的,关键字，可唯一标识数,据元素。,数据元素同属一个集合。,ADT,StaticSearchTable,Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();,基本操作,P,：,next, ADT,StaticSearchTable,构造一个含,n,个数据元素,的静态查找表,ST,。,Create(,操作结果：,销毁表,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;,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,定义：,查找算法的,平均查找长度,(,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,四、索引顺序表,以索引顺序表表示静态查找表，,search,操作可用分块查找来实现。,分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找方法中，除表本身以外，尚需建立一个,“,索引表,”,。,例如,表中含有,18,个元素，可分成三个子表,。,对每个子表（或称块）建立一个索引项，其中包括两项内容：关键字项（其值为该子表内的最大关键字）和项指针（指示该子表的第一个元素在表中位置）。,索引表,最大关键字,起始地址,22,48,86,1,7,13,22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53,索引表按关键字有序，故表或者有序，或者分块有序。所谓,“,分块有序,”,是指一个子表中所有元素的关键字均大于前一个子表的最大关键字。,索引顺序表的查找过程：,1,）由索引确定记录所在区间；,2,）在顺序表的某个区间内进行查找。,注意：索引可以根据查找表的特点来构造。,可见，,索引顺序查找,的过程也是一个,“,缩小区间,”,的查找过程。,索引顺序查找的平均查找长度,=,查找,“,索引,”,的平均查找长度,+,查找,“,顺序表,”,的平均查找长度,9.2,动 态 查 找 树 表,(n),(1),(n),(1),(,nlogn,),综合上一节讨论的几种查找表的特性：,查找 插入 删除,无序顺序表,无序线性链表,有序顺序表,有序线性链表,静态查找树表,(n),(n),(,logn,),(n),(,logn,),(1),(1),(n),(1),(,nlogn,),1,）从,查找,性能看，最好情况能达,(,logn,),，,此时要求表,有序,；,2,）从,插入,和,删除,的性能看，最好,情况能达,(1),，此时要求存储,结构是,链表,。,可得如下结论：,ADT,DynamicSearchTable,抽象数据类型,动态查找表,的定义如下：,数据对象,D,：,数据关系,R,：,数据元素同属一个集合。,D,是具有相同特性的数据元素的集合。,每个数据元素含有类型相同的关键字， 可唯一标识数据元素。,InitDSTable(&DT,),基本操作,P,：,DestroyDSTable(&DT,),SearchDSTable(DT, key);,InsertDSTable(&DT, e);,DeleteDSTable(&T, key);,TraverseDSTable(DT, Visit();,next,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(),失败，,则操作失败。,一、二叉排序树（二叉查找树）,二、二叉平衡树,三、,B -,树,四、,B,+,树,五、键 树,1,定义,2,查找算法,3,插入算法,4,删除算法,5,查找性能的分析,一、二叉排序树（二叉查找树）,（,1,）若它的左子树不空，则左子树上,所有,结点的值,均小于,根结点的值；,二叉排序树,或者是一棵空树；或者,是具有如下特性的二叉树：,（,3,）它的左、右子树,也都,分别,是二叉,排序树,。,（,2,）若它的右子树不空，则右子树上,所有,结点的值,均大于,根结点的值；,1,定义：,50,30,80,20,90,10,85,40,35,25,23,88,例如,:,是二叉排序树,66,不,通常，取二叉链表作为二叉排序树的存储结构,typedef,struct,BiTNode, /,结点结构,struct,BiTNode,*,lchild, *,rchild,;,/,左右孩子指针,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-,lchild, key, T, p ),;,/,在左子树中继续查找,SearchBST,(T-,rchild, 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,以中序遍历排好，,20-30-32-35-,40,-,50,-80-85-88-90,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,此处,p,应该换为,f,的左孩子或右，根据,p,为,f,左还是右而定,/,左子树为空树只需重接它的右子树,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,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的,ASL,值，显然，由值相同的,n,个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。,5,查找性能的分析,由关键字序列,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,1,定义,2,查找过程,3,插入操作,4,删除操作,5,查找性能的分析,三、,B -,树,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,）,插入后，该结点的关键字个数,nsymbol,其中,: 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 & i,bh.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,u,例如：,对于如下,9,个关键字,设,哈希函数,f(key) =,(,Ord,(,第一个字母,) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Du,问题,:,若添加关键字,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(key) = key MOD p,其中,，,pm,(,表长,),并且,p,应为不大于,m,的素数,或是,不含,20,以下的质因子,给定一组关键字为,:,12, 39, 18, 24, 33, 21,，,若取,p=9,则他们对应的哈希函数值将为,:,3, 3, 0, 6, 6, 3,例如：,为什么要对,p,加限制？,可见，若,p,中含质因子,3,则所有含质因子,3,的关键字均映射到,“,3,的倍数,”,的地址上,，从而增加了,“,冲突,”,的可能。,6.,随机数法,设定哈希函数为,:,H(key) = Random(key),其中，,Random,为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数。,实际造表时，,采用何种,构造哈希函数的,方法,取决于建表的关键字集合的情况,(,包括关键字的范围和形态,),，总,的原则是使产生冲突的可能性降到尽可能地小,。,“,处理冲突,”,的实际含义是：,为产生冲突的地址寻找下一个哈希地址,1.,开放定址法,2.,链地址法,三、处理冲突的方法,为产生冲突的地址,H(key),求得一个,地址序列,：,H,0, H,1, H,2,H,s,1 sm-1,其中：,H,0,= H(key),H,i,= ( H(key) +,d,i,) MOD m,i=1, 2, , s,1.,开放定址法,对增量,d,i,有三种取法：,1,),
展开阅读全文