数据结构 第9章 查找

1、概 述 查找表：由同一类型数据元素构成的集合。由于“集合”中的元素之间存在着完全松散的关系，因此查找表是一种非常灵便的数据结构。 查找，也称为检索。在我们日常生活中，如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如考生信息中，姓名不能唯一标识一个数据元素，而考号可以唯一标识一个数据元素(每个

2、考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。 有了关键字及查找表后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。 因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某

3、些特殊的数据结构来组织表（人为地加上一些关系以便按某种规则进行查找）。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL= ，其中i为查找第i个元素的概率，且 =1。一般情形下我们认为查找每个元素的概率相等，ci为查找第i个元素所用到的比较次数。9.1 静态查找表一、 顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较.i例 1 2 3 4

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. 查找过程: 从n开始,依次与k进行比较, 若相等则查找成功; 否则, 继续进行,直到与r0.key比较为止. 2. 算法分析: (1) 算法结构应由一个循环构成; (2) 循环结束有两种可能： 查找成功 ri.key = k 查找不成功 i = 0顺序查找方法的ASL二、折半查找查找过程：每次将待查记录所在区间缩小一

5、半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k=rmid.key，查找成功若krmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败算法描述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 92

6、lowhighmid1 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 92lowhighmid找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 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 1

7、9 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 92lowhigh1185210741936判定树：树中每个结点表示一个记录，结点的值为该记录在表中的位置，称这个描述查找过程的二叉树为判定树。1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92算法评价有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度折半查找的ASL三、 分块查找查找过程：将表分成几块，块内无序，块

8、间有序；先确定待查记录所在块，再在块内查找。说明：“分块有序”指的是第二块所有的关键字均大于第一块中最大的关键字。 查找分为两步: 1. 确定待查记录所在块; (可以用顺序或折半查找) 2. 在块内顺序查找. (只能用顺序查找)适用条件：分块有序表算法实现用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针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索引表查3

9、8算法描述分块查找方法评价ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找9.2 动态查找表 动态查找表的特点是: 表结构本身是在查找过程中动态生成的。 即查找不成功时，将该记录插入在动态查找表中。一、二叉排序树（Binary Sort Tree)（又称为二叉查找树）1、BST定义： BST或者是一棵空树；或者是具有如下性质的BT: 若左子树非空，则左子树上所有结点的值均小于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树也为BST781006190123724

10、84553例如：2、查找过程为: 若二叉排树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树的叶子结点时，还没有找到待找结点，则查找不成功。3、二叉排序树的基本运算（1）二叉排序树的建立 设已知一组待排序的数据，若要构造出对应的二叉排序树，一般是采取从空树开始，陆续插入一系列结点的办法，逐步生成对应的二叉排序树。 首先以第一个数据构成根结点，以后对应每个数据插入一个结点，在插入过程中，原有的结点位置均不再变动，只是将新数据结点作为一个叶子结点插入到合适的位置处，使树中

11、任何结点与其左、右子树结点数据之间的关系都符合二叉排序树的要求。例如，结定关键字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序树过程如图所示。（注：二叉排序树与关键字排列顺序有关，排列顺序不一样，得到的二叉排序树也不一样）79，62，68，90，88，89，17，5，100，120（2）二叉排序树的插入 若二叉排序树为空，则作为根结点插入，否则，若待插入的值小于根结点值，则作为左子树插入，否则作为右子树插入，算法描述（见课本P173）（3）二叉排序树的删除删除的原则：删除某个结点后仍保持BST的特性。设：被删除结点为p(指针p所指结点）其双亲结点为f ,且不失一

12、般性，设p 是f 的左孩子。分三种情况讨论： 若P结点为叶结点（即PL和PR均为空树，仅需将f. lchild:=NIL 若P结点只有左子树PL或只有右子树PR ，只需 令PL或PR为f 的左子树，即f . lchild:= p Lchild或 prchild 若p结点左、右子树均不空，此时，按中序遍历序列为：CL CQL Q SL S P PR F FR删除P后为： CLCQL Q SL S PR F FR。cqCSLsCLFFRfPRpPQQLS对f 的左孩子有两种处理办法：S不动，仍作为Q的右孩子，C代替P ，作为f的左孩子，PR作为S的右孩子;(2) S代替P，而 SL为QR ;CSL

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

14、树的形态有关。最差情况是BST退化为单支树，其深度为n，ASL=(n+1)/2 (同顺序查找）。最好情况与折半查找相同，ASL=log2n 随机情况下，平均查找长度为1+4log2n 为了避免出现单支树，在构成BST的过程中可进行“平衡化”处理。二. 平衡二叉树 (Balanced Binary Tree), 又称为AVL树 1 、AVL树定义AVL树或者是一棵空树，或者是具有下列性质的BT: 左、右子树均为AVL 且任一左、右子树的深度之差的绝对值不超过1.称某结点左子树的深度右子树的深度为该结点的平衡因子（balance factor) 2、AVL树的特点 AVL树上任何结点的平衡因子只可

15、能为-1，0或1; AVL树的深度与log n同数量级; AVL树的ASL也与log n同数量级; 完全二叉树一定是AVL , 当然AVL树不一定是完全二叉树1001(a)0100-11-1(b)01-1002(c)结点中的值为该结点的平衡因子3、BST变为AVL树 例：设表的关键字序列为（13，24，37，90，53）,BST生成过程为：132413AVL AVL AVL旋转372413非AVL372413AVL非AVL903724135390372413旋转旋转9053372413AVL3790532413(2) 调整形态 (可归纳为四种) LL型平衡旋转（顺时针） 失去平衡点的平衡因子为

16、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+11Chh-2CRLR0CARh-10BBLCLh-1h-1-1Ah-2CRA lchild =C rchild ; B rchild = C lchild C rchildA; C lchild B;2A2CARh-1h-2CR0BBLCLh-

17、1h-1 h h+1 RR型平衡旋转（逆时针，与LL对称)失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为 -1-2AALBLh-1h-1-1BhBRRR0BBLALh-10ABRRL型平衡旋转失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为 1RL0CBR0AALCL-1Bh-2CR1BBRh-1-2AALh-1CLh-11Ch-2CR中序遍历：AL A CL C CR B BR AL A CL C CR B BR(3) 为了得到平衡树，需作如下处理 找到可能失去平衡的最小子树的根结点 可能失去平衡的最小子树的根结点，是离插入结点最近的且插入前平衡因子值0: 插入前平衡因子的绝对值0

18、 插入后平衡因子的绝对值1 离插入结点最近的失去平衡的祖先结点判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡，（该结点的平衡因子的绝对值1）;判别旋转类型作相应处理。4、AVL树上插入结点算法(1) 算法描述 查找 s 结点的插入位置过程中，记下离s 最近的，且平衡因子不等于0的结点，令 a 指向该结点；（即可能失去平衡的最小子树的根结点）。 修改 a 至 s 路径上所有结点的平衡因子值； 判别a 结点的平衡因子绝对值是否大于1，若是，作旋转处理5平衡二叉树的查找及性能分析 平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序

19、树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。 例 对给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。 0 6 2 1 4 3 7 0 0 0 0 0 5 0 从二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。从平衡二叉树可知，查找6需2次，平均查找长度ASL=(1+2+2+3+3+3+3)=17/72.43。从结果可知，平衡二叉树的查找性能优于二叉排序树。9.3 哈希查找一、基本概念 散列查找，也称为哈

20、希查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表。 散列查找，与前面介绍的查找方法完全不同，前面介绍的所有查找都是基于待查关键字与表中元素进行比较而实现的查找方法，而散列查找是通过构造散列函数来得到待查关键字的地址，按理论分析真正不需要用到比较的一种查找方法。例如，要找关键字为k的元素，则只需求出函数值H（k），H（k）为给定的散列函数，代表关键字k在存贮区中的地址。例 假设有一批关键字序列18,75,60,43,54,90,46，给定散列函数H（k）=k%13，存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为： H（18）=18%13

21、=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（散列表）中，具体表示为： 其中HT就是散列存贮的表，称为散列表。从散列表中查找一个元素相当方便，例如，查找75，只需计算出H（75）=75%13=10，则可以在HT10中找到75。 上面讨论的散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址，这样，将导致后放的关键字无法存贮，我们

22、把这种现象叫做冲突（collision）。在散列存贮中，冲突是很难避免的，除非构造出的散列函数为线性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。 在散列存贮中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使散列查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。第一是与装填因子有关，所谓装填因子是指散列表中己存入的元素个数n与散列表的大小m的比值，即=n/m。当越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。但是，为了减少冲突的发生，不能将变得太小，这样将会造成大量存贮空间的浪费，因此必须

23、兼顾存储空间和冲突两个方面。第二是与所构造的散列函数有关。第三是与解决冲突的方法有关。 二、 散列函数的构造 散列函数的构造目标是使散列地址尽可能均匀地分布在散列空间上，同时使计算尽可能简单。具体常用的构造方法有如下几种： 1直接定址法 可表示为H（k）=a.k+b，其中a、b均为常数。这种方法计算特别简单，并且不会发生冲突，但当关键字分布不连续时，会出现很多空闲单元，将造成大量存贮单元的浪费。2数字分析法对关键字序列进行分析，取那些位上数字变化多的、频率大的作为散列函数地址。 例如，对如下的关键字序列： 430104681015355 430101701128352 430103720818

24、350 430102690605351 430105801226356 通过对上述关键字序列分析，发现前5位相同，第6、8、10位上的数字变化多些，若规定地址取3位，则散列函数可取它的第6、8、10位。于是有：H（430104681015355）480H（430101701128352）101H（430103620805351）328H（430102690605351）296H（430105801226356）5023平方取中法 取关键字平方后的中间几位为散列函数地址。这是一种比较常用的散列函数构造方法，在选定散列函数时不一定知道关键字的全部信息，取其中哪几位也不一定合适，而一个数平方后的中间

25、几位数和数的每一位都相关，因此，可以使用随机分布的关键字得到函数地址。如图，随机给出一些关键字，并取平方后的第2到4位为函数地址。 4折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列函数地址，称为折叠法。 例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加，即有53558101104643014932，舍去高位，则有H（430104681015355）4932为该身份证关键字的散列函数地址。 除留余数法计算简单，适用范围广，是一种最常使用的方法。这种方法的关键是选取较理想的p值，使得每一个关键字

26、通过该函数转换后映射到散列空间上任一地址的概率都相等，从而尽可能减少发生冲突的可能性。一般情形下，p取为一个质数或选取一个不含有小于20的质因子的合数较理想，并且要求装填因子最好是在0.60.9之间，所以p最好取1.1n1.7n之间的一个质数较好，其中n为散列表中待装元素个数.5除留余数法该方法是用关键字序列中的关键字k除以p(p是小于等于散列表长度m）所得余数作为散列函数的地址，即有H（k）kp 。 选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率三、 解决冲突的方法由于散列存贮中选取的散列函数不是线性函数，故不可避免地会产生冲

27、突，下面给出常见的解决冲突方法。1开放定址法 开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中找出一个空闲的存储单元，把发生冲突的待插入关键字存储到该单元中，从而解决冲突的发生。在开放定址法中，解决冲突时具体使用下面一些方法。（1）线性探查法 假设散列表的地址为0m-1，则散列表的长度为m。若一个关键字在地址d处发生冲突，则依次探查d+1，d+2，m-1(当达到表尾m-1时，又从0，1，2，.开始探查)等地址，直到找到一个空闲位置来装冲突处的关键字，将这一种方法称为线性探查法。探查下一位置的公式为di=(di-1+1)%m (1im-1)，最后将冲突位置的关键字存入di地址中

28、。例 给定关键字序列为19，14，23，1，68，20，84，27，55，11，10，79，散到函数H（k）=k%13 ，散列表空间地址为012，试用线性探查法建立散列存贮(散列表)结构。得到的散列表如下图所示(2) 平方探查法该方法规定，若在d地址发生冲突，下一次探查位置为d+12，d+22，直到找到一个空闲位置为止。(3) 双散列函数探查法该方法使用两个散列函数H和T，用H作散列函数建立散列存储（散列表），用T来解决冲突。具体实施时，若H(k)在d0位置发生冲突时，即d0 =H(k)，则下一个探查位置序列应该是di=(di-1+T(k)%m (1im-1)。 2.拉链法拉链法也称链地址法，是把相互发生冲突的同义词用一个单链表链接起来，若干组同义词可以组成若干个单链表 例 对给定的关键字序列19,14,23,1,68,20,84,27,55,11,10,79，给定散列函数为H(k)=k%13，试用拉链法解决冲突建立散列表。下图为用尾插法建立的关