课程设计说明书 No 6
扩充二叉树 F: {5},{4},{7},{2} F: {5},{6} ,{7} 6 5 4 7 2 2 4 5 7 (a) 初始 F: {11},{7} (b)合并树{2}{4} 后 F: {18} 18 117 5 6 5 6 11 2 4 7 2 4 (c) 合并树{5}{6} 后 (d) 合并树{7}{11} 后 图2 哈夫曼树的构造过程 2.4 详细设计 2.4.1 程序流程图 沈 阳 大 学 课程设计说明书 No 7
开 始 创建一个空的赫夫曼树 Y 判断PHt是否为空 N 输入m 判断m是否比1Y 输入外部结点个数及权值 找两个最小权的无父结点的结点构造新的二叉树 N 得到新的结点 所有结点生成树 得到赫夫曼树编码 输出 结束 图3 流程图 沈 阳 大 学 课程设计说明书 No 8
2.4.2 算法设计 (1)建立最优二叉树函数 由于赫夫曼树种没有度为的结点（这类又称严格的（strict）(或正则的)二叉树），则一颗有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。如何选定结点结构？由于在构成赫夫曼树之后，为求编码需要从叶子结点出发走一条从叶子到根的路径；而为译码需要从根出发走一条从根到叶子的路径。则对每个节点而言，既需知双亲的信息，又需知孩子结点的信息。由此： 二叉树的存储结构： #define MAXINT 2147483647 #define MAXNUM 50 /* 数组w中最多容纳的元素个数，注意 m<=MAXNUM */ #define MAXNODE 100 /* 哈夫曼树中的最大结点数，注意 2*m-1 {/* 置初态 */ pht->ht[i].llink = -1; pht->ht[i].rlink = -1; pht->ht[i].parent = -1; if (i < m) pht->ht[i].ww = w[i]; else pht->ht[i].ww = -1; } for ( i = 0; i < m-1; i++) {/* 每循环一次构造一个内部结点 */ m1 = MAXINT; m2 = MAXINT;/* 相关变量赋初值 */ x1 = -1; x2 = -1; for (j= 0; j < m+i; j++) /* 找两个最小权的无父结点的结点 */ if (pht->ht[j].ww < m1 && pht->ht[j].parent == -1) { m2 = m1; x2 = x1; m1= pht->ht[j].ww; x1 = j; } else if (pht->ht[j].ww < m2 && pht->ht[j].parent == -1) { m2 = pht->ht[j].ww; x2 = j; } pht->ht[x1].parent = m+i; /* 构造一个内部结点 */ pht->ht[x2].parent = m+i; pht->ht[m+i].ww = m1+m2; pht->ht[m+i].llink = x1; pht->ht[m+i].rlink = x2; pht->root = m+i; } return pht; } 沈 阳 大 学 课程设计说明书 No 10 (3)字符的赫夫曼编码的算法 向量HT的前n个分量表示叶子结点，最后一个分量表示根结点。各字符的编码长度不等，所以按实际长度分配空间。求每个字符的赫夫曼编码是从叶子到根的逆向处理。也可以从根出发遍历整棵赫夫曼树，求得各叶子结点所表示的字符的赫夫曼编码。算法如下： int main() { int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf(\ input m = \输入外部结点个数*/ scanf(\ &m); if (m < 1) { printf(\ reasonable!\\n\ return 1; } w = (int *)malloc(sizeof(int)*m); if (w == NULL) { printf(\ return 1; } printf(\ input the %d numbers：\\n\输入权值*/ for (j= 0; j < m; j++) scanf(\ w+j); pht = huffman(m, w); for (j = 0; j < m; j++) { printf(\ Reverse code of the %d node is:\ j+1);/*得到的编码应倒过来*/ i = j; while (pht->ht[i].parent != -1) { parent = pht->ht[i].parent; if (pht->ht[parent].llink == i) 沈 阳 大 学