数据结构第七章(上篇)

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)$
二叉排序树的操作——插入
- 若二叉排序树为空，则插入结点作为根结点插入到空树中
- 否则，继续在左右子树上查找
  - 树中已有，不再插入
  - 树中没有
    - 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子
- 插入的元素一定在叶子结点上
二叉排序树的操作——生成
- 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。
- 插入的结点均为叶子结点，故无序移动其他结点。相当于在有序序列上插入记录儿无需移动其他记录
- 不同的插入次序的序列生成不同形态的二叉排序树
二叉排序树的操作——删除
- 被删除的结点是叶子结点：直接删去该结点
- 被删除的结点只有左子树或右子树，用其左子树或右子树替换它
- 被删除的既有左子树，也有右子树，以其中序前驱值替换之（前驱是左子树中最大的结点），然后再删除该前驱结点
  - 也可以用其后继替换之（后继是右子树中最小结点），然后再删除该后继结点