《数据结构及算法查找.ppt》由会员分享，可在线阅读，更多相关《数据结构及算法查找.ppt（96页珍藏版）》请在三一办公上搜索。
1、第 7 章 查找技术,本章的主要内容是:,查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术,1.查找的基本概念,查找：在具有相同类型的记录构成的集合中找出满足给定条件的记录。,7.1 概述,查找表：具有相同类型的记录构成的集合,1.查找的基本概念,关键码：可以标识一个记录的某个数据项。键值：关键码的值。主关键码：可以唯一地标识一个记录的关键码。次关键码：不能唯一地标识一个记录的关键码。,7.1 概述,1.查找的基本概念,7.1 概述,数据结构里的查找主要通过给定值和查找表中记录的关键码进行比较查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。,给
2、定值 k=0004,静态查找：不涉及插入和删除操作的查找。动态查找：涉及插入和删除操作的查找。,7.1 概述,1.查找的基本概念,静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。,7.1 概述,1.查找的基本概念,查找结构：面向查找操作的数据结构，即查找基于的数据结构。,集合中元素之间不存在明显的组织规律，不便查找。,查找技术的分类,7.2 线性表的查找技术,查找技术,线性表的查找技
3、术(静态),树表的查找技术(动态),散列表的查找技术,1.静态查找技术,静态查找特点:不涉及插入和删除操作的查找.主要采用线性查找结构.顺序查找折半查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,T r10,7.2 线性表的查找技术,1.1顺序查找,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，返回该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,7.2 线性表的查找技术,例：
4、查找k35 或 k=22,r10,顺序查找（线性查找）,7.2 线性表的查找技术,int SeqSearch1(int r,int n,int k)/数组r1 rn存放查找集合 i=n;while(i0,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,7.2 线性表的查找技术,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找k35,哨兵,35,
5、基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,7.2 线性表的查找技术,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找k25,25,int SeqSearch2(int r,int n,int k)/数组r1 rn存放查找集合 r0=k;i=n;while(ri!=k)i-;return i;,7.2 线性表的查找技术,改进的顺序查找,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：,其中
6、：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第i个记录所需的关键码的比较次数。,7.1 概述,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,7.2 线性表的查找技术,顺序查找的性能：,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：,查找算法时间性能通过关键码的比较次数来度量。,平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。,7.2 线性表的查找技术,顺序查找的缺点：,算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有要求，无论记录是否按
7、关键码有序均可。,顺序查找的优点：,1.2折半查找,使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,7.2 线性表的查找技术,折半查找的基本思想,7.2 线性表的查找技术,r1 rn,k,rmid-1 rmid rmid+1,比较,如果k rmid左半区继续查找,如果k rmid右半区继续查找,例：查找值为k=1
8、4的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3114,1814,714,14=14,7.2 线性表的查找技术,mid=(low+high)/2,mid=(low+high)/2;如果k等于rmid，则查找成功如果k小于rmid，则 high=mid-1;否则low=mid+1;,例：查找值为k=22的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3122,1822,2322,
9、2122,7.2 线性表的查找技术,lowhigh,mid=(low+high)/2,mid=(low+high)/2;如果k等于rmid，则查找成功如果k小于rmid，则 high=mid-1;否则low=mid+1;,int BinSearch1(int r,int n,int k)/数组r1 rn存放查找集合 low=1;high=n;while(lowrmid)low=mid+1;else return mid;/查找成功 return 0;/查找失败,7.2 线性表的查找技术,折半查找非递归算法,int BinSearch2(int r,int low,int high,int k)
10、/数组r1 rn存放查找集合 if(lowhigh)return 0;/递归终止 else mid=(low+high)/2;if(krmid)return BinSearch2(r,mid+1,high,k);/在右半查找 else return mid;/查找成功,7.2 线性表的查找技术,折半查找递归算法,折半查找判定树,判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。,7.2 线性表的查找技术,当n=0时，折半查找判定树为空；当n0时，折半查找判定树的根结点是有
11、序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树，根结点的右子树是与rmid+1 rn相对应的折半查找判定树。,7.2 线性表的查找技术,判定树的构造方法,7.2 线性表的查找技术,判定树的构造方法,根结点是序号为mid=(n+1)/2的记录根结点的左子树是r1 rmid-1的判定树根结点的右子树是rmid+1 rn的判定树,1-5,7-11,1-2,4-5,7 14 18 21 23 29 31 35 38 42 46,1 2 3 4 5 6 7 8 9 10 11,对n个结点的判定树,深度,查找成功:在表中查找任一记录的过程，即是从
12、判定树根结点到该记录结点的路径，比较次数等于该记录结点在树中的层数,7.2 线性表的查找技术,内部结点,外部结点,判定树的构造方法,1-5,7-11,1-2,4-5,7 14 18 21 23 29 31 35 38 42 46,1 2 3 4 5 6 7 8 9 10 11,查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行比较次数等于该路径上内部结点的个数,查找5,查找10,具有n个结点的折半查找判定树的深度为,7.2 线性表的查找技术,折半查找性能分析,问题规模是n，折半查找的平均查找长度(假设树高度是K):,第j层,结点数2j-1,每个结点比较j次,练习,查找技术的分类,
13、7.2 线性表的查找技术,查找技术,线性表的查找技术(静态),树表的查找技术(动态),散列表的查找技术,顺序查找和折半查找的缺陷？,2.树查找技术,树查找特点:查找结构是采用树结构，有序的树结构可根据一个无序的查找表动态生成，并且查找过程中可以对树结构进行插入和删除操作.二叉排序树平衡二叉树,7.3 树表的查找技术,2.1二叉排序树,二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：如果它的左子树不空，则左子树上所有结点的值均小于根结点的值；如果它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左、右子树也都是二叉排序树。,7.3 树表的查找技术,二叉排
14、序树 非二叉排序树,二叉排序树,7.3 树表的查找技术,中序遍历二叉排序树可以得到一个按关键码有序的序列,二叉排序树,主要操作:1)查找2)构造3)插入4)删除,7.3 树表的查找技术,注意:插入和删除后,仍然是一棵二叉排序树,无序序列：63,55,90,42,58,70,二叉排序树的存储结构,以二叉链表形式存储：,7.3 树表的查找技术,二叉排序树的存储结构,以二叉链表形式存储，类声明如下：,class BiSortTree public:BiSortTree(int a,int n);BiSortTree();void InsertBST(BiNode*root,BiNode*s);voi
15、d DeleteBST(BiNode*p,BiNode*f);BiNode*SearchBST(BiNode*root,int k);private:BiNode*root;,7.3 树表的查找技术,例：在二叉排序树中查找关键字值k为35，95的过程：,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,2.1.1二叉排序树的查找,50,30,20,80,90,85,88,40,35,32,root,root,BiNode*SearchBST(BiNode*root,int k),二叉排序树的查找,在二叉排序树中查找给定值k的过程是：,若root是空树，则查找失
16、败；若kroot-data，则查找成功；否则 若kroot-data，则在root的左子树上查找；否则 在root的右子树上查找。上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。,7.3 树表的查找技术,root,BiNode*SearchBST(BiNode*root,int k),BiNode*BiSortTree:SearchBST(BiNode*root,int k)if(root=NULL)return NULL；else if(root-data=k)return root;else if(kdata)return SearchBST(root-l
17、child,k);else return SearchBST(root-rchild,k);,7.3 树表的查找技术,二叉排序树的查找,1)若root是空树，则查找失败;2)若kroot-data,则查找成功;3)若kroot-data 则在root的左子树上查找;否则在root的右子树上查找。,2.1.2二叉排序树的插入,分析：新插入的结点必为一个新的叶子结点,其插入位置由查找过程得到。,7.3 树表的查找技术,void InsertBST(BiNode*,例：插入值为98的结点,63,55,90,58,70,root,root,若二叉排序树为空树，则新插入的结点为新的根结点;否则,如果新插
18、入结点值小于根结点值,则把结点插入到根结点的左子树,否则插入到根结点的右子树。,void BiSortTree:InsertBST(BiNode*,7.3 树表的查找技术,二叉排序树的插入算法,若二叉排序树为空树，则新插入的结点为新的根结点;否则,如果新插入结点值小于根结点值,则把结点插入到根结点的左子树,否则插入到根结点的右子树。,2.1.3二叉排序树的构造,从空的二叉排序树开始，依次给每个数据分配一个结点，插入该结点。,例：关键码集合为63，90，70，55，58，二叉排序树的构造过程为：,7.3 树表的查找技术,63,BiSortTree:BiSortTree(int r,int n)r
19、oot=NULL;for(i=0;i;s-data=ri;s-lchild=s-rchild=NULL;InsertBST(root,s);,7.3 树表的查找技术,二叉排序树的构造算法,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;每次插入的新结点都是二叉排序树上新的叶子结点;找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；新插入的结点没有破坏原有结点之间的关系。,小 结：,7.3 树表的查找技术,2.1.4二叉排序树的删除,在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。,分三种情况讨论：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点
20、既有左子树，也有右子树。,7.3 树表的查找技术,情况1被删除的结点p是叶子结点,7.3 树表的查找技术,操作：将双亲结点中相应指针域的值改为空。f-lchild=NULL,右子树,设待删除的结点为p,双亲结点为f,且p是f的左孩子,则被删除结点存在三种情况,f,p,情况2被删除的结点p只有左子树或者只有右子树,操作：将双亲结点的指针域指向被删除结点的左子树。f-lchild=p-lchild,7.3 树表的查找技术,设待删除的结点为p,双亲结点为f,且p是f的左孩子,则被删除结点存在三种情况,右子树,f,p,PL,情况2被删除的结点只有左子树或者只有右子树,操作：将双亲结点的指针域的值指向被
21、删除结点的右子树 f-lchild=p-rchild,7.3 树表的查找技术,设待删除的结点为p,双亲结点为f,且p是f的左孩子,则被删除结点存在三种情况,右子树,f,p,PR,情况3被删除的结点既有左子树也有右子树,操作：p由后继结点(右子树中的最小值)替代,然后再删除该后继结点或由前驱结点(左子树中的最大值)替代,然后再删除该前驱结点。,7.3 树表的查找技术,右子树,f,p,PL,设待删除的结点为p,双亲结点为f,且p是f的左孩子,则被删除结点存在三种情况,PR,情况3被删除的结点p既有左子树也有右子树,操作：p由后继结点s(右子树中的最小值)替代,然后再删除该后继结点.,7.3 树表的
22、查找技术,s的右子树接到结点par的左子树,s一定没有左子树,s:p结点的右子树的最左边结点。par:s结点的双亲结点。,情况3被删除的结点p既有左子树也有右子树,操作：其后继结点s(右子树中的最小值)替代,然后再删除该后继结点，,7.3 树表的查找技术,53,17,9,78,94,95,45,23,32,p,65,par,s的右子树接到par的右子树,s,特殊情况:p的右孩子没有左子树,1.若结点p是叶子，则直接删除结点p；2.若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3.若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s及s的
23、双亲结点par；3.2 将结点s数据域替换到被删结点p的数据域；3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4 删除结点s；,7.3 树表的查找技术,二叉排序树的删除算法伪代码,二叉排序树的查找性能分析,由序列4,2,3,1,5得到二叉排序树：,由序列1,2,3,4,5得到二叉排序树：,ASL=（1+2+3+4+5）/5=3,ASL=（1+2+3+3+2）/5=2.2,二叉排序树的查找性能取决于二叉排序树的形状，在O(log2n)和O(n)之间。,7.3 树表的查找技术,平衡二叉树：或者是一棵空的二叉排序树，或者是具有下
24、列性质的二叉排序树：根结点的左子树和右子树的深度最多相差1;根结点的左子树和右子树也都是平衡二叉树。,结点的平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。,2.2平衡二叉树(AVL树),7.3 树表的查找技术,7.3 散列表的查找技术,平衡二叉树,在平衡树中，结点的平衡因子可以是1，0，-1。,结点的平衡因子HL-HR,最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。,7.3 树表的查找技术,4,平衡二叉树,基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不
25、平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。,7.3 树表的查找技术,平衡二叉树的构造,1)在构造二叉排序树的过程中,每当插入一个新结点,从该结点开始向上计算各结点平衡因子,如果该结点的祖先结点平衡因子绝对值都不超过1,则继续插入结点2)若某祖先结点的平衡因子的绝对值大于1,则找出最小不平衡子树的根结点3)根据新插入结点和最小不平衡子树的根结点的关系,确定是哪种类型的调整,7.3 树表的查找技术,平衡二叉树,设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：1.LL型 2.RR型 3.LR型
26、 4.RL型,7.3 树表的查找技术,平衡二叉树,插入前 插入后，调整前 调整后,7.3 树表的查找技术,平衡二叉树LL型,旋转：右旋转；冲突：旋转优先,A的左子树根结点的左子树上插入结点,向右旋转一次,B作为根结点,让A转为B的右子树,B的右子树BR转为A的左子树,12,例:LL型,7.3 树表的查找技术,平衡二叉树RR型,7.3 树表的查找技术,插入前 插入后，调整前 调整后,旋转：左旋转；冲突：旋转优先,A右子树根结点的右子树上插入结点,向左旋转一次,B为根结点,让A旋转为B的左子树,B的左子树BL转为A的右子树,16,例:RR型,7.3 树表的查找技术,10,8,14,12,插入后，调
27、整前 先A的左子树做一次左旋转 再整个树做一次右旋转,7.3 树表的查找技术,平衡二叉树LR型,h,A的左子树根结点的右子树上插入结点,2,-1,9,例:LR型,7.3 树表的查找技术,10,7,8,12,6,插入后，调整前 先A的右子树做一次右旋转 再整棵树做一次左旋转,7.3 树表的查找技术,平衡二叉树RL型,A右子树根结点的左子树上插入结点,练习：设有关键码序列5,4,2,8,6,9，构造平衡二叉树,5,2,7.3 树表的查找技术,课堂练习：设有关键码序列5,4,2,8,6,9，构造平衡树,7.3 树表的查找技术,7.3 树表的查找技术,课堂练习：设有关键码序列5,4,2,8,6,9，构
28、造平衡树,查找技术的分类,7.2 线性表的查找技术,查找技术,线性表的查找技术(静态),树表的查找技术(动态),散列表的查找技术,第 7 章 查找技术,本章的主要内容是:,查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术,7.4 散列表的查找技术,二叉排序树查找,10 15 24 6 12 1,0 1 2 3 4 5 6,这些查找技术都是通过给定值与查找表里记录的关键码的比较,7.4 散列表的查找技术,顺序查找、折半查找、二叉排序树查找等。这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。,在存储位置和关键码之间建立一个确定的
29、对应关系,每年招收1000名新生,建立一张查找表，每个学生的关键字XX000-XX999（XX为年份），以下标为000-999的顺序表表示。,举例,7.4 散列表的查找技术,查找时,不通过比较，通过关键码直接确定存储位置.,记录的关键码和存储位置之间建立一个对应关系,1.概 述,散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。,7.4 散列表的查找技术,关键码集合,ki,ri,H(ki),H,散列函数,散列地址（下标）,关键码集合为14,21,28,35,42,49,56，分配数组A20选取的散列函数为 则散列表为：
30、,举例,H(key)=key mod 19,9,2,14,散列函数是一个压缩映象,压缩是否存在问题?,7.4 散列表的查找技术,冲突：对于两个不同关键码kikj，有H(ki)H(kj)，即两个不同的记录需要存放在同一个存储位置,ki和kj相对于H称做同义词。,1.概 述,关键码集合,ki,ri,H(ki),kj,H(kj),H(key)=key mod 19,7.4 散列表的查找技术,散列技术的关键问题：散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。冲突的处理。如何采取合适的处理冲突方法来解决冲突。,1.概 述,7.4 散列表的查找技术,2.1散列函数直接定址法,散列函数是关
31、键码的线性函数，即：,H(key)=a key+b（a，b为常数）,例：关键码集合为10,30,50,70,80,90，选取的散列函数为H(key)=key/10，则散列表为：,10,30,50,70,80,90,适用情况？,事先知道关键码，关键码集合不是很大且连续性较好。,7.4 散列表的查找技术,散列函数为：,H(key)=key mod p,2.2散列函数除留余数法,关键码集合为14,21,28,35,42,49,56，分配数组A20选取的散列函数为 则散列表为：,H(key)=key mod 19,7.4 散列表的查找技术,散列函数为：,H(key)=key mod p,2.2散列函数
32、除留余数法,如何选取合适的 p，产生较少同义词？,例：p 2137,7.4 散列表的查找技术,一般情况下，选p为不大于表长的质数或不包含小于20质因子的合数。,2.2散列函数除留余数法,除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。,适用情况？,7.4 散列表的查找技术,根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。,例：关键码为8位十进制数，散列地址为2位十进制数,8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3
33、3 8 9 6 7,2.3散列函数数字分析法,7.4 散列表的查找技术,对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。,2.4散列函数平方取中法,事先不知道关键码的分布且关键码的位数不是很大。,适用情况:,例：散列地址为2位，则关键码1234的散列地址为：,(1234)21522756,7.4 散列表的查找技术,将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。,2.5散列函数折叠法,例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。,2 5 3 4 6 3 5 8 7+0 5 1 3 0 8 移位叠加,2 5
34、3 3 6 4 5 8 7+5 0 1 2 5 4 间界叠加,适用情况:,关键码位数很多，事先不知道关键码的分布。,7.4 散列表的查找技术,散列技术的关键问题：散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。冲突的处理。如何采取合适的处理冲突方法来解决冲突。,概 述,7.4 散列表的查找技术,3.处理冲突的方法开放定址法,由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。Hi=(H(key)di)%m,如何寻找下一个空的散列地址?,（1）线性探测法（2）二次探测法（3）随机探测法,H(key)=key mod 19,7.4 散列表的查找技术,3.
35、1线性探测法,当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。,对于键值key，设H(key)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为：Hi=(H(key)di)%m（di=1，2，m-1）,用开放定址法处理冲突得到的散列表叫闭散列表。,7.4 散列表的查找技术,例：关键码集合为 47,7,29,11,16,92,22,8,3，散列表表长为11，散列函数为H(key)=key mod 11，用线性探测法处理冲突，则散列表为：,47,7,29,11,16,92,29,22,22,8,8,3,3,3,3,线性探测法,Hi=(H(key)di)%m（di=1，
36、2，m-1）,7.4 散列表的查找技术,散列表的查找算法,1.对于给定值k,计算散列地址j=H(k);2.若Aj.key=k，则查找成功，返回记录在散列表中的下标；否则3.若Aj为空，则查找失败；4.否则求下一地址Hi，直至AHi.key=空,查找不成功 或AHi.key=k，查找成功；,查找过程和造表过程一致,设采用线性探测法处理冲突,H(key)=key mod 11,47,7,11,16,92,29,22,8,3,7.4 散列表的查找技术,3.2二次探测法,当发生冲突时，寻找下一个散列地址的公式为：Hi=(H(key)di)%m（di=12，12，22，22，q2，q2且qm/2）,7.
37、4 散列表的查找技术,47,7,29,11,16,92,29,22,22,8,8,3,3,3,例：关键码集合为 47,7,29,11,16,92,22,8,3，散列表表长为11，散列函数为H(key)=key mod 11，用二次探测法处理冲突，则散列表为：,二次探测法,Hi=(H(key)di)%m（di=12，12，22，22，q2，q2且qm/2）,7.4 散列表的查找技术,3.3随机探测法,当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为：Hi=(H(key)+di)%m（di是一个随机数列，i=1，2，m-1）,7.4 散列表的查找技术,基本思想：将所
38、有散列地址相同的记录，即所有同义词的记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子表的头指针。,用拉链法处理冲突构造的散列表叫做开散列表。,设n个记录存储在长度为m的散列表中，则同义词子表的平均长度为n/m。,3.4处理冲突的方法拉链法（链地址法）,7.4 散列表的查找技术,例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造的开散列表为：,7.4 散列表的查找技术,基本思想：散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与基本表的相应单元进行比较，若相等，则查找成功；否则，再到溢出表中进行顺序查找。,处理冲突的方法公共溢出区,7.4 散列表的查找技术,例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为H(key)=key mod 11，用公共溢出区法处理冲突，构造的散列表为：,0 1 2 3 4 5 6 7 8 910,基本表 溢出表,0 1 2 3 4 5 6 7 8 910,7.4 散列表的查找技术,第 7 章 查找技术,本章的主要内容是:,查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术,
