当前位置：首页 > news >正文

408考研必看：哈夫曼编码加权平均长度计算实战（附C语言完整代码）

news 2026/5/12 16:14:30

哈夫曼编码加权平均长度计算：从原理到C语言实战

在计算机考研408的数据结构科目中，哈夫曼编码及其加权平均长度的计算是一个高频考点。这道题目不仅考察对基础概念的理解，更检验考生的实际计算能力和编程实现水平。本文将带你从零开始，彻底掌握这一重要知识点。

1. 哈夫曼编码基础概念

哈夫曼编码是一种基于贪心算法的最优前缀编码方法，由David A. Huffman于1952年提出。它的核心思想是通过构建一棵特殊的二叉树——哈夫曼树，来实现对字符的高效编码。

关键术语解析：

字符频次：每个字符在文本中出现的频率，也称为权值
编码长度：字符对应的二进制码的位数
带权路径长度(WPL)：所有叶子节点的权值乘以其到根节点路径长度之和
加权平均长度：WPL除以总频次，表示平均每个字符的编码位数

注意：哈夫曼编码的一个重要性质是，没有任何一个字符的编码是另一个字符编码的前缀，这保证了编码的唯一可解码性。

2. 哈夫曼树构建实战

让我们通过一个具体例子来演示哈夫曼树的构建过程。假设有6个字符，其频次分别为：[3, 4, 5, 6, 8, 10]。

2.1 构建步骤详解

初始化森林：将每个字符视为一棵只有根节点的树，组成森林
```
{3}, {4}, {5}, {6}, {8}, {10}
```

第一次合并：选择权值最小的两棵树(3和4)合并

新节点权值 = 3 + 4 = 7 森林更新为：{5}, {6}, {7}, {8}, {10}

第二次合并：选择5和6合并

新节点权值 = 5 + 6 = 11 森林更新为：{7}, {8}, {10}, {11}

第三次合并：选择7和8合并

新节点权值 = 7 + 8 = 15 森林更新为：{10}, {11}, {15}

第四次合并：选择10和11合并

新节点权值 = 10 + 11 = 21 森林更新为：{15}, {21}

最终合并：合并最后两棵树

新节点权值 = 15 + 21 = 36 哈夫曼树构建完成

2.2 哈夫曼树可视化

最终的哈夫曼树结构如下：

36 / \ 15 21 / \ / \ 7 8 10 11 / \ 3 4

3. 加权平均长度计算方法

计算加权平均长度有两种等效的方法，下面我们分别演示。

3.1 方法一：直接计算WPL

确定每个字符的编码长度（路径边数）：
- 频次3：3
- 频次4：3
- 频次5：3
- 频次6：3
- 频次8：2
- 频次10：2

计算WPL：

WPL = (3×3) + (4×3) + (5×3) + (6×3) + (8×2) + (10×2) = 9 + 12 + 15 + 18 + 16 + 20 = 90

计算总频次：
```
总频次 = 3 + 4 + 5 + 6 + 8 + 10 = 36
```

求加权平均长度：

加权平均长度 = WPL / 总频次 = 90 / 36 = 2.5

3.2 方法二：利用内部节点权值和

哈夫曼树的一个重要性质是：WPL等于所有内部节点权值之和。

列出所有内部节点权值：
```
7, 11, 15, 21, 36
```
计算内部节点权值和：
```
7 + 11 + 15 + 21 + 36 = 90
```

计算加权平均长度：

加权平均长度 = 内部节点权值和 / 总频次 = 90 / 36 = 2.5

4. C语言完整实现

下面给出完整的C语言实现，包含哈夫曼树构建和两种WPL计算方法。

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_SIZE 100 typedef struct { int weight; int parent, lchild, rchild; } HTNode, *HuffmanTree; void Select(HuffmanTree HT, int end, int *s1, int *s2) { int i, min1 = INT_MAX, min2 = INT_MAX; *s1 = *s2 = 0; for (i = 1; i <= end; i++) { if (HT[i].parent == 0) { if (HT[i].weight < min1) { min2 = min1; *s2 = *s1; min1 = HT[i].weight; *s1 = i; } else if (HT[i].weight < min2) { min2 = HT[i].weight; *s2 = i; } } } } void CreateHuffmanTree(HuffmanTree *HT, int *weights, int n) { int i, m, s1, s2; m = 2 * n - 1; *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); for (i = 1; i <= m; i++) { (*HT)[i].parent = 0; (*HT)[i].lchild = 0; (*HT)[i].rchild = 0; (*HT)[i].weight = 0; } for (i = 1; i <= n; i++) { (*HT)[i].weight = weights[i - 1]; } for (i = n + 1; i <= m; i++) { 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; } } void CalculateCodeLengths(HuffmanTree HT, int n, int *lengths) { int i, p, len; for (i = 1; i <= n; i++) { len = 0; p = i; while (HT[p].parent != 0) { len++; p = HT[p].parent; } lengths[i - 1] = len; } } double CalculateWPL(int *weights, int *lengths, int n) { int i, totalWeight = 0, totalWeightedLength = 0; for (i = 0; i < n; i++) { totalWeight += weights[i]; totalWeightedLength += weights[i] * lengths[i]; } return (double)totalWeightedLength / totalWeight; } double CalculateWPLFromInternalNodes(HuffmanTree HT, int n) { int i, totalWeight = 0, internalNodesWeightSum = 0; for (i = 1; i <= n; i++) { totalWeight += HT[i].weight; } for (i = n + 1; i <= 2 * n - 1; i++) { internalNodesWeightSum += HT[i].weight; } return (double)internalNodesWeightSum / totalWeight; } int main() { int weights[] = {3, 4, 5, 6, 8, 10}; int n = sizeof(weights) / sizeof(weights[0]); int lengths[n]; HuffmanTree HT; CreateHuffmanTree(&HT, weights, n); CalculateCodeLengths(HT, n, lengths); printf("方法一结果: %.2f\n", CalculateWPL(weights, lengths, n)); printf("方法二结果: %.2f\n", CalculateWPLFromInternalNodes(HT, n)); free(HT); return 0; }