数据结构第七章(汇总)

7 查找

7.1 查找的基本概念

查找表：是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着某种松散的关系，因此查找表是一种应用灵便的结构
- 查找表分两类
  - 静态查找表：仅做“查询“{检索)操作的查找表
  - 动态查找表：做“插入”和“删除”操作的查找表
关键字：关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。
- 主关键字：此关键字可以唯一地标识一个记录，则称此关键字为主关键字
- 次关键字：用以识别若千记录的关键字为次关键字。
查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）
- 若查找表中存在这样一个记录，则称 查找成功
  - 查找结果给出整个记录的信息，或指示该记录在查找表中的位置；
- 否则称 查找不成功
  - 查找结果给出“空记录”或“空指针”
- 查找经常进行的操作
  - 查询某个**“特定的”**数据元素是否在查找表中；
  - 检索某个**“特定的”**数据元素的各种属性；
  - 在查找表中插入一个数据元素；
  - 删除查找表中的某个数据元素；
查找算法的评价指标：
- 关键字的平均比较次数，也称平均查找长度。
  
  $\LARGE ASL=\sum\limits_{i=1}^np_ic_i$ (关键字比较次数的期望值)
  - n：记录的个数
  - pi：查找第i个记录的概率（通常认为pi=1/n）
  - ci：找到第i个记录所需的比较次数

7.2 线性表的查找

7.2.1 顺序查找

应用范围：
- 顺序表或线性链表表示的静态查找表
- 表内元素之间无序

数据元素类型定义

typedef struct{
    KeyType key;
    ……
}ElemType;

顺序表的定义

typedef struct{					//顺序结构表结构类型定义
    ElemType *R;				//表基址
    int length;					//表长
}SSTable;
SSTable ST;						//定义顺序表ST

顺序查找
1
2
3
4
5
int Search_seq(SSTable st,keytype key){
for(i=ST.length;i>=1;--i)
if (ST.R[i].key==key)return i;
return 0;
}
- 改进：把待查关键字key存入表头（”哨兵“）从后往前挨个比较，可免去查找过程中每一步都要检查是否查找完毕，加快速度
  1
  2
  3
  4
  5
  int search_seq(SSTable ST,KeyType key){
  ST.R[0].key=key;
  for(i=ST.length;ST.R[i].key!=key;--i);
  return i;
  }
  - 比较次数与key位置有关：
    - 查找第i个元素，需要比较n-i+1次
    - 查找失败，需要比较n+1次
  - 时间复杂度O(n)
    - 查找成功时的平均查找长度，设表中各记录查找概率相等
      
      $ASL=（1+2+……+n）/n=\dfrac {n+1}{2}$
  - 空间复杂度：一个辅助空间——O(1)
顺序查找的特点
- 优点：算法简单，逻辑次序无要求，且不同存储结构均适用
- 缺点：ASL太长，时间效率太低

7.2.2 折半查找

算法步骤
1. 设表长为n，low、high和mid分别指向待查元素所在区闻的上界，下界和中点，key为给定的要查找的值；
2. 初始时，令low=1，high=n，
3. 让k与mid指向的记录比较
  1. 若key==R[mid].KEY,查找成功
  2. 若key<R[mid].key,则high=mid-1
  3. 若key>R[mid].key,则low=mid-1

折半查找

int search_bIN(SSTable ST,KeyType key){
    low=1;high=ST,length;
    while(low<=high){
        mid=(low+high)/2;
        if(ST.R[mid].key==KEY)return mid;
        else 
            if(key<ST.R[mid].key)
                high=mid-1;
            else low=mid+1;
    }
    return 0;
}

$\large ASL=1/11*(11+22+43+44)=33/11=3$
平均查找长度ASL（成功时）
- $设表长为n=2^h-1,则h=log_2(n+1)，且表中每个记录的查找概率相等：p_i=1/n$
  
  $则\begin{align}
  ASL_{bs}&=\dfrac {1}{n} \sum\limits ^{n}_{j=1}j*2^{j-1}\
  &=\dfrac{n+1}{n}log_2(n+1)-1\
  &≈log_2(n+1)-1(n>50)\end{align}$
- 折半查找的性能分析
  - 优点：效率比顺序查找高
  - 缺点：只适用于有序表，且限于顺序存储结构(对线性链表无效)

7.2.3 分块查找

分块查找 (Blocking Search) 又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。
1. 将表分成几块,且表或者有序，或者分块有序
2. 建立“索引表”（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）。
查找过程：先确定待查记录所在块，再在块内查找
查找效率：$ASL=L_b+L_w$
$\large ALS_{bs}≈log_2(\dfrac{n}{s}+1)+\dfrac {s}{2}$ s为每块内部的记录个数，n/s即块内数目
分块查找的特点
- 优点：插入和删除比较容易
- 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算
- 适用情况：线性表既要快速查找又要经常动态变化

	顺序查找	折半查找	分块查找
ASL	最大	最小	中间
表结构	有序表、无序表	有序表	分块有序
存储结构	顺序表、线性链表	顺序表	顺序表、线性链表

7.3 树表的查找

当表插入、删除操作频繁时，为了维护表的有序性，需要移动表中很多记录
- 改用动态查找表——几种特殊的树
- 表结构在查找过程中动态生成
- 对于给定值key，若表中存在，则成功返回；否则，插入关键字等于key的记录
  - 二叉排序树
    平衡二叉树
    红黑树
    B-树
    B+树
    键树

7.3.1 二叉排序树

二叉排序树又称为二叉搜索树、二叉查找树
- 二叉排序树或是空树，或是满足如下性质的二叉树；
  1. 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
  2. 若其右子树非空，则右子树上所有结点的值均大于根结点的值；
  3. 其左右子树本身又各是一棵二叉排序树
- 二叉排序树的性质
  - 中序遍历非空的二又排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。
二叉排列树的操作——查找
- 若查找的关键字等于根结点，成功
- 否则
  - 小于根结点，查左子树
  - 大于根结点，查右子树
- 在左右子树上的操作类似

算法描述

BSTree SearchBST (BSTree_T,KeyType key){
    if ((!T)||key==T->data.key) return T;
    else if (key<T->data.key)
        return SearchBST(T->lchild,key);
		 else return SearchBST (T->rchild,key);
}

二叉排序树的查找分析
- 含有n个结点的二叉排列树的平均查找长度和树的形态有关
  - 最好的情况：
    
    二叉排列树的形态和折半查找的判定树相似:
    
    $ASL=log_2(n+1)-1$
    $O(log_2n)$
  - 最坏情况
    
    二叉排序树的形态为单支树，树的深度为n，
    
    $ASL=\dfrac {n+1}{2}$
    
    $O(n)$
二叉排序树的操作——插入
- 若二叉排序树为空，则插入结点作为根结点插入到空树中
- 否则，继续在左右子树上查找
  - 树中已有，不再插入
  - 树中没有
    - 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
- 插入的元素一定在叶子结点上
二叉排序树的操作——生成
- 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。
- 插入的结点均为叶子结点，故无序移动其他结点。相当于在有序序列上插入记录儿无需移动其他记录
- 不同的插入次序的序列生成不同形态的二叉排序树
二叉排序树的操作——删除
- 被删除的结点是叶子结点：直接删去该结点
- 被删除的结点只有左子树或右子树，用其左子树或右子树替换它
- 被删除的既有左子树，也有右子树，以其中序前驱值替换之（前驱是左子树中最大的结点），然后再删除该前驱结点
  - 也可以用其后继替换之（后继是右子树中最小结点），然后再删除该后继结点

7.3.2 平衡二叉树

平衡二叉树的定义
- 又称AVL树
- 一棵平衡二叉树或者是空树，或者是具有以下性质的二叉排序树：
  - 左子树与右子树的高度之差的绝对值小于等于1；
  - 左子树和右子树也是平衡二叉排序树。
为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子
- 根据平衡二叉树的定义，平衡二叉树上所有结点的平衡因子只能是-1，0，或1
- 对于一棵有n个结点的AVL树，其高度保持在$O(log_2n)$数量级，ASL也是保持在$O(log_2n)$量级
- 当我们在一个平衡二叉树上插入结点时，可能导致失衡
  - 平衡调整的四种类型：
    
    LR型和RL型左右要看B和A哪个大
    - 调整原则：1. 降低高度 2. 保持二叉排序树性质

7.4 哈希表的查找

7.4.1 散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系

对应关系——hash函数（hash:散列）

Loc(i)=H(keyi)

散列表的查找
- 根据散列函数H(key)=k
  - 查找key=9，直接访问H(9)=9号地址，若内容为9则成功
    若查不到，则返回一个特殊值，如空指针或空记录。
- 优点：查找效率高
  缺点：空间效率低
散列函数和散列地址：在记录的存储位置p和其关键字key 之间建立一个确定的对应关系H, 使 p=H(key ), 称这个对应关系H为散列函数，p为散列地址。
散列表：一个有线连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标
冲突：不同的关键码映射到同一个散列地址
- key1≠key2，但是H(key1)=H(key2)
- 冲突是不可避免的，但可以减少
同义词：具有相同函数值的多个关键字

7.4.2 散列函数的构造方法

构造散列函数的考虑因素：
- 散列表的长度
- 关键字的长度
- 关键字的分布情况
- 计算散列函数所需的时间
- 记录的查找频率
构造号的散列函数要遵循以下两条原则
- 函数计算要简单，每一个关键字只能有一个散列地址与之对应
- 函数的值域需在表长的范围内，计算出的散列地址的分布应均匀，尽可能减少冲突。
根据数据元素的集合特性构造
- 要求一: n个数据原仅占用n个地址虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小
- 要求二:无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

7.4.2.1 直接定址法

Hash(key)=a.key+b
优点：以关键码key的某个线性函数值为散列地址，不会产生冲突
缺点：要占用连续的地址空间，空间效率低

7.4.2.2 除留余数法

Hash(key)=key mod p
- 技巧：设：表长为m，取p<=m且为质数
  - 例：{15,23,27,38,53,61,70}
    
    散列函数：Hash(key)=key mod 7
    
    0 1 2 3 4 5 6
    
    70 15 23 38 53 61 27

0	1	2	3	4	5	6
70	15	23	38	53	61	27

7.4.3 处理冲突的方法

7.4.3.1 开放地址法（开地址法）

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入
- 列入：除留余数法：$H_i=(Hash(key)+d)mod \ m$
- 常用方法：
  - 线性探测法 $d_i为1,2,……，m-1线性序列$
  - 二次探测法 $d_i为1^2,-1^2,2^2,-2^2……，q^2二次序列$
  - 伪随机探测法 $d_i为伪随机数序列$
例：关键码集为：{47，7，29，11，16，92，22，8，3}，散列表长m=11，散列函数为$Hash(key)=key \ mod \ 11$,拟用线性探测法处理冲突

0 1 2 3 4 5 6 7 8 9 10

11 22 47 92 16 3 7 29 8
- 使用线性探测法解释：
1. 47、7均是由散列函数得到的没有冲突的散列地址;
2. Hash(29)=7，散列地址有冲突，需寻找下一个空的散列地址由$H=(Hash(29)+1) mod \ 11=8$，散列地址8为空，因此将29存入。
3. 11、16、92均是由散列函数得到的没有冲突的散列地址:
4. 另外，22、8、3同样在散列地址上有冲突，也是由H,找到空的散列地址的。
  - 平均查找长度ASL=(1+2 +1 +1 +1 +4 +1 +2 +2)/9=1.67
0 1 2 3 4 5 6 7 8 9 10

11 22 3 47 92 16 7 29 8
- 使用二次探测法解释：
  - Hash(3)=3散列地址有冲突，由于$H_1=(Hash(3)+1^2)mod \ 11=4$，仍然冲突；
  - $H_2=(Hash(3)-1^2)mod \ 11=2$找到空的散列地址，存入

0	1	2	3	4	5	6	7	8	9	10
11	22		47	92	16	3	7	29	8

0	1	2	3	4	5	6	7	8	9	10
11	22	3	47	92	16		7	29	8

7.4.3.2 链地址法（拉链法）

基本思想：相同散列地址的记录链成一单链表
m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态结构。
链地址法建立散列表的步骤
- step1：取数据元素的关键字key，计算其散列函数值 (地址)。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。
- step2：根据选择的冲突处理方法，计算关键字key的下一个存储地址若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表
链地址法的优点：
- 非同义词不会冲突，无“聚集”现象
  - 链表上的结点空间动态申请，更适合于表长不确定的情况

7.4.4 散列表的查找

给定值查找值k，查找过程：

graph TD
A[给定k值]==>B(计算H)
B==>C{此地址为空}
C-->|N|D{关键字==k}
C-->|Y|G[查找失败]
D-->|N|E[案处理冲突方法计算Hi]
D-->|Y|H[查找成功]
E-->C
F[竖向流程图]

$ASL=(16+2+33+4+9)/12=2.5$
用连地址法处理冲突：
$ASL=(16+24+3+4)/12=1.75$
使用平均查找长度ASL来衡量查找算法，ASL取决于
- 散列函数
- 处理冲突的方法
- 散列表的装填因子α
  - $\Large α=\dfrac {表中填入的记录数}{哈希表的长度}$
  - α越大，表中的记录数越多，表越满，发生冲突的可能性就越大，查找时比较次数就越多
- 无冲突时才能达到O(1)
- $\large ASL≈1+\dfrac {α}{2}$
- $\large ASL≈\dfrac {1}{2}(1+\dfrac{1}{1-α})$
- $\large ASL≈-\dfrac{1}{α}ln(1-α)$
结论
- 链地址法优于开地址法
- 散列表技术具有很好的平均性能，优于一些传统的技术
- 除留余数法作散列函数优于其它类型函数