哈夫曼编码C语言实现

### 哈夫曼编码 C语言 实现 以下是基于哈夫曼编码原理的一个完整的 C 语言实现示例。该程序通过构建哈夫曼树来生成字符对应的编码表，并支持简单的编码功能。 #### 数据结构定义 为了方便操作，通常会定义两个数组分别存储哈夫曼树节点和最终的编码结果： ```c #include <stdio.h> #include <stdlib.h> #define MAXNODES 100 // 定义最大节点数 typedef struct { unsigned int weight; // 权重 unsigned int parent; // 父亲结点索引 unsigned int lchild; // 左孩子结点索引 unsigned int rchild; // 右孩子结点索引 } HTNode; // 创建哈夫曼树并计算编码 void createHuffmanTreeAndCode(double *weights, int n, HTNode ht[], char hc[][MAXNODES]) { int m = 2 * n - 1; int i, j; // 初始化哈夫曼树 for (i = 0; i < m; ++i) { ht[i].weight = (i < n ? weights[i] : 0); ht[i].parent = ht[i].lchild = ht[i].rchild = 0; } // 构建哈夫曼树 for (i = n; i < m; ++i) { int s1 = -1, s2 = -1; double min1 = __DBL_MAX__, min2 = __DBL_MAX__; for (j = 0; j < i; ++j) { if (!ht[j].parent && ht[j].weight < min1) { min2 = min1; s2 = s1; min1 = ht[j].weight; s1 = j; } else if (!ht[j].parent && ht[j].weight < min2) { min2 = ht[j].weight; s2 = j; } } ht[s1].parent = ht[s2].parent = i; ht[i].lchild = s1; ht[i].rchild = s2; ht[i].weight = ht[s1].weight + ht[s2].weight; } // 计算哈夫曼编码 for (i = 0; i < n; ++i) { int child = i, father = ht[child].parent; while (father != 0) { if (ht[father].lchild == child) strcat(hc[i], "0"); else strcat(hc[i], "1"); child = father; father = ht[child].parent; } strrev(hc[i]); // 将字符串反转得到正确的编码顺序 } } int main() { int n = 5; // 字符数量 double weights[] = {0.12, 0.40, 0.15, 0.08, 0.25}; // 各字符权重 HTNode ht[MAXNODES]; char hc[n][MAXNODES]; // 存储编码 // 初始化编码为空串 for (int i = 0; i < n; ++i) { hc[i][0] = '\0'; } // 创建哈夫曼树并获取编码 createHuffmanTreeAndCode(weights, n, ht, hc); // 输出编码结果 printf("Character\tWeight\tEncoding\n"); for (int i = 0; i < n; ++i) { printf("%c\t\t%.2f\t%s\n", 'a' + i, weights[i], hc[i]); } return 0; } ``` 此代码实现了以下功能： - 使用 `double` 类型表示权值，便于处理浮点概率[^3]。 - 动态调整父节点与子节点关系以完成哈夫曼树的构建[^1]。 - 编码过程采用逆序记录路径的方式，最后翻转字符串获得正确编码[^2]。 #### 运行结果示例 假设输入字符及其对应频率如下所示，则运行后的输出可能类似于下述形式： | Character | Weight | Encoding | |-----------|--------|----------| | a | 0.12 | 00 | | b | 0.40 | 1 | | c | 0.15 | 010 | | d | 0.08 | 0110 | | e | 0.25 | 011 | 以上表格展示了如何根据给定数据集生成相应的哈夫曼编码。