数据结构算法总结

线性表

  • 数组
  • 链表
    • 单链表
    • 双向链表
    • 循环链表
    • 双向循环链表
    • 静态链表
    • 顺序栈
    • 链式栈
  • 队列
    • 普通队列
    • 双端队列
    • 阻塞队列
    • 并发队列
    • 阻塞并发队列

散列表

  • 散列函数
  • 冲突解决
    • 链表法
    • 开放寻址
    • 其他
  • 动态扩容
  • 位图

  • 二叉树
    • 平衡二叉树
    • 二叉查找树
    • 平衡二叉查找树
      • AVL树
      • 红黑树
    • 完全二叉树
    • 满二叉树
  • 多路查找树
    • B树
    • B+树
    • 2-3树
    • 2-3-4树
    • 小顶堆
    • 大顶堆
    • 优先级队列
    • 斐波那契堆
    • 二项堆
  • 其他
    • 树状数组
    • 线段树

  • 图的存储
    • 邻接矩阵
    • 邻接表
  • 拓扑排序
  • 最短路径
  • 关键路径
  • 最小生成树
  • 二分图
  • 最大流

复杂度分析

  • 空间复杂度
  • 时间复杂度
    • 最好
    • 最坏
    • 平均
    • 均摊

基本算法思想

  • 贪心算法
  • 分治算法
  • 动态规划
  • 回溯算法
  • 枚举算法

排序

  • O(n^2)
    • 冒泡排序
    • 插入排序
    • 选择排序
    • 希尔排序
  • O(nlogn)
    • 归并排序
    • 快速排序
    • 堆排序
  • O(n)
    • 计数排序
    • 基数排序
    • 桶排序

搜索

  • 深度优先搜索
  • 广度优先搜索
  • A*启发式搜索

查找

  • 线性表查找
  • 树结构查找
  • 散列表查找

字符串匹配

  • 朴素
  • KMP
  • Robin-Karp
  • Boyer-Moore
  • AC自动机
  • Trie
  • 后缀数组

其他

  • 数论
  • 计算几何
  • 概率分析
  • 并查集
  • 拓扑网络
  • 矩阵运算
  • 线性规划