问问天笔记
数据结构 第 8 / 9 篇

第八章 查找

4,273 字约 11 分钟

一 基本概念

填空题

查找同排序一样，也有内查找和外查找之分：若整个查找过程都在内存中进行，则称之为内查找；反之，称之为外查找。

填空题，解答题

由于查找运算的主要操作是关键字的比较，因此，通常把查找过程中的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度（Average Search Length， ASL）的计算公式定义为：

ASL = ∑i=1nPiCi\sum_{i=1}^n P_iC_i

其中，n为结点个数，Pi是查找第i个结点的概率。若不特别说明，均认为查找每个结点是等概率的，即P1=P2=…=Pn=1/n；Ci为找到第i个结点所需要比较的次数。若查找每个元素的概率相等，则平均查找长度计算公式可简化为

ASL = 1/n [∑i=1nCi\sum_{i=1}^n C_i]

二 顺序表的查找

解答题

顺序表查找（Sequential Search）又称线性表查找，是一种最简单和最基本的查找方法。其基本思想是：从表的一端开始，顺序扫描线性表，依次把扫描到的记录关键字与给定的值k相比较，若某个记录的关键字等于k，则表明查找成功，返回该记录所在的下标；若直到所有记录都比较完，仍未找到关键字与k相等的记录，则表明查找失败，返回0值。

填空题

如果查找成功和不成功机会相等，那么顺序查找的平均查找长度：

((n+1)/2 + (n+1))/2 = 3(n+1)/4

单选题

二分查找(Binary Search)又称折半查找，是一种效率较高的查找方法。二分查找要求查找对象的线性表必须是顺序存储结构的有序表。

单选题，填空题，解答题

二分查找的过程是：首先将待查的k值和有序表R[1…n]的中间位置mid上的记录的关键字进行比较，若相等，则查找成功，返回该记录的下标mid；否则，若R[mid].key > k，则k在左子表R[1..mid-1]中，接着再在左子表中进行二分查找即可；否则，若R[mid].key < k，则说明待查记录在右子表R[mid+1..n]中，接着只要在右子表中进行二分查找即可。这样，经过一次关键字的比较，就可缩小一半的查找空间，如此进行下去，直到找到关键字为k的记录或者当前查找区间为空时（即查找失败）为止。

填空题

索引顺序查找又称为分块查找，是一种介于顺序查找和二分查找之间的查找方法。它要求按如下的索引方式来存储线性表：将表R[1..n]均分成b块，前B1块中的结点个数为s=[n/b]，第b块的结点数<=s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块的最小关键字，即要求表是“分块有序”的；抽取各块中的最大关键字及其起始位置构成一个索引表ID[1…b]，即ID[i](1<=i<=b)中存放着第i块的最大关键字及该块在表R中的起始位置，显然，索引表是按关键字递增有序的。

单选题

  1. 分块查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。查找块有两种方法，一种是二分查找，若按此方法来确定块，则分块查找的平均查找长度为：
ASLblk=ASLbin+ASLseq=log2(b+1)−1+(s+1)/2 ～=log2(n/s+1)+s/2ASL_blk = ASL_bin + ASL_seq = log_2(b+1) - 1 + (s + 1)/2 ~～= log_2(n/s+1) + s/2

另一种是顺序查找，此时的分块查找的平均查找长度为：

ASLblk=(b+1)/2+(s+1)/2=(s2+2s+n)/(2s)ASL_blk = (b+1)/2 + (s+1)/2 = (s^2 + 2s + n)/(2s)
  1. 顺序查找，二分查找和分块查找三种查找算法的时间复杂度分别为：O(n)，O(log2n)，O(根号n)。

三 树表的查找

单选题，解答题

二叉排序树（Binary Sort Tree，BST）又称二叉查找树，是一种特殊的二叉树，它或者是一棵空树，或者是具有下列性质的二叉树：

  1. 若它的右子树非空，则右子树上所有结点的值均大于根结点的值。
  2. 若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
  3. 左右子树本身又各是一棵二叉排序树。

二叉排序树的另一个重要性质：按中序遍历二叉排序树所得到的遍历序列是一个递增有序序列。

单选题，填空题

一棵m(m>=3)阶的B树，或为空树，或为满足下列性质的m叉树：

  1. 每个结点至少包含下列信息域：（n. p0,k1,p1,k2,…,kn,pn)，其中，n为关键字的个数；ki(1<=i<=n)为关键字，且ki<ki+1(i<=i<=n-1)；pi(0<=i<=n)为指向指向子树根结点的指针，且pi所指向子树中所有结点的关键字均小于ki+1，pn所指子树中所有结点关键字均大于kn。
  2. 树中每个结点至多有m棵子树。
  3. 若树为非空，则根结点至少有一个关键字，至多有m-1个关键字。因此，若根结点不是叶子，则它至少有两棵子树。
  4. 所有的叶子结点都在同一层上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向它们的指针均为空），叶子的层数为树的高度h。
  5. 每个非根结点中所包含的关键字个数满足：[m/2]-1<=n<=m-1。因为每个内部结点的度数正好是关键字总数加1，所以，除根结点之外的所有非终端结点（非叶子结点的最下层的结点称为终端结点）至少有[m/2]棵子树，至多有m棵子树。

单选题，填空题

B+树是一种常用语文件组织的B树的变形树。一棵m阶的B+树和m阶的B树的差异在于：

  1. 有k个孩子的结点必含有k个关键字。
  2. 所有的叶子结点中包含了关键字的信息及指向相应结点的指针，且叶子结点本身依照关键字的大小自小到大顺序链接。
  3. 所有非终端结点可看成是索引部分，结点中仅含有其子树（跟结点）中的最大关键字（或最小）关键字。

四 散列表查找

填空题

散列存储的基本思想是：以线性表中的每个元素的关键字key为自变量，通过一种函数H(key)计算出函数值，把这个函数值解释为一块连续存储空间的单元地址（即下标），将该元素存储到这个单元中。散列存储中使用的函数H(key)称为散列函数或哈希函数，它实现关键字到存储地址的映射(或称转换)。H(key)的值称为散列地址或哈希地址，使用的数组空间是线性表进行散列存储的地址空间，所以称之为散列表或哈希表。

单选题，填空题，常用的散列函数的构造方法有：

  1. 直接地址法，直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为 H(key)=key + C 。在使用时，为了使散列地址与存储空间吻合，可以调整C。这种方法计算简单，并且没有冲突。它适合于关键字的分布基本连续的情况，若关键字分布不连续，空号较多，将会造成较大的空间浪费。
  2. 数字分析法，数字分析法是假设有一组关键字，每个关键字由n位数字组成，如k1, k2, …,kn。数字分析法是从中提取数字分布比较均匀的若干位作为散列地址。
  3. 除余数法，除余数法是选择一个适当的p(p<=散列表长m)去除关键字k，所得余数作为散列地址的方法。对应的散列函数H(key)为 H(k)=k%p 其中，p最好选取小于或等于表长m的最大素数。
  4. 平方取中法，平方取中法是取关键字平方的中间几位作为散列地址的方法，因为一个乘积的中间几位和乘数的每一位都相关，故由此产生的散列地址较为均匀，具体取多少位视实际情况而定。
  5. 折叠法，折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些)，段的位数取决于散列地址的位数，由实际情况而定，然后将它们的叠加和（舍去最高进位）作为散列地址的方法。折叠法又分为移位叠加和边界叠加。移位叠加是将各段的最低位对齐，然后相加；边界叠加则是将两个相邻的段沿边界来回折叠，然后对齐相加。

单选题，填空题，常用的解决处理冲突的方法有两类：开放定址法和拉链法。

  1. 开放定址法，开放定址法又分为线性探查法，二次探查法和双重散列法。开放定址法解决冲突的基本思想：使用某种方法在散列表中形成一个探查序列，沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点存入其中。假设散列空间为T[0…m-1]，散列函数为H(key)，开放定址法的一般形式为：

hi = (H(key) + di) %m(0<=i<=m-1)

其中di为递增序列，m为散列表长。h0=H(key)为初始探查地址(假设d0=0)，后续的探查地址依次是h1, h2, …, hm-1。

（1） 线性探查法。

线性探查法的基本思想是：将散列表T[0..m-1]看成一个循环向量，若初始探查的地址为d(即H(key)=d)，则后续探查地址的序列为：d+1，d+2，…，m-1, 0, 1, …, d-1。也就是说，探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1],…, T[m-1]，此后有循环到T[0]，T[1]，…,T[d-1]。分两种情况分析：一种运算是插入，若当前探查单元为空，则将关键字key写入空单元，若不空则继续后续地址探查，直到遇到空单元插入关键字，若探查到T[d-1]时仍未发现空单元，则插入失败(表满)；另一种运算是查找，若当前探查单元中的关键字值等于key，则表示查找成功，若不等，则继续后续地址探查，若遇到单元中的关键字值等于key时，查找成功，若再探查T[d-1]单元时，仍未发现关键字值等于Key，则查找失败。

（2） 二次探查法。

二次探查法的探查序列是 hi=（H(key)+-i^2）%m (0<=i<=m-1) 即探查序列为：d=H(key), d+1^2,d-1^2

,d+2^2, d-2^2,…。也就是说，探查从地址d开始，先探查T[d]，然后再依次探查T[d+1^2]，T[d-1^2]，T[d+2^2]，T[d-2^2]，…。

（3） 双重散列法。

双重散列法是几种方法中最好的方法，他的探查序列为：hi=（H(key)+i*H1(key)）%m (0<=i<=m-1) 即探查序列为：d=H(key), (d+1*H1(key))%m, (d+2*H1(key))%m,…。

  1. 拉链法，拉链法是把所有的同义词用单链表链接起来的方法。当存储结构是链表时，多采用拉链法。用拉链法处理冲突的办法是：把具有相同散列地址的关键字（同义词）值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初始值应为空指针。