数据结构第9章查找

《数据结构第9章查找》由会员分享，可在线阅读，更多相关《数据结构第9章查找（59页珍藏版）》请在金锄头文库上搜索。

1、第九章第九章第九章第九章 查找查找查找查找概概 述述 查查找找表表：由由同同一一类类型型数数据据元元素素构构成成的的集集合合。由由于于“集集合合”中中的的元元素素之之间间存存在在着着完完全全松松散散的的关关系系，因因此此查查找找表表是是一一种种非非常常灵灵便便的的数数据结构。据结构。 查查找找，也也称称为为检检索索。在在我我们们日日常常生生活活中中，如如查查找找某某人人的的地地址址、电电话话号号码码；查查某某单单位位4545岁岁以以上上职职工工等等，都都属属于于查查找找范范畴畴。我我们们规规定定查查找找是是按按关关键键字字进进行行的的，所所谓谓关关键键字字( (key)key)是是数数据据元元

2、素素( (或或记记录录) )中中某某个个数数据据项项的的值值，用用它它可可以以标标识识一一个个数数据据元元素素。例例如如，描描述述一一个个考考生生的的信信息息，可可以以包包含含：考考号号、姓姓名名、性性别别、年年龄龄、家家庭庭住住址址、电电话话号号码码、成成绩绩等等关关键键字字。但但有有些些关关键键字字不不能能唯唯一一标标识识一一个个数数据据元元素素，而而有有的的关关键键字字可可以以唯唯一一标标识识一一个个数数据据元元素素。如如考考生生信信息息中中，姓姓名名不不能能唯唯一一标标识识一一个个数数据据元元素素，而而考考号号可可以以唯唯一一标标识识一一个个数数据据元元素素( (每每个个考考生生考考号

3、号是是唯唯一一的的，不不能能相相同同) )。我我们们将将能能唯唯一一标标识识一一个个数数据据元元素素的的关关键键字字称称为为主主关关键键字字，而而其其它它关关键键字字称称为为辅辅助助关关键键字字或或从从关关键键字字。第九章第九章第九章第九章 查找查找查找查找 有了关键字及查找表后，我们可以给查找下一个完整的有了关键字及查找表后，我们可以给查找下一个完整的定义。所谓定义。所谓查找查找，就是根据给定的值，在一个表中查找出其，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，查找是成功的，此时查找

4、的信息为给定整个数据元素的输出此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置或指出该元素在表中的位置；若表中不存在这样的记录，则；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。称查找是不成功的，或称查找失败，并可给出相应的提示。 因因为为查查找找是是对对已已存存入入计计算算机机中中的的数数据据所所进进行行的的操操作作，所所以以采采用用何何种种查查找找方方法法，首首先先取取决决于于使使用用哪哪种种数数据据结结构构来来表表示示“表表”，即即表表中中结结点点是是按按何何种种方方式式组组织织的的。为为了了提提高高查查找找速速度度，我我们们经经常常使使用用

5、某某些些特特殊殊的的数数据据结结构构来来组组织织表表（人人为为地地加加上上一一些些关关系系以以便便按按某某种种规规则则进进行行查查找找）。因因此此在在研研究究各各种种查查找找算算法法时时，我我们们首首先先必必须须弄弄清清这这些些算算法法所所要要求求的的数数据据结结构构，特别是存储结构。特别是存储结构。 第九章第九章第九章第九章 查找查找查找查找 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，

6、对于一个含有衡量一个查找算法好坏的标准，对于一个含有n n个元素的表，查找个元素的表，查找成功时的平均查找长度可表示为成功时的平均查找长度可表示为ASL= ASL= ，其中其中i i为查找第为查找第i i个元素的概率，且个元素的概率，且 =1=1。一般情形下我们认为查找每个元素。一般情形下我们认为查找每个元素的概率相等，的概率相等，c ci i为查找第为查找第i i个元素所用到的比较次数。个元素所用到的比较次数。第九章第九章第九章第九章 查找查找查找查找9.1 静态查找表静态查找表一、一、 顺序查找顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给查找过程：从表的一端开始逐个进行记录的关

7、键字和给定值的比较定值的比较.i例 1 2 3 4 5 6 7 8 9 10 1113 5 90 21 37 88 64 75 19 56 75找64监视哨令r0.key:=Kiiii比较次数=5比较次数：比较次数：查找第查找第n个元素：个元素： 1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素： n查找第查找第i个元素：个元素： n+1-i查找失败查找失败： n+164第九章第九章第九章第九章 查找查找查找查找算法分析算法分析1. 1. 1. 1. 查找过程查找过程查找过程查找过程: 从从从从n n n n开始开始开始开始, , , ,依次与依次与依次与依次与k k k

8、k进行比较进行比较进行比较进行比较, , , , 若相等则查找成功若相等则查找成功若相等则查找成功若相等则查找成功; ; ; ; 否则否则否则否则, , , , 继续进行继续进行继续进行继续进行, , , ,直到与直到与直到与直到与r0.keyr0.keyr0.keyr0.key比较为止比较为止比较为止比较为止. . . . 2. 2. 2. 2. 算法分析算法分析算法分析算法分析: (1) (1) (1) (1) 算法结构应由一个循环构成算法结构应由一个循环构成算法结构应由一个循环构成算法结构应由一个循环构成; ; ; ; (2) (2) (2) (2) 循环结束有两种可能：循环结束有两种可

9、能：循环结束有两种可能：循环结束有两种可能： 查找成功查找成功查找成功查找成功 ri.key = kri.key = kri.key = kri.key = k 查找不成功查找不成功查找不成功查找不成功 i = 0i = 0i = 0i = 0第九章第九章第九章第九章 查找查找查找查找顺序查找方法的顺序查找方法的ASL第九章第九章第九章第九章 查找查找查找查找二、折半查找二、折半查找查找过程：每次将待查记录所在区间缩小一半查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的适用条件：采用顺序存储结构的有序表有序表算法实现算法实现v设表长为设表长为n n，lowlow、highh

10、igh和和midmid分别指向待查元素所在分别指向待查元素所在区间的上界、下界和中点区间的上界、下界和中点, ,k k为给定值为给定值v初始时，令初始时，令low=1,high=n,mid=low=1,high=n,mid= (low+high)/2(low+high)/2 v让让k k与与midmid指向的记录比较指向的记录比较l若若k=rmid.keyk=rmid.key，查找成功查找成功l若若krmid.keykrmid.keykrmid.key，则则low=mid+1low=mid+1v重复上述操作，直至重复上述操作，直至lowhighlowhigh时，查找失败时，查找失败第九章第九章

11、第九章第九章 查找查找查找查找算法描述算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid第九章第九章第九章第九章 查找查找查找查找例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lo

12、whighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid第九章第九章第九章第九章 查找查找查找查找1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936

13、判定树：树中每个结点表示一个判定树：树中每个结点表示一个记录，结点的值为该记录在表中记录，结点的值为该记录在表中的位置，称这个描述查找过程的的位置，称这个描述查找过程的二叉树为判定树。二叉树为判定树。1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92第九章第九章第九章第九章 查找查找查找查找算法评价算法评价v有有n n个结点的判定树的深度为个结点的判定树的深度为 loglog2 2n n +1+1v折半查找法在查找过程中进行的比较次数最多不超过折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度其判定树的深度v折半查找的折半查找

14、的ASLASL第九章第九章第九章第九章 查找查找查找查找三、三、 分块查找分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。查记录所在块，再在块内查找。说明：说明：“分块有序分块有序”指的是第二块所有的关键字均大于第一指的是第二块所有的关键字均大于第一块中最大的关键字。块中最大的关键字。 查找分为两步查找分为两步: 1. 确定待查记录所在块确定待查记录所在块; (可以用顺序或折半查找可以用顺序或折半查找) 2. 在块内顺序查找在块内顺序查找. (只能用顺序查找只能用顺序查找)适用条件：分块有序表适用条件：

15、分块有序表算法实现算法实现v用数组存放待查记录用数组存放待查记录,每个数据元素至少含有关键字域每个数据元素至少含有关键字域v建立索引表，每个索引表结点含有最大关键字域和指向本块第一建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针个结点的指针第九章第九章第九章第九章 查找查找查找查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查查38v算法描述算法描述第九章第九章第九章第九章 查找查找查找查找分块查

16、找方法评价分块查找方法评价第九章第九章第九章第九章 查找查找查找查找ASL最大最大最小最小两者之间两者之间表结构表结构有序表、无序表有序表、无序表 有序表有序表分块有序表分块有序表存储结构存储结构顺序存储结构顺序存储结构线性链表线性链表顺序存储结构顺序存储结构 顺序存储结构顺序存储结构线性链表线性链表查找方法比较查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找第九章第九章第九章第九章 查找查找查找查找9.2 动态查找表动态查找表 动态查找表的特点是动态查找表的特点是: 表结构本身是在查找过程中动态生表结构本身是在查找过程中动态生成的。成的。 即查找不成功时，将该记录插入在动态查找表

17、中。即查找不成功时，将该记录插入在动态查找表中。一、二叉排序树一、二叉排序树（Binary Sort Tree)（又称为二叉查找树）又称为二叉查找树）1、BST定义：定义： BST或者是一棵空树；或者是具有如下性质的或者是一棵空树；或者是具有如下性质的BT: 若左子树非空，则左子树上所有结点的值均小于根结点的值；若左子树非空，则左子树上所有结点的值均小于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树也为左、右子树也为BST第九章第九章第九章第九章 查找查找查找查找78100619012372484553例如：例

18、如：例如：例如：第九章第九章第九章第九章 查找查找查找查找2 2、查找过程为、查找过程为、查找过程为、查找过程为: : 若二叉排树为空，则查找失败，否则，先拿根结点值与若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。有找到待找结点，则查找不成功。第九章第九章

19、第九章第九章 查找查找查找查找3 3、二叉排序树的基本运算、二叉排序树的基本运算（1）二叉排序树的建立二叉排序树的建立 设已知一组待排序的数据，若要构造出对应的二叉排设已知一组待排序的数据，若要构造出对应的二叉排序树，一般是采取从空树开始，陆续插入一系列结点的办序树，一般是采取从空树开始，陆续插入一系列结点的办法，逐步生成对应的二叉排序树。法，逐步生成对应的二叉排序树。 首先以第一个数据构成根结点，以后对应每个数据插首先以第一个数据构成根结点，以后对应每个数据插入一个结点，在插入过程中，原有的结点位置均不再变动，入一个结点，在插入过程中，原有的结点位置均不再变动，只是将新数据结点作为一个叶子结

20、点插入到合适的位置处，只是将新数据结点作为一个叶子结点插入到合适的位置处，使树中任何结点与其左、右子树结点数据之间的关系都符使树中任何结点与其左、右子树结点数据之间的关系都符合二叉排序树的要求。合二叉排序树的要求。第九章第九章第九章第九章 查找查找查找查找例如，结定关键字序列例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如图所示。（注：二叉排序树与关，生成二叉排序树过程如图所示。（注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样）一样）第九章第九章第九章第九章

21、 查找查找查找查找79，62，68，90，88，89，17，5，100，120第九章第九章第九章第九章 查找查找查找查找（2）二叉排序树的插入）二叉排序树的插入 若二叉排序树为空，则作为根结点插入，否则，若待插入若二叉排序树为空，则作为根结点插入，否则，若待插入的值小于根结点值，则作为左子树插入，否则作为右子树插的值小于根结点值，则作为左子树插入，否则作为右子树插入，算法描述（见课本入，算法描述（见课本P173）第九章第九章第九章第九章 查找查找查找查找（3）二叉排序树的删除）二叉排序树的删除删除的原则：删除的原则：删除某个结点后仍保持删除某个结点后仍保持BST的特性。的特性。设：被删除结点为

22、设：被删除结点为p(指针指针p所指结点）所指结点）其双亲结点为其双亲结点为f ,且不失一般性，设且不失一般性，设p 是是f 的左孩子。的左孩子。第九章第九章第九章第九章 查找查找查找查找分三种情况讨论：分三种情况讨论： v 若若P结点为叶结点（即结点为叶结点（即PL和和PR均均为空树，仅需将为空树，仅需将f. lchild:=NILv 若若P结点只有左子树结点只有左子树PL或只有右子或只有右子树树PR ，只需只需 令令PL或或PR为为f 的左子树，的左子树，即即f . lchild:= p Lchild或或 prchildv 若若p结点左、右子树均不空，此时，结点左、右子树均不空，此时，按中序

23、遍历序列为：按中序遍历序列为：CL CQL Q SL S P PR F FRv删除删除P后为：后为： CLCQL Q SL S PR F FR。cqCSLsCLFFRfPRpPQQLS第九章第九章第九章第九章 查找查找查找查找对对f 的左孩子有两种处理办法：的左孩子有两种处理办法：(1)S不动，仍作为不动，仍作为Q的右孩子，的右孩子，C代替代替P ，作为作为f的左孩子，的左孩子，PR作为作为S的右孩子的右孩子;(2)(2) S代替代替P，而而 SL为为QR ;CSLCLPRQQLSFSSLCLFPRQQLC第九章第九章第九章第九章 查找查找查找查找4 4、BST BST 的查找分析的查找分析

24、BST BST 上查找过程与折半查找类似，是从根结点到所找到上查找过程与折半查找类似，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度结点的一条路径。与给定值比较次数等于该路径长度+1+1（即（即结点所在层次数），最大次数不超过树的深度。结点所在层次数），最大次数不超过树的深度。 但长度为但长度为n n的折半查找表对应的判定树是唯一的。而含有的折半查找表对应的判定树是唯一的。而含有n n个结点的个结点的BSTBST却不唯一。却不唯一。459353371224 ( (a)a)(45, 24, 53, 12, 37, 93)(45, 24, 53, 12, 37, 93)12243

25、7455393 ( (b)b)(12, 24, 37, 45, 53, 93)(12, 24, 37, 45, 53, 93)ASL(a)=1/6（1+2+2+3+3+3）=14/6ASL(b)=1/6（1+2+3+4+5+6）=21/6第九章第九章第九章第九章 查找查找查找查找因此，含有因此，含有n个结点的个结点的BST的的ASL和树的形态有关。和树的形态有关。最差情况是最差情况是BST退化为单支树，其深度为退化为单支树，其深度为n，ASL=(n+1)/2 (同顺序查找）。同顺序查找）。最好情况与折半查找相同，最好情况与折半查找相同，ASL=log2n 随机情况下，平均查找长度为随机情况下，

26、平均查找长度为1+4log2n 为了避免出现单支树，在构成为了避免出现单支树，在构成BST的过程中可进行的过程中可进行“平平衡化衡化”处理。处理。第九章第九章第九章第九章 查找查找查找查找二二. 平衡二叉树平衡二叉树 (Balanced Binary Tree), 又称为又称为AVL树树 1 、AVL树定义树定义AVL树或者是一棵空树，或者是具有下列性质的树或者是一棵空树，或者是具有下列性质的BT: 左、右子树均为左、右子树均为AVL 且任一左、右子树的深度之差的绝对值不超过且任一左、右子树的深度之差的绝对值不超过1.称某结点左子树的深度右子树的深度为该结点的称某结点左子树的深度右子树的深度为

27、该结点的平衡因子平衡因子（balance factor) 2、AVL树的特点树的特点 AVL树上任何结点的平衡因子只可能为树上任何结点的平衡因子只可能为-1，0或或1; AVL树的深度与树的深度与log n同数量级同数量级; AVL树的树的ASL也与也与log n同数量级同数量级; 完全二叉树一定是完全二叉树一定是AVL , 当然当然AVL树不一定是完全二叉树树不一定是完全二叉树第九章第九章第九章第九章 查找查找查找查找1001(a)0100-11-1(b)01-1002(c)结点中的值为该结点的平衡因子结点中的值为该结点的平衡因子第九章第九章第九章第九章 查找查找查找查找3 3 3 3、BS

28、TBSTBSTBST变为变为变为变为AVLAVLAVLAVL树树树树 例：设表的关键字序列为（例：设表的关键字序列为（例：设表的关键字序列为（例：设表的关键字序列为（13131313，24242424，37373737，90909090，53535353）, , , ,BSTBSTBSTBST生成过程为：生成过程为：生成过程为：生成过程为：132413AVL AVL AVL旋转旋转372413非非AVL372413AVL非非AVL903724135390372413旋转旋转9053372413AVL3790532413第九章第九章第九章第九章 查找查找查找查找(2) 调整形态调整形态 (可归纳

29、为四种可归纳为四种) LL型平衡旋转（顺时针）型平衡旋转（顺时针） 失去平衡点的平衡因子为失去平衡点的平衡因子为2, 其左孩子的平衡因子为其左孩子的平衡因子为12AaARh-11BBRBLh-1hh+1LL0AARBRh-1h-10BBLhh调整语句为：调整语句为： B rchild =A;A lchild =B rchild ; A bf=0B rchild=A; B bf=0第九章第九章第九章第九章 查找查找查找查找 LR型平衡旋转型平衡旋转失去平衡点的平衡因子为失去平衡点的平衡因子为2, 其左孩子的平衡因子为其左孩子的平衡因子为 -1ARh-12A-1BBLCLh-1h-1 h+11Ch

30、h-2CRLR0CARh-10BBLCLh-1h-1-1Ah-2CRA lchild =C rchild ; B rchild = C lchild C rchildA; C lchild B;2A2CARh-1h-2CR0BBLCLh-1h-1 h h+1第九章第九章第九章第九章 查找查找查找查找 RR型平衡旋转（逆时针，与型平衡旋转（逆时针，与LL对称对称)失去平衡点的平衡因子为失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为其右孩子的平衡因子为 -1-2AALBLh-1h-1-1BhBRRR0BBLALh-10ABR第九章第九章第九章第九章 查找查找查找查找RL型平衡旋转型平衡旋转失

31、去平衡点的平衡因子为失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为其右孩子的平衡因子为 1RL0CBR0AALCL-1Bh-2CR1BBRh-1-2AALh-1CLh-11Ch-2CR中序遍历：中序遍历：AL A CL C CR B BR AL A CL C CR B BR第九章第九章第九章第九章 查找查找查找查找(3) (3) 为了得到平衡树，需作如下处理为了得到平衡树，需作如下处理 找到可能失去平衡的最小子树的根结点找到可能失去平衡的最小子树的根结点 可能失去平衡的最小子树的根结点，是离插入结点最近可能失去平衡的最小子树的根结点，是离插入结点最近的且插入前平衡因子值的且插入前平衡因子

32、值0:0: 插入前平衡因子的绝对值插入前平衡因子的绝对值00 插入后平衡因子的绝对值插入后平衡因子的绝对值11 离插入结点最近的失去平衡的祖先结点离插入结点最近的失去平衡的祖先结点判别插入结点后可能失去平衡的最小子树的根结点是判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡，（该结点的平衡因子的绝对值否失去平衡，（该结点的平衡因子的绝对值11）; ;判别旋转类型作相应处理。判别旋转类型作相应处理。第九章第九章第九章第九章 查找查找查找查找4、AVL树上插入结点算法树上插入结点算法(1) 算法描述算法描述 查找查找 s 结点的插入位置过程中，记下离结点的插入位置过程中，记下离s 最近的，

33、且平衡因最近的，且平衡因子不等于子不等于0的结点，令的结点，令 a 指向该结点；（即可能失去平衡的指向该结点；（即可能失去平衡的最小子树的根结点）。最小子树的根结点）。 修改修改 a 至至 s 路径上所有结点的平衡因子值；路径上所有结点的平衡因子值； 判别判别a 结点的平衡因子绝对值是否大于结点的平衡因子绝对值是否大于1，若是，作旋转处，若是，作旋转处理理第九章第九章第九章第九章 查找查找查找查找5 5平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找叉排序树完全相同

34、。但它的查找 性能优于二叉排序树，不像性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度二叉排序树一样，会出现最坏的时间复杂度O(n)O(n)，它的时间它的时间复杂度与二叉排序树的最好时间复杂相同，都为复杂度与二叉排序树的最好时间复杂相同，都为O(logO(log2 2n)n)。 第九章第九章第九章第九章 查找查找查找查找例例 对给定的关键字序列对给定的关键字序列4,5,7,2,1,3,64,5,7,2,1,3,6，试用二叉排序树，试用二叉排序树和平衡二叉树两种方法查找，给出查找和平衡二叉树两种方法查找，给出查找6 6的次数及成功的平均的次数及成功的平均查找长度。查找长度。 0 6

35、 2 1 4 3 7 0 0 0 0 0 5 0 从二叉排序树可知，查找从二叉排序树可知，查找6 6需需4 4次，平均查找长度次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57ASL=(1+2+2+3+3+3+4)/7=18/72.57。从平衡二叉树可知，查找从平衡二叉树可知，查找6 6需需2 2次，平均查找长度次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。从结果可知，平衡二叉树的查找性能优于二叉排序树。第九章第九章第九章第九章 查找查找

36、查找查找9.3 哈希查找哈希查找一、基本概念一、基本概念 散列查找，也称为哈希查找。它既是一种查找方法，又是一散列查找，也称为哈希查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表。列表。 散列查找，与前面介绍的查找方法完全不同，前面介绍的所散列查找，与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造散列函数来得到待查关键字的地址，法，而散列查找是通过构造散列函数来得到待

37、查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。例如，要找关按理论分析真正不需要用到比较的一种查找方法。例如，要找关键字为键字为k k的元素，则只需求出函数值的元素，则只需求出函数值H H（k k），），H H（k k）为给定的散为给定的散列函数，代表关键字列函数，代表关键字k k在存贮区中的地址。在存贮区中的地址。第九章第九章第九章第九章 查找查找查找查找例例 假设有一批关键字序列假设有一批关键字序列18,75,60,43,54,90,46，给定散列函数，给定散列函数H（k）=k%13，存贮区的内存地址从存贮区的内存地址从0到到15，则可以得到每个关，则可以得到每个关键字的散列地

38、址为：键字的散列地址为： H（18）=18%13=5 H（75）=75%13=10 H（60）=60%13=8 H（43）=43%13=4 H（54）=54%13=2 H（90）=90%13=12 H（46）=46%13=7于是，根据散列地址，可以将上述于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维个关键字序列存贮到一个一维数组数组HT（散列表）中，具体表示为：散列表）中，具体表示为：第九章第九章第九章第九章 查找查找查找查找 其其中中HTHT就就是是散散列列存存贮贮的的表表，称称为为散散列列表表。从从散散列列表表中中查查找找 一一 个个 元元 素素 相相 当当 方方 便便 ， 例

39、例 如如 ， 查查 找找 7575， 只只 需需 计计 算算 出出H H（7575）=75%13=10=75%13=10，则可以在则可以在HT10HT10中找到中找到7575。 上上面面讨讨论论的的散散列列表表是是一一种种理理想想的的情情形形，即即每每一一个个关关键键字字对对应应一一个个唯唯一一的的地地址址。但但是是有有可可能能出出现现这这样样的的情情形形，两两个个不不同同的的关关键键字字有有可可能能对对应应同同一一个个内内存存地地址址，这这样样，将将导导致致后后放放的的 关关 键键 字字 无无 法法 存存 贮贮 ， 我我 们们 把把 这这 种种 现现 象象 叫叫 做做 冲冲 突突（colli

40、sioncollision）。在在散散列列存存贮贮中中，冲冲突突是是很很难难避避免免的的，除除非非构构造造出出的的散散列列函函数数为为线线性性函函数数。散散列列函函数数选选得得比比较较差差，则则发发生生冲冲突突的的可可能能性性越越大大。我我们们把把相相互互发发生生冲冲突突的的关关键键字字互互称称为为“同义词同义词”。第九章第九章第九章第九章 查找查找查找查找 在散列存贮中，若发生冲突，则必须采取特殊的方法来解在散列存贮中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使散列查找能顺利进行。虽然冲突不可避免，决冲突问题，才能使散列查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个

41、方面因素有关。第一是与装填因但发生冲突的可能性却与三个方面因素有关。第一是与装填因子子有关，所谓有关，所谓装填因子装填因子是指散列表中己存入的元素个数是指散列表中己存入的元素个数n n与与散列表的大小散列表的大小m m的比值，即的比值，即=n/m=n/m。当。当越小时，发生冲突的越小时，发生冲突的可能性越小，可能性越小，越大（最大为越大（最大为1 1）时，发生冲突的可能性就越）时，发生冲突的可能性就越大。但是，为了减少冲突的发生，不能将大。但是，为了减少冲突的发生，不能将变得太小，这样将变得太小，这样将会造成大量存贮空间的浪费，因此必须兼顾存储空间和冲突两会造成大量存贮空间的浪费，因此必须兼顾

42、存储空间和冲突两个方面。第二是与所构造的散列函数有关。第三是与解决冲突个方面。第二是与所构造的散列函数有关。第三是与解决冲突的方法有关。的方法有关。 第九章第九章第九章第九章 查找查找查找查找二、二、 散列函数的构造散列函数的构造 散列函数的构造目标是使散列地址尽可能均匀地分散列函数的构造目标是使散列地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单。具体常用的布在散列空间上，同时使计算尽可能简单。具体常用的构造方法有如下几种：构造方法有如下几种： 1 1直接定址法直接定址法 可表示为可表示为H H（k k）=a.k+b=a.k+b，其中其中a a、b b均为常数。均为常数。这这种种方方法

43、法计计算算特特别别简简单单，并并且且不不会会发发生生冲冲突突，但但当当关关键键字字分分布布不不连连续续时时，会会出出现现很很多多空空闲闲单单元元，将将造造成成大大量存贮单元的浪费。量存贮单元的浪费。2 2数字分析法数字分析法对关键字序列进行分析，取那些位上数字变化多的、频率对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。大的作为散列函数地址。 第九章第九章第九章第九章 查找查找查找查找例如，对如下的关键字序列：例如，对如下的关键字序列： 43010430104 46 68 81 10 01535515355 43010430101 17 70 01 11 1283522

44、8352 43010430103 37 72 20 08 81835018350 43010430102 26 69 90 06 60535105351 43010430105 58 80 01 12 22635626356 通通过过对对上上述述关关键键字字序序列列分分析析，发发现现前前5 5位位相相同同，第第6 6、8 8、1010位位上上的的数数字字变变化化多多些些，若若规规定定地地址址取取3 3位位，则则散散列函数可取它的第列函数可取它的第6 6、8 8、1010位。于是有：位。于是有：H H（430104681015355430104681015355）480480H H（430101

45、701128352430101701128352）101101H H（430103620805351430103620805351）328328H H（430102690605351430102690605351）296296H H（430105801226356430105801226356）502502第九章第九章第九章第九章 查找查找查找查找3 3平方取中法平方取中法 取取关关键键字字平平方方后后的的中中间间几几位位为为散散列列函函数数地地址址。这这是是一一种种比比较较常常用用的的散散列列函函数数构构造造方方法法，在在选选定定散散列列函函数数时时不不一一定定知知道道关关键键字字的的全全部

46、部信信息息，取取其其中中哪哪几几位位也也不不一一定定合合适适，而而一一个个数数平平方方后后的的中中间间几几位位数数和和数数的的每每一一位位都都相相关关，因因此此，可可以以使使用用随随机机分分布的关键字得到函数地址。布的关键字得到函数地址。如图，随机给出一些如图，随机给出一些关键字，并取平方后关键字，并取平方后的第的第2 2到到4 4位为函数地位为函数地址。址。 第九章第九章第九章第九章 查找查找查找查找4 4折叠法折叠法将关键字分割成位数相同的几部分（最后一部分的位数可将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散以不同），然后取这几部分的

47、叠加和（舍去进位）作为散列函数地址，称为折叠法。列函数地址，称为折叠法。 例例如如，假假设设关关键键字字为为某某人人身身份份证证号号码码430104681015355430104681015355，则则可可以以用用4 4位位为为一一组组进进行行叠叠加加，即即有有535553558101810110461046 430430 1493214932， 舍舍 去去 高高 位位 ， 则则 有有H H（430104681015355430104681015355）49324932为为该该身身份份证证关关键键字字的的散散列函数地址。列函数地址。第九章第九章第九章第九章 查找查找查找查找 除除留留余余数数法

48、法计计算算简简单单，适适用用范范围围广广，是是一一种种最最常常使使用用的的方方法法。这这种种方方法法的的关关键键是是选选取取较较理理想想的的p p值值，使使得得每每一一个个关关键键字字通通过过该该函函数数转转换换后后映映射射到到散散列列空空间间上上任任一一地地址址的的概概率率都都相相等等，从从而而尽尽可可能能减减少少发发生生冲冲突突的的可可能能性性。一一般般情情形形下下，p p取取为为一一个个质质数数或或选选取取一一个个不不含含有有小小于于20的的质质因因子子的的合合数数较较理理想想，并并且且要要求求装装填填因因子子最最好好是是在在0.60.90.60.9之之间间，所所以以p p最最好好取取1

49、.11.1n1.7nn1.7n之之间间的的一一个个质质数较好，其中数较好，其中n n为散列表中待装元素个数为散列表中待装元素个数. .5 5除留余数法除留余数法该方法是用关键字序列中的关键字该方法是用关键字序列中的关键字k k除以除以p(pp(p是小于等于是小于等于散列表长度散列表长度m m）所得余数作为散列函数的地址，即有所得余数作为散列函数的地址，即有H H（k k）k kp p 。 第九章第九章第九章第九章 查找查找查找查找v选取哈希函数，考虑以下因素：选取哈希函数，考虑以下因素：l计算哈希函数所需时间计算哈希函数所需时间l关键字长度关键字长度l哈希表长度（哈希地址范围）哈希表长度（哈希

50、地址范围）l关键字分布情况关键字分布情况l记录的查找频率记录的查找频率第九章第九章第九章第九章 查找查找查找查找三、三、 解决冲突的方法解决冲突的方法由由于于散散列列存存贮贮中中选选取取的的散散列列函函数数不不是是线线性性函函数数，故故不不可可避避免地会产生冲突，下面给出常见的解决冲突方法。免地会产生冲突，下面给出常见的解决冲突方法。1 1开放定址法开放定址法 开开放放定定址址法法就就是是从从发发生生冲冲突突的的那那个个单单元元开开始始，按按照照一一定定的的次次序序，从从散散列列表表中中找找出出一一个个空空闲闲的的存存储储单单元元，把把发发生生冲冲突突的的待待插插入入关关键键字字存存储储到到该

51、该单单元元中中，从从而而解解决决冲冲突的发生。突的发生。第九章第九章第九章第九章 查找查找查找查找在开放定址法中，解决冲突时具体使用下面一些方法。在开放定址法中，解决冲突时具体使用下面一些方法。（1 1）线性探查法）线性探查法 假假设设散散列列表表的的地地址址为为00m-1m-1，则则散散列列表表的的长长度度为为m m。若若一一个个关关键键字字在在地地址址d d处处发发生生冲冲突突，则则依依次次探探查查d+1d+1，d+2d+2，m-m-1(1(当当达达到到表表尾尾m-1m-1时时，又又从从0 0，1 1，2 2，.开开始始探探查查) )等等地地址址，直直到到找找到到一一个个空空闲闲位位置置来

52、来装装冲冲突突处处的的关关键键字字，将将这这一一种种方方法法称称为为线线性性探探查查法法。探探查查下下一一位位置置的的公公式式为为d di i=(d=(di-1i-1+1)%m +1)%m (1im-1)(1im-1)，最后将冲突位置的关键字存入最后将冲突位置的关键字存入didi地址中。地址中。例例 给给定定关关键键字字序序列列为为1919，1414，2323，1 1，6868，2020，8484，2727，5555，1111，1010，7979，散散到到函函数数H H（k k）=k%13 =k%13 ，散散列列表表空空间间地地址址为为012012，试试用用线线性性探探查查法法建建立立散散列列

53、存存贮贮( (散散列列表表) )结结构构。得得到到的的散列表如下图所示散列表如下图所示第九章第九章第九章第九章 查找查找查找查找(2) (2) 平方探查法平方探查法该该方方法法规规定定，若若在在d d地地址址发发生生冲冲突突，下下一一次次探探查查位位置置为为d+1d+12 2，d+2d+22 2，直到找到一个空闲位置为止。直到找到一个空闲位置为止。(3) (3) 双散列函数探查法双散列函数探查法该方法使用两个散列函数该方法使用两个散列函数H H和和T T，用，用H H作散列函数建立散列作散列函数建立散列存储（散列表），用存储（散列表），用T T来解决冲突。具体实施时，若来解决冲突。具体实施时，

54、若H(k)H(k)在在d0d0位置发生冲突时，即位置发生冲突时，即d0 =H(k)d0 =H(k)，则下一个探查位置则下一个探查位置序列应该是序列应该是d di i=(d=(di-1i-1+T(k)%m (1im-1)+T(k)%m (1im-1)。 第九章第九章第九章第九章 查找查找查找查找 2.2.拉链法拉链法拉链法也称链地址法，是把相互发生冲突的同义词用拉链法也称链地址法，是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个一个单链表链接起来，若干组同义词可以组成若干个单链表单链表 例例 对对给给定定的的关关键键字字序序列列19,14,23,1,68,20,84,27

55、,55,11,10,7919,14,23,1,68,20,84,27,55,11,10,79，给给定定散散列列函数为函数为H(k)=k%13H(k)=k%13，试用拉链法解决冲突建立散列表。试用拉链法解决冲突建立散列表。下下图图为为用用尾尾插插法法建建立立的的关关于于上上例例的的拉拉链链法法解解决决冲冲突的散列表。突的散列表。第九章第九章第九章第九章 查找查找查找查找第九章第九章第九章第九章 查找查找查找查找四、四、 散列查找的性能分析散列查找的性能分析散散列列查查找找按按理理论论分分析析，它它的的时时间间复复杂杂度度应应为为O(1)O(1)，它它的的平平均均查查找找长长度度应应为为ASL=1

56、ASL=1，但但实实际际上上由由于于冲冲突突的的存存在在，它它的的平平均均查查找找长长度度将将会会比比1 1大大。下下面面将将分分析析几几种种方方法法的的平均查找长度。平均查找长度。1.1.线性探查法的性能分析线性探查法的性能分析由由于于线线性性探探查查法法解解决决冲冲突突是是线线性性地地查查找找空空闲闲位位置置的的，平平均均查查找找长长度度与与表表的的大大小小m m无无关关，只只与与所所选选取取的的散散列列函函数数H H及及装装填填因因子子的的值值和和该该处处理理方方法法有有关关，这这时时的的成功的平均查找长度为成功的平均查找长度为ASL=1/2 (1+1/(1- ) ASL=1/2 (1+

57、1/(1- ) 。 2.2.拉链法查找的性能分析拉链法查找的性能分析由于拉链法查找就是在单链表上查找，查找单链表由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为中第一个结点的次数为1 1，第二个结点次数为，第二个结点次数为2 2，其，其余依次类推。它的平均查找长度余依次类推。它的平均查找长度ASL=1+/2ASL=1+/2。 第九章第九章第九章第九章 查找查找查找查找 例例 给给定定关关键键字字序序列列1111，7878，1010，1 1，3 3，2 2，4 4，2121，试试分分别别用用顺顺序序查查找找、二二分分查查找找、二二叉叉排排序序树树查查找找、平平衡衡二二叉叉树树查查

58、找找、散散列列查查找找( (用用线线性性探探查查法法和和拉拉链链法法) )来来实实现现查查找找，试试画画出出它它们们的的对对应应存存储储形形式式( (顺顺序序查查找找的的顺顺序序表表，二二分分查查找找的的判判定定树树，二二叉叉排排序序树树查查找找的的二二叉叉排排序序树树及及平平衡衡二二叉叉树树查查找找的的平平衡衡二二叉叉树树，两两种种散散列列查查找找的的散散列列表表) )，并并求求出出每每一一种种查查找找的的成成功功平平均均查查找找长长度度。散散列列函函数数H(k)=k%11H(k)=k%11。顺序查找的顺序表（一维数组）如图所示，顺序查找的顺序表（一维数组）如图所示， 从图可以得到顺序查找的

59、成功平均查找长度为：从图可以得到顺序查找的成功平均查找长度为：ASL=(1+2+3+4+5+6+7+8)/8=4.5ASL=(1+2+3+4+5+6+7+8)/8=4.5；第九章第九章第九章第九章 查找查找查找查找二分查找的判定树（中序序列为从小到大排列的有序序列）二分查找的判定树（中序序列为从小到大排列的有序序列）如下图所示如下图所示 从图可以得到二分查找的成功平均查找长度为：从图可以得到二分查找的成功平均查找长度为：ASL=(1+2*2+3*4+4)/8=2.625ASL=(1+2*2+3*4+4)/8=2.625；第九章第九章第九章第九章 查找查找查找查找二叉排序树（关键字顺序已确定，该

60、二叉排序树应唯一）二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图如图 ( (a)a)所示，平衡二叉树（关键字顺序已确定，该平所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图衡二叉树也应该是唯一的），如图( (b)b)所示：所示： 从图从图 ( (a)a)可以得到二叉排序树查找的成功平均查找长度为：可以得到二叉排序树查找的成功平均查找长度为：ASL=(1+2*2+3*2+4+5*2)=3.125ASL=(1+2*2+3*2+4+5*2)=3.125；从图从图 ( (b)b)可以得到平衡二叉树的成功平均查找长度为：可以得到平衡二叉树的成功平均查找长度为：ASL=(1+

61、2*2+3*3+4*2)/8=2.75ASL=(1+2*2+3*3+4*2)/8=2.75；第九章第九章第九章第九章 查找查找查找查找线性探查法解决冲突的散列表如图所示：线性探查法解决冲突的散列表如图所示： 从上图可以得到线性探查法的成功平均查找长度为：从上图可以得到线性探查法的成功平均查找长度为：ASL=ASL=（1+1+2+1+3+2+1+81+1+2+1+3+2+1+8）/8=2.375/8=2.375；第九章第九章第九章第九章 查找查找查找查找拉链法解决冲突的散列表如下图所示。拉链法解决冲突的散列表如下图所示。从图可以得到拉链法的成功平均查找长度为：从图可以得到拉链法的成功平均查找长度为：ASL=(1*6+2*2)/8=1.25ASL=(1*6+2*2)/8=1.25。