本文介绍 JPEG 编解码过程（附简单的cpp实现）。JPEG 中常用到的熵编码是变长编码：Huffman 编码，本文也对算术编码（附cpp实现）、LZW 编码（附py实现）两种熵编码进行介绍。

　　加密方法可以分为两大类：一类是对称密码体制，又称单钥或私钥密码体制（private key cryptography）；还有一类是非对称密码体制，也称双钥或公开密钥体制（public key cryptography）。前者的加密和解密过程都用同一套密码，后者的加密和解密过程用的是两套密码。
　　在单钥加密的情况下，密钥只有一把，所以密钥的保存变得很重要，一旦秘钥泄露，密文也就被破解了；在双钥加密的情况下，秘钥有两把，一把是公开的公钥，还有一把是不公开的私钥，公钥与私钥是一一对应的关系，有一把公钥就必然有一把与之对应的、独一无二的私钥，反之亦成立。此外，①同时生成公钥和私钥应该是相对比较容易的：所有的公钥、私钥对都不同，用公钥可以解开私钥加密的信息，反之用私钥也可以解开公钥加密的信息；但是②从公钥推算出私钥，应该是很困难或者是不可能的。
　　目前，通用的单钥加密算法有 DES（Data Encryption Standard），通用的双钥加密算法为 RSA（Rivest-Shamir-Adleman），本文主要介绍三种常用的单钥加密算法：DES、3DES（Triple DES） 以及 AES（Advanced Encryption Standard）。

　一些计算机程序设计中常用的线性数据结构：Array、ArrayList、LinkedList、List、Stack、Queue、Hashtable 和Dictionary。为了更高效的进行数据的查找和访问，例如避免普通数据查找的 $O(N)$ 线性时间复杂度，常用树这种数据结构保存数据。
　树（Tree）是由多个节点（Node）的集合组成，每个节点又有多个与其关联的子节点（Child Node）；子节点就是直接处于节点之下的节点，而父节点（Parent Node）则位于节点直接关联的上方；树的根（Root）指的是一个没有父节点的单独的节点。所有的树都呈现了一些共有的性质：①只有一个根节点；②除了根节点，所有节点都有且只有一个父节点；③无环。将任意一个节点作为起始节点，都不存在任何回到该起始节点的路径（正是前两个性质保证了无环的成立）。
　更高效同时也相对更加复杂的树型数据结构包括 BST（二叉查找树）、R-B Tree（红黑树）、AVL Tree（平衡二叉树：父节点的左子树和右子树的高度之差不能大于1）、Treap（树堆：满足①二叉查找树的性质；满足②堆的性质）、Splay Tree（伸展树：在一次搜索后，会对树进行一些特殊的操作，这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度；伸展树并没有AVL树的平衡要求，任意节点的左右子树可以相差任意深度）、B-Tree（B树：多叉平衡查找树，B$^{+}$-Tree（B+树）是B树的变体）等。
　本文主要介绍基础的 BST（二叉查找树）以及提升搜索效率的更高级的数据结构：R-B Tree（红黑树）。

1
2
3
4
5
6
7
8
9
10

// 定义（定义性声明）
int i;
// 声明（引用性声明）
extern int j;
// 初始化
int k = 7;
// 默认初始化
int l;
// 赋值
l = 100;

• 引用性声明不分配存储空间，如：extern int x;只是告诉编译器变量x是整型，已经在其它地方定义了。
• 定义是在内存中确定变量的位置、大小。
• 初始化是定义变量的时候赋给变量的值，强调从无到有这一过程。
• 赋值是初始化后用到该变量，赋给该变量新的值。

　本文是关于C/C++语言中常见的五个修饰符：static、const、extern、inline、volatile的含义和用法，在阅读本文前，建议先通过《声明/定义/初始化/赋值》了解有关C/C++中定义、声明等概念以及变量声明和定义的区别。

如何对 vector 初始化

• 大小为size的一维向量，二位向量

1
2

vector<what-type> var-name(what-size);
vector<vector<what-type>> var-name(rowSize, vector<what-type>(colSize));

• 数组转 vector

1
2
3
4
5
6
7
8
9
10
11
12

int rowSize = ?;
int colSize = ?;
what-type A_[rowSize][colSize] = {
  {element1, elment2, ..., element},
  {},
  ...
  {}
};
vector<vector<what-type>> A(rowSize, vector<what-type>(colSize));
for(int row=0; row<rowSize; row++) {
  A[row].assign(A_[row], A_[row] + colSize);
}

有向图 vs 无向图

• 有向图强调出入度的概念；无向图，其邻接矩阵 是一个对称矩阵。
• 无向图边的两端是对称的，无向图讲究连通这个概念，没有方向，没有拓扑。

判断图是否连通？（一个图有几个连通分量）

• 从一个指定的点开始，通过不同的策略去遍历这个图，有深度遍历和广度遍历。
• 每次经过一个节点的时候，首先判断一下这个节点是否已经访问过了，如果没有访问过，则这个节点可以作为下一次继续遍历的候选。
• 如果这个图是连通的话，这种方法最终会覆盖到整个图。所以可以采用一种计数统计的方式来实现。
  • 比如说每次访问一个以前没有遍历的节点，则将对应的计数加一。这样当最后遍历结束后，如果统计的节点和图本身的节点一样的话，表示这个图是连通的，否则表示不连通。
• 这种方法用来判断整个图是否为连通的时候，实际上只要给定一个点，然后按照给定的步骤可以把该点所连接的所有点都涵盖到。如果有其它分隔的部分则不会再处理了，所以，通过这种办法我们在图不是连通的情况下，它只需要涵盖图的一部分就执行结束了。最坏的情况时间复杂度也就是$O(V+E)$。

何为贪心？

• 贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就作出选择（下一步的选择总是在当前看来收敛最快和效果最明显的那一个），而且一旦做出了选择，不管将来有什么结果，这个选择策略都不会改变（以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题）。
• 贪心算法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。
• 贪心算法对于大部分的优化问题都能产生最优解（如单源最短路径问题，最小生成树等），但不能总获得整体最优解，通常可以获得近似最优解。
• 贪心策略一旦经过证明成立后，它就是一种高效的算法。