数据结构第7章查找更新.ppt

B-树遍历面临的问题 假设下图所示的这棵B树的每个结点都属于硬盘的不同页面,为了中序遍历所有的元素,就得遵循”页面2→页面1→页面3→页面1→页面4→页面1→页面5”这样的顺序,频繁地访问硬盘,导致效率很低.如何解决这个问题呢? * * 3 3 5 8 n K1 K2 K3 2 1 2 2 4 2 6 7 1 9 页面1 页面2 页面3 页面4 页面5 A0 A1 A2 A3 B+树 为了解决B-树面临的遍历等基本问题，在原有B树结构基础上加了新的元素组织方式，于是产生了B+树。 B+树是应文件系统所需而设计的一种B树的变形树，严格意义上已经不是我们数据结构课上定义的树了。 一棵B阶的B+树和m阶的B树的差异在于： 有n棵子树的结点中包含有n个关键字； 所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接； 所有分支结点可以看成是索引，结点中仅含有其子树种的最大（或最小）关键字。 注意：B+树的插入、删除过程与B树类似，只不过插入和删除操作都需要在叶子结点进行。 * * 3 5 8 1 2 3 4 5 6 7 8 9 9 内容提要 查找概论 静态查找表 动态查找表 哈希表 * * 散列表检索（一） 在已经介绍过的线性表、树等数据结构中，记录存储在结构中的相对位置是随机的，因而相应的检索是通过若干次的比较以寻找指定的记录。接下来将介绍一种新的存储结构——散列存储，它既是一种存储方式，又是一种常见的检索方法。 * * U S k1 k2 k3 k5 k4 0 H(k1) H(k5) H(k2)=H(k4) H(k3) H(km-1) 散列存储的基本思想是以关键码的值为自变量，通过一定的函数关系（称为散列函数，或称哈希(Hash)函数），计算出对应的函数值来，以这个值作为结点的存储地址，将结点存入计算得到的存储单元里去。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。关键字对应的记录存储位置称为散列地址。 散列表检索（二） 散列过程： 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。 当查找记录时，通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。 散列技术的特点 记录间不存在逻辑关系，只和关键字有关； 最适合求解查找与给定值相等的记录，不适合范围查找，或者那种同一个关键字对应很多记录的情况。 散列表实例：已知线性表的关键字集合为： S = {and, begin, do, end, for, go, if, then, until } 则可设哈希表为： char HT[26][8] 哈希函数H(key)的值，可取关键字key中第一个字母在字母表中的序号（0~25），即 H(key) = key[0]- ‘a’ * * 散列技术的冲突问题 散列存储中经常会出现对于两个不同关键字xi，xj，却有H（xi）=H（xj），即对于不同的关键字具有相同的存放地址，这种现象称为冲突或碰撞。碰撞的两个（或多个）关键字称为同义词（相对于函数H而言）。 “负载因子”?反映了散列表的装填程度，其定义为： 当?1时冲突是不可避免的。因此，散列存储必须考虑解决冲突的办法。 综上所述，对于Hash方法，需要研究下面两个主要问题： （1）选择一个计算简单，并且产生冲突的机会尽可能少 的Hash函数； （2）确定解决冲突的方法。 * * ?= 散列表中结点的数目 基本区域能容纳的结点数 U S k1 k2 k3 k5 k4 0 H(k1) H(k5) H(k2)=H(k4) H(k3) H(km-1) 散列函数的构造 * * 构造哈希函数时的几点要求： 哈希函数的定义域必须包括需要存储的全部关键字，如果哈希表允许有 m 个地址时, 其值域必须在 0 到 m-1 之间。 哈希函数计算出来的地址应能均匀分布在整个地址空间中：若 key 是从关键字集合中随机抽取的一个关键字，哈希函数应能以同等概率取 0 到 m-1 中的每一个值。 哈希函数应是简单的，能在较短的时间内计算出结果。 散列函数的构造方法（一） * * （1）除留余数法 选择一个适当的正整数P，用P去除关键字，取所得得余数作为散列地址，即： hash ( key ) = key % p p ? m 这个方法的关键是选取适当的P。选择P最好不要是偶数，也不要是基数的幂。一般地选P为小于或等于散列表长度m的某个最大质数比较好。例如 m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1