第二十五讲 赫夫曼编码算法.pptVIP

第 二十五讲 知 识 点 赫夫曼树的建立和编码算法 图的基本定义和性质 3、从叶子结点向上编码算法 P147 算法6.12 void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n) { // w存放n个字符的权值(均0)，构造哈夫曼树HT， // 并求出n个字符的哈夫曼编码HC int i, j, m, s1, s2, start; char *cd; unsigned int c, f; if (n=1) return; m = 2 * n - 1;//m=n0+n2=2*n0-1 HT=(HuffmanTree)malloc((m+1)* sizeof(HTNode)); // 0号单元未用 for (i=1; i=n; i++) //初始化 { HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i=m; i++) { HT[i].weight=0; //初始化 HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i=m; i++) { // 建哈夫曼树 // 在HT[1..i-1]中选择parent为0且weight最小的两个结点， // 其序号分别为s1和s2。 Select(HT, i-1, s1, s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; //--- 从叶子到根逆向求每个字符的哈夫曼编码 --- cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间 cd[n-1] = \0; // 编码结束符。 for (i=1; i=n; ++i) {// 逐个字符求哈夫曼编码 start = n-1; // 编码结束符位置，最长只可能有n-1个编码 for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) // 从叶子到根逆向求编码 if (HT[f].lchild==c) cd[--start] = 0; else cd[--start] = 1; HC[i] = (char *)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间 strcpy(HC[i], cd[start]); // 从cd复制编码(串)到HC } free(cd); // 释放工作空间} 图G由V（G）和E（G）这两个集合所组成，记为G=（V，E），其中V（G）是顶点（Vertex）的非空集，每个顶点可以标以不同的字符或数字；E（G）是边（Edge）的集合，特殊情况下E（G）可以是空集。每个边由其所连接的两个顶点表示。 无向图：对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。 有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。 3、完全图 在一个有n个顶点的无向图中，若每个顶点 到其它（n-1）个顶点都有一条边，则图中 共有n(n-1)/2条边，这种图称为完全图（Complete graph，也称完备图）。 下图所示就是n=4的完全图，共有六条边。 4、权和网络 对应每条边有一相应的数值，这个数值叫做该 边的权(Weight)。边上带权的图称为带权图， 也称为网络(Network)。 5、子图 设有两个图G =(V,E)和G’=(V’,E’)，若V(G’)是 V(G)的子集，且E(G’)是E(G)的子集，则称G’是 G的子图Subgraph)。 6、顶点的度 图中与每个顶点相连的边数叫该顶点的度。 7、入度、出度 对于有向图，顶点的度分为入度和出度。 入度是以该顶点为终点（头）的入边数目； 出度是以该顶点为起点（尾）的出边数目； 顶点的度等于其入度