《数据结构第八章.ppt》由会员分享，可在线阅读，更多相关《数据结构第八章.ppt（84页珍藏版）》请在课桌文档上搜索。
1、,数据结构(DATA STRUCTURE),计算机科学与技术学院,2,第九章 查找,基本概念静态索引结构 动态索引结构散列,3,基本概念,查找表：由同一类型的数据元素(记录)构成的集合。分为静态查找表和动态查找表两类静态查找表:仅对查找表进行查找操作,而不能改变的表动态查找表:对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。查找：简单地说,查找就是给定一个值 K，在含有众多数据元素的查找表中找出关键字等于给定值 K 的记录。,4,查找也是计算机中经常遇到的操作。特别是当问题所涉及的数据量相当大时，查找的效率就显得格外重要。查找运算的主要操作是关键字的比较，所以
2、，通常把查找过程中需要执行的关键字的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。,5,9.1 静态查找表,9.1.1 顺序表的查找 又称线性查找，是最基本的查找方法之一基本思想：从表的一端开始，向另一端逐个按给定值 k 与关键码进行比较，若找到，表明查找成功；若直到所有元素都比较完毕，仍未找到与k 相同的关键码，则表明查找失败。适用的数据结构：顺序表、线性链表算法实现：静态查找表的顺序存储结构：typedef struct ElemType*elem；/*数组基址*/int length；/*表长度*/SSTable；,6,算法：int S_search(SSTabl
3、e ST，KeyType k)ST.elem0.key=k；/作为监测哨兵*/for(i=ST.length;ST.elemi.key!=k；i-)；/*从表尾端向前找*/return i；/*返回k元素在数组中的下标，否则返回0*/,设置哨兵的好处:在顺序表中总可以找到待查结点。否则，必须将判断条件 i=0 加进 for 语句。,7,4)性能分析：,分析查找算法的效率,通常用平均查找长度ASL衡量在查找成功时，平均查找长度ASL是指为确定数据元素在表中的位置所进行的关键字比较次数的期望值。其中：Pi为查找表中第i个数据元素的概率；Ci为查找表中第 i 个元素所需比较次数。查找成功时，顺序查找
4、的平均查找长度为：查找不成功时，关键码的比较次数总是n+1次,8,9.1.2 有序表的查找,有序表即是表中数据元素按关键码升序或降序排列；二分查找又称为折半查找 适用的数据结构：顺序存储的有序表基本思想:在有序表中,取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。,9,假设静态查找表ST递增有序，折半查找过程为：low=1；high=length；/设置初始区间 若lowhigh,返回
5、查找失败信息/当前查找区间为空，查找失败 若lowhigh，mid=(low+high)/2;/取中点 a.若 k ST.elemmid.key，low=mid+1；转/查找在右半区进行 c.若 k=ST.elemmid.key，返回元素在表中位置/查找成功,3)算法实现,10,举例,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,查找K=85的过程（查找失败）,05 13 19 21 37 56 64 75 80 88 92,11,4)性能分析
6、：,从折半查找过程看，以表的中点为比较对象，并以中点将表分割为两个子表，对定位到的子表继续这种操作。因而对表中每个数据元素的查找过程可用二叉树描述，称此描述查找过程的二叉树为判定树。查找表中任一元素的过程，即是判定树中从根到该元素结点路径上各结点关键码的比较次数，也即该元素结点在树中的层次数。,12,例：05 13 19 21 37 56 64 75 80 88 92,判定树：,借助于判定树很容易求得二分查找的平均查找长度。设结点总数为：树中第 k 层上的结点个数不超过：,13,因此，在等概率假设下，二分查找的平均查找长度为：二分查找的算法复杂度为：优点：查找的效率较高 缺点：要求被查找序列事
7、先按关键字排好序，而排序本身是一种很费时的运算；另外，二分查找只适用于顺序存储结构。,14,9.1.3 索引顺序表的查找(分块查找),是一种性能介于顺序查找和二分查找之间的查找算法1)数据结构设置：将长度为 n 的查找表Rn均分成b块(子表),要求:每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即要“分块有序”。建立索引表IDb，其中IDi存放第 i 块中的最大关键字及该块在查找表中的起始位置。由于表Rn分块有序，所以索引表IDb递增有序。,15,首先查找索引表ID，以确定待查结点在哪一分块(由于索引项按关键码字有序，可用顺序或折半查找)然后，在已确定的那一块
8、中进行顺序查找。3)算法实现数据结构定义：长度为 n 的查找表采用顺序表：SSTable ST索引表的结构 typedef struct/*索引表结点结构*/keytype key;int addr;IDtable;IDtabel IDb;/*索引表*/,2)算法基本思想：,16,4)性能分析：,分块查找由索引表查找和子表查找两步完成，故整个算法的平均查找长度是两次查找的平均查找长度之和。ASL=ASL索引表+ASL子表 设查找表长为 n,分为 b个子表,每块中均有s=n/b 个元素 若用二分查找来确定块，则分块查找的平均查找长度约为：若用顺序查找来确定块，则分块查找的平均查找长度约为：对于后
9、一种情况，当 时，平均查找长度为极小值。在实用中，可根据表的具体情况进行分块。,17,分块查找的性能介于顺序查找和二分查找之间，例如对长度为10000的线性表,它们的平均查找长度分别是:顺序查找：ASL=(n+1)/2=5000 分块查找：ASL=log2(b+1)-1+(S+1)/2 57 或 ASL=(b+1)/2+(S+1)/2=101 二分查找：ASL=log2(n+1)-1 14 优点：把线性表分成若干逻辑子表，提高了查找效率 缺点：增加了一索引存储空间，和将初始表进行分块的运算,18,9.2 动态查找表,9.2.1 二叉排序树(Binary Search Tree)定义:二叉搜索树
10、或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同。左子树(如果存在)上所有结点的关键码都小于根结点的关键码。右子树(如果存在)上所有结点的关键码都大于根结点的关键码。左子树和右子树也是二叉排序树。2)存储结构:二叉链表,19,几个二叉排序树的例子,20,3)二叉排序树上的查找算法,在二叉排序树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。假设想要在二叉排序树中搜索关键字为 x 的元素，搜索过程从根结点开始。如果给定值等于根结点的关键码，则搜索成功。如果给定值小于根结点的关键码，则继续递归搜索根结点的左
11、子树；否则，递归搜索根结点的右子树。,21,二叉搜索树的搜索 插入新结点88,每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。,22,查找过程走了一条从根到该元素结点路径，比较次数等于该结点所在层次数。其中:Pi 查找某元素的概率,等概率情况下 1/n Ci 该元素结点在二叉排序树中的层次数 最坏情况:单支树(树的高度达到最大)ASL=(n+1)/2 最好情况:与二叉判定树相似 ASL=log2(n+1)-1 平均：O(nlog2n),4)查找分析,23,5)二叉排序树的插入,在插入之前，先使用搜索算法在树中检查要插入元素是否已经存在。搜索成功:树中已有这个元素，不再
12、插入。搜索不成功:把新元素加到搜索停止的地方。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树。,24,6）二叉排序树的删除,在二叉搜索树中删除一个结点时，必须将因删除结点而断开的二叉链表重新链接起来，同时确保二叉搜索树的性质不会失去。为保证在执行删除后，树的搜索性能不至于降低，还需要防止重新链接后树的高度增加。删除叶结点，只需将其双亲结点指向该结点的指针清空，再释放它即可。被删结点无右子树，可以拿该结点左孩子结点顶替它的位置，再释放它。被删结点无左子树，
13、可以拿该结点右孩子结点顶替它的位置，再释放它。,25,被删结点左、右子树都存在，有两种处理方式：用该结点的左孩子代替该结点，将其右子树插入到中序遍历该结点左子树时最后访问结点的右孩子上。用该结点的直接前驱或直接后继代替该结点，在处理其前驱或后继的删除问题。算法：P230-231,26,27,29,9.2.2 AVL树 高度平衡的二叉排序树,1）AVL树的定义,一棵AVL树或者是空树，或者是具有下列性质的二叉排序树：它的左子树和右子树都是AVL 树，且左子树和右子树的高度之差的绝对值不超过 1。,高度不平衡的二叉搜索树 高度平衡的二叉搜索树,30,结点的平衡因子(BF-Balance Facto
14、r):任一结点的左子树的高度减去右子树的高度所得的高度差称为该结点的平衡因子BF。根据AVL树的定义，任一结点的平衡因子只能取-1，0 和 1。如果一个结点的平衡因子的绝对值大于1，则这棵二叉排序树就失去了平衡，不再是AVL树。如果一棵二叉排序树是高度平衡的，它就成为 AVL树。如果它有 n 个结点，其高度可保持在O(log2n)，平均查找长度也可保持在O(log2n)。,31,2)如何构造平衡二叉排序树,基本思想：在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入而破坏了树的平衡性。若是,则找出其中最小不平衡子树，在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的
15、连接关系,以达到新的平衡。最小不平衡子树：以离插入结点最近，且平衡因子绝对值大于 1 的结点作为根的子树。假设二叉排序树的最小不平衡子树的根结点为 A，则有四种形态需要调整,32,LL型右旋,33,RR型 左旋,E,34,LR型先左旋后右旋,35,RL型先右旋后左旋,36,9.2.3 B-树,为什么采用B_树和B+树：大量数据存放在外存中，由于海量数据，不可能一次调入内存,要多次访问外存。硬盘的驱动受机械运动制约，速度慢。主要矛盾变为减少访外次数。在1970年由R bayer和E macreight 提出用B_树作为索引组织文件。提高访问速度、减少时间。,E.G:用二叉树组织文件，当文件的记录
16、个数为 100000时,要找到给定关键字的记录，需访问外存17次(log100000),50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,37,一棵 m 阶B-树是一棵平衡的 m 路搜索树，它或者是空树，或者是满足下列性质的m叉树：树中每个结点至多有 m 棵子树。若根结点不是叶子结点至少有 2 棵子树。除根结点以外的所有非终端结点至少有 m/2棵子树。所有的非终端结点中包含以下信息数据：（n，A0，K1，A1，K2，Kn，An）其中:Ki(i=1,2,n)为关键字,且KiKi+1,Ai为指向子树根结点的指针(i=0
17、,1,n),且指针Ai-1所指子树中所有结点的关键码均小于Ki(i=1,2,n),An所指子树中所有结点的关键码均大于Kn,m/21nm1,n为关键码的个数。所有的叶子结点都出现在同一层次上,且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。,例如：m=4 阶 B_ 树,39,例:一棵5 阶的 B-树，其深度为 4。,一棵 5 阶的 B-树,40,1)B_树的搜索算法,B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表:在到达某个结点时，先在(多关键码的)有序表中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的
18、子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码，查找失败。即在B-树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。,41,42,B_树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。即 在B-树上找结点；在结点中找关键码。因此，B_树的搜索时间与B_树的阶数m 和 B_树的高度 h 直接有关。在B_树上进行搜索，搜索成功所需的时间取决于关键码所在的层次，搜索不成功所需的时间取决于树的高度。需要了解树的高度h 与树中的关键码个数 N 之间的关系。,查找分析,43,2)B_树的插入,关键字插入在最底层某个非终端结点中添加一个关键码。若该结点上
19、关键字个数不超过 m-1个，则可直接插入到该结点上；否则，该结点上关键码个数将达到m个，要进行调整，即结点的“分裂”。实现结点“分裂”的方法:关键码加入结点后，将结点中的关键码分成三部分，前后两部分成为两个结点，中间的一个结点将其插入到父结点中。若插入父结点而使父结点中关键码个数超过m-1，则父结点继续分裂，直到插入某个父结点，其关键码个数小于m。可见，B-树是从底向上生长的。,44,例：从空树开始逐个加入关键码建立3阶B_树,45,46,3)B_树的删除,在B_树上删除一个关键码时，首先需要找到这个关键码所在的结点，从中删去这个关键码。删除分两种情况：(1)删除最底层结点中关键码(2)删除非
20、底层结点中关键码,47,(1)在最底层结点中删除有 3 种情况,a)若结点中关键码个数大于m/2-1，直接删去。,48,b)被删关键码所在结点删除前关键字个数等于m/2-1，而与该结点相邻的右兄弟(或左兄弟)结点的关键字个数大于 m/2-1，则可按以下步骤调整该结点、右兄弟(或左兄弟)结点以及其双亲结点,49,例：结点联合调整,50,例：,51,c)被删除关键码所在结点和其相邻兄弟结点的关键码个数均等于 m/2-1，则必须按以下步骤合并这两个结点。合并结点过程中，双亲结点中关键码个数减少了。若双亲结点的关键码个数小于m/2-1，则该双亲结点应从树中删除，重复上述合并步骤。最坏情况下这种结点合并
21、处理要自下向上直到根结点。,52,例：结点合并,53,例：结点合并,54,(2)删除非底层结点中关键码,若所删除非底层结点中关键码Ki，则可用指针Ai 所指子树中的最小关键码 X 替代Ki，然后在相应结点中删去X，直到这个 X 在最底层结点上，即转为(1)的情形。,55,例：删除非底层结点中关键码,56,结点合并与调整,57,58,59,9.2.4 B+树,B+树可以看作是B_树的一种变形，在实现文件索引结构方面比B_树使用得更普遍。一棵m阶的 B+树和m阶的 B-树的差异在于：有 n 棵子树的结点中含有 n 个关键码；所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针,且
22、叶子结点本身依关键码的大小自小而大的顺序链接。所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键码。,60,例:一棵4阶的B+树,一棵 4 阶的B+树,61,通常在B+树上有两个头指针，一个指向根结点，另一个指向关键码最小的叶子结点。在B+树上进行随机搜索、插入和删除的过程基本上与B_树类似。只是在搜索过程中，若非终端结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针向下，一直查到叶结点上的这个关键码。在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。,1)B+树的搜索,62,B+树的插入仅在叶结点上进行。每插入一个关键码后都要判断结点中
23、的子树棵数是否超出范围。,2)B+树的插入,63,B+树的删除仅在叶结点上进行。当在叶结点上删除一个关键码后，结点中子树棵数不少于 m/2，属于简单删除，其上层索引可以不改变。若删除关键码是该结点的最大关键码,因其上层副本只起了一个引导搜索的“分界关键码”的作用,所以上层副本仍可保留。如果在叶结点中删除一个关键码后，该结点中的子树棵数 n 小于结点子树棵数的下限 m/2，必须做结点的调整或合并工作。结点的调整与合并过程亦和B-树类似。,3)B+树的删除,64,9.3 哈希表（散列 Hashing),9.3.1 什么是哈希表散列(hashing)：是一种存储和查找方法。其基本思想：在记录的关键字
24、 K 与记录的存储为置之间建立一个确定的对应关系f。存储时，使关键字为 K 的记录存入函数值 f(k)所指的存储为置中。查找时，再根据要查找的关键字K，用同样的函数计算出存储地址，然后到相应单元中去取要找的记录。哈希方法中使用的转换函数称为哈希函数(杂凑函数)；按这个思想构造的表称为哈希表(杂凑表)。,65,冲突：若某个哈希函数H，key1key2，而H(key1)=H(key2)，即经过哈希函数变换后，可能将不同的关键字映射到同一个哈希地址上，这种现象称为冲突(Collision)，映射到同一哈希地址上的关键码称为同义词。哈希函数可以灵活设置，最好是一一对应函数，但冲突不可能避免，只能尽可能
25、减少。哈希方法需要解决以下两个问题：构造好的哈希函数：对于给定的一个关键字集合，选择一个计算简单且地址分布比较均匀的哈希函数，避免或尽量减少冲突制定解决冲突的方案,66,9.3.2 哈希函数的构造方法,1）构造哈希函数时的几点要求(构造原则)散列函数的定义域必须包括需要存储的全部关键字，如果散列表允许有 m 个地址时,其值域必须在 0 到 m-1 之间。散列函数计算出来的地址应能均匀分布在整个地址空间中：若 key 是从关键码集合中随机抽取的一个关键码，散列函数应能以同等概率取0 到 m-1 中的每一个值（即尽量是一一对应函数）。散列函数的运算尽可能简单，能在较短的时间内计算出结果。,67,2
26、）构造方法举例,直接定址法:取关键码的某个线性函数值作为散列地址:Hash(key)a*key+b a,b为常数 这类散列函数是一对一的映射,一般不会产生冲突。但是,它要求散列地址空间的大小与关键码集合的大小相同。,68,数字分析法:设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r 种不同符号在各位上出现频率不一定相同，可能在某些位上分布均匀；在某些位上分布不均匀。可根据散列表大小，选取其中各种符号分布均匀的若干位作为散列地址。数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键码集合，选择哪几位要重新决定。,69,除留余数法：
27、设散列表中允许的地址数为 m,取一个不大于 m，但最接近于或等于 m 的质数 p,利用以下公式把关键码转换成散列地址。散列函数为：hash(key)=key%p p m,70,乘余取整法:使用此方法时，先让关键码 key 乘上一个常数 A(0 A 1)，提取乘积的小数部分。然后再用整数 n 乘以这个值，对结果向下取整做为散列地址。散列函数为:hash(key)=n*(A*key%1)其中,“A*key%1”表示取 A*key 小数部分:A*key%1=A*key-A*key,71,平方取中法：先计算构成关键字的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。,72,折叠法：
28、把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。,73,9.3.3 处理冲突的构造方法,处理冲突就是为发生地址冲突的记录找到一个空的Hash 地址。1）开放地址法：由关键字得到的哈希地址一旦产生了冲突（即该地址已经存放了数据元素)，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。找空哈希地址方法很多，下面介绍三种：线性探测法(Linear Probing)Hi=(Hash(key)+di)mod m(1i m)其中：Hash(key
29、)为哈希函数 m 为哈希表长度 di 为增量序列 1，2，m-1，且di=i,74,线性探测法可能使第 i 个哈希地址的同义词存入第 i+1 个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第 i+2 个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，降低了查找效率。堆积(二次聚集)：在处理冲突的过程中，两个第一哈希地址不同的记录争夺同一后继地址的现象。可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。,75,二次探测法(quadratic probing),Hi=(Hash(key)di)mod m 其中：Hash(key)为哈希函数M 为哈希表长度，m
30、 要求是某个 4k+3 的质数(k是整数)Di 为增量序列 12,-12,22,-22,q2,-q2 且 q(m-1)随机探测法:di为随机数序列,76,2)再哈希法（双散列法）,Hi=ReHashi(key)其中 ReHashi(key)是不同于Hash(key)的哈希函数。再哈希法先用第一个函数 Hash(key)对关键字计算哈希地址，一旦产生地址冲突，再用第二个函数ReHash(key)计算哈希地址Rehash()的取法很多。例如,当 m 是质数时,可定义 ReHash(key)=key%(m-2)+1 ReHash(key)=key/m%(m-2)+1优点：不容易产生“堆积”缺点：增加
31、了计算时间,77,3）链地址法,查找时按 H(key)地址得到链表表头地址，查找相应的单链表。数据结构：散列表是指针向量，其长度由散列表值域决定。例：关键字序列为 47,7,29,11,16,92,22,8,3,50,37,89,94,21：哈希函数为 Hash(key)=key mod 11,设哈希函数得到的哈希地址域在区间0,m-1上，以每个哈希地址作为一个指针指向一个链，建立m个空链表,由哈希函数对关键字转换，映射到同一哈希地址 i 的同义词加入到同一链表中。,78,4）建立公共溢出区：,设哈希函数产生的哈希地址集为0,m-1,则分配两个表：一个基本表 ElemType base_tbl
32、 m；每个单元只能存放一个元素；一个溢出表 ElemType over_tbl k；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中（即所有发生冲突的关键字都填入公共溢出区）。,79,1）哈希表的查找在哈希表上进行查找的过程和哈希造表的过程基本一致。过程：给定关键字K，根据造表时设定的哈希函数求得哈希地址。若此位置上无记录，则查找失败。否则，比较关键字若相等，查找成功若不等，按造表时设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为“空”或表中所填记录等于给定值时为止。,9.3.4 哈希表的查找及其分析,80,散列表是一种直接计算记录存放地址的方法，它在关键字
33、与存储位置之间直接建立了映象。当选择的散列函数能够得到均匀的地址分布时，在搜索过程中可以不做多次探查。但由于很难避免冲突，使得散列表的查找过程仍然是一个给定值和关键字比较的过程。因此，仍需以平均查找长度ASL作为衡量哈希表查找效率的度量。,2）查找分析,81,查找过程中，关键字的比较次数取决于三个因素：哈希函数是否均匀；处理冲突的方法；哈希表的装填因子。若设 是哈希表的装填因子：散列表的搜索性能(即平均搜索长度)依赖于散列表的装填因子。哈希表的装填因子 表明表中的装满程度。越大说明表越满，再插入新元素时发生冲突的可能性越大。,82,本章小结,静态查找表 顺序搜索算法、分析 折半搜索算法、分析 分块搜索算法、分析动态查找表二叉排序树(定义、搜索、ASL、插入、删除）平衡的二叉排序树（定义、构造）B_树与B+树(定义、插入、删除）,83,哈希表 哈希函数的构造 处理冲突的方法线性探测法二次探测法 哈希造表与查找分析,84,谢谢大家！,
