C++ 标准模板库（Standard Template Library，STL）：STL 的代码从广义上讲分为三类：algorithm（算法）、container（容器）和 iterator（迭代器），几乎所有的代码都采用了模板类和模板函数的方法，这相比于传统的由函数和类组成的库来说提供了更好的代码 ...

树的定义 树（tree）是包含 n(n≥1)n(n \ge 1)n(n≥1) 个结点，(n−1)(n-1)(n−1) 条边的有穷集，其中： 每个元素成为结点 (node)，只有有限个子结点或无子结点 有一个特定的结点（无父结点）称为根结点 (root) 每一个非根节点有且只有一个父节点 除了根节 ...

堆的定义 堆（Heap） 是通常是一个可以被看作 完全二叉树 的 数组 对象。总是满足以下性质： 堆中某个结点的值总是不大于或不小于其父结点的值 不大于：大根堆；不小于：小根堆 堆总是一棵完全二叉树 具有 n 个结点，深度为 ⌊log2k⌋+1\lfloor log_2k \rfl ...

静态链表：需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。 静态链表的实现原理是 hash，即通过建立一个结构体数组，并令数组的下标直接表示结点的地址，来达到直接访问数组中的元素就能访问结点的效果。 由于结点的访问十分方便，因 ...

并查集定义 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。 名字取自：Union、Find、Set 三个单词，Union-Find Disjoint Sets。 并查集的实现就是用一个数组：father[] fat ...

AVL 树的定义 AVL 树本质上是：带了平衡功能的二叉查找树，它的特点是： 是一棵二叉查找树 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1。 平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。 每次插入元素之后仍然保持 O(logn)O(logn)O( ...

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。 Catalan(0)=1，Catalan(n)=C2nn−C2nn+1=C2nnn+1Catalan(0) = 1，Catalan(n) = C^n_{2n}-C^{n+1}_{2n} = \frac{C^n_{2n}}{n+1} Catala ...

二叉查找树（Binary Search Tree，BST），（又：二叉搜索树，二叉排序树）是一中特殊的二叉树： 要么是一棵空树 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树 二叉搜 ...

**回溯法（Backtracking）：基本做法是搜索，是一种避免不必要搜索的穷举式搜索法。 有”通用的解题法“之称 按深度优先策略，从根结点出发搜索解空间树 根据剪枝函数来避免无用搜索 回溯法设计过程： 确定问题的解空间 常见解空间：排列树和子集树 确定结点的扩展规则 搜索 ...

对一个 有向无环图(Directed Acyclic Graph，DAG) G 进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边 <u,v> ∈ E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序(Topological ...