数据结构和算法

线性表

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

树

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

散列表

• 散列函数
• 链表法
• 开放寻址法
• 冲突解决

复杂度分析

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

基本算法思想

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

排序

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

查找

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

图

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

字符串匹配

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

搜索

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

其它

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