第八章：查找

一：基本概念

  • 查找：
    根据给定的某个值，在查找表中确定一个与其关键字等于给定值的数据元素（或记录）
  • 关键字：
    用来表示一个数据元素（或记录）的某个数据项的值
    主关键字：
    可以唯一地表示一个记录的关键字
    次关键字：
    用以识别若干记录的关键字
  • 查找表：
    由同一类型的数据元素（或记录）构成的集合。由于集合中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构
    静态查找表：
    做查询、检索操作的查找表
    动态查找表：
    做插入、删除操作的查找表
  • 对查找表常进行的几个操作：
    1.查询某个特定的数据元素是否在查找表中
    2.检索某个特定的数据元素的各种属性
    3.如果查询结果为不存在，则在查找表中插入一个数据元素
    4.如果查询结果为存在，则删除查找表中的某个数据元素
  • 查找算法的评价标准：
  • 关键字的平均比较次数，也叫平均查找长度(ASL)image_808949c0.png

二：线性表的查找

1.顺序（线性）查找

优点：
算法简单，逻辑次序无要求，不同存储结构均适用
缺点：
ASL太长，时间效率低
查找范围：

  • 顺序表/线性表表示的静态查找表
    表内元素之间无序
//数据元素类型定义
typedef struct{
    KeyType key;  //关键字域
    ...           //其他域
}ElemType;
typedef struct{
    ElemType *R;  //表基址
    int length;   //表长
}SSTable;  //Sequential Search Table
SSTable ST;  //定义顺序表ST
//在ST中查找值为key的值
int Search_Seq(SSTable ST, KeyType key){
    //此查找表为从1开始，0号位置为空，可按需更改
    for (int i = 1; i <= ST.length; i++)
        if(ST.R[i].key == key)
            return i;
    return 0;
    //其他形式
    /*for(i = ST.length; ST.R[i].key != key && i > 0; i--)
        ;
    return i*/
}

改进：
把待查关键字key存入表头（哨兵/监视哨），从后往前逐个比较，可以免去查找过程中每一步都要检查是否查找完毕的步骤（从后往前找，不需要检测是否越界，但越界时也就是比较的元素等于表头元素，此时自然就返回表头元素的位置0了）

//设置监视哨的顺序查找，可使平均时间减少一半
int Search_Seq(SSTable ST, KeyType key){
    ST.R[0].key = key;
    for(i = ST.length; ST.R[i].key != key; i--);
    return i
}

顺序查找的性能分析：

image_340982f6.png
image_76237dbc.png

image_600a757d.png

2.二分查找

折半查找仅适用于有序表，且仅限于顺序存储结构m，对链式存储结构无效

折半查找算法（非递归算法）：image-20220919210606914

int Search_Bin(SSTable ST, KeyType key)
{
    int low = 1, high = ST.length;  //初始化
    while(low <= high)
    {
        int 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;  //查找不到
}

折半查找（递归算法）：

int Search_Bin(SSTable ST, KeyType key,int low, int hight){
  if(low>hight) return 0;
  int mid = (low+hight)/2;
  if(key == ST.elem[mid].key) return mid;
  else if(key < ST.elem[mid].key){
    hight = mid-1;
    return Search_Bin(SSTable ST,KeyType key,int low,int hight);
  }
  else{
    low = mid+1;
    return Search_Bin(SSTable ST,KeyType key,int low,int hight);
  }
}

折半查找算法的性能分析：

image_becce687.png

折半查找法的查找次数小于等于二叉数的深度

image-20220919212318438

平均查找长度=所有元素查找成功的总次数/元素个数

image_86b99089.png

3.分块（索引顺序）查找

image_9329a22c.png

假如一个顺序表，按元素的内容分为三块，建立一个索引表，记录每一块内容的最大值以及从哪开始的，如果块内元素是无序的，则里面的元素用顺序查找

分块查找性能分析：

image_155602f8.png

分块查找法的平均查找效率由两部分组成，一部分是索引表的平均查找效率，索引表的查找类似于折半查找再加上块内的顺序查找

image-20220919214047888

三：树表的查找

image-20220919214438385

1.二叉排序树（Binary Sort Tree）

1.1BST的定义

  • 若其左子树非空，则左子树上所有结点的值均小于根节点的值
  • 若其右子树非空，则右子树上所有结点的值均大于等于根节点的值
  • 其左右子树本身又各是一颗二叉排序树
  • 二叉排序树可以是空树

image-20220919215122150

规律：中序遍历二叉排列树，得到的数据元素序列是一个递增有序的序列

1.2 BST的存储结构

typedef struct
{
    KeyType key;  //关键字
    InfoType otherinfo;  //其他数据域
}ElemType;
typedef struct BSTNode
{
    ElemType data;  //数据域
    struct BSTNode *lchild, *rchild;  //左右孩子指针
}BSTNode, *BSTree;
BSTree T;  //定义二叉排序树T

1.3 BST的查找

image_b8e16b58.png

查找过程：

  • 若查找到的关键字等于根节点，成功
  • 否则
    • 若小于根节点，查左子树
    • 若大于根节点，查右子树

二叉排序树查找算法：

BSTree SearchBST(BSTree T, KeyType key)
{
    if((!T) || key == T->data.Tree)
        return T;
    else if(key < T->data.key)
        return SearchBST(T->lchild, key);  //在左子树继续查找
    else
        return SearchBST(T->rchild, key);  //在右子树继续查找
}

二叉排序树的查找分析：

image_6da8796c.png

image_3b6a93dd.png

image_d51dcea8.png

问题：如何提高形态不均衡的二叉排序树的查找效率？

解决办法：做平衡化处理，也就是平衡二叉树

1.4 BST的插入和生成

二叉排序树的插入：

image_f52308ec.png

void InsertBST(BSTree &T,ElemType e){
  KeyType key = e.key;
  if(!T){         //如果该节点为空
    BSTree s = new BSNode;
    s->data = e;
    s->lchild = nullptr;
    s->rchild = nullptr;
    T = S
  }
  else{
    if(!SearchBST(BSTree &T, KeyType key)){   //如果没有在此树上找到该节点
   		BSTree s = new BSNode;
   	  s->data = e;
   	  s->lchild = nullptr;
    	s->rchild = nullptr;
      if(key<T->data.key) InsertBST(T->lchild,e)
      else InsertBST(T->rchild,e)
  }
}

插入的元素一定是在叶子节点山

二叉排序树的生成：image_58f67ce0.png

image-20220919221551271

image_9e074f8e.png

1.5 BST的删除

  • 被删除的是叶子结点：
    直接删去该结点
  • 被删除的结点只有左子树或只有右子树：
    用其左/右子树替换它

image-20220920092621516

image-20220920092728840

其双亲节点的指针域的值改为：指向被删除节点的左子树或右子树

  • 被删除的结点既有左子树又有右子树：
    用中序前趋值替换它，再删除该前趋结点。前趋是左子树中最大结点 或用后继替换它，再删除该后继结点，后继是右子树中最小结点。（虽然两种替换都可以，但是一般使用让树的深度小一点的那种替换方式）
    image_51f55567.png

image-20220920093105736

void DeleteBST(BSTree &T, KeyType key){
    if(T)
        return;
    else if(key == T->data.key)
        return delete(T->lchild);  //找到匹配的元素就直接动用delete函数去删除这个节点
    else if(key < T->data.key)
      	return DeleteBST(T->lchild,key); //若要删除的节点值小于BST树中的节点，则递归寻找BST该节点的左子树
  	else 
      return DeleteBST(T->rchild,key)
}

这段删除节点的操作很类似与查找节点的操作，需要额外实现具体怎么删除节点的算法Delete

void Delete(BSTree &p){
  BSTree s,q;  //s指针用来指向要删除节点的前驱节点，p指针用来指向s的双亲节点
  if(!p->rchild){  //如果p的右子树为空
    q = p;   //将要删除的节点赋给临时变量q
    p = p->lchild;
    delete q;
  }
  else if(!p->lchild){
    q = p;   //将要删除的节点赋给临时变量q
    p = p->rchild;
    delete q; 
  }
  else{
    q = p;  //初始的时候让q指向p
    s = q->lchild;  //s始终是q的子树
    while(s->rchild){  //删除节点左子树上的最右的子树(如果有的话)才是其前驱节点
      q = s;
      s = s->rchild;
    }
    if(q!=p) 
      q->rchild = s->lchild;  //q与p不等的话，说明q的右子树是要删除的s节点，s节点的右子树经过while循环后肯定为空，其左子树上的节点要接回树上
    else
      q->lchild = s->lchild;  //q与p相等说明这颗树p的左子树没有右子树，也就是没有执行while代码，此时的p前驱节点就是p的左子树
  }
}

2.二叉平衡树（Adelson-Velskii and Landis）

2.1 AVL的定义

平衡二叉树是具有以下性质的二叉排序树

  • 左子树与右子树的高度之差的绝对值小于等于1
  • 左子树和右子树也是平衡二叉排序树

为了方便起见，给每个节点附加一个数字，此数字给出该节点左子树与右子树的高度差，这个数字称为该节点的平衡因子(BF)

平衡二叉树可以是空树；平衡因子 = 结点左子树高度 - 结点右子树高度 。AVL的平衡因子只能是-1,0,1

对于一颗由n个节点的AVL树，其高度需要保持在O(log2n)数量级，这样的话才能让AVL算法的效率保持在这个数量级

2.2 失衡二叉排序树的分析与调整

image_39d895e5.png

如果失衡节点不止一个，找最小失衡子树的根节点

image_0c65ff3b.png

调整失衡节点的原则：1）降低高度；2）保持二叉排序树的性质

平衡二叉树节点结构的定义（同BST的结构一致，需要加上平衡因子这个参数）

typedef struct BSTNode
{
    ElemType data;  //数据域
    int bf;  //定义平衡因子
    struct BSTNode *lchild, *rchild;  //左右孩子指针
}AVLNode, *AVLTree;
AVLTree T;
  1. LL型调整过程：

GIF 2022-9-20 11-18-20

void LLAdjust(const AVLTree &p){
  AVLTree L;
  L = p->lchild;
  p->lchild = L->rchild;
  L->rchild = p;
  p = L;
}

image_b2ae60f1.png

  1. RR型调整过程：

GIF 2022-9-21 9-22-36

  1. LR型调整：

image-20220921092925009

image_e59e8228.png

image_1c326268.png

四：哈希表的查找

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

  • 优点：查找效率快O(1)
  • 缺点：空间效率低

散列表的若干术语：

image_bde013f8.png
image_e3779df3.png

1.构造散列函数的方法

1）构造好的散列函数：

  • 所选函数尽可能简单，提高转换速度读
  • 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，减少空间浪费

2）构造散列函数考虑的因素：

  • 关键字长度
  • 执行速度（计算散列函数所需时间）
  • 散列表的大小
  • 关键字的分布情况
  • 查找频率

散列函数的构造方法：
image_f47aee94.png

image_7f9a1154.png

image_27e1f8d9.png

2.处理冲突的方法

制定一个好的解决冲突的方案：

  • 查找时，如果从散列函数中计算出的地址中查不到关键码，应依据解决冲突的规则，有规律地查询其他相关单元

开放定址法（开地址法）
image_3e7aa373.png

image_d091683e.png

image_f426a112.png

image-20220921111538796

image_5a43bb21.png

链地址法（拉链法）

优点：

  • 非同义词不会冲突，无“聚集”现象
  • 适合表长不确定的情况（链表动态申请）

image_fb69ef62.png
image_61d748cd.png

3.散列表的查找

image_d4fb733d.png

image-20220921141453193

余数取13是因为散列表长度为16，16以下的最大质数为13

image-20220921141627282

散列表的查找效率分析：

image-20220921141932993

image_968d88f2.png

结论

  • 散列表技术具有很好的平均性能，优于一些传统的技术
  • 链地址法优于开地址法
  • 除留余数法做散列函数优于其他类型函数

五：散列表查找代码实现

#define NULLKEY -32768

//散列表的结构：
typdef struct{
  int *elem;  //数组元素存储的地址，动态开辟
  int count;  //存储数组元素的个数
}HashTable;
int m = 0;  //全局变量定义散列表的长度

//初始化散列表
void InitHashTable(HashTable &H){
  int i;
  m = 12;
  H.count = m;
  H.elem = new int[m];
  for(i=0;i<m;i++){
    H.elem[i] = NULLKEY;
  }
}

//定义散列函数
int Hash(int key){
  return key%m; //除留取余法
}

//散列表插入元素
void InsertHash(HashTable &H,int key){
  int addr = Hash(key);
  while(H.elem[addr] != NULLKEY){
    addr = (addr+1)%m;  //地址不为空，发生冲突，使用开放定址法
  }
  H.elem[addr] = key;
  H.count++;
}

查找代码懒得写了，很类似于插入算法，值得注意的是在while循环里面需要加上没有查到的判别代码，即判断H.elem[addr] == NULLKEY || addr == Hash(key)，如果循环回到了起点(也就是判断了m次仍然不匹配)或者是下一个元素为NULLKEY都能说明不存在这样的关键字key

第九章：排序

1.分类

按数据存储介质：

  • 内部排序：数据量不大、数据在内存，无需内外存交换数据
  • 外部排序：数据量较大、数据在外存（文件排序），外存排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，比较复杂

按比较器个数：

  • 串行排序：单处理机（同一时刻比较一对元素）
  • 并行排序：多处理机（同一时刻比较多对元素）

按主要操作：

  • 比较排序：插入排序、交换排序、选择排序、归并排序
  • 基数排序：不比较元素大小，仅根据元素本身的取值确定其有序位置

按辅助空间：

  • 原地排序：辅助空间用量为O(1)，与参加排序的数据量大小无关
  • 非原地排序：辅助空间用量超过O(1)，与参加排序的数据量大小有关

按稳定性：

  • 稳定排序：能使任何数值相等的元素，排序后相对次序不变
  • 非稳定排序：数值相等的元素，排序后相对次序变化

image_ad12e3eb.png

image_7168c7a8.png

image-20220922092330005

按自然性：

  • 自然排序：输入数据越有序，排序的速度越快
  • 非自然排序：输入数据越有序，排序的速度越慢

2.存储结构——记录序列以顺序表存储

#define MAXSIZE 20  //记录最大个数
typedef int KetType;  //关键字类型
//定义每个记录（数据元素）的结构
Typedef struct{
    KeyType key;  //关键字
    InfoType otherinfo;  //其他数据项
}RedType;  //Record Type
//定义顺序表的结构
typedef struct{
    RedType r[MAXSIZE + 1];  //存储顺序表的向量，r[0]一般做哨兵或缓冲区
    int length;  //顺序表长度
}SqList;

3.插入排序

每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止
插入排序的分类：

image-20220922093111085

3.1 直接插入排序

image_4a5c06e5.png

void InsertSort(SqList &L){
    int i, j;
    for(i = 2; i < L.length; i++){
        if(L.r[i].key < L.[r - 1].key){  //要插入的元素比其前一位元素要大的话就不用后续操作了
            L.r[0] = L.r[i];  //复制为哨兵
            for(j = i - 1; L.r[0].key<L.r[j].key; j--){
                L.r[j + 1] = L.[j];  //记录后移
            }
            L.r[j + 1] = L.r[0];  //插入到正确位置
        }
    }
}

image_b1c85496.png

image_d5400621.png

image_eca9ec32.png

插入排序的原始数据越接近有序，排序速度越快

时间复杂度：

  • 最好情况：O(n)
  • 最坏情况：O(n2)
  • 平均情况：O(n2)

空间复杂度：O(1) ，是一种稳定的排序方法

3.2 折半插入排序

image_5a1ee1be.png

void BLinsertSort(SqList &L){
    int i, j;
    int low, high, mid;
    for(i = 2; i <= L.length; i++){
        L.r[0] = L.r[i];  //插入当前元素到哨兵位置
        low = 1;
        high = i - 1;
        while(low <= high){
       //用二分查找法查找插入位置
            mid = (low + high) / 2;
            if (L.r[0].key < L.r[mid].key)
                high = mid - 1;
            else
                low = mid + 1;
        }//循环结束，high+1为插入位置
        for(j = i - 1; j >= high + 1; j--)
            L.r[j + 1] = L.r[j];  //移动元素
        L.r[high + 1] = L.r[0];  //插入正确位置
    }
}

image_92b845cf.png
image_e39a7df6.png

3.3 希尔排序

特点：

  • 一次移动，移动位置比较大，跳跃式地接近排序后的最终位置
  • 最后一次只需少量移动
  • 增量必须递减，最后一次必须是1
  • 增量序列应该是互质的

image_e052c854.png

image_25d1b191.png

image_7d2b30e7.png

image_6356e0ad.png

void ShellSort(SqList &L, int dlta[], int t){
    //按增量序列dlta[0..t-1]对顺序表L作希尔排序
    for(int k = 0; k < t; k++)
        ShellInsert(L, dlta[k]);  //一趟增量为dlta[k]的插入排序
}
void ShellInsert(SqList &L, int dk){
    //对顺序表L进行一趟增量为dk的shell排序，dk为增长因子
    int i, j;
    for(i = dk + 1; i < L.length; i++){
        if(L.r[i].key < L.[i - dk].key){
            L.r[0] = L.r[i];  //复制为哨兵
            for(j = i - dk; j > 0 && (L.r[0].key < L.r[j].key); j = j- dk){
                L.r[j + dk] = L.[j];  //记录后移
            }
            L.r[j + dk] = L.r[0];  //插入到正确位置
        }
    }
}

在这段代码里面每一组的插入排序并不是一次性排完的

image_380899bc.png

image_904ec7fa.png

image_ed87ac9f.png

时间复杂度：

  • 最好情况：O(n)
  • 最坏情况：O(n2)
  • 平均情况：O(n1.3)

空间复杂度：O(1)
是一种不稳定的排序方法

4.交换排序

image_3948c7cd.png

4.1 冒泡排序

image_d8518827.png

n个记录需要比较n-1次
第m次需要比较n-m次

void BubbleSort(SqList &L){
    int i, j, m;
    RedType temp; //交换时临时储存
    bool flag = 1;  //标记是否有交换
    for(m = 1; m < L.length - 1 && flag == 1; m++){
        flag = 0;
        for(j = 1; j <= L.length - m; j++){
            if(L.r[j].key > L.[j + 1].key){
       //交换
                flag = 1;
                temp = L.r[j];
                L.r[j] = L.r[j + 1];
                L.r[j + 1] = temp;
            }
        }
    }
}

image_e63e26f9.png

时间复杂度：

  • 最好情况：O(n)
  • 最坏情况：O(n2)
  • 平均情况：O(n2)

空间复杂度：O(1)
是一种稳定的排序方法

4.2 快速排序

image_3adf1c37.png

image_b02ed28a.png

image-20220922191117553

void QSort(SqList &L, int low, int high){
    if(low >=  high)
        return;
    int pivotloc = Partition(L, low, high);  //找出中心点的位置，当表中low=high的位置时为中心点所在位置，在此点处安放我们选择的那个中心元素(表中第一个点的值)
    QSort(L,low,pivotloc - 1);  //对低子表递归排序
    QSort(L, pivotloc + 1, high);  //对高子表递归排序
}
int Partition(SqList &L, int low, int high){
    L.r[0] = L.r[low];  //复制到哨兵位置
    KeyType pivotkey = L.r[low].key;
    while(low < high){
        while(low < high && L.r[high].key >= pivotkey)  high--;  //从后往前找小的
      	L.r[low].key = L.r[high].key;
        while(low < high && L.r[high].key <= pivotkey) low++;  //从前往后找大的
        L.r[high].key = L.r[low].key;
        }
        L.r[low] = L.r[0];
        return low;  
}

image_d3de4a54.png

image_6d82c1c4.png

快速排序时，越乱越好，基本有序的不适合用快速排序

image-20220922195302044

时间复杂度：

  • 最好情况：O(nlogn)
  • 最坏情况：O(n2)
  • 平均情况：O(nlogn)

空间复杂度：O(nlogn)
是一种不稳定的排序方法，例如对于49,38,49*,20,97,76的第一次划分：20,38,49*,49,97,76

5.选择排序

5.1 简单选择排序

image_c75d99fd.png

void SelectSort(SqList &K){
    int i, j, k;
    ElemType temp;
    for(i = 1; i < L.length; i++){
        k = i;
        for(j = i + 1; j <= L.length; j++)
            if(L.r[j].key < L.r[k].key)
                k = j;
        if(k != i){
            temp = L.r[i];
            L.r[i] = L.r[k];
            L.r[k] = temp;
        }
    }
}

image_b86ced16.png

时间复杂度：

  • 最好情况：O(n2)
  • 最坏情况：O(n2)
  • 平均情况：O(n2)

空间复杂度：O(1)
是一种不稳定的排序方法

5.2 堆排序

  • 堆的定义
    image_6a46b5cf.png
    image_e948dbfc.png
    image_955be8d4.png

先解决一个问题：在输出堆顶元素后，如何调整其余元素为一个新的堆？

小根堆：

  • 输出堆顶后，用堆中最后一个元素代替之
  • 将根节点与左、右子树的根节点值比较，并与其中较小的交换
  • 重复上述操作，直到叶子结点，将得到新的堆，称这个从堆顶到叶子的调整过程为“筛选”
void HeapAdjust(Elem R[], int s, int m){
    //调整R[s]的关键字，使R[s..m]成为一个大根堆
    rc = R[s];
    for(j = 2 * s; j <= m; j *= 2){
        if(j < m && R[j] < R[j + 1])
            j++;  //j为关键字较大的数据元素下标
        if(rc >= R[j])
            break;
        R[s] = R[j];
        s = j;  //记录位置
    }
    R[s] = rc;  //插入
}

再解决第二个问题：如何建立一个堆
image_cf273bca.png

image-20220922204755265

image_37fd46a7.png

image_9040f667.png

for(int i = n / 2; i >= 1; i--)
    HeadAdjust(R, i, n);

实现堆排序

void HeapSort(Elen R[]){
    int i;
    for(int i = n / 2; i >= 1; i--)  //建立初始堆
        HeadAdjust(R, i, n);
    for(i = n; i > 1; i--){
        Swap(R[1], R[i]);  //根与最后一个元素交换
        HeapAdjust(R, 1, i - 1);  //剩下的重新建堆
    }
}

image_8be10773.png

image_87252749.png

时间复杂度：O(nlog2n)
空间复杂度：O(1)
是一种不稳定的排序方法

6.归并排序

将多个有序子序列归并成一个有序序列

image_8e5bd30b.png

需要进行⌈log2n⌉次，就是上面这颗树的高度

关键问题：如何将两个有序的序列合并成一个有序的序列？

在两个有序序列的首部分别建立一个指针，比较两指针所指元素，哪个指针所指元素值小就把这个元素移到新的序列中，同时此指针向右移动一位，这两个指针都移动到末尾则合并成功。

image-20220922211533322

时间复杂度：O(nlogn)
空间复杂度：O(n)
是一种稳定的排序方法

7.基数排序（桶/箱排序）

基本思想：分配 + 收集

image-20220922211908567

image_a97eb4dc.png

image_76e605ec.png

image_b55e2dea.png

8.总结

image-20220922212801344

image-20220922212918356

image-20220922213040327

image-20220922213119853

时间复杂度

  • O(nlogn)：快速排序、堆排序、归并排序
  • O(n2)：直接插入排序、冒泡排序、简单选择排序
  • O(n)：基数排序
  • 当待排序序列为有序是：用直接插入排序、冒泡排序时间复杂度为O(n)，而快速排序退化为O(n2)
  • 简单选择排序、堆排序、归并排序的时间性能不随序列分布二改变

空间复杂度：

  • O(1)：所有简单排序（直接插入排序、冒泡排序、简单选择排序）和堆排序
  • O(logn)：快速排序
  • O(n)：归并排序

image_af653491.png