1、第第8 8章章 查查 找找查找是数据处理中经常使用的一种重要运算，查找是数据处理中经常使用的一种重要运算，查找算法的优劣对系统运行效率的影响非常查找算法的优劣对系统运行效率的影响非常大。静态查找表、动态查找表和哈希表是主大。静态查找表、动态查找表和哈希表是主要的查找技术。要的查找技术。本章要点本章要点 v查找的基本概念；查找的基本概念；v几种常见的静态查找表的查找算法；几种常见的静态查找表的查找算法；v二叉排序树的创建、查找和删除算法；二叉排序树的创建、查找和删除算法；v平衡二叉树的基本操作；平衡二叉树的基本操作；v哈希函数的构造方法和哈希表的查找算法。哈希函数的构造方法和哈希表的查找算法。感
2、谢你的观看2019年8月23章节安排章节安排8.18.1查找的基本概念查找的基本概念8.28.2静态表的查找静态表的查找8.38.3动态表的查找动态表的查找8.48.4散列表散列表感谢你的观看2019年8月238.18.1查找的基本概念查找的基本概念v查找：又称检索，是指在查找表中查找满足一查找：又称检索，是指在查找表中查找满足一定条件的结点或记录。定条件的结点或记录。v查找方法：静态查找、动态查找查找方法：静态查找、动态查找 v衡量查找算法优劣指标：最大查找长度、平均衡量查找算法优劣指标：最大查找长度、平均查找长度如对查找长度如对n n个记录进行查找时，平均查找长个记录进行查找时，平均查找长
3、度可表示为：度可表示为：1niiiASL np c感谢你的观看2019年8月238.28.2静态表的查找静态表的查找 静态查找表可分为顺序表、有序表和静态查找表可分为顺序表、有序表和索引顺序表三种。索引顺序表三种。感谢你的观看2019年8月23顺序表的查找基本思想是：从顺序表的顺序表的查找基本思想是：从顺序表的一端开始，逐个比较结点的关键字和给一端开始，逐个比较结点的关键字和给定值，若某个结点的关键字与给定值相定值，若某个结点的关键字与给定值相等，则查找成功；若找遍整个顺序表都等，则查找成功；若找遍整个顺序表都不相等，则查找失败。查找成功时，查不相等，则查找失败。查找成功时，查找算法返回找到结
4、点在顺序表中的位置，找算法返回找到结点在顺序表中的位置，失败时返回失败时返回1 1。8.2.18.2.1顺序表的查找顺序表的查找 感谢你的观看2019年8月23下面的算法描述了顺序查找过程。下面的算法描述了顺序查找过程。v顺序表的存储结构定义如下：顺序表的存储结构定义如下：typedef structtypedef struct KeyTypeKeyType key key；/*关键字的数据类型关键字的数据类型*/DataType DataType；/*数据元素的类型数据元素的类型*/typedef structtypedef struct DataType DataType *datadat
5、a；/*顺序表顺序表datadata*/int len int len；/*顺序表的长度顺序表的长度*/Stable Stable；感谢你的观看2019年8月23【算法【算法8.18.1】顺序表查找算法】顺序表查找算法int Stable_Search(Stableint Stable_Search(Stable S S，KeyTypeKeyType key)key)/*在顺序表在顺序表S S中查找关键字等于中查找关键字等于keykey的结点的结点*/int int i;i;S.data0.key=key S.data0.key=key；/*设置哨兵设置哨兵*/i=S.len i=S.len;
6、/*设置初始查找位置设置初始查找位置*/while(S.datai.keywhile(S.datai.key!=key)i-!=key)i-；/*从从后往前找后往前找*/if(i=0)return 1 if(i=0)return 1；/*查找失败查找失败*/else return ielse return i；/*查找成功查找成功*/v 顺序查找的平均查找长度为：顺序查找的平均查找长度为：111(1)2ninASLnin 感谢你的观看2019年8月23 二分法查找（二分法查找（Binary SearchBinary Search）又称为折半查）又称为折半查找，其基本思想是：首先取查找表中间位置
7、上找，其基本思想是：首先取查找表中间位置上的结点的关键字与给定值进行比较，若相等，的结点的关键字与给定值进行比较，若相等，则查找成功；否则，如果给定值比中间位置上则查找成功；否则，如果给定值比中间位置上的结点的关键字大，则把查找区间定为表的后的结点的关键字大，则把查找区间定为表的后半段，反之把查找区间定为表的前半段；然后半段，反之把查找区间定为表的前半段；然后在前半段或后半段采用同样的方法继续查找，在前半段或后半段采用同样的方法继续查找，如此继续，直到找到关键字等于给定值的结点，如此继续，直到找到关键字等于给定值的结点，则查找成功；若出现查找区间的左右边界异常，则查找成功；若出现查找区间的左右
8、边界异常，则查找失败。则查找失败。8.2.28.2.2有序表的查找有序表的查找 感谢你的观看2019年8月23例：已知有例：已知有1111个关键字的有序表序列如下所示：个关键字的有序表序列如下所示：0202，0808，1515，2323，3131，3737，4242，4949，6767，8383，9191 当给定的当给定的k k值为值为2323和和8383时，折半查找的过程如图时，折半查找的过程如图所示。图中用方括号表示当前的查找区间，用所示。图中用方括号表示当前的查找区间，用“”指向中间位置。指向中间位置。感谢你的观看2019年8月23【算法【算法8.28.2】二分法查找非递归算法】二分法查
9、找非递归算法int Binary_Search(Stableint Binary_Search(Stable S S，KeyTypeKeyType key)key)intint low low，midmid，highhigh；low=1low=1；high=S.lenhigh=S.len；while(lowwhile(low=high)mid=(low+high)/2=high)mid=(low+high)/2；if(keyS.datamid.keyif(keyS.datamid.keyif(keyS.datamid.key)low=mid+1low=mid+1；else return mid
10、 else return mid；return 1return 1；感谢你的观看2019年8月23索引顺序查找又称为分块查找，是顺序查找的一索引顺序查找又称为分块查找，是顺序查找的一种改进方法。在索引顺序查找法中，除表本身以种改进方法。在索引顺序查找法中，除表本身以外，还需要建立一个外，还需要建立一个“索引表索引表”。分块查找的基本思想：把顺序表分成若干块，每分块查找的基本思想：把顺序表分成若干块，每一块中结点的存放是任意的，但是块与块之间必一块中结点的存放是任意的，但是块与块之间必须有序。假设块间按关键字值递增排序，以每块须有序。假设块间按关键字值递增排序，以每块中的最大（小）关键字值建立一
11、个索引表，存放中的最大（小）关键字值建立一个索引表，存放每块的最大（小）关键字值和每块的起始位置。每块的最大（小）关键字值和每块的起始位置。查找时需分两步走，首先在索引表中采用顺序查查找时需分两步走，首先在索引表中采用顺序查找或折半查找算法查找给定值，确定给定值所在找或折半查找算法查找给定值，确定给定值所在的块；然后在所确定的块中顺序查找。的块；然后在所确定的块中顺序查找。8.2.38.2.3索引顺序表的查找索引顺序表的查找 感谢你的观看2019年8月23 例例8.2 8.2 设有一个顺序表共有设有一个顺序表共有2020个结点，现将它个结点，现将它分成四块，每块分成四块，每块5 5个结点。以每
12、块最大关键字值建个结点。以每块最大关键字值建立索引表，索引表包含最大关键字值和对应块的立索引表，索引表包含最大关键字值和对应块的起始地址两个域，如图起始地址两个域，如图8.28.2所示。试查找关键字值所示。试查找关键字值为为5858的结点。的结点。图图8.2表及索引表结构图表及索引表结构图感谢你的观看2019年8月23分块查找的平均查找长度：分块查找的平均查找长度：ASLASLbsbs=ASLASLb b+ASLASLw wASLASLbsbs表示分块查找的平均查找长度，表示分块查找的平均查找长度，ASLASLb b表表 示查找索引表以确定所在块的平均查找长度，示查找索引表以确定所在块的平均查
13、找长度，ASLASLw w表示在块中查找关键字的平均查找长度。表示在块中查找关键字的平均查找长度。感谢你的观看2019年8月238.38.3动态表的查找动态表的查找 动态查找表的特点是：表结构本身是在查动态查找表的特点是：表结构本身是在查找过程中动态生成的，即对于给定值找过程中动态生成的，即对于给定值keykey，若表中存在关键字等于若表中存在关键字等于keykey的结点，则查找的结点，则查找成功；否则插入关键字为成功；否则插入关键字为keykey的结点。的结点。感谢你的观看2019年8月23二叉排序树又称二叉查找树，它或者是一棵空二叉排序树又称二叉查找树，它或者是一棵空树，或者是具有以下性质
14、的二叉树：树，或者是具有以下性质的二叉树：若任一结点的左子树非空，则左子树中的所有若任一结点的左子树非空，则左子树中的所有结点的值都不大于根结点的值；结点的值都不大于根结点的值；若任一结点的右子树非空，则右子树中的所有若任一结点的右子树非空，则右子树中的所有结点的值都不小于根结点的值。结点的值都不小于根结点的值。8.3.1 8.3.1二叉排序树二叉排序树 感谢你的观看2019年8月23 例如：图例如：图8.38.3所示为一棵二叉排序树（结点内的所示为一棵二叉排序树（结点内的数为数据元素的关键字）。其中序遍历序列为：数为数据元素的关键字）。其中序遍历序列为：1515，5555，6565，7575
15、，7979，9595，100100，120120，200200，230230，240240。图图8.3 8.3 二叉排序树二叉排序树感谢你的观看2019年8月23二叉排序树一般采用二叉链表作为存储结二叉排序树一般采用二叉链表作为存储结构，可定义如下：构，可定义如下：typedef struct BSTNodetypedef struct BSTNode DataTypeDataType datadata；/*数据元素字段数据元素字段*/struct BSTNodestruct BSTNode *lchildlchild，*rchildrchild；/*左、右指针字段左、右指针字段*/NodeT
16、ypeNodeType；感谢你的观看2019年8月23【算法【算法8.38.3】二叉排序树查找算法】二叉排序树查找算法int BST_Search(NodeTypeint BST_Search(NodeType *T T，KeyType KeyType key,NodeType key,NodeType*p,NodeTypep,NodeType *q)q)if(T)if(T)*p=Tp=T；*q=NULL;q=NULL;while(while(*p)p)if(key(if(key(*p)-p)-data.keydata.key)*q=q=*p p ；(*p)=(p)=(*p)-rchildp)
17、-rchild；elseelseif(keydata.keyif(keydata.key)*q=q=*p p ；(*p)=(p)=(*p)-lchildp)-lchild；else elsereturn 1return 1；return 0return 0；感谢你的观看2019年8月23 二叉排序树的插入和生成过程如下：二叉排序树的插入和生成过程如下：(1)(1)若二叉排序树为空，则把待插入的结点作为根若二叉排序树为空，则把待插入的结点作为根结点插入到空树中。结点插入到空树中。(2)(2)若二叉排序树非空，则将待插入的结点关键字若二叉排序树非空，则将待插入的结点关键字和根结点的关键字进行比较，
18、若两者相等，表示该和根结点的关键字进行比较，若两者相等，表示该结点已在二叉排序树中，无需插入；若待插入的结结点已在二叉排序树中，无需插入；若待插入的结点关键字小于根结点的关键字，将待插入的结点插点关键字小于根结点的关键字，将待插入的结点插入到根的左子树中，否则插入到右子树中。入到根的左子树中，否则插入到右子树中。(3)(3)子树中的插入过程和树中的插入过程相同，如子树中的插入过程和树中的插入过程相同，如此插入下去，直到把待插入的结点作为叶子插入到此插入下去，直到把待插入的结点作为叶子插入到二叉排序树中。二叉排序树中。感谢你的观看2019年8月23【算法【算法8.48.4】二叉排序树的插入算法】
19、二叉排序树的插入算法int InsertNode(NodeTypeint InsertNode(NodeType *t t，KeyType key)KeyType key)NodeTypeNodeType *p,p,*q q，*s;s;if(!BST_Searchif(!BST_Search(*t t，key,&p,&q)key,&p,&q)s=(NodeTypes=(NodeType*)malloc(sizeof(NodeType)malloc(sizeof(NodeType););s-data.keys-data.key=key=key；s-lcs-lc=NULL=NULL；s-rcs-r
20、c=NULL=NULL；if(!pif(!p)t=st=s；elseelse if(keyp-data.key)if(keyp-data.key)p-rchildp-rchild=s=s；elseelsep-lchildp-lchild=s=s；return 1 return 1；return 0return 0；感谢你的观看2019年8月23 例如，给定关键字序列例如，给定关键字序列5353，8080，6969，4545，5858，3030，8888，则构造相对应的一棵二叉排序树的，则构造相对应的一棵二叉排序树的过程如图过程如图8.58.5所示：所示：(a)(a)(b)(b)5353(c)(
21、c)53538080(d)(d)696980805353(e)(e)6969808053534545(f)(f)69698080535345455858(g)(g)6969808053534545585830306969808053534545585830308888(h)(h)图图8.58.5二叉排序树的插入过程二叉排序树的插入过程(a)(a)空树；（空树；（b b）插入）插入5353；(c)(c)插入插入9090；(d)(d)插入插入6969；(e)(e)插入插入4545；(f)(f)插入插入5858；(g)(g)插入插入3030；(h)(h)插入插入8888；感谢你的观看2019年8月2
22、3二叉排序树的删除二叉排序树的删除 设待删结点的为设待删结点的为p p，p p的双亲结点为的双亲结点为d d，若，若p p的左右孩的左右孩子分别为子分别为plpl和和prpr，则删除操作可分以下三种情况进，则删除操作可分以下三种情况进行讨论：行讨论：（1 1）若结点）若结点p p为叶子结点，则为叶子结点，则plpl和和prpr均为空二叉树。均为空二叉树。由于删除叶子结点不会破坏整棵树的结构，则根据由于删除叶子结点不会破坏整棵树的结构，则根据p p是是d d的左子树还是右子树，将的左子树还是右子树，将d d的左孩子或右孩子的左孩子或右孩子指针域置空即可。删除过程如图指针域置空即可。删除过程如图8
23、.68.6所示。所示。(b)607555365912删去叶子结点80图8.6删除二叉排序树中的叶子结点(a)删除叶子80之前；(b)删除叶子80之后60755536591280(a)p感谢你的观看2019年8月23 （2 2）若结点）若结点p p只有左子树只有左子树plpl或右子树或右子树prpr时，时，则用则用p p的左子树的根结点的左子树的根结点plpl或右子树的根结或右子树的根结点点prpr取代被删除的结点即可。删除过程如取代被删除的结点即可。删除过程如图图8.78.7所示。所示。图8.7删除二叉排序树中的单支结点(a)删除左单支结点36之前；(b)删除左单支结点36之后；(a)删除右单
24、支结点80之前；(b)删除右单支结点80之后删去左单支结点3660755536591280(a)p9080(b)607555125990删去右单支结点8060755536591280(c)90p60755536591290(d)感谢你的观看2019年8月23 （3 3）若结点）若结点p p同时有左右子树同时有左右子树plpl和和PrPr时，则时，则用被删除结点的左子树的根取代被删除的用被删除结点的左子树的根取代被删除的结点，将被删除结点的右子树移动到被删结点，将被删除结点的右子树移动到被删除结点的左子树的最右下方，即用结点除结点的左子树的最右下方，即用结点plpl取代结点取代结点p p，将，将
25、PrPr及其子树移动到及其子树移动到plpl的右子的右子树的最右下方，如图树的最右下方，如图8.88.8所示。所示。(a)dpp rp l8060755512599070(b)p lp r70596055128090图8.8删除二叉排序树中的具有左右子树的结点(a)删除有左右子树结点75之前；(b)删除有左右子树结点75之后感谢你的观看2019年8月23【算法【算法8.58.5】二叉排序树的删除算法】二叉排序树的删除算法int DeleteNode(NodeTypeint DeleteNode(NodeType *t t，KeyTypeKeyType key)key)/*在二叉排序树在二叉排序
26、树t t中若存在关键字值为中若存在关键字值为keykey的结点的结点则删除，函数返回则删除，函数返回1 1，否则返回，否则返回0 0*/NodeTypeNodeType*p,p,*d d，*s;s;if(BST_Searchif(BST_Search(*t t，keykey，&p&p，&d)&d)/*调用查调用查找算法，查找关键字值为找算法，查找关键字值为keykey的结点的结点*/if(q if(q=NULL)=NULL)/*被删除结点是被删除结点是根结点根结点*/if(p-lchildif(p-lchild=NULL)=NULL)*t=p-rchildt=p-rchild;/;/*被删除结
27、点无左子树，将其右子被删除结点无左子树，将其右子树作为删除此结点后的树树作为删除此结点后的树*/感谢你的观看2019年8月23（续）elseelse/*被删除结点有左子树，将其左被删除结点有左子树，将其左子树作为根结点子树作为根结点*/*t=p-lchildt=p-lchild;s=s=*t;/t;/*寻找被删除结点左子树的寻找被删除结点左子树的最右下结点最右下结点*/while(s-rchild!=NULL)while(s-rchild!=NULL)s=s-rchilds=s-rchild;s-rchilds-rchildp-rchildp-rchild;else if(!p-lchilde
28、lse if(!p-lchild)/*待删结点不是根结点，待删结点不是根结点，且其左子树为空，重接它的右子树且其左子树为空，重接它的右子树*/s=p s=p；p=p-rchildp=p-rchild；free(sfree(s)；感谢你的观看2019年8月23（续）（续）elseelse if(!p-rchildif(!p-rchild)/*待删结点的待删结点的右子树为空，重接它的左子树右子树为空，重接它的左子树*/s=p s=p；p=p-lchildp=p-lchild；free(sfree(s)；else/else/*待删结点的左右子树均不空，将其右待删结点的左右子树均不空，将其右子树挂到左
29、子树的最右下方子树挂到左子树的最右下方*/s=p-lchild s=p-lchild；while(s-rchild)s=s-rchildwhile(s-rchild)s=s-rchild；/*找到左子树最右下的结点找到左子树最右下的结点*/s-rchild=p-rchild s-rchild=p-rchild;/*将被删除结点将被删除结点的右子树作为的右子树作为s s的右子树的右子树*/s=ps=p；p=p-lchildp=p-lchild；free(sfree(s)；/*用被删除结点的用被删除结点的左子树的根取代被删除结点左子树的根取代被删除结点*/retrun retrun 1 1；ret
30、urn 0 return 0；感谢你的观看2019年8月23平衡二叉树又称平衡二叉树又称AVLAVL树，其性质是：树，其性质是：(1)(1)、或者是一棵空树，或者是满足下列性、或者是一棵空树，或者是满足下列性质的二叉树；质的二叉树；(2)(2)、树的左子树和右子树的深度之差的绝、树的左子树和右子树的深度之差的绝对值不大于对值不大于1 1且左右子树也需满足上述性质。且左右子树也需满足上述性质。*8.3.2 8.3.2 平衡二叉树平衡二叉树感谢你的观看2019年8月23 如图如图8.98.9所示，结点左边的数字为该结点所示，结点左边的数字为该结点的平衡因子，图的平衡因子，图(a)(a)为非平衡二叉
31、树，图为非平衡二叉树，图(b)(b)为平衡二叉树。为平衡二叉树。060852080897751-221-102550(a)不平衡二叉树8520808960775101-11100(b)平衡二叉树图8.9平衡二叉树与非平衡二叉树感谢你的观看2019年8月23 动态平衡技术的基本思想：在构造二叉排动态平衡技术的基本思想：在构造二叉排序树的过程中，每当插入一个结点时，首序树的过程中，每当插入一个结点时，首先检查插入之后是否破坏了树的平衡性，先检查插入之后是否破坏了树的平衡性，若是则找出其中离插入结点最近的不平衡若是则找出其中离插入结点最近的不平衡子树，在保持二叉排序树特性的前提下，子树，在保持二叉排
32、序树特性的前提下，调整不平衡子树中各结点之间的关系，以调整不平衡子树中各结点之间的关系，以达到新的平衡。设离插入结点最近的不平达到新的平衡。设离插入结点最近的不平衡子树的根结点为衡子树的根结点为r r，则对该子树进行的平，则对该子树进行的平衡化调整，归纳起来有以下四种情况：衡化调整，归纳起来有以下四种情况：感谢你的观看2019年8月231.RR1.RR型调整型调整(逆时针逆时针)(a)插入前的平衡子树0-1rLhhRaMh(b)插入后未调整的子树-1-2rLhaMhh+1Re(c)调整后的平衡子树00aMrLh+1eRh+1图8.10RR型平衡处理过程感谢你的观看2019年8月232.LL2.
33、LL型调整型调整(顺时针顺时针)hRrMaLhh01(a)插入前的平衡子树h+1h+1LaRrMe00(c)调整后的平衡子树(b)插入后未调整的子树hRr21eh+1MaLh图8.11LL型平衡处理过程感谢你的观看2019年8月233.LR3.LR型调整型调整(先逆后顺先逆后顺)hLah-1NdMh-1hRr001(a)插入前的平衡子树hLah-1NdMh-1hRre12-1(b)插入后未调整的子树2h-1NdhRrLhaMeh02(c)先左旋处理h-1NhRrdLhaMeh00-1(d)后右旋处理图8.12LR型平衡处理过程感谢你的观看2019年8月234 4RLRL型调整型调整(先顺后逆先
34、顺后逆)(c)先右旋处理-2hLrd-1-1hRah-1NMeh0d0-1hRah-1NhLrMeh(d)后左旋处理图8.13RL型平衡处理过程感谢你的观看2019年8月231.B1.B树的定义树的定义一棵一棵m m阶的阶的B B树满足下列条件：树满足下列条件：(1)(1)树中每个结点至多有树中每个结点至多有m m棵子树；棵子树；(2)(2)除根结点和叶子结点外，其他每个结点至少除根结点和叶子结点外，其他每个结点至少有有m m/2/2 棵子树；棵子树；(3)(3)根结点至少有两个子树根结点至少有两个子树(B(B树只有一个结点树只有一个结点除外除外)；(4)(4)所有的叶子结点都在同一层，且叶结
35、点不包所有的叶子结点都在同一层，且叶结点不包含任何信息；含任何信息；*8-3-3 B_8-3-3 B_树和树和B+B+树树感谢你的观看2019年8月23(5)(5)有有j j个孩子的非叶子结点恰好有个关键字，个孩子的非叶子结点恰好有个关键字，该结点包含的信息为该结点包含的信息为P0,K1,P1,K2,P2,P0,K1,P1,K2,P2,P,Pj j-1,K-1,Kj j-1,P-1,Pj j-1-1其中，其中，K Ki i为关键字，且满足为关键字，且满足K Ki iKKi i+1+1；P Pi i为指为指向子树根结点的指针，且向子树根结点的指针，且P Pi i-1-1所指子树中所有所指子树中所
36、有结点的关键字都小于结点的关键字都小于K Ki i，P Pi i所指子树中所有结所指子树中所有结点的关键字都大于点的关键字都大于K Ki i。感谢你的观看2019年8月23例如，下图为一个例如，下图为一个6 6阶的阶的B B树。树。感谢你的观看2019年8月23vB B树的查找树的查找在在B B树上的查找给定的关键字树上的查找给定的关键字KeyKey的方法是：的方法是：首先根据给定的首先根据给定的B B树的指针取出根结点，树的指针取出根结点，在根结点所包含的关键字中按顺序或二分法在根结点所包含的关键字中按顺序或二分法查找给定的关键字，若查找给定的关键字，若K Ki i=Key=Key，则查找成
37、功；，则查找成功；否则一定可以找到否则一定可以找到K Ki i-1-1和和K Ki i，使得，使得K Ki i-1KeyK1KeyKi i，取指针，取指针P Pi i所指的结点继续查找，所指的结点继续查找，重复上述过程，直到找到或指针重复上述过程，直到找到或指针P Pi i为空，查为空，查找失败。整个查找过程中访问外存的次数不找失败。整个查找过程中访问外存的次数不超过超过B B树的深度。树的深度。感谢你的观看2019年8月23vB+B+树的定义树的定义B+B+树是树是B B树的一个变形树，它和树的一个变形树，它和B B树的区树的区别在于：别在于：(1)(1)有有n n棵子树的结点中包含有棵子树
38、的结点中包含有n n个关键字；个关键字；(2)(2)所有的叶子结点中包含了全部关键字的所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，信息，以及指向含这些关键字记录的指针，且叶子结点按关键字大小顺序链接。且叶子结点按关键字大小顺序链接。(3)(3)所有分支结点可看成是索引部分，结点所有分支结点可看成是索引部分，结点中仅包含其子树中最大中仅包含其子树中最大(或最小或最小)关键字。关键字。感谢你的观看2019年8月23如下图所示为一棵如下图所示为一棵3 3阶的阶的B+B+树。为便于查树。为便于查找提供了两个头指针找提供了两个头指针(root(root和和headhead指针
39、指针)。感谢你的观看2019年8月23*8-3-4 8-3-4 键树键树 键树又称为数字查找树（键树又称为数字查找树（Digital Search Digital Search TreeTree）或）或TrieTrie树树(trie(trie为为retrieveretrieve中间中间4 4个个字符字符)。它是一棵度。它是一棵度22的树，树中的每个的树，树中的每个结点中不是包含一个或几个关键字，而是结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。只含有组成关键字的符号。感谢你的观看2019年8月23 例如：例如：JANJAN，FEBFEB，MARMAR，APRAPR，MAYMAY，
40、JUNJUN，JULJUL，AGUAGU，SEPSEP，OCTOCT，NOVNOV，DECDEC可用图可用图8.168.16所示的键树表示。所示的键树表示。图8.16 关键字符集的一棵键树感谢你的观看2019年8月23 键树的查找过程为：从根结点出发，沿和键树的查找过程为：从根结点出发，沿和给定值相应的指针逐层向下，直到叶子结给定值相应的指针逐层向下，直到叶子结点；若叶子结点中的关键字和给定值相等，点；若叶子结点中的关键字和给定值相等，则查找成功；若分支结点中与给定值相应则查找成功；若分支结点中与给定值相应的指针为空，或叶子结点中的关键字和给的指针为空，或叶子结点中的关键字和给定值不相等，则查
41、找失败。定值不相等，则查找失败。感谢你的观看2019年8月23哈希表查找基本思想：哈希表查找基本思想：根据结点的键值从而确定结点的存储位置。即以待查的结点关键字K为自变量，通过一个确定的函数H，计算出对应的函数值H(K)，并以这个函数值作为该结点的存储地址，将结点存入H(K)所指的存储位置上。查找时再根据要查找的关键字K为自变量，用同样的函数计算地址，然后到相应的单元里去取要查找的结点。上述的函数H称为哈希函数，H(K)称为哈希地址。8-4-18-4-1哈希表哈希表感谢你的观看2019年8月231.1.数字分析法数字分析法当关键字的位数比哈希表的地址码位数多时，当关键字的位数比哈希表的地址码位
42、数多时，对关键字的各位数字进行分析，丢掉数字分布对关键字的各位数字进行分析，丢掉数字分布不均匀的位，取分布均匀的位作为地址。不均匀的位，取分布均匀的位作为地址。8.4.28.4.2哈希函数的构造方法哈希函数的构造方法 感谢你的观看2019年8月23 例如，有例如，有8080个结点，个结点，其关键字为其关键字为8 8位十进制位十进制数。若哈希表的表长数。若哈希表的表长为为100100，则可取两位十，则可取两位十进制数组成哈希地址，进制数组成哈希地址，地址编号为地址编号为099099。设。设这这8080个关键字中的一个关键字中的一部分如图部分如图8.178.17所示。所示。924566399236
43、7668923267989241688992314456924765299238774992433818图8.17 数字分析法求哈希地址感谢你的观看2019年8月232.2.平方取中法平方取中法该方法是先计算出关键字该方法是先计算出关键字K K的平方值的平方值K2K2，然后，然后再取再取K2K2值的中间几位或几位的组合作为哈希地值的中间几位或几位的组合作为哈希地址，取的位数由哈希表的表长决定。址，取的位数由哈希表的表长决定。例如，关键字为例如，关键字为36323632，则，则36322=1319142436322=13191424。若表长为若表长为10001000，则可以取第四位到第六位为哈，
44、则可以取第四位到第六位为哈希地址，即希地址，即H(3632)=914H(3632)=914。感谢你的观看2019年8月233.3.折叠法折叠法将关键字分割成位数将关键字分割成位数相同的几部分相同的几部分(最后一最后一部分的位数可以不同部分的位数可以不同)，然后取这几部分的叠然后取这几部分的叠加和加和(舍去进位舍去进位)作为作为哈希地址，这方法称哈希地址，这方法称为折叠法。例如，为折叠法。例如，key=978 750 835 150key=978 750 835 150，哈希表的长度为哈希表的长度为10001000，则应把关键字分成则应把关键字分成3 3位位一段，分别进行移位一段，分别进行移位叠
45、加和折叠叠加，求叠加和折叠叠加，求得哈希地址为得哈希地址为713713和和921921，如图，如图8-188-18所示。所示。978978750057835835+）150+）05127131921（a）(b)图8-18 由折叠法求哈希地址(a)移位叠加法(b)折叠叠加法感谢你的观看2019年8月234 4除余法除余法(亦称为除留余数法亦称为除留余数法)选择一个适当的正整数选择一个适当的正整数P P，用，用P P去除关键去除关键字，取其余数作为哈希地址，即字，取其余数作为哈希地址，即H(key)=key%P+bH(key)=key%P+b (b (b为常数为常数)感谢你的观看2019年8月23
46、5 5伪随机数法伪随机数法采用一个伪随机函数作哈希函数，即采用一个伪随机函数作哈希函数，即H(key)=random(keyH(key)=random(key)。在实际应用中，应根据具体情况选用不同在实际应用中，应根据具体情况选用不同的方法。通常考虑以下因素：的方法。通常考虑以下因素：（1 1）计算哈希函数所需要的时间。）计算哈希函数所需要的时间。（2 2）关键字的长度。）关键字的长度。（3 3）哈希表的大小。）哈希表的大小。（4 4）关键字的分布情况。）关键字的分布情况。（5 5）查找结点的频率。）查找结点的频率。感谢你的观看2019年8月231.1.开放地址法开放地址法 基本思想是：当哈希
47、地址基本思想是：当哈希地址I=H(keyI=H(key)出现出现冲突时，以冲突时，以I I为基础，产生另一个哈希地为基础，产生另一个哈希地址址I1I1；若；若P1P1仍然冲突，再以仍然冲突，再以I1I1为基础，为基础，产生下一个哈希地址产生下一个哈希地址I2I2，直到找出，直到找出一个不冲突的哈希地址为止。这种方法一个不冲突的哈希地址为止。这种方法的一般哈希函数的形式为：的一般哈希函数的形式为：Hi+1=(Hi(key)+diHi+1=(Hi(key)+di)MOD m )MOD m i=1,2,i=1,2,k(km-1),k(km-1)8.4.38.4.3处理冲突的方法处理冲突的方法感谢你的
48、观看2019年8月23其中，其中，H(keyH(key)为哈希函数；为哈希函数；m m为哈希表表长；为哈希表表长；didi为增量序列，通常有三种取法：为增量序列，通常有三种取法：（1 1）didi=1=1，2 2，3 3，m-1m-1，称为线性探测，称为线性探测再散列；再散列；（2 2）didi=12=12，-12-12，2222，-22-22，k2,-k2,-k2(km/2)k2(km/2)，称为二次探测再散列；，称为二次探测再散列；（3 3）didi=伪随机数序列，称为伪随机探测再伪随机数序列，称为伪随机探测再散列。散列。感谢你的观看2019年8月232 2再哈希法再哈希法这种方法是构造多
49、个哈希函数：这种方法是构造多个哈希函数：Hi=RHi(keyHi=RHi(key)i=1)i=1，2 2，k k（式（式8.128.12）当哈希地址当哈希地址H1=RH1(key)H1=RH1(key)发生冲突时，发生冲突时，再计算再计算H2=RH2(key)H2=RH2(key)，直到没有冲，直到没有冲突发生。这种方法不容易产生聚集，但突发生。这种方法不容易产生聚集，但增加了计算时间。增加了计算时间。感谢你的观看2019年8月233 3链地址法链地址法这种方法的基本思想是将所有关键字为同义这种方法的基本思想是将所有关键字为同义词的结点存储在同一个线性链表中，形成词的结点存储在同一个线性链表中
50、，形成一同义词链。一同义词链。感谢你的观看2019年8月23例例8.4 8.4 已知一组关键字为（已知一组关键字为（2121，4040，3737，6767，8686，4545，4343，8484，7676，5454），若哈希表表长为），若哈希表表长为1111，取哈，取哈希函数希函数H(keyH(key)=key MOD 11)=key MOD 11，则用链地址法法处理冲，则用链地址法法处理冲突的结果如图突的结果如图8.218.21所示。所示。图8.21 链地址法处理冲突的哈希表感谢你的观看2019年8月234 4建立公共溢出区建立公共溢出区 这也是处理冲突的一种常用方法。基本思想这也是处理冲突
