数据结构查找.ppt

,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,9,章 查找,1,查找表,(Search Table),：,是由同一类型的数据元素（或记录）构成的集合。,前面已介绍了各种线性或非线性的数据结构，本章讨论另一种在实际应用中大量使用的数据结构,-,查找表。,由于“集合”中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。,2,对查找表经常进行的操作：,（,1,）查询某个“特定的”数据元素是否在查找表中。,（,2,）检索某个“特定的”数据元素的各种属性。,（,3,）在查找表中插入一个数据元素。,（,4,）从查找表中删去某个数据元素。,3,查找表可分为两类：,若对查找表只作,查询,和,检索,操作，则称此类查找表为静态查找表（,Static Search Table),。,若在查找过程中同时,插入,查找表中不存在的数据元素，或者从查找表中,删除,已存在的某个数据元素，则称此类查找表为动态查找表（,Dynamic Search Table,）。,4,在各种系统软件或应用软件中，查找表是最常见的结构之一。如编译程序中符号表、信息处理系统中信息表等。,综上所述，所谓“查找”即为在一个含有众多的数据元素（或记录）的查找表中找出某个“特定的”数据元素（或记录）。,关于“特定的”词的具体含义：,关键字（,Key,）：,是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。,主关键字（,Primary Key,）：,若此关键字可以惟一地标识一个记录，则称此关键字为主关键字。,对不同的记录，其主关键字均不同。,5,次关键字（,Secondary Key,）：,用以识别若干记录的关键字为次关键字。,当数据元素只有一个数据项时，其关键字即为该数据元素的值。,查找（,Searching),：,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。,查找成功：,若表中存在这样的一个记录，则查找成功，此时查找的结果为给出整个记录的信息，或指示该记录在查找表中的位置。,查找不成功：,若表中不存在关键字等于给定值的记录，则查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。,6,此表为一个查找表。,表中每一行为一个记录，学生的学号为记录的关键字。,若给定值为,20010985,，则通过查找可得学生王五的各项信息。此时查找是成功的。,若给定值为,20011930,，则由于表中没有关键字为,20011930,的记录，则查找不成功。,学号,姓名,性别,入学总分,录取专业,20010983,张三,女,438,计算机,20010984,李四,男,430,计算机,20010985,王五,女,445,计算机,20010998,张三,男,458,计算机,招生录取登记表,例：,7,如何进行查找？,在一个结构中查找某个数据元素的过程依赖于这个数据元素在结构中所处,的地位。,即：对查找表进行查找的方法取决于表中数据元素依何种关系组织在一起。（这个关系是人为加上的。因为查找表中数据元素之间原本仅存在“同属于一个集合”的松散关系）。,例：查英文单词。,字典是按单词的字母在字母表中的次序编排的，则查找时不需要从字典中第一个单词比较起，而只要根据待查单词中每个字母在字母表中的位置查到该单词。,字典这种查找表的数据元素之间原本仅存在着“同属于一个集合”的松散,关系，给查找带来不便。,对字典按单词的字母在字母表中的次序进行编排，就是对字典这种查找表人为加上的一种关系，以便按某种规则进行查找。,8,总之：,查找的方法取决于查找表的结构。,由于查找表中的数据元素之间不存在明显的组织规律，因此不便,于查找。,为了提高查找的效率，需要在查找表中的元素之间人为地附加某,种确定的关系，换句话说，,用另外一种结构来表示查找表。,9,内查找和外查找：,若整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。本书仅介绍内查找。,平均查找长度,ASL,：,查找算法的效率，主要看要查找的值与关键字的比较次数，通常用平均查找长度来衡量。,10,对一个含,n,个数据元素的表，查找成功时：,其中：,P,i,为找到表中第,i,个数据元素的概率，且有：,C,i,为查找表中第,i,个数据元素所用到的比较次数。不同的查找方法有不同的,C,i,。,查找是许多程序中最消耗时间的一部分。因而，一个好的查找方法会大大提高运行速度。,11,9.1,静态查找表,9.2,动态查找表,9.3,哈希表,本章内容：,12,9.1,静态查找表,13,1.,顺序表的查找,静态查找表的存储结构可用顺序表或线性链表表示。,本节只讨论在顺序存储结构中查找的实现。,顺序查找的基本思想：,从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较都不等，则表明表中没有所查记录，查找不成功。,14,i,例,0 1 2,3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找,64,64,监视哨,i,i,i,i,比较次数,=5,比较次数：,查找第,n,个元素：,1,查找第,n-1,个元素：,2,.,查找第,1,个元素：,n,查找第,i,个元素：,n-i+1,查找失败,：,n+1,15,例,0 1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找,64,64,监视哨,#define M 500,typedef struct,int key;,float info;,JD;,int seqsrch(JD r,int n,int k),int i=n;,r0.key=k;,while(ri.key!=k),i-;,return(i);,16,监测哨的作用：,（,1,）省去判定循环中下标越界的条件，从而节约比较时间。,（,2,）保存查找值的副本，查找时若遇到它，则表示查找不成功。这样在从后向,前查找失败时，不必判断查找表是否检测完，从而达到算法统一。,上述算法中，对于有,n,个数据元素的表，给定值,k,与表中第,i,个元素的关键字相等，即定位第,i,个记录时，需进行：,n,i,+1,次关键字比较，即,C,i,=,n,i,+1,。则查找成功时，顺序查找的平均查找长度为：,顺序查找性能分析：,对一个含有,n,个数据元素的表，查找成功时有：,17,设每个数据元素的查找概率相等，即,Pi=,，则等概率情况下有：,查找不成功时，关键字的比较次数总是,n+1,次。,算法中的基本工作就是关键字的比较，因此，查找长度的量级就是查找算法的时间复杂度为,O(n),。,顺序查找缺点是当,n,很大时，平均查找长度较大，效率低；优点是对,表中数据元素的存储没有特殊要求。,18,2.,有序表的查找,以有序表表示静态查找表时，可用折半查找法来实现查找。,折半查找的基本思想：,在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。,折半查找也叫二分查找，是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。,19,算法实现：,设表长为,n,，,low,，,high,和,mid,分别指向待查元素所在区间的上界、下界和中点,k,为给定值,。,初始时，令,low=1,high=n,mid=,(low+high)/2,让,k,与,mid,指向的记录比较,：,若,k=rmid.key,，则,查找成功,若,k rmid.key,，,则,low=mid+1,重复上述操作，直至,lowhigh,时，查找失败,20,算法描述：,low,high,mid,例,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找,21,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,21,例,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,找,70,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,22,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,int binsrch(JD r,int n,int k ),int low,high,mid,found;,low=1;high=n;,found=0;,/found,为找到标志。值为,0,表示未找到。,while(lowrmid.key)low=mid+1;,else if(k=rmid.key)found=1;,else high=mid-1;,if(found=1),/,如果已找到,return(mid);,/,找到的记录的下标肯定为,mid,else,return(0);,#define M 500,typedef struct,int key;,float info;,JD;,23,折半查找的性能分析：,从折半查找的过程看，每次查找都是以表的中点为比较对象，并以中,点将表分割为两个子表，对定位到的子表继续作同样的操作。所以，对表,中每个数据元素的查找过程，可用二叉树来描述，称这个描述查找过程的,二叉树称为判定树。,判定树中每一结点对应表中一个记录，但结点值不是某个记录的关键,字，而是某个记录在表中的位置序号。根结点对应当前区间的,中间记录,，,左子树对应前一子表，右子树对应后一子表。,24,11,8,5,2,10,7,4,1,9,3,6,判定树：,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,从上面判定树可看到，查找第一层的根结点,56,，一次比较即可找,到；查找第二层的结点,19,和,80,，二次比较即可找到；查找第三层的,结点,5,、,21,、,64,、,88,，三次比较即可找到；查找第四层的结点,13,，,37,、,75,、,92,，四次比较即可找到。,25,n,个结点的判定树，树高为,k,，则有,2,k-1,-1n2,k,-1,，即,k-1 di.key)&(i=b),/,确定要比较的值,k,在哪一块,i+;,/k b),printf(n Not found);return(0);,j=di.link;,/,要比较的值,k,在以,di.link,为起点下标的块中,while(jn)&(k!=rj.key)&(rj.keydata.key),p=T;return TRUE;,/,查找成功,else if(LT(key,T-data.key),SearchBST(T-lchild,key,T,p);,/,在左子树中继续查找,else,SearchBST(T-rchild,key,T,p);,/,在右子树中继续查找,42,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,43,二叉排序树的查找分析：,在二叉排序树上查找其关键字等于给定值结点的过程，恰是走了一条从根结点到该结点的路径的过程。含有,n,个结点的二叉树是不唯一的，如何来进行查找分析呢？,44,例如：上图两棵二叉排序树中，结点的个数和值均相同。,但（,a,）的深度 为,3,，而（,b,）的深度为,6,。,其等概率平均查找长度分别为：,ASL(a)=(1*1+2*2+3*3)/6=14/6,ASL(b)=(1*1+2*1+3*1+4*1+5*1+6*1)/6=21/6,因此，二叉排序树的平均查找长度和二叉树的形态有关。,最好情况下，二叉排序树在生成过程中，树的,形态比较均匀,，其最终得到的是一颗形态与二分查找的判定树相似的二叉排序树，如图,(a),所示。,最坏情况下，二叉排序树通过一个有序表的,n,个结点依次插入生成的，此时所得的二叉排序树为一颗深度为,n,的,单支树,，如图,(b),所示。它的平均查找长度和单链表的顺序查找相同，也是（,n+1,）,/2,。,对均匀的二叉排序树进行插入或删除结点后，应对其进行调整，使其依然保持均匀。,45,(3),二叉排序树的插入算法,根据动态查找表的定义，插入操作在查找不成功时才进行。,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,45,12,53,3,37,24,100,61,90,78,20,例如：在右图给定的二叉排序树中插入结点,20,46,Status InsertBST(BiTree&T,ElemType e ),/,当二叉排序树中不存在关键字等于,e.key,的数据元素时，插入元素值为,e,的结点，并返回,TRUE,;,否则，不进行插入并返回,FALSE,。,if(!SearchBST(T,e.key,NULL,p),/,如果查找不成功，才进行插入,else,/,如果查找成功，则不进行插入,return FALSE,;,47,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;,/,插入成功,48,(4),二叉排序树的删除算法,和插入相反，删除在查找成功之后进行，并且要求删除二叉排序树,上某个结点之后，仍然保持二叉排序树的特性。,可分三种情况讨论：,1,）被删除的结点是叶子；,2,）被删除的结点只有左子树或者只有右子树；,3,）被删除的结点既有左子树，也有右子树。,49,50,30,80,20,90,85,40,35,88,32,被删除的结点是叶子结点。,例如,:,被删关键字,=20,88,其双亲结点中相应指针域的值改为“空”,50,50,30,80,20,90,85,40,35,88,32,被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为,“,指向被删除结点的左子树,或右子树,”,。,被删关键字,=40,80,51,50,30,80,20,90,85,40,35,88,32,被删除的结点既有左子树，也有右子树。,40,40,以其前驱替代之，然后再删除该前驱结点。,被删结点,前驱结点,被删关键字,=50,52,Status DeleteBST(BiTree&T,KeyType key),/,若二叉排序树,T,中存在其关键字等于,key,的数据元素，则删除该数据,元素结点，并返回函数值,TRUE,，否则返回函数值,FALSE,。,if(!T),/,若,T,为空,return FALSE;,/,不存在关键字等于,key,的数据元素,else,if(EQ(key,T-data.key),Delete(T);return TRUE;,/,找到关键字等于,key,的数据元素,else if(LT(key,T-data.key),DeleteBST(T-lchild,key);,/,继续在左子树中进行查找，删除,else,DeleteBST(T-rchild,key);,/,继续在右子树中进行查找，删除,53,void Delete(BiTree&p),/,从,二叉排序树中删除结点,p,，,并重接它的左子树或右子树,if(!p-rchild),else if(!p-lchild),else,其中删除操作过程如下所描述：,54,/,右子树为空树则只需重接它的左子树,q=p;,p=p-lchild;,free(q);,p,p,55,/,左子树为空树只需重接它的右子树,q=p;,p=p-rchild;,free(q);,p,p,56,q=p;,s=p-lchild;,/,转左,while(s-rchild),/,转左后，到右尽头,q=s;,s=s-rchild;,/,q,指向,s,的双亲，,s,指向被删结点的前驱,p-data=s-data;,/,以 前驱结点的数据替换被删结点的数据,if(q!=p),q-rchild=s-lchild;,/,重接*,q,的右子树,else,q-lchild=s-lchild;,/,重接*,q,的左子树,free(s);,/,左右子树均不空,p,q,s,57,(5),二叉排序树的构造过程,例：记录的关键字序列为：,33,，,50,，,42,，,18,，,39,，,9,，,77,，,44,，,2,，,11,，,24,，,则构造一棵二叉排序树的过程如下：,从空树开始建立二叉排序树的过程图示,58,一个无序序列可以通过构造二叉排序树而成为一个有序序列。,每次插入新结点都是二叉排序树上新的叶子结点，不必移动,其它结点，仅需改动某个结点指针，由空变为非空即可。,59,#include,typedef int TElemType;,typedef struct BiTNode,/,结点结构,TElemType data;,struct BiTNode *lchild,*rchild;/,左、右指针,BiTNode,*BiTree;,生成二叉排序树的算法：,60,void InsBST(BiTree&T,TElemType K),BiTNode*f,*p;,p=T;,while(p),/,当,p,为空时，即左孩子或右孩子为空时，,p,不再往下指,/,即 从根结点开始找插入的位置，找到后，,f,为要插入位置的双亲结点的地址,if(p-data=K),printf(,树中已有,%d,，不需插入,n,K);,return;,f=p;,p=(Kdata)?p-lchild:p-rchild;,/p,指向自己的左孩子或右孩子，,f,指向 左右孩子的双亲,p=new BiTNode;,/,申请一个新结点，把输入的值放入新结点,p-data=K;,p-lchild=p-rchild=NULL;,if(T=NULL),/,如果根结点为空，新结点为根结点,T=p;,else if(K data),/,如果输入值小于它的根结点，则作为此根结点的左孩子,f-lchild=p;,else,f-rchild=p;,/,如果输入值大于它的根结点，则作为此根结点的右孩子,61,BiTree CreateBST(),BiTree T;,/T,是 一个指针变量，指向二叉排序树的根结点,TElemType K;,T=NULL;,printf(,请输入一个整数关键字,(,输入,0,时结束输入,),：,);,scanf(%d,while(K),InsBST(T,K);,printf(“,请输入下一个整数关键字,(,输入,0,时结束输入,),：,);,scanf(%d,return T;,void main(),CreateBST();,62,例如,:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,平衡二叉树的定义：,又称,AVL,树。它或者是一棵空树，或者是具有下列性质的二叉树：,1,）它的左子树和右子树高度之差的绝对值不超过,1,；,2,）它的左子树和右子树都是平衡二叉树。,2.,二叉平衡树,63,二叉树上结点的平衡因子：,为该结点的左子树的深度减去它的右子树的深度。,平衡二叉树上所有结点的平衡因子只可能是：,-1,、,0,、,1,64,65,在插入过程中，采用平衡旋转技术。,例如：依次插入的关键字为,5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转,一次,先向右旋转,再向左旋转,构造二叉平衡树 的方法：,66,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,67,当平衡的二叉排序树因插入结点而失去平衡时，仅需对离插入结点最近的,最小不平衡子树,进行平衡旋转处理即可。,平衡旋转处理可分为下列,4,种情况：,（,1,）单向,右,旋（顺时针）,（,2,）单向,左,旋（逆时针）,（,3,）,先左后右,双向旋转,（,4,）,先右后左,双向旋转,68,例：,已知一棵平衡二叉排序树如图（,a,）所示。在,A,的左子树的左子树上插入,15,后，导致失衡，如图（,b,）所示。为恢复平衡并保持二叉排序树的特性，可将,A,改为,B,的右子，,B,原来的右子改为,A,的左子，如图（,c,）所示。这相当于以,B,为轴，对,A,做了一次顺时针旋转。,不平衡二叉树的调整,(1),69,例：已知一棵平衡二叉排序树如图（,a,）所示。在,A,的右子树,B,的右子树上插入,70,后，导致失衡，如图（,b,）所示。为恢复平衡并保持二叉排序树的特性，可将,A,改为,B,的左子，,B,原来的左子改为,A,的右子，如图（,c,）所示。这相当于以,B,为轴，对,A,做了一次逆时针旋转。,不平衡二叉树的调整,(2),70,例：已知一棵平衡二叉排序树如图（,a,）所示。在,A,的左子树,B,的右子树上插入,45,后，导致失衡，如图（,b,）所示。为恢复平衡并保持二叉排序树的特性，可首先将,B,改为,C,的左子，而,C,原来的左子改为,B,的右子；然后将,A,改为,C,的右子，,C,原来的右子改为,A,的左子，如图（,c,）所示。这相当于对,C,做了一次逆时针旋转，对,A,做了一次顺时针旋转。,71,不平衡二叉树的调整,(3),72,例：,已知一棵平衡二叉排序树如图（,a,）所示。在,A,的右子树的左子树上插入,55,后，导致失衡，如图（,b,）所示。为恢复平衡并保持二叉排序树的特性，可首先将,B,改为,C,的右子，而,C,原来的右子改为,B,的左子；然后将,A,改为,C,的左子，,C,原来的左子改为,A,的右子，如图（,c,）所示。这相当于对,C,做了一次顺时针旋转，对,A,做了一次逆时针旋转。,73,不平衡二叉树的调整,(4),74,在,二叉,平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。,二叉平衡树的查找性能分析：,问，含,n,个关键字的二叉平衡树可能达到的最大深度是多少？,75,n,=0,空树,最大深度为,0,n,=1,最大深度为,1,n,=2,最大深度为,2,n,=4,最大深度为,3,n,=7,最大深度为,4,先看几个具体情况,:,76,反过来问，深度为,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,77,因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个数和,log(n),相当。即：在二叉平衡树上进行查找的时间复杂度为,Olog(n),。,由此推得，深度为,h,的二叉平衡树中所含结点的最小值,N,h,=,h+2,/5-1,。,反之，含有,n,个结点的二叉平衡树能达到的最大深度为：,h,n,=log,(5(n+1)-2,。,78,9.3,哈希表,79,1.,什么是哈希表,以上讨论的查找方法，由于数据元素的存储位置与关键字之间不存在,确定的关系，因此，查找时，需要进行一系列对关键字的查找比较，即查,找算法是建立在比较的基础上的，查找效率由比较一次缩小的查找范围决,定。,理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关,键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字,得到对应的数据元素位置。,80,例：,11,个元素的关键字分别为,18,，,27,，,1,，,20,，,22,，,6,，,10,，,13,，,41,，,15,，,25,。,选取关键字与元素位置间的函数为：,f(key)=key mod 11,1.,通过这个函数对,11,个元素建立查找表如下：,0 1 2 3 4 5 6 7 8 9 10,10,20,41,18,6,27,15,25,13,1,22,查找时，对给定值,kx,通过这个函数计算出地址，再将,kx,与该地址单元中元素的关键字比较，若相等，查找成功。,81,哈希表与哈希方法：,选取某个函数，依据该函数按关键字计算数据元素的存储地址，并按此地址存放数据元素；查找时，由同一个函数对给定值,kx,计算出地址，将,kx,与该地址单元中数据元素的关键字进行比较，确定查找是否成功，这就是哈希方法。,哈希方法中使用的转换函数称为哈希函数。,哈希方法中计算的存储地址称为哈希地址或散列地址。,按这个思想构造的查找表称为哈希表。,82,对于,n,个数据元素的集合，总能找到关键字与存放地址一一对应的,函数。,若最大关键字为,m,，可以分配,m,个数据元素存放单元，选取函,数,f(key)=key,即可，但这样会造成存储空间的很大浪费，甚至不可能分,配这么大的存储空间。,通常关键字的集合比哈希地址集合大得多，因而经过哈希函数变换,后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突。,83,冲突不可能避免，只能尽可能减少。所以，哈希方法需要解决以,下两个问题：,1,）构造好的哈希函数,a.,所选函数尽可能简单，以便提高转换速度。,b.,所选函数对关键字计算出的地址，应在哈希地址集中大致,均匀分布，以减少空间的浪费。,2,）制定解决冲突的方案。,换句话说，就是使关键字经过哈希函数得到一个随机的地址，以便,使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。,84,2.,哈希函数的构造方法,（,1,）直接定址法,Hash(key)=akey+b (a,、,b,为常数,),即：取关键字的某个线性函数值为哈希地址。,这类函数是一一对应函数，不会产生冲突，但要求地址集合,与关键字集合大小相同，因此，对于较大的关键字集合不适用。,实际中能使用这种哈希函数的情况很少。,例：关键字集合为,20,，,30,，,50,，,60,，,80,，,90,，选取哈希函数为：,Hash(key)=key/10,，则存放如下：,0 1 2 3 4 5 6 7 8 9,关键字存放地址图示,80,60,50,30,20,90,85,（,2,）除留余数法,Hash(key)=key mod p (p,是一个整数,),即：取关键字除以,p,的余数作为哈希地址。,使用除留余数法，选取合适的,p,很重要，若哈希表表长为,m,，,则要求,pm,，且接近,m,或 等于,m,。,p,一般选取质数，也可以是不,包含小于,20,质因子的合数。,这是一种最简单，也最常用的构造哈希函数的方法。,86,（,3,）平方取中法,对关键字平方后，按哈希表大小，取中间的若干位作为哈希地址。,例：若存储区域可存,100,个记录，关键字,=4731,则,47314731=223,82,361,取地址,82,例：若存储区域可存,10000,个记录，关键字,=14625,则,1462514625=213,8906,25,取地址,8906,取的位数由表长决定，这是一种较常用的构造哈希函数的方法。,87,3.,处理冲突的方法,（,1,）开放定址法,所谓开放定址法，即是由关键字得到的哈希地址一旦产生了冲突，,也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，,只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。,1,）线性探测法,H,i,=(Hash(key)+d,i,)mod m (1i m),其中：,Hash(key),为哈希函数,m,为哈希表长度,d,i,=i,；,i=1,，,2,，,3,，,，,m-1,88,例,：,关键字集为,47,，,7,，,29,，,11,，,16,，,92,，,22,，,8,，,3,，,哈希表表长为,11,，,Hash(key)=key mod 11,。,用线性探测法处理冲突，建表如下：,0 1 2 3 4,5,6,7 8,9 10,8,29,7,3,16,92,47,22,11,用线性探测法处理冲突的哈希表图示,47,、,7,、,11,、,16,、,92,均是由哈希函数得到的没有冲突的哈希地址而直接存入的；,Hash(29)=7,，哈希地址上冲突，需寻找下一个空的哈希地址。由,H,1,=(Hash(29)+1)mod 11=8,，哈希地址,8,为空，将,29,存入。,另外，,22,、,8,同样在哈希地址上有冲突，也是由,H,1,找到空的哈希地址的；,89,而,Hash(3)=3,，哈希地址上冲突，由,H,1,=(Hash(3)+1)mod 11=4,仍然冲突；,H,2,=(Hash(3)+2)mod 11=5,仍然冲突；,H,3,=(Hash(3)+3)mod 11=6,找到空的哈希地址，存入。,线性探测法可能使第,i,个哈希地址的同义词存入第,i+1,个哈希,地址，这样本应存入第,i+1,个哈希地址的元素变成了第,i+2,个哈希,地址的同义词，,，因此，可能出现很多元素在相邻的哈希地,址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，,或双哈希函数探测法，以改善“堆积”问题。,90,2,）二次探测法（平方探测法）,H,i,=(Hash(key)d,i,)mod m,其中：,Hash(key),为哈希函数,m,为哈希表长度，,m,要求是某个,4k+3,的质数,(k,是整数,),d,i,为增量序列,1,2,，,-1,2,，,2,2,，,-2,2,，,，,q,2,，,-q,2,且,q(m-1),仍以上例，用二次探测法处理冲突，建表如下：,0 1 2 3 4 5 6 7 8 9 10,8,29,17,16,92,47,3,22,11,二次探测法处理冲突的哈希表图示,对关键字寻找空的哈希地址只有,3,这个关键字与上例不同，,Hash(3)=3,，哈希地址上冲突，由,H,1,=(Hash(3)+1,2,)mod 11=4,仍然冲突；,H,2,=(Hash(3)-1,2,)mod 11=2,找到空的哈希地址，存入。,91,3,）双哈希函数探测法,H,i,=(Hash(key)+i*ReHash(key)mod m,(i=1,，,2,，,，,m-1),其中：,Hash(key),，,ReHash(key),是两个哈希函数，,m,为哈希表长度,双哈希函数探测法，先用第一个函数,Hash(key),对关键字计算哈希,地址，一旦产生地址冲突，再用第二个函数,ReHash(key),确定移动的步,长因子，最后，通过步长因子序列由探测函数寻找空的哈希地址。,比如，,Hash(key)=a,时产生地址冲突，就计算,ReHash(key)=b,，,则探测的地址序列为：,H,1,=(a+b)mod m,，,H,2,=(a+2b)mod m,，,，,H,m-1,=(a+(m-1)b)mod m,92,（,2,）链地址法,设哈希函数得到的哈希地址域在区间,0,，,m-1,上，以每个哈希地址作为,一个指针，指向一个链，即分配指针数组,ElemType *eptrm,；建立,m,个空,链表，由哈希函数对关键字转换后，映射到同一哈希地址,i,的同义词均加入,到*,eptri,指向的链表中。,例：关键字序列为：,47,7,29,22,27,92,33,8,3,51,37,78,94,21,哈希函数为：,Hash(key)=key mod 11,用拉链法处理冲突，建表如图所示：,93,(,向链表中插入元素均在表头进行,),94,（,3,）建立一个公共溢出区,设哈希函数产生的哈希地址集为,0,，,m-1,，则分配两个表：,一个基本表,ElemType base_tblm,；每个单元只能存放一个元素；,一个溢出表,ElemType over_tblk,；只要关键字对应的哈希地址在,基本表上产生冲突，则所有这样的元素一律存入该表中。,查找时，对给定值,kx,通过哈希函数计算出哈希地址,i,，先与基本,表的,base_tbli,单元比较，若相等，查找成功；否则，再到溢出表中进,行查找。,95,（,1,）查找又称为检索，是从一个数据元素（记录）的集合中，按某个关键字值查找特定数据元素（记录）的一种操作。若表中存在这样一个数据元素（或记录），则查找成功；否则，查找失败。,（,2,）查找可以分为静态查找和动态查找。在查找过程中仅查找某个特定元素是否存在或它的属性的，称为静态查找；在查找过程中对查找表进行插入元素或删除元素操作的，称为动态查找。,（,3,）查找算法的效率，主要是看要查找的值与关键字的比较次数，通常用平均查找长度（,ASL,）来衡量。,（,4,）顺序查找对查找表无任何要求，既适合无序表，又适合有序表，其查找成功的平均查找长度为,(n+1)/2,，时间复杂度为,O(n),。,小结：,96,（,5,）二分查找要求表中元素必须按关键字有序，其平均查找长度为近似（,log,2,（,n+1,）,-1,），时间复杂度为：,O,（,log,2,n,）。,（,6,）分块查找，每块内的元素可以无序，但要求块与块之间必须有序，并建立索引表。,（,7,）二叉排序树是一种有序树，在它上面的查找类似于二分查找的判定树上的查找。这是一种动态查找过程，在查找过程中插入结点，不必移动其它结点，仅需修改指针即可。其查找性能介于二分查找和顺序查找之间。,（,8,）散列查找是通过构造散列函数来计算关键字存储地址的一种查找方法，时间复杂度为：,O,（,1,）。,（,9,）两个不同的关键字，其散列函数值相同，因而得到同一个表的相同地址的现象称为冲突。,（,10,）常用的解决冲突的方法有：线性探测法、平方探测法、链地址法等。,97,