本章讨论的数据结构是查找表课件

第九章第九章 查查 找找本章讨论的数据结构是查找表查找表 查找表是由同一类型同一类型的数据元素(或记录)构成的集合集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种非常灵活的数据结构。何谓何谓查找表查找表？对查找表经常进行的对查找表经常进行的操作操作:1）查查询询某个“特定的”数据元素是否在查找表中；2）检索检索某个“特定的”数据元素的各种属性；3）在查找表中插入插入一个数据元素；4）从查找表中删去删去某个数据元素。仅作查询和检索操作的查找表。静态查找表静态查找表在查询之后，还需要插入查找表中不存在的数据元素到查找表中；或者，从查找表中删除已存在的数据元素。动态查找表动态查找表查找表可分为两类查找表可分为两类:是数据元素（或记录）中某个数据项数据项的值，用以标识标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的唯一的一个记录，则称之谓“主关键字主关键字”。若此关键字能识别若干若干记录，则称之谓“次关次关键字键字”。术语术语关键字关键字 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。若查找表中存在这样一个记录，则称“查找成功查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功查找不成功”。查找结果给出“空记录”或“空指针”。查找查找 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，用另外一种用另外一种结构来表示查找表结构来表示查找表。查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。如何进行查找？如何进行查找？9.1 静态查找表静态查找表9.2 动态查找表动态查找表9.3 哈希表哈希表提要9.1 静静 态态 查查 找找 表表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据元素同属一个集合。抽象数据类型定义抽象数据类型定义:ADT StaticSearchTable Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit();ADT StaticSearchTable基本操作基本操作 P：构造一个含n个数据元素的静态查找表ST。操作结果：Create(&ST,n);销毁表ST。初始条件：操作结果：静态查找表ST存在；Destroy(&ST);若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。初始条件：操作结果：静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；Search(ST,key);按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；Traverse(ST,Visit();typedef struct /数据元素存储空间基址，建表时 /按实际长度分配，0号单元留空 int length;/表的长度 SSTable;ElemType*elem;假设静态查找表静态查找表的顺序存储结构顺序存储结构为:typedef struct KeyType key;/关键字域 /其它属性域 ElemType;,TElemType;数据元素类型的定义为数据元素类型的定义为:一、顺序查找表一、顺序查找表二、有序查找表二、有序查找表三、索引顺序表三、索引顺序表静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同。以顺序表或线性链表表示静态查找表一、顺序查找顺序查找表表顺序查找顺序查找顺序查找的查找过程：从表中最后一个记录开始，逐个向前，比较记录的关键字和给定值，若某个记录的关键字和给定值相等，则查找成功，返回该记录的存储位置；反之，若直至第一个记录，所有记录的关键字和给定值都不相等，则查找不成功，返回空地址。ST.Length0 1 2 3 4 5 6 7 8 9 10 11ST.elem1380755664059219883721iiiii例如：例如：64key=64ST.LengthST.elem0 1 2 3 4 5 6 7 8 9 10 111380755664059219883721iiiiiiiiiiii60key=60int 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注意：本算法通过设置“哨兵哨兵”起到监视哨监视哨的作用，使查找过程中的每一步免去了检测整个表是否查找完毕这一动作，提高了查找的效率。定义：定义：查找算法在查找成功时的平均查找长度平均查找长度 (Average Search Length)：为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中:n 为表长；Pi 为查找表中第i个记录的概率，且 ；Ci为找到该记录时，曾和给定 值比较过的关键字的个数。分析顺序查找的时间性能在等概率查找的情况下，顺序表查找的平均查找长度为：ASL=nP1+(n-1)P2+2Pn-1+Pn对顺序表顺序表而言，Ci=n-i+1 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上或与其后一元素交换位置。在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值。顺序查找在查找不成功时，给定值与关键字比较次数为n+1。顺序查找的优缺点：优点优点：算法简单；对表的结构无任何要求，适应面广。缺点缺点：平均查找长度较大，(n)，特别当n很大时，查找效率低。上述顺序查找表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。若以有序表有序表(表中元素按关键字有序排列)表示静态查找表，则查找过程可以采用更为高效的方法进行。二、有序查找表二、有序查找表折半查找（折半查找（又称二分查找）例如例如:key=64 的查找过程如下：0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length9288807564563721191305 lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/2int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值 while(low 50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。(O(log2n)折半查找在查找不成功时的关键字比较次数不超过 log2n+1。折半查找的效率比顺序查找高，但它只适用于有序表，且限于顺序存储结构，对线性链表通常不能进行折半查找。折半查找的优缺点：优点：查找效率高；缺点：只适用于向量结构，而且要求表是有序的。关键字:A B C D E Pi:0.2 0.3 0.05 0.3 0.15 Ci:2 3 1 2 3 在不等概率查找不等概率查找的情况下，折半查找折半查找不是不是有序表最好的查找方法。例如例如:此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4若改变Ci的值 2 1 3 2 3则 ASL=20.2+10.3+30.05+20.3+30.15=1.9三、静态查找树表三、静态查找树表 使 达最小的判定树称为最优二叉树，其中:定义定义:为计算方便，令 wi=pi选择二叉树的根结点，使 达最小 为便于计算，引入累计权值和 并设 wl-1=0 和 swl-1=0，则推导可得介绍一种次优二叉树的构造方法：023811151823lh211812431018h9608EC21Ah53lhG3013例如例如:ECGABDF 查找比较查找比较“总次数总次数”=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和折半查找相比较和折半查找相比较DBACFEG所得次优二叉树如下所示所得次优二叉树如下所示:Status SecondOptimal(BiTree&T,ElemType R,float sw,int low,int high)/由有序表Rlow.high及其累计权值表sw/递归构造次优查找树T。选择最小的选择最小的Pi值值 if(!(T=(BiTree)malloc(sizeof(BiTNode)return ERROR;T-data=Ri;/生成结点构造次优二叉树的算法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;/SecondOptimalStatus 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次优查找树采用二叉链表的存储结构三、索引顺序三、索引顺序表表分块查找分块查找（又称索引顺序查找）将待查的元素均匀的分成若干个子表（称为块），块间按大小排序，块内不排序。因此需要建立一个块的最大（或最小）关键字表，称之为“索引表”。例如：索引表索引表224886 1 71322 12 13 8920 33 42 44 38 24 48 60 58 74 49 86 531 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18最大关键字起始地址索引表按关键字有序。1）由索引确定记录所在区间（折半查找或顺序查找）；2）在顺序表的某个区间内进行查找（顺序查找）。可见，索引顺序查找索引顺序查找的过程也是一个“缩小区间缩小区间”的查找过程。索引顺序表的查找过程：索引顺序表的查找过程：索引顺序查找的平均查找长度索引顺序查找的平均查找长度=查找查找“索引索引”的平均查找长度的平均查找长度 +查找查找“顺序表顺序表”的平均查找长度的平均查找长度结论见教材教材P.226(9-15)、(9-16)这种查找方法优于顺序查找，次于折半查找。9.2 动动 态态 查查 找找 表表ADT DynamicSearchTable 数据对象数据对象D：数据关系数据关系R：数据元素同属一个集合。D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。抽象数据类型抽象数据类型动态查找表动态查找表的定义如下的定义如下：InitDSTable(&DT)DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&T,key);TraverseDSTable(DT,Visit();ADT DynamicSearchTable基本操作基本操作P：操作结果：操作结果：构造一个空的动态查找表DT。InitDSTable(&DT);销毁动态查找表DT。初始条件：操作结果：动态查找表DT存在；DestroyDSTable(&DT);若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。初始条件：操作结果：动态查找表DT存在，key为和关键字类型相同的给定值；SearchDSTable(DT,key);动态查找表DT存在，e 为待插入的数据元素；初始条件：操作结果：若DT中不存在其关键字等于 e.key 的 数据元素，则插入 e 到DT。InsertDSTable(&DT,e);动态查找表DT存在，key为和关键字类型相同的给定值；初始条件：操作结果：若DT中存在其关键字等于key的数据元素，则删除之。DeleteDSTable(&T,key);动态查找表DT存在，Visit是对结点操作的应用函数；初始条件：操作结果：按某种次序对DT的每个结点调用函数 Visit()一次且至多一次。一旦 Visit()失败，则操作失败。TraverseDSTable(DT,Visit();一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）二、二叉平衡树二、二叉平衡树三、三、B-树树四、四、B+树树提要1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析一、二叉排序树（二叉查找树一、二叉排序树（二叉查找树）（1）若它的左子树不空，则左子树上所有结点 的值均小于根结点的值；二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：（3）它的左、右子树也都分别是二叉排序树。（2）若它的右子树不空，则右子树上所有结点 的值均大于根结点的值；1定义：定义：是二叉排序树。是二叉排序树。50308020901085403525238866不不例如例如:typedef struct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;通常，取二叉链表作为二叉排序树的存储结构:1）若给定值等于等于根结点的关键字，则查查找成功找成功；2）若给定值小于小于根结点的关键字，则继继续在左子树上进行查找续在左子树上进行查找；3）若给定值大于大于根结点的关键字，则继继续在右子树上进行查找续在右子树上进行查找。否则，若二叉排序树为空为空，则查找不成功查找不成功；2二叉排序树的查找算法：二叉排序树的查找算法：查找关键字查找关键字=50,35,90,503080209085403588325050503040355050809095例如例如:二叉排序树二叉排序树从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条查找路径查找路径：从根结点出发，沿着左分支或右分支逐层向从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。下直至指针指向空树为止。查找成功查找成功 查找不成功查找不成功算法请看：1.P.228 算法9.5(a)2.P.228 算法9.5(b)30201040352523fT设 key=48fTfT22pfTfTTTTfffp根据动态查找表的定义，“插入插入”操作操作在在查找不成功查找不成功时才进行时才进行；若二叉排序树为空树空树，则新插入的结点为新的根结点新的根结点；否则，新插入的结点必为一个新的叶子结点新的叶子结点，其插入位置插入位置由查找过程得到。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二叉排序树的删除算法二叉排序树的删除算法50308020908540358832例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”（1）被删除的结点是叶子结点叶子结点50308020908540358832 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被指向被删除结点的左子树或右子树删除结点的左子树或右子树”。被删关键字被删关键字=4080（2）被删除的结点只有左子树只有左子树或者只只有右子树有右子树5030802090854035883240以其前驱替代之，然后以其前驱替代之，然后再删除该前驱结点再删除该前驱结点被删结点前驱结点被删关键字被删关键字=50（3）被删除的结点既有左子树，又有既有左子树，又有右子树右子树中序9640Status 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);pp/左子树为空树只需重接它的右子树q=p;p=p-rchild;free(q);ppq=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);pCLCQSPRQLSLqsqssqSqs 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。5查找性能的分析查找性能的分析由关键字序列 3，1，2，5，4构造而得的二叉排序树，由关键字序列 1，2，3，4，5构造而得的二叉排序树，2134535412ASL=（1+2+3+4+5）/5 =3ASL=（1+2+3+2+3）/5 =2.2例如：例如：最好的情况最好的情况是二叉排序树的深度与折半查找的判定树深度相同；最坏的情况最坏的情况是单枝树。在随机的情况下，二叉排序树的平均查找长度即O(log n)，但在很多情况下还达不到这个值。(教材P.232)为了降低平均查找长度，有必要在构成二叉排序树的过程中进行“平衡化”处理，使之成为平衡的二叉排序树。不失一般性，假设长度为 n 的序列中有 k 个关键字小小于于第一个关键字，则必有 n-k-1 个关键字大于大于第一个关键字,由它构造的二叉排序树：n-k-1k的平均查找长度是 n 和 k 的函数P(n,k)(0 k n-1)。下面讨论平均情况下面讨论平均情况:假设 n 个关键字可能出现的 n!种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度：在等概率查找等概率查找的情况下，由此可类似于解差分方程，此递归方程有解：何谓何谓“二叉平衡树二叉平衡树”？二叉平衡树的查找性能分析二叉平衡树的查找性能分析如何构造如何构造“二叉平衡树二叉平衡树”二、二叉平衡树二、二叉平衡树例如例如:树中每个结点的树中每个结点的左、右子树深度之差的绝左、右子树深度之差的绝对值不大于对值不大于1，即，即 。548254821是平衡树是平衡树不是平衡树不是平衡树 二叉平衡树二叉平衡树是二叉查找树的另一种形式，其特点为：例如：依次插入的关键字为5,4,2,8,6,95424258665842向右旋转一次先向右旋转再向左旋转构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。426589642895向左旋转一次继续插入关键字 9 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。问：含 n 个关键字的二叉平衡树可能达到的最大深度最大深度是多少？平衡树的查找性能分析：平衡树的查找性能分析：n=0空树空树最大深度为最大深度为 0n=1最大深度为最大深度为 1n=2最大深度为最大深度为 2n=4最大深度为最大深度为 3n=7最大深度为最大深度为 4先看几个具体情况:h=0N0=0h=1h=2h=3一般情况下一般情况下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1反过来问，深度为深度为 h 的二叉平衡树平衡树中所含结点的含结点的最小值最小值 Nh 是多少？结论：在二叉平衡树二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字的个进行比较的关键字的个数和数和 log n 相当。即在平衡树上查找的时间复杂度为O(log n)。1定义定义2查找操作查找操作3插入操作插入操作4删除操作删除操作5查找性能的分析查找性能的分析三、三、B-树树B-树是一种 平衡平衡 的 多路多路 查找查找 树：1B-树的定义树的定义root5071 8489 96FFFFFFFFFFFFFFF153820 26 437856 624阶B_树typedef struct BTNode int keynum;/结点中关键字个数，结点大小 struct BTNode *parent;/指向双亲结点的指针 KeyType keym+1;/关键字(0号单元不用)struct BTNode *ptrm+1;/子树指针向量 Record *recptrm+1;/记录指针向量(0号单元不用)BTNode,*BTree;/B树结点和B树的类型B-树结构的树结构的C语言描述如下语言描述如下:在 m 阶的B-树上，每个非终端结点可能含有：n 个关键字关键字 Ki（1 in）nm n 个指向记录的指针指向记录的指针 Di（1in）n+1 个指向子树的指针指向子树的指针 Ai（0in）多叉树的特性非叶结点中的多个关键字多个关键字均自小至大自小至大有序排列，即：K1 K2 keynum;i=Search(p,K);/在p-key1.keynum中查找 i，使p-keyi=Kkeyi+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);/查找不成功在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下层的非叶最下层的非叶结点结点，有下列几种情况：1）插入后，该结点的关键字个数nm，不修改指针;例如3插入插入2）插入后，该结点的关键字个数 n=m，则需进行“结点分裂”，令 s=m/2，在原结点中保留 （A0，K1，Ks-1，As-1）；建新结点p （As，Ks+1，Kn，An）；将（Ks，p）插入双亲结点；例如3）若双亲为空，则建新根结点。例如50 20 40 80 插入关键字=60,60 80 90,60 80 90 90 50 80 60 30,40 20 30 50 808030 50例如:下列为 3 阶B-树 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。4删除删除请看P.244-245 在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的树的深度深度。问：含 N 个关键字的 m 阶 B-树可能达到的最大深度 H 为多少？5查找性能的分析查找性能的分析第第 2 层层 2 个个先推导每一层所含最少结点数：第第 1 层层 1 个个第第 H+1 层层 2(m/2)H-1 个个第第 4 层层 2(m/2)2 个个第第 3 层层 2m/2 个个反过来问：深度为H的B-树中，至少含有多少个结点？假设 m 阶 B-树的深度为 H+1，由于第 H+1 层为叶子叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个，N+12(m/2)H-1 H-1log m/2(N+1)/2)Hlog m/2(N+1)/2)+1由此可推得下列结果：在含在含 N 个关键字的个关键字的 B-树上进行一次查找，树上进行一次查找，需访问的结点个数不超过需访问的结点个数不超过 log m/2(N+1)/2)+1结论：结论：是是B-树的一种变型树的一种变型四、四、B+树树 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子叶子结点彼此相链接链接构成一个有序链表，其头指针指向含最小关键字的结点；1B+树的结构特点：树的结构特点：每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值；所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。50 96 15 5062 78 96 71 7884 89 96 56 6220 26 43 50 3 8 15sqroot 在 B+树上，既可以进行缩小范围的查 找，也可以进行顺序查找；在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束；若在结点内查找时，给定值Ki，则 应继续在 Ai 所指子树中进行查找。2查找过程查找过程类似于类似于B-树进行，即必要时，也需要树进行，即必要时，也需要进行结点的进行结点的“分裂分裂”或或“归并归并”。3插入和删除的操作插入和删除的操作 一、一、哈希表是什么？哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法 三、处理冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找 五、哈希表的删除操作哈希表的删除操作9.3 哈哈 希希 表表 以上两节讨论的表示查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关键字关键字之间不存在不存在一个确定的关系;查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较;查找的效率查找的效率取决于和给定值进行比较进行比较的关键字个数个数。一、哈希表是什么？哈希表是什么？不同的表示方法，其差别仅在于：差别仅在于：关键字和给定值进行比较的顺序不同。用这类方法表示的查找表，其平均查找长度都不为零。只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。对于频繁使用的查找表，希望 ASL=0。若以下标为以下标为000 999 的顺序表的顺序表表示之。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999(前两位为年份)。因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key)为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。但是，对于动态查找表动态查找表而言，Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei 对于如下 9 个关键字设设 哈希函数哈希函数f(key)=(Ord(第一个字母第一个字母)-Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 10 11 12 13ChenZhaoQian SunLiWuHanYeDei问题问题:若添加关键字 Zhou,怎么办？怎么办？能否找到能否找到另一个哈希函数？例如：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.直接定址法直接定址法此方法仅适合于：此方法仅适合于：能预先估计出预先估计出全体关键字的每一位上每一位上各种数字出现的频度数字出现的频度。假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。2.数字分析法数字分析法 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。3.平方取中法平方取中法 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠加间界叠加。此方法适合于此方法适合于:关键字的数字位数特别多。4.折叠法折叠法 设定哈希函数为设定哈希函数为:H(key)=key MOD p 其中其中，pm(表长表长)并且并且 p 应为小于等于应为小于等于m 的的(最大最大)素数素数 或是或是 不含不含 20 以下的质因子以下的质因子5.除留余数法除留余数法 给定一组关键字为：12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为：3,3,0,6,6,3例如：例如：可见，若 p 中含质因子 3，则所有含质因子则所有含质因子 3 的关的关键字均映射到键字均映射到“3 的倍数的倍数”的地址上的地址上，从而增加了“冲突”的可能。为什么要对 p 加限制？设定哈希函数为设定哈希函数为:H(key)=Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。6.随机数法随机数法 实际造表时，采用何种采用何种构造哈希函数的方方法法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能的原则是使产生冲突的可能性降到尽可能地小性降到尽可能地小。“处理冲突处理冲突”的实际含义是：为产生冲突的地址寻找下一个寻找下一个哈希地址。1.开放定址法开放定址法2.链地址法链地址法三、处理冲突的方法处理冲突的方法 3.再哈希法再哈希法4.公共溢出区法公共溢出区法 为产生冲突的地址 H(key)求得一个地址地址序列序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s1.开放定址法开放定址法对增量 di 有三种取法：1)线性探测再散列线性探测再散列 di=c i 最简单的情况 c=12)平方探测再散列平方探测再散列 di=12,-12,22,-22,3)随机探测再散列随机探测再散列 di 是一组伪随机数列伪随机数列例1例2设定设定哈希函数 H(key)=key MOD 11(表长=11)190123 145568190123 1468若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突11 823655118236例如例如:关键字集合 19,01,23,14,55,68,11,82,36 112113625112114312ASL=(41+22+3+5+6)/9=22/9ASL=(51+22+3+4)/9=16/9容易产生“聚集”不易产生“聚集”将所有哈希地址相同的记录都链接在同一链表中。012345601196814 36 23 11 82 55 ASL=(61+22+3)/9=13/9例如:同前例的关键字 19,01,23,14,55,68,11,82,36 ，哈希函数为 H(key)=key MOD 72.链地址法链地址法3.再哈希法再哈希法Hi=RHi(key)i=1,2,kRhi是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。此法不易产生“聚集”，但增加了计算工作量。4.公共溢出区法公共溢出区法除了有HashTable0.m-1外，另设一个溢出表OverTable0.v。一旦发生冲突，就填入溢出表。查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为：对于给定值 K，计算哈希地址 i=H(K)若若 ri=NULL 则查找不成功若若 ri.key=K 则查找成功否则否则“求下一地址 Hi”，直至 rHi=NULL (查找不成功)或 rHi.key=K (查找成功)为止。四、哈希表的查找哈希表的查找int hashsize=997,.;typedef struct ElemType *elem;int count;/当前数据元素个数 int sizeindex;/hashsizesizeindex为当前容量 HashTable;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/-开放定址哈希表开放定址哈希表的存储结构-Status SearchHash(HashTable H,KeyType K,int&p,int&c)/在开放定址哈希表H中查找关键码为K的记录/SearchHashp=Hash(K);/求得哈希地址while(H.elemp.key!=NULLKEY&!EQ(K,H.elemp.key)）collision(p,+c);/求得下一探查地址 pif(EQ(K,H.elemp.key)return SUCCESS;/查找成功，返回待查数据元素位置 pelse return UNSUCCESS;/查找不成功Status InsertHash(HashTable&H,Elemtype e)c=0;if(SearchHash(H,e.key,p,c)=SUCCESS)return DUPLICATE;/表中已有与 e 有相同关键字的元素 else if(c hashsizeH.sizeindex/2)/冲突次数 c 未达到上限，（阀值 c 可调）H.elemp=e;+H.count;return OK;/查找不成功时，返回 p为插入位置 else RecreateHashTable(H);/重建哈希表/InsertHash1)选用的哈希函数哈希函数；2)选用的处理冲突的方法处理冲突的方法；3)哈希表饱和的程度，装填因子装填因子 =n/m 值的大小大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素的因素：从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。哈希表查找的分析:一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，因此，哈希表的哈希表的ASL是是处理冲突方法处理冲突方法和和装填装填因子因子的函数。的函数。线性探测再散列线性探测再散列链地址法链地址法随机探测再散列随机探测再散列可以证明：查找成功查找成功时有下列结果：(P.261)哈希表的平均查找长度是 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定平均查找长度限定在某个范围内在某个范围内。这是哈希表所特有的特点。这是哈希表所特有的特点。从以上结果可见：从哈希表中删除记录时，要作特殊处理特殊处理，相应地，需要修改查找的算法。五、哈希表的删除操作哈希表的删除操作 1.掌握顺序表顺序表、有序表和索引顺序表有序表和索引顺序表的查找方法及顺序表顺序表、有序表有序表平均查找长度的计算方法。2.熟练掌握二叉排序树二叉排序树的构造和查找方法。本章小结 3.理解B-树树、B+树树的特点特点以及它们的建树和查找以及它们的建树和查找的过程。的过程。4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。5.掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。本章作业本章作业:9.19.39.49.269.99.119.139.149.19