赫夫曼编码(前缀码)
向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。
五、 图
1．
完全图：有1\\2 n(n-1)条变得无向图
有向完全图：具有n（n-1）条弧的有向图。 权：与图的边或弧相关的数。
顶点v的度：和v相关联的边的数目。 入度：以顶点v为头的弧的数目 出度：以顶点v为尾的弧的数目
回路或环：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 2. 图的存储结构
·邻接矩阵：
A 0 1 1 0 0 B 0 0 1 1 0 C 0 0 0 1 0 D 1 0 0 0 0 E 1 0 0 1 0 ·邻接表：
typedef struct ArcNode { // 弧结点 int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VexNode { // 顶点结点 VertexType
ArcNode *firstarc; } VexNode;
const int MAX_VERTEX = 最大顶点个数; typedef struct Graph { // 图 VexNode
int vexnum, arcnum; } Graph;
边(弧)多则需要存储空间多。
// 邻接点
// 下一个邻接点
data; // 顶点信息 // 第一个邻接点
vexs[MAX_VERTEX]; // 顶点向量 // 顶点和弧的个数
·十字链表： 十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点。 ·邻接多重表 3. 图的遍历
1) 深度优先（DFS）搜索
访问方式：从图中某顶点v出发： a）访问顶点v；
b）从v的未被访问的邻接点出发，继续对图进行深度优先遍历，若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，结束。
2) 广度（宽度，BFS）优先搜索
a）访问顶点v ；
b）访问同v相邻的所有未被访问的邻接点w1,w2, …wk； c）依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问； 4. 生成树和最小生成树
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。 1) 最小生成树
·Kruskal算法
一句话，“不构成环的情况下，每次选取最小边”。
5 B 3 1 A 3 E 3 C 5 B 3 1 A 3 E 3 C ·普里姆算法
2 6 7 D (d) B 2 6 7 D (a) B 5 3 1 A 3 E 3 C 5 3 1 A 3 E 3 C 2 6 7 D (e) B 2 6 7 D (b) B 5 3 1 A 3 E 3 C 5 3 1 A 3 E 3 C 2 6 7 D (f) 2 6 7 D (c)
0 1 2 3 4 A B C D E 1 2 3 0 0 /\\ /\\ 2 /\\ 3 /\\ 3 /\\