0%

数据结构与算法学习（二）：第二阶段知识总结

发表于 更新于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

1. 散列表概述

  1. 概念

    1. 通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置
    2. 当按照键值查询元素时，可以用同样的散列函数将键值转化为数组下标，从对应的数组下标位置读取数据
    3. 数组的一种扩展，由数组演化而来。没有数组，就没有散列表

  2. 散列函数

    • 概念

      • hash(key) ，key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值

    • 实现

      1. 散列函数计算得到的散列值是一个非负整数
      2. 如果 key1 == key2，那么 hash(key1) == hash(key2)
      3. 如果 key1 != key2，那么 hash(key1) != hash(key2)

    • 设计要点

      1. 设计函数的设计不能太复杂
      2. 散列函数生成的值要尽可能随机并且均匀分布

  3. 装载因子

    • 概念

      1. 散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
      2. 装载因子越大，说明空闲位置越少冲突越多，散列表的性能会下降

    • 装载因子过大的问题

      1. 可以进行动态扩容，重新申请一个更大的散列表，再将数据搬移到新散列表中
      2. 针对散列表的扩容，数据搬移操作比数组要复杂很多，需要通过散列函数重新计算每个数据的存储位置

  4. 如何解决散列冲突

    • 开放寻址法

      • 概念

        • 如果出现散列冲突，就重新探测一个空闲位置将其插入

      • 应用

        • 数据量比较小装载因子小的时候，适合采用开放寻址法

      • 优点

        1. 散列表中的数据都存储在数组中，可以有效利用 CPU 缓存加快查询速度
        2. 这样实现的散列表，序列化起来比较简单

      • 缺点

        1. 删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据
        2. 装载因子的上限不能太大

      • 线性探测

        • 往散列表中插入数据时，如果某个数据经过散列函数散列之后存储位置已经被占用，就从当前位置开始依次往后查找看是否有空闲位置，直到找到为止

      • 二次探测

        1. 跟线性探测很像
        2. 线性探测每次探测的步长是 1，探测的下标序列就是 hash(key)+0, hash(key)+1, hash(key)+2, …
        3. 二次探测的步长就变成了原来的“二次方”，探测的下标序列是 hash(key)+0, hash(key)+1^2, hash(key)+2^2, …

      • 双重散列

        • 先用一组散列表中的第一个散列函数，计算得到的存储位置已经被占用再用第二个散列函数，以此类推，直到找到空闲的存储位置

    • 链表法

      • 概念

        1. 一种更加常用的散列冲突解决办法，比开放寻址法简单很多
        2. 每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中

      • 操作

        1. 插入时，只需要通过散列函数计算对应的散列槽位，将其插入到对应链表中即可
        2. 查找、删除一个元素时，同样通过散列函数计算出对应的槽，遍历链表查找或删除

      • 应用

        1. 适合存储大对象、大数据量的散列表
        2. 更加灵活支持更多的优化策略，比如用红黑树代替链表

  5. 工业级散列表的特性

    1. 支持快速的查询、插入和删除操作
    2. 内存占用合理，不能浪费过多的内存空间
    3. 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的程度

  6. 实现工业级散列表的要点

    1. 设计一个合适的散列函数
    2. 定义装载因子阈值，并且设计动态扩容策略
    3. 选择合适的散列冲突解决方法

2. 二叉树概述

  1. 概念

    1. 每个节点最多有两个“叉”也就是两个子节点，分别是左子节点和右子节点
    2. 二叉树并不要求每个结点都有两个子节点，有的结点只有左子节点、有的结点只有右子节点

  2. 计算公式

    1. 节点高度 = 节点到叶子节点的最长路径边数（相对最底层叶子节点而言）
    2. 节点深度 = 根节点到这个节点所经历的边的个数（相对最顶层根节点而言）
    3. 节点层数 = 节点深度 + 1
    4. 树的高度 = 根节点的高度

  3. 分类

    1. 满二叉树：叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点
    2. 完全二叉树：叶子节点都在最底下两层，而且最后一层的叶子节点都靠左排列

  4. 存储

    1. 链式存储法
    2. 顺序存储法

  5. 遍历

    1. 分类：前序遍历、中序遍历、后序遍历
    2. 时间复杂度是 O(n)
    3. 本质：二叉树的前中后序遍历就是一个递归的过程
    4. 递推公式
      • 前序遍历的递推公式：preOrder(r) = print r -> preOrder(r->left) -> preOrder(r->right)
      • 中序遍历的递推公式：inOrder(r) = inOrder(r->left) -> print r -> inOrder(r->right)
      • 后序遍历的递推公式：postOrder(r) = postOrder(r->left) -> postOrder(r->right) -> print r

3. 堆概述

  1. 概念

    1. 一个完全二叉树
    2. 每一个节点的值都必须大于等于（大顶堆）或小于等于（小顶堆）其子树中每个节点的值

  2. 存储

    • 数组

  3. 操作

    • 插入一个元素和删除堆顶元素

  4. 堆排序

    1. 借助堆实现的排序算法
    2. 时间复杂度是 O(nlogn)，非常稳定
    3. 是原地排序算法

  5. 基于堆实现排序的步骤

    1. 建堆

      • 思路 1：从前往后处理数据，并且每个数据插入堆中时都是从下往上堆化
      • 思路 2：从后往前处理数据，并且每个数据都是从上往下堆化

    2. 排序

      1. 堆顶跟最后一个元素交换，把下标为 n 的元素放到堆顶，通过堆化的方法将剩下的 n-1 个元素重新构建成堆
      2. 堆化完成之后，取堆顶的元素放到下标是 n-1 的位置
      3. 一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了

  6. 快排比堆排序性能好的原因

    1. 堆排序数据访问的方式没有快排友好
    2. 同样的数，在排序过程中堆排序算法的数据交换次数多于快速排序

  7. 应用

    1. 实现优先级队列
    2. 针对静态/动态数据集合求 Top K
    3. 求动态数据集合中的中位数

4. 字符串匹配算法概述

  1. 单模式串算法

    • BF 算法

      1. 在主串中，检查起始位置分别是 0, 1, 2, …, n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的
      2. 时间复杂度很高，是 O(n*m)
      3. 实现简单，对于处理小规模的字符串匹配很好用

    • RK 算法

      1. 借助哈算法对 BF 算法进行改造，是 BF 算法的升级版
      2. 对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间
      3. 理想情况下，RK 算法的时间复杂度是 O(n) 的效率，比 BF 算法高

5. Trie 树概述

  1. 概念

    1. 即字典树，一个树形结构，专门处理字符串匹配的数据结构
    2. 用来解决在一组字符串集合中快速查找某个字符串的问题
    3. 利用字符串之间的公共前缀，将重复的前缀合并在一起

  2. 实现

    1. 构造 Trie 树的每一步，都相当于往 Trie 树中插入一个字符串
    2. 当所有字符串都插入完成之后，Trie 树就构造好了

  3. 应用

    1. 精确匹配查找这类问题更适合用散列表或者红黑树来解决
    2. Trie 树比较适合查找前缀匹配的字符串

6. 图概述

  1. 概念

    • 一种非线性表数据结构，比树要复杂

  2. 分类

    • 有向图
    • 无向图
    • 带权图

  3. 存储

    • 邻接矩阵法

      1. 缺点：浪费存储空间
      2. 优点：存储方式简单、直接、方便计算
      3. 应用：Floyd-Warshall 算法

    • 邻接表法

      1. 查询效率没有邻接矩阵存储方式高
      2. 如果链过长，可以将链表换成其他更高效的数据结构，比如平衡二叉查找树
      3. 实际开发中，用红黑树或者其他动态数据结构，比如跳表、散列表等，更加快速地查找两个顶点之间是否存在边
      4. 将链表改成有序动态数组，通过二分查找的方法快速定位两个顶点之间是否存在边

7. 搜索概述

  1. 广度优先搜索

    • 概念

      • 从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止

    • 复杂度

      1. 时间复杂度是 O(V+E)，简写为 O(E)
      2. 空间复杂度是 O(V)，其中 V 表示顶点的个数，E 表示边的个数

  2. 深度优先搜索

    • 概念

      1. 沿着树的深度遍历树的节点，已经访问过的节点不再访问，所有点仅访问一次
      2. 用的是回溯思想，非常适合用递归，借助栈来实现的
      3. 目的是“遍历”，本质是无序的。访问次序不重要，重要的是都被访问过了

    • 复杂度

      • 时间复杂度是 O(E)
      • 空间复杂度是 O(V)
-------------------- 本文结束感谢您的阅读 --------------------