1、第八章 查找 8.1 基本概念与术语基本概念与术语 8.2 静态查找表静态查找表 8.3 动态查找表动态查找表 8.4 哈希表查找哈希表查找 8.5 小结与习题小结与习题1第八章 查找本章主要内容本章主要内容n本章主要学习本章主要学习静态查找静态查找和和动态查找动态查找方法。静态查方法。静态查找包括顺序查找、二分查找和分块索引查找等，找包括顺序查找、二分查找和分块索引查找等，动态查找包括二叉排序树、动态查找包括二叉排序树、B树等。作为重点内树等。作为重点内容本章还介绍了哈希查找及相关知识。容本章还介绍了哈希查找及相关知识。n查找是数据结构中的重要操作，好的查找方法会查找是数据结构中的重要操作，
2、好的查找方法会大大提高执行效率。通过本章学习，应掌握以下大大提高执行效率。通过本章学习，应掌握以下内容：内容：n查找的有关概念查找的有关概念；n静态查找；静态查找；n动态查找动态查找；哈希查找。哈希查找。2第八章 查找查找查找就是指在给定的一组数据中对某个数值进行就是指在给定的一组数据中对某个数值进行查询的过程。查询的过程。关键字关键字是数据元素（或记录）中某个项或组合项是数据元素（或记录）中某个项或组合项的数值，它可以标识一个数据元素或记录。的数值，它可以标识一个数据元素或记录。主关键字主关键字将能唯一确定一个数据元素（或记录）将能唯一确定一个数据元素（或记录）的的关键字关键字。查找表查找表
3、是由具有相同类型的数据元素（或记录）是由具有相同类型的数据元素（或记录）组成的集合。分为静态查找表和动态查找表两大类。组成的集合。分为静态查找表和动态查找表两大类。如果查找表中能够找到满足条件的记录，称为如果查找表中能够找到满足条件的记录，称为查查找成功找成功，否则称为，否则称为查找不成功查找不成功。8.1 8.1 基本概念与术语基本概念与术语3第八章 查找 静态查找表静态查找表：在对查找表进行操作时，不改变：在对查找表进行操作时，不改变表的结构，只进行查找操作；表的结构，只进行查找操作；动态查找表动态查找表：在对查找表进行操作时，可以改：在对查找表进行操作时，可以改变该查找表的结构，既可以进
4、行查找操作，又可以变该查找表的结构，既可以进行查找操作，又可以进行插入、删除等操作。进行插入、删除等操作。8.2 8.2 静态查找表静态查找表8.2.1 8.2.1 静态查找表结构静态查找表结构 静态查找表是由数据元素组成的线性表。其存静态查找表是由数据元素组成的线性表。其存储结构分为顺序存储和链式存储两种。可以用储结构分为顺序存储和链式存储两种。可以用顺序顺序表表或或线性链表线性链表来表示静态查找表。来表示静态查找表。4第八章 查找8.2.1 静态查找表结构typedefintKeyType;typedefstructKeyTypekey;ElemType;typedefstructElem
5、TypeelemMAXSIZE+1；intlength；SST；typedefstructNODEElemTypedata；/*结点的数据域结点的数据域*/structNODE*next；/*指针域指针域*/NodeType；静态查找表静态查找表的顺序存储的顺序存储结构定义结构定义静态查找表静态查找表的链式存储的链式存储结构定义结构定义5第八章 查找8.2.2 顺序查找顺序查找顺序查找又称线性查找，它思路简单、容易实又称线性查找，它思路简单、容易实现，是一种最基本的查找方法。现，是一种最基本的查找方法。其查找过程为：从查找表的一端开始，逐个进行关其查找过程为：从查找表的一端开始，逐个进行关键字
6、与查找值的比较，若某个记录的关键字值与给键字与查找值的比较，若某个记录的关键字值与给定值相等，则查找成功，给出数据元素在查找表中定值相等，则查找成功，给出数据元素在查找表中的位置；若将整个表查找完，仍未找到与给定值相的位置；若将整个表查找完，仍未找到与给定值相同的关键字，则查找失败，给出提示信息。同的关键字，则查找失败，给出提示信息。6第八章 查找【算法【算法8.1】顺序查找】顺序查找intSearch_Seq(SSTST，KeyTypex)ST.elem0.key=x;/*设置监护哨设置监护哨*/i=ST.length;while(ST.elemi.key!=x)i-;/*返回找到记录的下标
7、或者返回找到记录的下标或者0(查找不成功查找不成功)*/returni;/*Search_Seq*/将查找过程中给定值和关键字将查找过程中给定值和关键字比较的次数称为比较的次数称为查找长度查找长度。通常用。通常用平均查找长度平均查找长度ASL来衡量查找算法来衡量查找算法的优劣。的优劣。算法分析：算法分析：7第八章 查找 平均查找长度：平均查找长度：在查找成功时，平均查找长度在查找成功时，平均查找长度ASLASL是指为确定数据元素在表中位置所进行关键字比是指为确定数据元素在表中位置所进行关键字比较次数的期望值。对一个含较次数的期望值。对一个含n n个数据元素的表，查找个数据元素的表，查找成功时成
8、功时 ASL=Pi*Ci ni=1Pi为表中第为表中第i个数据元素的查找概率，个数据元素的查找概率，Ci为表中为表中第第i个数据元素的关键字与给定值个数据元素的关键字与给定值x相等时，需要比较相等时，需要比较的次数。的次数。设查找表长度为设查找表长度为n，查找元素查找元素x和表中第和表中第i个元素个元素关键字相等时，需要比较的次数为关键字相等时，需要比较的次数为n-i+1，则平均查则平均查找长度为：找长度为：ASL=Pi*（n-i+1）ni=18第八章 查找 设查找表中各元素的查找概率相等，即设查找表中各元素的查找概率相等，即Pi=1/n，则上面的式子表示为：则上面的式子表示为：ni=1ASL
9、=（n-i+1）=当查找成功时，顺序查找的时间复杂度就是当查找成功时，顺序查找的时间复杂度就是O(n)。当查找失败时，关键字与给定值的比较次数总是当查找失败时，关键字与给定值的比较次数总是n+1次。次。8.2.3二分查找二分查找 二分查找，也称为二分查找，也称为折半折半查找，是对查找，是对有序表有序表进行的进行的一种高效率的线性查找。有序表是指数据元素按给一种高效率的线性查找。有序表是指数据元素按给定的关键字已经是升序（或者是降序）的查找表。定的关键字已经是升序（或者是降序）的查找表。9第八章 查找 假设各记录的关键字是由小到大排序的，算法假设各记录的关键字是由小到大排序的，算法的实现过程为：
10、在待查找的有序表中，将的实现过程为：在待查找的有序表中，将中间中间元素元素首先与给定值进行比较，若相等，则表示查找成功；首先与给定值进行比较，若相等，则表示查找成功；若给定值若给定值小于小于中间元素的关键字，则在中间元素的关键字，则在左边左边的区域的区域中继续查找；若给定值中继续查找；若给定值大于大于中间元素的关键字，则中间元素的关键字，则在在右边右边的区域中继续查找。重复上述过程，直到查的区域中继续查找。重复上述过程，直到查找成功或者查找失败，查找的过程随之结束找成功或者查找失败，查找的过程随之结束。例在给定的序列例在给定的序列A=6，13，17，20，24，28，30，36，39，44，4
11、8，51，55中查找给定值中查找给定值13和和52这两个数据。这两个数据。查找关键字为查找关键字为13的过程的过程10第八章 查找 6131720242830363944485155第一次第一次 low=1 mid=7 high=13因因x30 x30，下一步继续在左半区查找，即：下一步继续在左半区查找，即：0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 7 8 9 10 11 12 13 8 9 10 11 12 13第二次第二次 low=1 mid=3 high=6因因x17x 6x 6，下 一 步 继 续 在 右 半 区 查 找。此 时，下 一 步 继 续 在 右 半 区 查
12、 找。此 时，low=2,high=2low=2,high=2,mid=(2+2)/2=2。由于由于x=13,查找成功，所查找成功，所找到的记录序号为找到的记录序号为2。查找关键字为查找关键字为5252的过程的过程第一次第一次 low=1 mid=7 high=13因因x30 x30，下一步继续在右半区查找，即：下一步继续在右半区查找，即：0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 7 8 9 10 11 12 13 8 9 10 11 12 13第二次第二次 low=8 mid=10 high=13 因因x44x44，下一步继续在右半区查找，即：下一步继续在右半区查找，即：0
13、 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1010 11 12 13 11 12 13 6131720242830363944485155 613172024283036394448515512第八章 查找第三次第三次low=11 high=13 mid=12因因x51x51，下一步继续在右半区查找，即：下一步继续在右半区查找，即：0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 1212 13 13 第四次第四次 low=mid=high=13因因x55xhigh，所以查找失败。所以查找失败。0 1 2
14、 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 6131720242830363944485155 613172024283036394448515513第八章 查找【算法【算法8.2】二分查找】二分查找intSearch_Bin(SSTST，KeyTypex)low=1；high=ST.length；while(low=high)/*区间条件判断区间条件判断*/*当区间下限不高于上限时，进行比较测试当区间下限不高于上限时，进行比较测试*/mid=(low+high)/2；/*取中点取中点*/if(xST.elemmid.k
15、ey)low=mid+1；/*查找区间缩小到右边区域查找区间缩小到右边区域*/elsereturnmid;returnERROR;14第八章 查找算法分析：算法分析：对于有序查找表，可采用建立二叉树的方法：将表对于有序查找表，可采用建立二叉树的方法：将表的的中间元素中间元素作为二叉树的作为二叉树的根结点根结点，比中间值，比中间值小小的所的所有结点全部在二叉树的有结点全部在二叉树的左子树左子树中，比中间值中，比中间值大大的所的所有结点全部在二叉树的有结点全部在二叉树的右子树右子树中。按照这种思路建中。按照这种思路建立的二叉树称为立的二叉树称为判定二叉树判定二叉树。如图所示。如图所示。513928
16、176445530244836132015第八章 查找时间复杂度：该算法的时间复杂度取决于该二叉树时间复杂度：该算法的时间复杂度取决于该二叉树中从根结点到该查找元素所在的结点的路径上与中中从根结点到该查找元素所在的结点的路径上与中间结点的比较次数，即该元素结点在树中的所在的间结点的比较次数，即该元素结点在树中的所在的层数。对于层数。对于n n个结点的判定树，树高为个结点的判定树，树高为h h，则有则有2 2h-1h-1-1 n 21 n 2h h-1-1，即即 h-1 l o gh-1 key)returnp;/*查找结束查找结束*/elseif(xkey)f=p;p=p-lchild;/*在
17、左子树上查找在左子树上查找*/elsef=p;p=p-rchild;/*在右子树上查找在右子树上查找*/returnNULL;29第八章 查找【算法【算法8.4】二叉排序树的建立】二叉排序树的建立BTNode*BST_Insert(BTNode*t,intx)/*在二叉排序树上执行插入操作在二叉排序树上执行插入操作*/BTNode*s,*p=BST_search(t,x);if(p=NULL)s=(BTNode*)malloc(sizeof(BTNode);s-key=x;s-lchild=s-rchild=NULL;if(t=NULL)t=s;elseif(xkey)f-lchild=s;/
18、*生成左孩子生成左孩子*/elsef-rchild=s;/*生成右孩子生成右孩子*/returnt;30第八章 查找8.3.38.3.3平衡二叉树（平衡二叉树（AVLAVL树）树）平衡二叉树平衡二叉树(BalancedBinaryTree)指的是指的是形态匀称的形态匀称的二叉树，其定义是一个递归过程：二叉树，其定义是一个递归过程：它或是一棵空树，或者是具有下列性质的二叉排序树：它或是一棵空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是平衡二叉树，且左子树和右它的左子树和右子树都是平衡二叉树，且左子树和右子树高度之差的绝对值不超过子树高度之差的绝对值不超过1 1。1498560775
19、4-220054854960770100031第八章 查找 对于非平衡二叉排序树，希望通过适当调整，使其对于非平衡二叉排序树，希望通过适当调整，使其成为平衡二叉树，设成为平衡二叉树，设A A结点为失去平衡的最小子树根结点为失去平衡的最小子树根结点，对该子树进行平衡化调整归纳起来有以下结点，对该子树进行平衡化调整归纳起来有以下四四种情况种情况：1.1.LLLL型平衡旋转型平衡旋转 当在当在A A的左子树上插入结点，使的左子树上插入结点，使A A的平衡因子由的平衡因子由1 1增至增至2 2而失去平衡，因此需要进行一次顺时针旋转操作。如而失去平衡，因此需要进行一次顺时针旋转操作。如图图8-9(8-9
20、(a)a)所示。所示。AB1插入前，平衡插入前，平衡AB2C插入结点，失去平衡插入结点，失去平衡AB0C顺时针旋转后，平衡顺时针旋转后，平衡32第八章 查找2.2.RRRR型平衡旋转型平衡旋转 由于在由于在A A的右子树上插入结点，使的右子树上插入结点，使A A的平衡因子由的平衡因子由-1-1增增至至-2-2而失去平衡，因此需要进行一次逆时针旋转操作。而失去平衡，因此需要进行一次逆时针旋转操作。如图所示。如图所示。AB-1插入前插入前平衡平衡AB-2C插入结点插入结点失去平衡失去平衡CB0A逆时针旋转后逆时针旋转后平衡平衡33第八章 查找3.3.LRLR型平衡旋转型平衡旋转由于在由于在A A的
21、左子树的右子树上插入结点，使的左子树的右子树上插入结点，使A A的平衡因的平衡因子由子由1 1增至增至2 2而失去平衡，因此需要进行两次旋转（先而失去平衡，因此需要进行两次旋转（先逆时针旋转，再顺时针旋转）操作。如图逆时针旋转，再顺时针旋转）操作。如图8-9(8-9(c)c)所示。所示。AB1插入前插入前平衡平衡AC0B顺时针旋转顺时针旋转使其平衡使其平衡AB2C插入结点插入结点失去平衡失去平衡AC2以以C为轴为轴逆时针旋转逆时针旋转B34第八章 查找4.4.RLRL型平衡旋转型平衡旋转由于在由于在A A的右子树的左子树上插入结点，使的右子树的左子树上插入结点，使A A的平衡的平衡因子由因子由
22、-1-1增至增至-2-2而失去平衡，因此需要进行两次旋而失去平衡，因此需要进行两次旋转（先顺时针旋转，再逆时针旋转）操作。如图转（先顺时针旋转，再逆时针旋转）操作。如图8-8-9(9(d)d)所示。所示。-1插入前插入前平衡平衡ABAB-2CBC0A插入结点插入结点失去平衡失去平衡逆时针旋转逆时针旋转使平衡使平衡AC-2以以C为轴为轴顺时针旋转顺时针旋转B35第八章 查找【例【例8-48-4】设有数据序列】设有数据序列6363，9090，7070，5555，6767，4242，9898，试用这组数建立平衡二叉排序树，如图，试用这组数建立平衡二叉排序树，如图8-108-10所示。所示。63639
23、0639070709063709063557090635567709063556742 (e)(f)(g)失去平衡36第八章 查找 (h)调整平衡 (i)结束67906355704267906355704298平衡二叉树的查找分析：平衡二叉树的查找分析：在查找过程中将给定值进行比较的关键字个数不在查找过程中将给定值进行比较的关键字个数不超过树的深度。因此，在平衡树上进行查找的时间复超过树的深度。因此，在平衡树上进行查找的时间复杂度为杂度为O(log2n)。(等概率的提前下进行的等概率的提前下进行的)37第八章 查找8.3.4 8.3.4 B B树树如果查找需要在外存储器上进行，需要使用外部查如
24、果查找需要在外存储器上进行，需要使用外部查找方法。找方法。1.B树的定义树的定义一棵一棵m阶的阶的B树，或者为空树，或为满足下列特性树，或者为空树，或为满足下列特性的的m叉树：叉树：树中每个结点至多有树中每个结点至多有m棵子树；棵子树；除非根结点为叶子结点，否则至少有两棵子树；除非根结点为叶子结点，否则至少有两棵子树；除根结点之外的所有非终端结点至少有除根结点之外的所有非终端结点至少有 m/2 棵棵子树；子树；所有的非终端结点中包含以下信息数据：所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，Kn，An）38第八章 查找 其中：其中：K Ki i（i=1,2,ni=1,2,n
25、）为关键字，且为关键字，且K Ki i K Ki i+1+1，A Ai i为指向子为指向子树根结点的指针树根结点的指针(i=0,1,n)i=0,1,n)，且指针且指针A Ai-1i-1所指子树中所有结所指子树中所有结点的关键字均小于点的关键字均小于K Ki i(i=1,2,n)(i=1,2,n)，A An n所指子树中所所指子树中所有结点有结点的关键字均大于的关键字均大于K Kn n，m/2m/2 1nm 1nm 1 1，n n为为关键字的个关键字的个数。数。所有的叶子结点都出现在同一层次上，并且不带信息。所有的叶子结点都出现在同一层次上，并且不带信息。1L2DG3OSW3ABC2EF 2HK
26、2 MN 3PQR 3TUV 3XYZ图图8-11一棵一棵5阶的阶的B-树树39第八章 查找2 2B B树基本操作树基本操作 B B树的基本操作也是查找、插入和删除等操作。树的基本操作也是查找、插入和删除等操作。现以现以B B树查找为例做简单介绍。树查找为例做简单介绍。B B树的查找类似二叉树的查找类似二叉排序树的查找，所不同的是排序树的查找，所不同的是B B树每个结点上是多关键树每个结点上是多关键字的有序表，在到达某个结点时，先在有序表中查字的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否则，按照对应的指针找，若找到，则查找成功；否则，按照对应的指针信息指向的子树中去查找
27、，当到达叶子结点时，则信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键字，查找失败。说明树中没有对应的关键字，查找失败。可见，可见，B B树上进行查找的过程是一个顺指针查找结树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程。点和在结点的关键字中进行查找交叉进行的过程。40第八章 查找8.4 8.4 哈希表查找哈希表查找8.4.1 8.4.1 哈希表与哈希方法哈希表与哈希方法前面介绍的查找算法基本上都是建立在前面介绍的查找算法基本上都是建立在“比较比较”的基的基础上。而数据元素的存储位置与关键字之间不存在确础上。而数据元素的存储位置与关键字之间不存
28、在确定的关系，查找效率由每次比较缩小的查找范围决定。定的关系，查找效率由每次比较缩小的查找范围决定。哈希表哈希表（Hash）是由哈希函数生成的表示是由哈希函数生成的表示关键字与关键字与存储位置之间关系的表存储位置之间关系的表。哈希函数是一个。哈希函数是一个以关键字以关键字值为自变量值为自变量，在，在关键字值与记录存储位置之间建立关键字值与记录存储位置之间建立确定关系的函数确定关系的函数。哈希函数的值，就是指定关键字。哈希函数的值，就是指定关键字对应的存储地址。对应的存储地址。41第八章 查找【例【例8-5】设有设有11个记录的关键字，其值分别为个记录的关键字，其值分别为6，37，12，21，6
29、9，31，16，33，41，13，51。选取关键字与记录位置间。选取关键字与记录位置间的函数为的函数为Hash(key)=key%11建立的哈希查找表如下：建立的哈希查找表如下：331213693716651413121对于对于n个数据元素的集合，总能找到关键字与存放地址一一个数据元素的集合，总能找到关键字与存放地址一一对应的函数。但当对应的函数。但当key1key2，而而Hash(key1)=Hash(key2)时，时，即将不同的关键字映射到同一个哈希地址上，这种现象称为即将不同的关键字映射到同一个哈希地址上，这种现象称为冲冲突突，映射到同一哈希地址上的关键字称为，映射到同一哈希地址上的关键
30、字称为同义词同义词。可以说，冲。可以说，冲突是不可能避免的，只能尽可能减少。因此选取适当的哈希函突是不可能避免的，只能尽可能减少。因此选取适当的哈希函数很关键。数很关键。42第八章 查找8.4.2常用的哈希函数常用的哈希函数1.1.直接定址法直接定址法 Hash(key)=a*key+b (a、b为常数为常数)直接地址法取关键字的某个线性函数值为哈希地址。直接地址法取关键字的某个线性函数值为哈希地址。【例【例8-6】解放后，某农作物年产量解放后，某农作物年产量(单位：吨单位：吨)序列为下表：序列为下表：1950年年1951年年1952年年1953年年1954年年1955年年160万万240万万
31、360万万540万万810万万1006万万若选取哈希函数：若选取哈希函数：Hash(key)=key-1950，其中其中key取取“年份年份”，则建立的哈希查找表如下：，则建立的哈希查找表如下：012345195019511952195319541955160240360540810100643第八章 查找2.除留余数法除留余数法Hash(key)=key%p(p是一个整数是一个整数)即取关键字除以即取关键字除以p的余数作为哈希地址。使用除留余数的余数作为哈希地址。使用除留余数法，选取合适的法，选取合适的p很重要，若哈希表表长为很重要，若哈希表表长为m，一般选一般选取取pm的质数。的质数。【例
32、【例8-7】关键字集合为关键字集合为34，21，78，52，16，46，33，构造哈希函数。，构造哈希函数。选取哈希函数为选取哈希函数为Hash(key)=key%7，则存放如下：则存放如下：21781652463334012345644第八章 查找3.数字分析法数字分析法设关键字集合中，每个关键字均由设关键字集合中，每个关键字均由m位组成，每位上可能位组成，每位上可能有有r种不同的符号。种不同的符号。数字分析法根据数字分析法根据r种不同的符号，在各位上的分布情况，选种不同的符号，在各位上的分布情况，选取某几位，组合成哈希地址。所选的位应取某几位，组合成哈希地址。所选的位应使使各种符号在该位上
33、各种符号在该位上出现的频率大致相同。出现的频率大致相同。【例【例8-8】有一组关键字如下：有一组关键字如下：27403642761487275249627554702757305分析：第分析：第1、2位均是位均是“2和和7”，第，第3位也只有位也只有“4、5、6”，因此，这几位，因此，这几位不能用，余下四位分布不能用，余下四位分布较均匀，可作为哈希地较均匀，可作为哈希地址选用。址选用。45第八章 查找4.平方取中法平方取中法对关键字平方后，按哈希表大小，取中间的若干位对关键字平方后，按哈希表大小，取中间的若干位作为哈希地址。作为哈希地址。【例【例8-9】设有如下关键字序列】设有如下关键字序列0
34、100，0110，1010，1001，0111，采用平方取中法建立哈希表。，采用平方取中法建立哈希表。关键字关键字平方平方取值取值0100001000010001100012100121101010201002011001100200102001110012321123则该关键字序列对应的地址值分别为则该关键字序列对应的地址值分别为100，121，201，020，123。46第八章 查找8.4.3处理冲突的方法处理冲突的方法1.开放定址法：当由关键字得到的哈希地址发生了冲突，即开放定址法：当由关键字得到的哈希地址发生了冲突，即该地址已经存放了某数据元素时，就该地址已经存放了某数据元素时，就自动
35、寻找下一个空的内自动寻找下一个空的内存地址存地址，只要哈希表足够大，总能找到一个位置，将数据元，只要哈希表足够大，总能找到一个位置，将数据元素存入。素存入。(1)线性探测法线性探测法Hi=(Hash(key)+di)%m(1im)其中：其中：Hash(key)为哈希函数，为哈希函数，m为哈希表长度，为哈希表长度，di为增量序列为增量序列1，2，m-1，且且di=i【例【例8-11】关键字集为】关键字集为47，7，29，11，16，92，22，8，3，哈希表表长为哈希表表长为11，Hash(key)=key%11，用线性探测法处理冲突，如下所示：用线性探测法处理冲突，如下所示：012345678
36、91011224792163729847第八章 查找存储元素存储元素47、7后，再存储后，再存储29时，时，Hash(29)=7，哈希地址哈希地址上冲突，由上冲突，由H1=(Hash(29)+1)%11=8，哈希地址哈希地址8为空，将为空，将29存入；存入；线性探测法可能使第线性探测法可能使第i个哈希地址的同义词存入第个哈希地址的同义词存入第i+1个哈希个哈希地址，这样本应存入第地址，这样本应存入第i+1个哈希地址的元素变成了第个哈希地址的元素变成了第i+2个哈个哈希地址的同义词，希地址的同义词，因此，可能出现很多元素在相邻的，因此，可能出现很多元素在相邻的哈希地址上哈希地址上“堆积堆积”起来
37、，大大降低了查找效率。起来，大大降低了查找效率。可采用可采用二次探测法二次探测法，或双哈希函数探测法，以改善，或双哈希函数探测法，以改善“堆堆积积”问题。问题。01234567891011224792163729848第八章 查找(2)二次探测法二次探测法Hi=(Hash(key)di)modm其中：其中：Hash(key)为哈希函数，为哈希函数，m为哈希表长度，通常取为哈希表长度，通常取m为为4k+3的质数，的质数，di为增量序列为增量序列12，-12，22，-22，q2，-q2且且q(m-1)/2 当对例当对例8-11使用二次探测法处理冲突时，如果已经将前使用二次探测法处理冲突时，如果已经
38、将前8个数都存入相应的位置，其结果如下所示：个数都存入相应的位置，其结果如下所示：0 1 2 3 4 5 6 7 8 9 10112234792167298 当存入最后一个元素当存入最后一个元素3时，时，Hash(3)=3，哈希地址上冲突，哈希地址上冲突，由由H1=(Hash(3)+12)mod 11=4，仍然冲突；仍然冲突；H2=(Hash(3)-12)mod 11=2找到空的哈希地址，将元素找到空的哈希地址，将元素3存入该位置。存入该位置。49第八章 查找(3)(3)双哈希函数探测法双哈希函数探测法 H Hi i=(Hash(key)+i=(Hash(key)+i*ReHashReHash
39、(key)%m(key)%m(i=1,2,(i=1,2,，m-1)m-1)其中：其中：Hash(key)，ReHash(key)是两个哈希函数，是两个哈希函数，m为哈希表长度，其方法是：先用第一个函数为哈希表长度，其方法是：先用第一个函数Hash(key)对关键字计算哈希地址，一旦产生地址冲对关键字计算哈希地址，一旦产生地址冲突，再用第二个函数突，再用第二个函数ReHash(key)确定移动的步长因确定移动的步长因子，最后，通过步长因子序列由探测函数寻找空哈希子，最后，通过步长因子序列由探测函数寻找空哈希地址地址。如，如，Hash(key)=a时 产 生 地 址 冲 突，就 计 算时 产 生
40、地 址 冲 突，就 计 算ReHash(key)=b，则探测的地址序列为则探测的地址序列为H1=(a+b)%m，H2=(a+2b)%m，Hm-1=(a+(m-1)b)%m50第八章 查找2.拉链法拉链法设哈希函数得到的哈希地址域在区间设哈希函数得到的哈希地址域在区间0，m-1上，以每个哈希地址作为一个指针，指向一个链，上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组即分配指针数组ElemType*eptrm，建立建立m个空链个空链表，由哈希函数对关键字转换后，映射到同一哈希表，由哈希函数对关键字转换后，映射到同一哈希地址。地址。i的同义词均加入到的同义词均加入到*eptri指向的链表
41、中。指向的链表中。【例【例8-12】关键字序列为关键字序列为47,7,29,11,16,92,22,8,3,50,37,89,21，哈希函数为哈希函数为Hash(key)=keymod11用拉链法处理冲突，如图用拉链法处理冲突，如图8-13所示。所示。51第八章 查找01234567891022389114737921650297821拉链法处理拉链法处理冲突时的哈冲突时的哈希表希表47,7,29,11,16,92,22,8,3,50,37,89,21Hash(key)=key mod 1152第八章 查找哈希表的查找过程基本上和表的生成过程相同。哈希表的查找过程基本上和表的生成过程相同。首先
42、一些关键字可通过哈希函数转换的地址直接首先一些关键字可通过哈希函数转换的地址直接找到，如果某关键字在哈希函数得到的地址上产找到，如果某关键字在哈希函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。查生了冲突，需要按处理冲突的方法进行查找。查找过程中，关键字的比较次数，取决于产生冲突找过程中，关键字的比较次数，取决于产生冲突的次数，冲突次数越少，查找效率越高。因此，的次数，冲突次数越少，查找效率越高。因此，影响冲突次数的因素，也就是影响查找效率的因影响冲突次数的因素，也就是影响查找效率的因素。素。53第八章 查找小小 结结1.1.掌握掌握顺序表和有序表顺序表和有序表的查找方法。的查找方法。.熟练掌握熟练掌握二叉排序树的构造和查找二叉排序树的构造和查找方法。方法。.掌握二叉平衡树的维护平衡方法。掌握二叉平衡树的维护平衡方法。.理解理解B B树的特点以及建树过程。树的特点以及建树过程。.熟练掌握哈希表的构造方法熟练掌握哈希表的构造方法，深刻理解哈希表与，深刻理解哈希表与其它结其它结构构的表的实质性的差别。的表的实质性的差别。6.6.掌握描述查找过程的判定树的构造方法，以及按掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功定义计算各种查找方法在等概率情况下查找成功时的平均查找长度时的平均查找长度。54
