Fundamentals-of-Data-Structures

基础知识

时间复杂度

空间复杂度

数据结构

字符串

字符串匹配算法（$O(n * m)$的枚举算法，$O(n + m)$的KMP算法）

数组

栈

先进后出

队列

先进先出

链表

并查集

树

叶子结点、非叶子节点、深度、父亲、祖先

二叉树

完全二叉树、满二叉树

遍历顺序

层次遍历、先（前）序遍历、中序遍历、后序遍历

堆

大根堆、小根堆

二叉搜索树

左小右大

AVL平衡二叉搜索树

旋转操作（左旋、右旋）

胜者树

多叉树

B-树

图

有向图、无向图

存储方式

邻接矩阵、领接链表

DFS和BFS

深度优先搜索、宽度优先搜索

最小生成树算法

Kruskal算法

将边权从小到大排序，依次取边，如果边的两个端点所属不同的联通分量，则取这一条边，否则不取

Prim算法

将点分为两个集合，一个是已选集合，一个是未选集合，每次取未选集合中到已选集合距离最近的点，将其从未选集合移动到已选集合

最短路算法

Floyed算法

Dijkstra算法

拓扑排序

关键路径

AOE网络

AOV网络

算法

排序

快速排序、归并排序、堆排、桶排（计数排序）、冒泡排序、插入排序、选择排序

稳定排序、非稳定排序

内排序、外排序

Hash（哈希）