数据结构与算法 提纲

表

• 简单数组实现
• 链表实现 👋
  • 单链表
  • 双链表
  • 循环链表
  • 哑节点
• 约瑟夫问题
• 多项式运算
• 链表的游标实现 👋
• Radix Sort

栈和队列

• 栈 👋
  • 链表实现
  • 数组实现
  • 括号匹配 → 有效的括号
• 队列
  • 链表实现
  • 循环数组实现

树

• 二叉树
  • 二叉树的性质、完全二叉树
  • 二叉树的表示
    • 数组（完全二叉树）
    • 链表
    • 游标
  • 二叉树的遍历
    • 非递归算法
  • 二叉树的构造
    • 利用遍历轨迹
    • 利用后缀表示
• 杂项
  • 树的表示
    • 广义表
    • 树的双亲表示法、孩子表示法和孩子兄弟表示法
  • 树与森林
  • 线索二叉树
  • 霍夫曼树
• 二叉搜索树 👋
  • 插入与删除
  • 向上取整与向下取整
  • 选择与排名
• AVL Tree
  • 插入
  • 删除
  • Refer to DSAAC
  • 性能分析 → Fibonacci Tree
• B-Tree
  • 平衡的多路搜索树
  • Refer to DSACPP

AVL

B-Tree

插入

• 插入 23 → 直接插入
• 插入 29 → 分裂，将 23 提升至父节点
• 插入 45 → 分裂，将 45 提升至父节点 → 再次分裂，将 36 提升至父节点

• 插入 87 → 三次分裂

删除

• 删除 41 → 直接删除
• 删除 53 → 与直接后继 64 交换位置后，再删除
• 删除 75 → 从右侧兄弟借得一个关键码

• 删除 84 → 从父节点借得一个关键码，与左侧兄弟合并
• 删除 51 → 从父节点借得一个关键码，与左侧兄弟合并 → 从根节点借得一个关键码，与父节点的右侧兄弟合并，并删除空的根节点

散列

• 散列函数
• 线性探测
• 平方探测 👋
• 双散列
• 再散列
• 分离链接 👋

优先队列

• 基于完全二叉树
• 下沉与上浮
• 建堆
  • 自底向上 → 下沉 → $O(n)$
  • 自顶向下 → 上浮 → $O(nlogn)$
• 堆排序
  • 对分支结点进行下沉操作
  • 从小到大 → 大顶堆
  • 不稳定
• Top K
  • 把所有 n 个元素建最大堆 → $O(n+klogn)$
  • 先从 n 个数据中取出前 k 个建堆 → $O(k+(n-k)logk)$​

并查集

• 快并
  • 按高度 → 根结点中放负数，而且是代表高度
  • 按大小
• 快查
  • 路径压缩
  • s[x] = find(s[x])

路径压缩与按大小求并完全兼容，这就使得两个例程可以同时实现。

路径压缩不完全与按高度求并兼容，因为路径压缩可以改变树的高度。我们根本不清楚如何有效地去重新计算它们。答案就是不去计算。此时，对于每棵树所存储的高度就变成了估计的高度，有时称为秩，但实际上按秩求并理论上和按大小求并效率是一样的。

图

• 基本概念
  • 不考虑自环、多重边，即只考虑简单图
  • 极大连通子图 → 连通分量
  • 极小连通子图 → 生成树
• 图的表示
  • 邻接矩阵
  • 邻接表，逆邻接表
  • 邻接多重表 → 无向图
  • 十字链表 → 有向图
• 图的遍历
  • DFS
    • 用邻接表表示 $O(n+e)$
    • 用邻接矩阵表示 $O(n^2)$
  • BFS
    • 用邻接表表示 $O(n+e)$
    • 用邻接矩阵表示 $O(n^2)$
  • 对应的生成树
• 最小生成树
  • Kruskal
    • 利用最小堆和并查集 👋
    • $O(elogn)$
    • 稀疏图
  • Prim
    • 朴素实现
    • 使用两个辅助数组优化 👋
    • $O(n^2)$
    • 稠密图
• 最短路径
  • 非负权单源
    • Dijkstra 👋
    • 类似 Prim
    • $O(n^2)$
  • 任意权单源
    • Bellman–Ford 👋
    • 不允许负权重环
    • $O(n^3)$
  • 任意权多源
    • Floyd 👋
    • 不允许负权重环
    • $O(n^3)$
• 活动网络
  • AOV
    • 用顶点表示活动
    • 拓扑排序
    • $O(n+e)$
  • AOE
    • 用边表示活动
    • 关键路径
    • $O(n+e)$

代码备注

使用邻接矩阵简化实现

图的数据中 0 号索引不使用（除了有向图判环）

顶点数为最大索引数加 1

排序

• 概述
  • 稳定性
  • 内排序、外排序（使用外存）
  • 性能分析
    • 时间
      • 比较次数
      • 移动次数
    • 空间
• 插入排序
  • 朴素插入排序 👋
    • 平方时间
  • 折半插入排序 👋
    • 线性对数时间 -> 比较
    • 平方时间 -> 移动
  • 希尔排序 👋
    • 不稳定
• 交换排序
  • 冒泡排序 👋
  • 快速排序 👋
    • 不稳定
• 选择排序
  • 朴素选择排序 👋
    • 不稳定
  • 树形选择排序（锦标赛排序）
  • 堆排序 👋
    • 不稳定
• 归并排序
  • 迭代
  • 递归 👋
  • 两个有序链表的的归并

数据结构与算法 手撕代码

• 有向图判环 👋
• 判定 BST
• 非递归（递归）反转单链表
• 二叉堆上浮与下沉
• BST 的各种操作