数据结构九章节查找.ppt

数据结构第九章查找,本章内容9.1 查找的基本概念9.2 静态查找表9.3 动态查找表9.4 哈希表,9-3,9.1 查找的基本概念,查找表(Search Table)查找表是由同一类型的数据元素(或记录)构成的集合。对查找表的操作主要有：查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素。查找表分类静态查找表仅作查询和检索操作的查找表。动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,9-4,9.1 查找的基本概念,关键字(Key)关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。主关键字：可以识别唯一的一个记录的关键字次关键字：能识别若干记录的关键字查找(Searching)是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。,9-5,9.1 查找的基本概念,衡量查找算法的标准时间复杂度；空间复杂度；平均查找长度ASL：定义为确定记录在表中的位置所进行的和关键字比较的次数的平均值 n ASL=PiCi i=1n为查找表的长度，即表中所含元素的个数Pi为查找第i个元素的概率(Pi=1)Ci是查找第i个元素时同给定值K比较的次数,9-6,9.2 静态查找表,9.2.1 顺序表的查找顺序查找算法是顺序表（既无序表）的查找方法。在顺序查找算法中，以顺序表或线性链表表示静态查找表。面临的问题下标越界的检查，需要相当的时间和空间代价。解决的办法是，将ST.elem0.key 置为key,所有元素检查完还没有找到时，在ST.elem0处一定找到。从而免去了检查下标越界的时间。顺序查找算法从表中最后一个记录开始逐个进行记录的关键字和给定值的比较若某个记录比较相等，则查找成功若直到第1个记录都比较不等，则查找不成功,9-7,9.2 静态查找表,顺序查找算法描述设置“哨兵”的目的是省略对下标越界的检查，提高算法执行速度。当然，哨兵也可以设置在高下标处。,int Search_Seq(SSTable ST,KeyType key)/若查找成功，返回位置ST.elem0.key=key;/“哨兵”，for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找return i;/找不到时,i=0,9-8,9.2 静态查找表,顺序查找示举例在下列顺序表中寻找62，如果找到，给出其所在位置的下标。,监视哨兵,比较次数=5,比较次数分析：查找第n个元素：1次查找第n-1个元素：2次.查找第1个元素：n次查找第i个元素：n+1-i次查找失败：n+1次,0 1 2 3 4 5 6 7 8 9 10 11,9-9,9.2 静态查找表,顺序查找性能分析对顺序表而言，Ci=n-i+1在等概率查找的情况下，Pi=1/n平均查找长度 ASLss=n*P1+(n-1)P2+2Pn-1+Pn=(n+1)/2如果被查找的记录概率不等时，ASLss在 PnPn-1 P2P1 时取极小值若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。顺序查找特点优点：1.简单2.适应面广(对表的结构无任何要求)缺点：1.平均查找长度较大2.特别是当n很大时，查找效率很低,9-10,9.2 静态查找表,9.2.2 折半查找折半查找算法是有序表的查找方法。在折半查找算法中，静态查找表按关键字大小的次序，有序地存放在顺序表中。折半查找的原理先确定待查记录所在的范围(前部分或后部分)逐步缩小(一半)范围直到找(不)到该记录为止,9-11,9.2 静态查找表,折半查找算法n个对象从小到大存放在有序顺序表ST中，k为给定值设low、high指向待查元素所在区间的下界、上界，即low=1,high=n设mid指向待查区间的中点，即 mid=(low+high)/2让k与mid指向的记录比较 若 k=STmid.key，查找成功 若 kSTmid.key，则low=mid+1下半区间重复3,4操作，直至lowhigh时，查找失败。,9-12,9.2 静态查找表,折半成功查找举例：在下列有序表中用折半查找法查找62所在位置。Key=62,第一步：low=1,high=11,mid=6,STmid=ST6=5662,则改变low；,第二步：low=mid+1=7,mid=9,STmid=ST9=8062,则改变high；,第三步：high=mid-1=8,mid=7,STmid=ST7=62=62,找到！,62,9-13,9.2 静态查找表,折半查找失败举例：在上例有序表中找61。,high=6,low=7,找61,当下界low大于上界high时，说明有序 表中没有关键字等于K的元素，查找失败,9-14,9.2 静态查找表,折半查找的性能分析折半查找过程可以用二叉树（也叫判定树）来描述：判定树上每个结点需要的查找次数刚好为该结点所在的层数；查找成功时查找次数不会超过判定树的深度n个结点的判定树的深度为 log2n+1比较次数最多不超过 log2n+1折半查找的算法复杂度为 log2n+1,9-15,9.2 静态查找表,折半查找特点折半查找的效率比顺序查找高，特别是查找表的长度很长时；折半查找只能适用于等概率有序表，并且以顺序存储结构存储。,9-16,9.2 静态查找表,9.2.3 分块查找分块查找是一种索引顺序表(分块有序表)查找方法，是折半查找和顺序查找的简单结合；索引顺序表(分块有序表)将整个表分成几块，块内无序，块间有序所谓块间有序是指后一块表中所有记录的关键字均大于前一块表中的最大关键字,9-17,9.2 静态查找表,基本概念主表：用数组存放待查记录,每个数据元素至少含有关键字域索引表：每个结点含有最大关键字域和指向本块第一个结点的指针,9-18,9.2 静态查找表,分块查找举例采用折半查找方法在索引表中找到块（第2块）用顺序查找方法在主表对应块中找到记录（第3个记录）,找62,9-19,9.2 静态查找表,分块查找性能分析若将长度为n的表分成b块，每块含s个记录，并设表中每个记录查找概率相等用折半查找方法在索引表中查找索引块，ASL块间log2(n/s+1)用顺序查找方法在主表对应块中查找记录，ASL块内=s/2ASLlog2(n/s+1)+s/2,9-20,9.3 动态查找表,动态查找表如果应用问题涉及的数据量很大，而且数据经常发生变化，如图书馆经常购进图书，每购进新书，需将新书记录插入图书表，对这类表除了提供前面的介绍的查找外，还要提供动态查找功能：查找某个“特定”元素是否在表中，若不在，将该元素插入；查找某个“特定”元素是否在表中，若在，从表中删除；如何组织动态查找表？用静态查找方法不能满足要求了。本节介绍几种方法。,9-21,9.3 动态查找表,9.3.1 二叉排序树二叉排序树又称二叉查找树空树或者是具有如下特性的二叉树：若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值；左、右子树也都分别是二叉排序树。,21,二叉排序树,非二叉排序树,9-22,9.3 动态查找表,二叉排序树查找算法 给定值与根结点比较：若相等，查找成功若小于，查找左子树若大于，查找右子树,例1：在右图二叉排序树中查找关键字值等于37,37,找到,例2：在右图二叉排序树中查找关键字值等于88,找到,例3：在右图二叉排序树中查找关键字值等于94,无此数,9-23,9.3 动态查找表,二叉排序树插入二叉排序树是一种动态树表。当树中不存在查找的结点时，作插入操作新插入的结点一定是叶子结点（只需改动一个结点的指针）该叶子结点是查找不成功时路径上访问的最后一个结点左孩子或右孩子(新结点值小于或大于该结点值),例：在右图二叉树中插入结点94。,9-24,9.3 动态查找表,二叉排序树生成例：画出在初始为空的二叉排序树中依次插入56,64,92,80,88,75时该树的生长全过程,56,9-25,9.3 动态查找表,二叉排序树中序遍历中序遍历二叉排序树，可得到一个关键字的有序序列,如5,13,19,21,37,56,64,92,75,80,88,9-26,9.3 动态查找表,二叉排序树删除删除二叉排序树中的一个结点后，必须保持二叉排序树的特性：左子树的所有结点值小于根结点，右子树的所有结点值大于根结点。也即保持中序遍历后，输出为有序序列被删除结点具有以下三种情况是叶子结点只有左子树或右子树同时有左、右子树下面针对三种情况各举一例。,9-27,9.3 动态查找表,被删除结点是叶子结点：直接删除结点，并让其父结点指向该结点的指针变为空。例：删除右二叉排序树中的88节点,56,64,5,92,37,88,19,80,21,13,75,9-28,9.3 动态查找表,被删除结点只有左子树或右子树删除结点,让其父结点指向该结点的指针指向其左子树(或右子树),即用孩子结点替代被删除结点即可例：对于右边二叉排序树中，先删除节点37，再删除节点64。,56,5,13,9-29,9.3 动态查找表,被删除结点p既有左子树，又有右子树以中序遍历时的直接前驱s替代被删除结点p，然后再按照前面介绍的发删除该直接前驱s（只可能有左孩子）,56,64,5,92,37,88,80,13,75,例：在右边二叉排序树中,节点56的中序遍历的直接前趋是节点37。,9-30,9.3 动态查找表,二叉排序树性能分析在最好的情况下，二叉排序树为一近似完全二叉树时，其查找深度为log2n量级，即其时间复杂性为O(log2n)在最坏的情况下，二叉排序树为近似线性表时(如以升序或降序输入结点时，见右图)，其查找深度为n量级，即其时间复杂性为O(n),9-31,9.3 动态查找表,二叉排序树特性一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列（通过中序遍历）插入新记录时，只需改变一个结点的指针，相当于在有序序列中插入一个记录而不需要移动其它记录二叉排序树既拥有类似于折半查找的特性，又采用了链表作存储结构但当插入记录的次序不当时(如升序或降序)，则二叉排序树深度很深（见右图），增加了查找的时间,9-32,9.3 动态查找表,平衡二叉树平衡二叉树(Balanced Binary Tree,Height-Balanced Tree,又称AVL树,Adelsen-Velskii and Landis，阿德尔森一维尔斯和兰迪斯)是二叉排序树的另一种形式。其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1，即|hL-hR|1。可以证明，它们的深度和logn是同数量级的（其中n为节点个数）。,AVL树,非AVL树,9-33,9.3 动态查找表,平衡二叉树平衡因子每个结点附加一个数字,给出该结点左子树的高度减去右子树的高度所得的高度差,这个数字即为结点的平衡因子(balance factor)AVL树任一结点平衡因子只能取-1,0,1若某个结点的平衡因子的绝对值大于1，则这棵二叉搜索树就失去了平衡，不再是AVL树。,9-34,9.3 动态查找表,非平衡二叉树的平衡处理若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。下面将分四种情况讨论平衡处理。,9-35,9.3 动态查找表,LL型 的处理(左左型)如下图所示，若在C的左孩子B上扦入一个左孩子结点A，使C的平衡因子由1变成了2，成为不平衡的二叉树序树。平衡处理：将C顺时针旋转，成为B的右子树，而原来B的右子树则变成C的左子树，待扦入结点A作为B的左子树。,结点旁边的数字表示该 结点的平衡因子,9-36,9.3 动态查找表,LR型的处理(左右型)如下图所示，在C的左孩子A上扦入一个右孩子B，使的C的平衡因子由1变成了2，成为不平衡的二叉排序树。平衡处理：将B变到A与C 之间，使之成为LL型，然后按第1种情形LL型处理。,结点旁边的数字表示该 结点的平衡因子,9-37,9.3 动态查找表,RR型的处理(右右型)如下图所示，在A的右孩子B上扦入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。平衡处理：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待扦入结点C成为B的右子树。,结点旁边的数字表示该 结点的平衡因子,9-38,9.3 动态查找表,RL型的处理(右左型)如下图所示，在A的右孩子C上扦入一个左孩子B，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。平衡处理：将B变到A与C之间，使之成为RR型，然后按第(3)种情形RR型处理。,结点旁边的数字表示该 结点的平衡因子,9-39,9.3 动态查找表,例1：给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见下图。,9-40,9.3 动态查找表,9-41,9.3 动态查找表,9-42,9.3 动态查找表,平衡二叉树的查找及性能分析平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。,9-43,9.3 动态查找表,例2，对例1给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的。得到的平衡二叉树见下座图，得到的二叉排序树见下右图。,从右图的二叉排序树可知，查找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-44,9.4 哈希表,9.4.1 哈希表哈希(Hash)表又称散列表,是一种直接计算记录存放地址的方法，它在关键码与存储位置之间直接建立了映象。哈希函数哈希函数是从关键字空间到存储地址空间的一种映象哈希函数在记录的关键字与记录的存储地址之间建立起一种对应关系。可写成：addr(ai)=H(keyi)H()为哈希函数keyi是表中元素ai关键字,addr(ai)是存储地址,9-45,9.4 哈希表,哈希查找哈希查找也叫散列查找，是利用哈希函数进行查找的过程首先利用哈希函数及记录的关键字计算出记录的存储地址然后直接到指定地址进行查找不需要经过比较，一次存取就能得到所查元素哈希冲突不同的记录，其关键字通过哈希函数的计算，可能得到相同的地址把不同的记录映射到同一个散列地址上，这种现象称为冲突,9-46,9.4 哈希表,哈希表定义根据设定的哈希函数 H(key)和所选中的处理冲突的方法将一组关键字映象到一个有限的、地址连续的地址集上以关键字在地址集中的“象”作为相应记录在表中的存储位置如此构造所得的查找表称之为“哈希表”。哈希函数均匀性哈希函数实现的一般是从一个大的集合（部分元素，空间位置上一般不连续）到一个小的集合（空间连续）的映射一个好的哈希函数，对于记录中的任何关键字，将其映射到地址集合中任何一个地址的概率应该是相等的即关键字经过哈希函数得到一个“随机的地址”,9-47,9.4 哈希表,9.4.2 哈希函数要求哈希函数应是简单的，能在较短的时间内计算出结果哈希函数的定义域必须包括需要存储的全部关键字，如果散列表允许有 m 个地址时，其值域必须在 0 到 m-1 之间 散列函数计算出来的地址应能均匀分布在整个地址空间中,9-48,9.4 哈希表,哈希函数(直接定址法)直接定址法中，哈希函数取关键字的线性函数 H(key)=a key+b其中a和b为常数直接定址法举例H(key)=key-2005131000,9-49,9.4 哈希表,直接定址法特性直接定址法仅适合于地址集合的大小与关键字集合的大小相等的情况当a=1时，H(key)=key，即用关键字作地址在实际应用中能使用这种哈希函数的情况很少,9-50,9.4 哈希表,哈希函数(数字分析法)假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)分析关键字集中的全体从中提取分布均匀的若干位或它们的组合作为地址。,9-51,9.4 哈希表,数字分析法举例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析：只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈希地址,9-52,9.4 哈希表,数字分析法特性数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况数字分析法完全依赖于关键码集合。如果换一个关键码集合，选择哪几位要重新决定。,9-53,9.4 哈希表,哈希函数(平方取中法)以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”同时平方值的中间各位又能受到整个关键字中各位的影响。,9-54,9.4 哈希表,平方取中法举例此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址。标识符的八进制内码表示及其平方值,标识符 内码 内码的平方 散列地址A 01 01 001A1 0134 20420 042B 02 4 004 DMAX 04150130 21526443617100 443DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236AMAX1 0115013034 3454246522151420 652,9-55,9.4 哈希表,平方取中法特性平方取中法是较常用的构造哈希函数的方法适合于关键字中的每一位都有某些数字重复出现且频度很高的情况中间所取的位数，由哈希表长决定,9-56,9.4 哈希表,哈希函数(折叠法)将关键字分割成位数相同的若干部分(最后部分的位数可以不同)，然后取它们的叠加和(舍去进位)为哈希地址。移位叠加:将分割后的几部分低位对齐相加间界叠加:从一端沿分割界来回折送，然后对齐相加,9-57,9.4 哈希表,折叠法举例：关键字为：0442205864，哈希地址位数为4折叠法特性折叠法适合于关键字的数字位数特别多，而且每一位上数字分布大致均匀的情况,9-58,9.4 哈希表,哈希函数(除留余数法)取关键字被某个不大于哈希表长m的数p除后所得余数为哈希地址H(key)=key MOD p(pm)m为表长 p为不大于m的素数或是不含20以下的质因子哈希函数(除留余数法p值)给定一组关键字为:12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为:3,3,0,6,6,3可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能除留余数法特性除留余数法是一种最简单、最常用的构造哈希函数的方法可以对关键字直接取模(MOD)，也可在折叠、平方取中等运算之后取模。,9-59,9.4 哈希表,9.4.3 处理冲突法“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。处理冲突的方法主要有三种：开放定址法再哈希法链地址法,9-60,9.4 哈希表,处理冲突的方法(开放定址法)为产生冲突的地址 H(key)求得一个空的地址序列：H0,H1,H2,Hs，1sm-1Hi=H(key)+di MOD m(i=1,2,s)H(key)为哈希函数m为哈希表长当di取1,2,3,m-1时，称这种开放定址法为线性探测再散列。,9-61,举例：在长度为11的哈希表中已填有关键字分别为17，60和29的记录（哈希函数H(key)key MOD 11），现有第四个记录，其关键字为38，由哈希函数得到的哈希地址为5，产生冲突。线性探测再散列：得到下一个地址6，仍冲突；再求下一个地址7，仍冲突；直到哈希地址为8的位置（“空”）时止。二次探测再散列：应填入序号为4的位置。伪随机探测再散列：伪随机数列9,应填入序号为2的位置。,9.4 哈希表,9-62,9.4 哈希表,用开放定址处理冲突时，关键字为38的记录插入前后的哈希表,9-63,9.4 哈希表,处理冲突的方法(再哈希法)Hi=RHi(key)(i=1,2,k)其中，R、Hi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。再哈希法特点：不易产生聚集，但增加计算时间处理冲突的方法(链地址法)将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址区间0,m1上，则设立一个指针型向量：Chain Chain Hashm;其每个分裂的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为Chain Hashm的链表中。在链表中的插入位置可以在表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。,9-64,9.4 哈希表,举例：给定关键字集合19,01,23,14,55,68,11,82,36，设定哈希函数H(key)=key MOD 11(表长=11)表后插入查找不成功，再插入新结点时，用表后插入方法较好,9-65,9.4 哈希表,举例：给定关键字集合19,01,23,14,55,68,11,82,36，设定哈希函数H(key)=key MOD 11(表长=11)表头插入给定关键字集合，逐步生成哈希表时，用表头插入方法较好,9-66,9.4 哈希表,9.4.4 哈希表的实现假设哈希函数为关键字求模运算，哈希表用拉链法解决冲突，其结构可以定义如下：,#define LEN 31/表长LEN最好为质数typedef struct node int data;struct node*next;node;struct node HashTabLEN;,9-67,9.4 哈希表,哈希表的实现哈希函数hash()返回值为哈希表地址:查找过程对于给定值key，计算哈希地址 p=hash(Key)若HashTabp.next=NULL，则查找不成功若HashTabp.next.data=key，则查找成功否则“求下一地址”，再进行比较,int hash(int key)retAddr=key MOD LEN;return(retAddr);,9-68,9.4 哈希表,查找函数search()若找到key，返回其结点指针；否则将其插入表中再返回其结点指针链地址法解决冲突，表头插入,node*search(int key)i=hash(key);p=HashTabi.next;while(p!=NULL)if(p.data=key)return(p);p=p.next;q=malloc(sizeof(node);/表头插入q.data=key;q.next=HashTabi.next;HashTabi.next=q;return(q);,9-69,9.4 哈希表,9.4.5 哈希查找的性能分析哈希查找按理论分析，它的时间复杂度应为O(1)，它的平均查找长度应为ASL=1，但实际上由于冲突的存在，它的平均查找长度将会比1大。下面将分析几种方法的平均查找长度。线性探查法的性能分析由于线性探查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的散列函数H及装填因子的值和该处理方法有关，这时的成功的平均查找长度为ASL=1/2(1+1/(1-)。链地址法的性能分析由于拉链法查找就是在单链表上查找，查找单链表中第一个结点的次数为1，第二个结点次数为2，其余依次类推。它的平均查找长度ASL=1+/2。,9-70,9.4 哈希表,哈希查找的性能分析(平均查找长度ASL)线性探测再散列的哈希表查找成功时：ASL()(1+1/(1-)二次探测再散列的哈希表查找成功时：ASL-(1/)ln(1-)链地址法处理冲突的哈希表查找成功时：ASL(1+/2),9-71,习题,本章习题参见教师网页：http:/,