Sukun
归档
类别 标签 所有文章
站点
公告留言 站点日志 关于
文档
LoveIt主题文档 Hugo官方文档
友链墙
小游戏
mikutap catch the cat
搜索
Sukun

目录

数据结构学习(八)

Sukun 收录于 算法与数据结构
     约 4357 字  预计阅读 9 分钟    次阅读     条评论

数据结构——用C语言描述(八)

技术

查找

查找的基本概念

  • 列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现

  • 关键字：数据元素的某个数据项的值可标识列表中的一个数据元素

    主关键字可唯一标识列表中的一个数据元素，否则为次关键字

  • 查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置

    1. 查找对象 K（找什么）

    2. 查找范围 L（在哪找）

    3. K 在 L 中的位置（查找的结果）

  • 平均查找长度（ASL）：查找过程中对关键码的比较次数的平均值 $$ ASL=P_1C_1+P_2C_2+…+P_nC_n=\sum_{i=1}^nP_iC_i\\ P_i为查找概率，C_i为查找次数 $$

  • 查找基本方法：

    1. 线性表查找法
    2. 树表式查找法
    3. 计算式（哈希）查找法

基于线性表的查找法

顺序查找法
数据类型定义
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#define KeyType int
#define OtherType int
#define LIST_SIZE 20
typedef struct
{
    KeyType key;
    OtherType other_data;
} RecordType;
typedef struct
{
    RecordType r[LIST_SIZE + 1]; // r[0]为工作单元
    int length;
} RecordList;
顺序结构算法

此处为从后往前的顺序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

//不设置监视哨，在顺序表中查找关键字等于k的元素
int SeqSearch_1(RecordList L, KeyType k)
{
    int i;
    for (i = L.length; i >= 1 && L.r[i].key != k; i--)
        ;
    if (i >= 1)
        return i;
    else
        return 0;
}
//设置监视哨，顺序表L由后往前查找关键字k，查到返回k在L中的位置，否则返0
int SeqSearch_2(RecordList L, KeyType k)
{
    int i;
    L.r[0].key = k;
    for (i = L.length; L.r[i].key != k; i--)
        ;
    return i;
}
性能分析

$$ n为表长，c_i为比较次数\\ c_1=n-1+1\\ c_2=n-2+1\\ …\\ c_n=n-n+1\\ 即c_i=n-i+1\\ 查找每个元素的概率相等，即P_i=\frac{1}{n}\\ 查找成功时平均查找长度为\\ ASL_{succ}=\sum_{i=1}^nP_iC_i=\frac{1}{n}\sum_{i=1}^nC_i=\frac{1}{n}\sum_{i=1}^n(n-i+1)=\frac{n+1}{2} $$

注意
ASL为$O(n)$
折半查找法
定义

折半查找（二分查找），要求：

  1. 采用顺序存储
  2. 关键字有序排列
基本过程

中间记录关键字与查找关键字比较：

如果两者相等，则查找成功；

否则如查找关键字小于中间位置关键字，则查前部子表，否则查找后部子表。

算法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int BinSrchZ(SqList L, KeyType k)
{
    int low, high, mid;
    low = 1;
    high = L.length; //置区间初值
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (k == L.r[mid].key)
            return mid; //查找成功
        else if (k < L.r[mid].key)
            high = mid - 1; //继续在前半区间查找
        else
            low = mid + 1; //继续在后半区间查找
    }
    return 0;
}
性能分析

折半查找过程可用判定树描述判定树结构：

  • 树中每一结点表示表中一记录结点值记录在表中的位置
  • 从根到被查结点路径关键字比较次数为被查结点层数
  • 成功进行最多比较次数不超过树深度$[\log_2n] +1$

假定表的长度$n=2h-1$，则相应判定树必为深度是 h 的满二叉树，$h=\log_2(n+1)$

折半查找成功的平均查找长度： $$ ASL_{bs}=\sum_{i=1}^nP_iC_i=\frac{1}{n}\sum_{j=1}^hj×2^{j-1}=\frac{n+1}{n}\log_2(n+1)-1 $$ 每个记录的查找概率相等，j 为每层的比较次数，$2^{j-1}$为每层的元素个数

注意
ASL为$O(\log_2n)$
  • 优点：
    • 比较次数少
    • 查找速度快
    • 平均性能好
    • 适用于固定长度频繁查找的有序表
  • 缺点：
    • 要求待查表为有序表
    • 插入删除时需再排序
分块查找法
对所查表要求
  • 等长分块，最后一块可不满
  • 块内无序
  • 块间有序
基本思想
  • 分块构造索引表
  • 定块可用顺序或折半查找关键字 k 与索引表关键字比较，确定该查记录所在块
  • 块内顺序查找
平均查找长度

查找索引表的平均查找长度$L_B$，相应块内顺序查找的平均查找长度$L_W$

平均查找长度：$ASL_{bs}=L_B+L_W$

假定将长度为 n 的表分成 b 块，每块含 s 个元素，则$b=\frac{n}{s}$，

又假定表中每个元素的查找概率相等，则每个索引项的查找概率为$\frac{1}{b}$，块中每个元素的查找概率为$\frac{1}{s}$。则有

  • 顺序法平均查找长度： $$ L_B=\frac{1}{b}\sum_{j=1}^bj=\frac{b+1}{2}\\ L_W=\frac{1}{s}\sum_{i=1}^si=\frac{s+1}{2}\\ $$ 将$b=\frac{n}{s}$代入得 $$ ASL_{bs}=\frac{\frac{n}{s}+1}{2}+1\\ =\frac{b+1+s+1}{2}\\ =\frac{b+s}{2}+1 $$

  • 折半法平均查找长度： $$ L_B=\log_2(b+1)-1\\ ASL_{bs}=\log_2(b+1)-1+\frac{s+1}{2}\\ =\log_2(\frac{s}{n}+1)+\frac{s-1}{2} $$

基于树的查找法

步骤：

  1. 将待查表组织成特定树
  2. 在树结构上实现查找

有三种树：

  1. 二叉排序树
  2. 平衡二叉树
  3. B 树

此处重点讲述二叉排序树

二叉排序树
定义

二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：

  1. 若它的左子树非空，则左子树上所有结点的值均小于根结点的值
  2. 若它的右子树非空，则右子树上所有结点的值均大于根结点的值
  3. 它的左右子树也分别为二叉排序树

https://s2.loli.net/2022/02/17/slmnZP2eaRKA95z.png

插入和生成
  • 若二叉排序树是空树，则key成为二叉排序树的根
  • 若二叉排序树非空，key与二叉排序树的根比较：
    1. key的值小于根结点的值，则将key插入左子树
    2. key的值大于等于根结点的值，则将key插入右子树
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

void CreateBST(BSTree *bst) //从键盘输入元素的值，创建相应的二叉排序树
{
    KeyType key;
    *bst = NULL;
    scanf("%d", &key);
    while (key != ENDKEY)
    {
        InsertBST(bst, key);
        scanf("%d", &key);
    }
}
void InsertBST(BSTree *bst, KeyType key) // key插入到bst为根的二叉排序树，从根比
{
    BiTree s;
    if (!*bst)
    {
        s = (BSTree)malloc(sizeof(BSTNode));
        s->key = key;
        s->LChild = s->RChild = NULL;
        *bst = s;
    }
    else if (key < (*bst)->key)
        InsertBST(&((*bst)->LChild), key);
    else
        InsertBST(&((*bst)->RChild), key);
}
注意
插入一个结点InsertBST(bst, key)时间复杂度为$O(\log_2n)$，创建二叉排序树 n 个结点的时间复杂度为$O(n\log_2n)$。
技巧
对二叉排序树进行中序遍历，一定会得到一个递增有序序列。
查找

方法：

根据二叉排序树的特点，关键字 k 与根 t 比较：

  1. key = t：返回根结点地址
  2. key < t：进一步查左子树
  3. key > t：进一步查右子树

算法：

  • 递归

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    BSTree SearchBST(BSTree bst, KeyType key)
{
    if (!bst)
        return NULL;
    else if (bst->key == key)
        return bst;
    else if (bst->key > key)
        return SearchBST(bst->LChild, key);
    else
        return SearchBST(bst->RChild, key);
}

  • 非递归

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    BSTree SearchBST_2(BSTree bst, KeyType key) //非递归查找
{
    BSTree q;
    q = bst;
    while (q)
    {
        if (q->key == key)
            return q; //查找成功
        else if (q->key > key)
            q = q->LChild;
        else
            q = q->RChild;
    }
    return NULL; //查找失败
}
查找性能

平均查找长度和二叉排序树的形态有关：

就平均性能而言，二叉排序树上的查找和二分查找相差不大，并且二叉排序树上的插入和删除结点十分方便，无需移动大量结点

  • 最好情况：

    二叉排序树接近二分平衡树，平均查找长度大约是$\log_2n$

  • 最坏情况：

    得到一棵深度为 n 的单支树，平均查找长度和单链表上的顺序查找相同，是$\frac{n+1}{2} $。

平衡二叉树
定义

平衡二叉排序树又称为 AVL 树。

一棵平衡二叉排序树或者是空树，或者是具有下列性质的二叉排序树：

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

平衡因子（balance factor）即结点的左子树深度与右子树深度之差。

对一棵平衡二叉排序树而言，其所有结点的平衡因子只能是-1、0或1。

https://s2.loli.net/2022/02/17/OgEZ8dYelJku3Mt.png

计算式查找法——哈希法

哈希的基本思想

比较式查找通过对关键字的一系列查找比较实现，效率与查找表长有关，当关键字可能取值的集合远远大于实际表长时，比较式查找效率低。

而计算式查找对关键字计算得到对应元素的地址$H(key)=Addr$

哈希法（散列法、杂凑法）基本思想：

  1. 哈希函数：

    建立哈希函数$p=H(key)$，计算关键字 key 在哈希表中的存储位置 p。

  2. 冲突：

    冲突问题:若关键字$key_1 key_2$，哈希函数值$H(key_1)= H(key_2)$，则发生冲突。

冲突原因：

  1. 必然性：由于关键字可能的取值空间远远大于哈希表的地址空间，冲突不可避免
  2. 可能性：哈希函数$H(key)$的散列性能不好，可能加剧冲突发生
哈希函数的构造方法

原则：

  1. 函数本身便于计算
  2. 计算出来的地址分布均匀

方法：

  1. 数字分析法：

    从关键字中选出分布较均匀的若干位，构成哈希地址

  2. 平方取中法：

    先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址

  3. 分段叠加法：

    按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。

  4. 除留余数法：

    哈希函数为$H(K)=K\%P$，其中%为模 P 取余运算，表长为 m，P 应为小于等于 m 的最大素数

  5. 伪随机数法：

    采用一个伪随机函数做哈希函数，即$h(key)=random(key)$。

处理冲突的方法

  1. 开放定址法

    当关键字 key 的哈希地址$p=H (key)$出现冲突时，以 p 为基础，产生另一个哈希地址$p_1$，如果$p_1$仍然冲突，再以 p 为基础，产生另一个哈希地址$p_2$，…，直到找出一个不冲突的哈希地址$p_i$ ，将相应元素存入其中。通用的再散列函数形式：$H_i=(H(key)+d_i)\%m$

    形成$d_i$的方法：

    1. 线性探测再散列

      $d_i=1,2,3,…,m-1$

      冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表

    2. 二次探测再散列

      $d_i=1^2,-1^2,2^2,-2^2,…,k^2,-k^2$

      特点:冲突发生时，在表的左右进行跳跃式探测，比较灵活

    3. 伪随机探测再散列

      $d_i=伪随机数序列$

  2. 再哈希法

    同时构造多个不同的哈希函数：$H_i=RH_1(key)\ i=1,2,…,k$

    当哈希地址$H_i=RH_1(key)$发生冲突时，再计算$H_i=RH_2(key)$……直到冲突不再产生。

    这种方法不易产生聚集，但增加了计算时间。

  3. 链地址法

    https://s2.loli.net/2022/02/18/WIV1uPTQ9kUgD5j.png

  4. 建立公共溢出区

    将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

哈希表的查找过程

哈希表的查找过程与哈希表的创建过程规则一致

注意：查到空单元时表示找不到

查找过程：

  1. 计算$p_0=hash(K)$

  2. 如果单元$p_0$为空，则所查元素不存在

  3. 如果单元$p_0$中元素的关键字为K，则找到所查元素

  4. 否则重复下述解决冲突的过程：

    按解决冲突的方法，找出下一个哈希地址$p_i$

    1. 如果单元$p_i$为空，则所查元素不存在
    2. 如果单元$p_i$中元素的关键字为K，则找到所查元素

查找算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int HashSearch(HashTable ht, KeyType K)
{
    int i, p0, pi;
    p0 = hash(K);
    if (ht[p0].key == NULLKEY)
        return -1;
    else if (ht[p0].key == K)
        return 0;
    else //线性探测再散列
    {
        for (i = 1; i <= m - 1; i++)
        {
            pi = (p0 + i) % m;
            if (ht[pi].key == NULLKEY)
                return -1;
            else if (ht[pi].key == K)
                return pi;
        }
        return -1;
    }
}
哈希法性能分析

影响比较次数的因素：

  1. 哈希函数

  2. 处理冲突的方法

  3. 装填因子

哈希表的装填因子 α 的定义： $$ α=\frac{哈希表中元素个数}{哈希表的长度} $$ α 可描述哈希表的装满程度。显然，α 越小，发生冲突的可能性越小；而 α 越大，发生冲突的可能性也越大。

等概率情况下查找成功的平均查找长度： $$ ASL_{succ}=\frac{1}{表中置入元素个数n}\sum_{i=1}^nC_i $$ 等概率情况下查找不成功的平均查找长度公式 $$ ASL_{unsucc}=\frac{1}{哈希函数取值个数r}\sum_{i=0}^{r-1}C_i $$

  1. 线性探测再散列： $$ ASL_{succ}≈\frac{1+\frac{1}{1-α}}{2}\\ ASL_{unsucc}=\frac{1+\frac{1}{(1-α)^2}}{2} $$

  2. 伪随机探测再散列、二次探测再散列、再哈希： $$ ASL_{succ}≈-\frac{\ln(1-α)}{α}\\ ASL_{unsucc}=\frac{1}{1-α} $$

  3. 链址法： $$ ASL_{succ}≈1+\frac{α}{2}\\ ASL_{unsucc}=α+e^{-α} $$

更新于 2022-02-17
CC BY-NC 4.0
阅读原始文档
 数据结构, 学习
返回 | 主页