简介：这份PDF实验报告面向计算机专业学生及数据结构初学者，围绕哈夫曼树与哈夫曼编码的C语言实现展开，帮助读者理解变长前缀编码在数据压缩与通信中的核心作用。报告完整覆盖初始化、编码、译码、打印代码文件与打印哈夫曼树五大功能模块，并给出HTNode结构体、HuffmanCode指针数组及initHuffmanTree、HuffmanCoding、Select、encoding、decode、dispHT等核心函数的实现思路，还包含教科书例6-2与字符频度统计两组测试数据。资源包内共1个PDF文件，大小约917KB，内容以实验报告文档形式呈现，便于直接阅读与对照复现。目前已有196人学习下载，适合需要完成数据结构课程实验、准备算法练习或想深入掌握二叉树构建与遍历、文件读写及编解码流程的读者参考，可据此梳理需求分析、概要设计与详细设计各阶段的写作与编码要点。

1. 哈夫曼树实验报告为什么总在编码表这步翻车

带过几届数据结构实验课之后，我发现一个规律：哈夫曼树的实验报告，十份里有七份的分数差距不在建树，而在编码表。建树部分大家照着教材伪代码都能写出来，选两个最小权值、合并、放回，循环到只剩一个根节点，逻辑清晰。但一到生成编码、输出编码表、计算带权路径长度（WPL），各种问题就冒出来了——编码反了、前缀冲突、WPL 算错、中文乱码、文件读写路径不对。

这篇笔记面向正在做数据结构（C语言版）哈夫曼树实验的读者，也面向需要把哈夫曼编码真正用到压缩场景的开发者。我会把整个实验拆成可复现的步骤：从权值数组到哈夫曼树构建，从编码表生成到 WPL 验证，再到文件压缩解压的最小闭环。每一步都给可抄的 C 代码，并说清楚参数怎么设、哪里容易踩坑。读完你应该能独立写出一个能跑通、能验证、能讲清楚原理的哈夫曼树实验报告，而不是拼凑一份只能交差的文档。

2. 哈夫曼树构建：从权值数组到最小堆的选型与实现

2.1 为什么不用有序数组而用最小堆

哈夫曼树的核心操作是「每次取两个最小权值的节点」。最朴素的做法是每次遍历整个数组找最小值，时间复杂度 O(n²)。当字符集只有几十个时，这确实能跑，实验报告里也常见这种写法。但如果字符集到几千个，或者你想在报告里体现一点工程思维，最小堆是更合理的选择。

最小堆的插入和删除都是 O(log n)，整体建树复杂度降到 O(n log n)。C语言版实验里，我一般会手写一个简单的堆，而不是引入第三方库，因为实验报告需要展示你对数据结构的理解。堆里存的是节点指针或节点索引，比较的是权值。

还有一种做法是把所有节点按权值排序，然后维护两个队列：一个存叶子节点，一个存合并后的内部节点。每次从两个队列头部取最小值。这个做法在权值已经有序时是 O(n)，但需要额外处理排序，代码量不比堆少。对于实验报告，最小堆的通用性更好，也更容易讲清楚。

2.2 节点结构体与堆操作的最小实现

先定义节点结构。这里用静态数组存树节点，避免动态内存管理带来的调试麻烦。数组大小设为 2n-1，因为 n 个叶子节点合并 n-1 次，总共 2n-1 个节点。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_CHAR 256 #define MAX_NODE (2 * MAX_CHAR - 1) typedef struct { unsigned char ch; // 叶子节点对应的字符，内部节点为 0 int weight; // 权值 int parent; // 父节点下标，-1 表示无 int left; // 左孩子下标，-1 表示无 int right; // 右孩子下标，-1 表示无 } HTNode; typedef struct { int *data; // 存节点下标 int size; // 当前元素个数 int capacity; } MinHeap; // 初始化堆 MinHeap* heap_create(int capacity) { MinHeap *h = (MinHeap*)malloc(sizeof(MinHeap)); h->data = (int*)malloc(sizeof(int) * capacity); h->size = 0; h->capacity = capacity; return h; } // 交换两个下标 static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } // 向上调整 static void heap_up(MinHeap *h, int idx, HTNode *nodes) { while (idx > 0) { int parent = (idx - 1) / 2; if (nodes[h->data[parent]].weight <= nodes[h->data[idx]].weight) break; swap(&h->data[parent], &h->data[idx]); idx = parent; } } // 向下调整 static void heap_down(MinHeap *h, int idx, HTNode *nodes) { while (1) { int left = 2 * idx + 1; int right = 2 * idx + 2; int smallest = idx; if (left < h->size && nodes[h->data[left]].weight < nodes[h->data[smallest]].weight) smallest = left; if (right < h->size && nodes[h->data[right]].weight < nodes[h->data[smallest]].weight) smallest = right; if (smallest == idx) break; swap(&h->data[idx], &h->data[smallest]); idx = smallest; } } // 入堆 void heap_push(MinHeap *h, int node_idx, HTNode *nodes) { h->data[h->size] = node_idx; h->size++; heap_up(h, h->size - 1, nodes); } // 出堆，返回节点下标 int heap_pop(MinHeap *h, HTNode *nodes) { int top = h->data[0]; h->data[0] = h->data[h->size - 1]; h->size--; heap_down(h, 0, nodes); return top; }

这段代码里，heap_up和heap_down是比较权值来调整的，注意比较的是nodes[下标].weight，不是下标本身。heap_push把新节点放到数组末尾再向上调整，heap_pop把堆顶和末尾交换、缩小 size、再向下调整。参数nodes是整棵树的节点数组，堆里只存下标，这样节点权值变化时堆不需要重建。

2.3 建树主循环与三个易错参数

有了堆之后，建树逻辑就很直接了。先把所有叶子节点初始化，权值大于 0 的入堆。然后循环：弹出两个最小节点，合并成新节点，新节点入堆。直到堆里只剩一个节点，那就是根。

// 构建哈夫曼树，返回根节点下标 int huffman_build(HTNode *nodes, int *weights, int n) { // 初始化叶子节点 for (int i = 0; i < n; i++) { nodes[i].ch = (unsigned char)i; nodes[i].weight = weights[i]; nodes[i].parent = -1; nodes[i].left = -1; nodes[i].right = -1; } MinHeap *h = heap_create(n); for (int i = 0; i < n; i++) { if (weights[i] > 0) heap_push(h, i, nodes); } int next = n; // 下一个可用节点下标 while (h->size > 1) { int a = heap_pop(h, nodes); int b = heap_pop(h, nodes); nodes[next].ch = 0; nodes[next].weight = nodes[a].weight + nodes[b].weight; nodes[next].parent = -1; nodes[next].left = a; nodes[next].right = b; nodes[a].parent = next; nodes[b].parent = next; heap_push(h, next, nodes); next++; } int root = heap_pop(h, nodes); heap_free(h); return root; }

这里有三个参数容易出错。第一，next从n开始，因为前 n 个位置被叶子占了。第二，合并时左孩子放a、右孩子放b，这个顺序会影响后面编码的 0/1 方向，但不会影响 WPL，所以实验报告里只要前后一致就行。第三，循环条件是h->size > 1，不是>= 1，否则会多合并一次。

还有一个细节：如果某些字符权值为 0，不应该入堆，否则会生成无意义的编码。我在初始化时加了weights[i] > 0的判断。如果所有权值都是 0，堆为空，heap_pop会越界，所以实际使用时要保证至少有一个正权值。

3. 编码表生成：递归遍历与 WPL 计算的完整闭环

3.1 从根到叶的路径就是编码

哈夫曼编码的本质是：从根节点出发，往左走记 0，往右走记 1，到达叶子节点时路径上的 0/1 序列就是该字符的编码。因为每个叶子到根的路径唯一，所以编码不会重复；因为所有字符都在叶子节点，所以任何一个编码都不是另一个的前缀，这就是前缀码性质。

生成编码有两种方式。一种是递归遍历树，维护一个路径数组，到叶子时把路径复制出来。另一种是从叶子往上找父节点，反向确定 0/1，最后反转。递归方式更直观，也更容易在实验报告里画图说明。我一般用递归。

// 递归生成编码表 // code: 当前路径缓冲区 // depth: 当前深度 // codes: 输出编码表，每个字符一个字符串 void huffman_encode(HTNode *nodes, int root, char *code, int depth, char codes[MAX_CHAR][MAX_CHAR]) { if (root == -1) return; // 叶子节点 if (nodes[root].left == -1 && nodes[root].right == -1) { code[depth] = '\0'; strcpy(codes[nodes[root].ch], code); return; } // 左子树，路径加 '0' code[depth] = '0'; huffman_encode(nodes, nodes[root].left, code, depth + 1, codes); // 右子树，路径加 '1' code[depth] = '1'; huffman_encode(nodes, nodes[root].right, code, depth + 1, codes); }

code数组长度要足够，最坏情况是树退化成链，深度为 n-1。codes是二维数组，第一维按字符索引，第二维存编码字符串。注意strcpy之前要保证codes[nodes[root].ch]有足够空间，这里用MAX_CHAR作为每行长度，对于 256 个字符的字符集够用。

3.2 WPL 的两种算法与交叉验证

带权路径长度 WPL 是哈夫曼树实验报告里必算的指标。定义是：所有叶子节点的权值乘以路径长度之和。有两种算法。

第一种是遍历每个叶子，累加weight * depth。第二种是利用性质：WPL 等于所有非叶子节点的权值之和。这个性质在教材里通常作为习题出现，但实验报告里用第二种算法可以交叉验证第一种的结果。

// 算法一：遍历叶子累加 int wpl_by_leaves(HTNode *nodes, int n) { int total = 0; for (int i = 0; i < n; i++) { if (nodes[i].weight == 0) continue; int depth = 0; int cur = i; while (nodes[cur].parent != -1) { depth++; cur = nodes[cur].parent; } total += nodes[i].weight * depth; } return total; } // 算法二：非叶子节点权值之和 int wpl_by_internal(HTNode *nodes, int n, int total_nodes) { int total = 0; for (int i = n; i < total_nodes; i++) { total += nodes[i].weight; } return total; }

两个函数的结果应该相等。如果不等，说明建树过程有问题，比如某个节点 parent 没设对，或者合并时权值算错了。我在实验报告里会同时贴出两个结果，并说明它们为什么相等，这样能体现对原理的理解，而不是只贴一个数字。

3.3 编码表输出与文件写入

生成编码表之后，通常要输出到控制台和文件。控制台输出用printf，文件输出用fprintf。这里有一个常见坑：字符可能是不可打印的，比如换行符、制表符，直接输出会破坏格式。我一般会把字符转成可读形式，比如用%02X输出十六进制，或者对特殊字符做转义。

void print_codes(HTNode *nodes, int n, char codes[MAX_CHAR][MAX_CHAR]) { printf("%-8s %-8s %-8s %s\n", "字符", "权值", "编码", "码长"); for (int i = 0; i < n; i++) { if (nodes[i].weight == 0) continue; // 可打印字符直接显示，否则显示十六进制 if (nodes[i].ch >= 32 && nodes[i].ch < 127) printf("%-8c %-8d %-8s %zu\n", nodes[i].ch, nodes[i].weight, codes[i], strlen(codes[i])); else printf("0x%02X %-8d %-8s %zu\n", nodes[i].ch, nodes[i].weight, codes[i], strlen(codes[i])); } }

%-8c表示左对齐占 8 个字符宽度，%zu是size_t的格式符，用于strlen返回值。如果编译器不支持%zu，可以强制转成int用%d。文件写入类似，把printf换成fprintf(fp, ...)即可。

4. 避坑与排查：哈夫曼树实验里最常见的 5 个翻车现场

4.1 编码反了：左 0 右 1 还是左 1 右 0

现象：生成的编码和同学对不上，或者和教材例题对不上。原因：左孩子记 0 还是记 1 没有统一约定。哈夫曼编码本身不唯一，左 0 右 1 和左 1 右 0 都是合法的，WPL 也一样。但如果实验报告要求与某个标准答案一致，就需要按标准来。解决：在报告里明确写出你的约定，并且全篇一致。如果老师要求特定方向，就按老师的要求改递归里code[depth]的赋值。

4.2 前缀冲突：某个编码是另一个的前缀

现象：解码时出现歧义，比如 01 既是 A 的编码又是 B 的编码前缀。原因：通常是把字符放在了内部节点，或者建树时没有保证所有字符都在叶子。解决：检查建树代码，确保只有叶子节点才被赋予字符编码。内部节点的ch应该设为 0 或特殊标记，不参与编码表生成。另外，如果两个字符权值相同，合并顺序不同会导致树形不同，但不会产生前缀冲突，因为哈夫曼树的性质保证前缀码。

4.3 WPL 算错：深度从 0 还是从 1 开始

现象：WPL 结果比预期小或大。原因：路径长度的定义。根节点深度为 0 时，叶子深度等于边数；根节点深度为 1 时，叶子深度等于节点数。教材通常用边数，即根深度为 0。解决：在wpl_by_leaves里，depth初始为 0，每向上走一次加 1，这样叶子深度就是边数。如果从 1 开始，结果会多出权值总和。两种算法交叉验证时，确保都用同一定义。

4.4 中文乱码：字符集与文件编码不匹配

现象：处理中文文本时，编码表里出现乱码，或者压缩后解压不对。原因：C 语言里char是有符号的，中文 UTF-8 编码每个字节可能大于 127，作为unsigned char处理才安全。另外，文件读写时没有用二进制模式，导致换行符被转换。解决：节点里的ch用unsigned char，文件用"rb"和"wb"打开。如果只处理 ASCII，可以忽略这条，但实验报告里如果用了中文测试数据，就要注意。

4.5 内存越界：节点数组开小了

现象：程序崩溃或结果随机。原因：MAX_NODE设为2 * MAX_CHAR - 1，但如果实际字符数超过MAX_CHAR，或者权值数组长度超过预期，就会越界。解决：动态计算节点数，用2 * n - 1分配，而不是固定宏。如果坚持用静态数组，就在入口处检查n是否超过MAX_CHAR，超过就报错退出。另外，堆的capacity也要至少为n，否则heap_push会越界。

5. 从实验到实战：文件压缩解压的最小闭环与验证技巧

5.1 把编码表变成二进制流

实验报告通常到生成编码表就结束了，但真正理解哈夫曼编码，最好再走一步：用编码表压缩一个文件，再解压回来，对比是否一致。这一步能把「前缀码」「位操作」「文件读写」串起来。

压缩的核心是：读入原文件每个字节，查编码表得到 0/1 字符串，把这些位拼成字节写入输出文件。需要维护一个位缓冲区，每 8 位写一个字节。最后一个字节不足 8 位时，要记录有效位数，否则解压时多出的 0 会变成额外字符。

// 压缩文件：in_path 原文件，out_path 输出文件 // codes 编码表，n 字符种类数 void compress_file(const char *in_path, const char *out_path, char codes[MAX_CHAR][MAX_CHAR], int n) { FILE *fin = fopen(in_path, "rb"); FILE *fout = fopen(out_path, "wb"); if (!fin || !fout) { perror("open"); return; } // 先写字符种类数，解压时要用 fwrite(&n, sizeof(int), 1, fout); // 写编码表：每个字符的 ch、权值、编码长度、编码位 for (int i = 0; i < n; i++) { if (codes[i][0] == '\0') continue; unsigned char ch = (unsigned char)i; int len = strlen(codes[i]); fwrite(&ch, sizeof(unsigned char), 1, fout); fwrite(&len, sizeof(int), 1, fout); // 把编码字符串转成位写入，这里简化：按字节存 0/1 字符 fwrite(codes[i], 1, len, fout); } // 压缩数据 unsigned char buf = 0; int bit_count = 0; int ch; while ((ch = fgetc(fin)) != EOF) { char *code = codes[(unsigned char)ch]; for (int i = 0; code[i]; i++) { buf = (buf << 1) | (code[i] - '0'); bit_count++; if (bit_count == 8) { fwrite(&buf, 1, 1, fout); buf = 0; bit_count = 0; } } } // 处理剩余位 if (bit_count > 0) { buf = buf << (8 - bit_count); fwrite(&buf, 1, 1, fout); } // 写有效位数，解压时用 fwrite(&bit_count, sizeof(int), 1, fout); fclose(fin); fclose(fout); }

这段代码为了可读性，编码表直接按 0/1 字符存储，没有做位压缩。实际压缩率会差一些，但逻辑清晰，适合实验报告。bit_count记录最后一个字节的有效位数，解压时据此判断是否读完。

5.2 解压与一致性验证

解压是压缩的逆过程：读编码表重建哈夫曼树，然后读二进制流，从根开始走，遇 0 往左、遇 1 往右，到叶子就输出字符，回到根继续。

// 解压文件 void decompress_file(const char *in_path, const char *out_path) { FILE *fin = fopen(in_path, "rb"); FILE *fout = fopen(out_path, "wb"); if (!fin || !fout) { perror("open"); return; } int n; fread(&n, sizeof(int), 1, fin); // 重建编码表 char codes[MAX_CHAR][MAX_CHAR] = {{0}}; for (int i = 0; i < n; i++) { unsigned char ch; int len; fread(&ch, sizeof(unsigned char), 1, fin); fread(&len, sizeof(int), 1, fin); fread(codes[ch], 1, len, fin); codes[ch][len] = '\0'; } // 读压缩数据，这里需要知道文件剩余长度和最后有效位数 // 简化处理：先读到最后，再解析 fseek(fin, 0, SEEK_END); long file_size = ftell(fin); // 最后 4 字节是 bit_count fseek(fin, -(long)sizeof(int), SEEK_END); int last_bits; fread(&last_bits, sizeof(int), 1, fin); long data_start = ftell(fin) - (file_size - ftell(fin)) + sizeof(int); // 实际实现时建议记录数据段起始偏移，这里略去细节 // 用编码表反向查找：读位，匹配编码 // 更高效的做法是重建哈夫曼树，这里用简单匹配演示 unsigned char buf; char bit_str[MAX_CHAR * 8] = {0}; int bit_len = 0; // ... 读取位并匹配编码，输出字符 // 完整实现需要处理位缓冲和最后字节有效位 fclose(fin); fclose(fout); }

上面解压代码省略了位读取和匹配的完整实现，因为篇幅关系。核心思路是：维护一个当前编码字符串，每读一位就追加，然后查表看是否匹配某个字符的编码。匹配就输出并清空，继续。由于是前缀码，不会出现匹配歧义。验证方法是：压缩一个文本文件，再解压，用diff或fc对比原文件和解压文件，完全一致就说明编码表、位操作、文件读写都正确。

5.3 一个验证 WPL 是否正确的技巧

如果不想写完整的压缩解压，可以用一个更轻量的验证：对同一组权值，分别用「遍历叶子」和「非叶子求和」算 WPL，再手工算一遍小规模例子。比如权值 {1, 2, 3, 4}，手工建树：合并 1+2=3，得到 {3, 3, 4}；合并 3+3=6，得到 {4, 6}；合并 4+6=10。WPL = 1×3 + 2×3 + 3×2 + 4×1 = 3+6+6+4 = 19。非叶子权值和 = 3+6+10 = 19。两个结果一致，说明代码正确。

这个手工验证花不了几分钟，但能帮你快速定位是建树错了还是 WPL 计算错了。我一般会在实验报告里附上这个小例子，作为代码正确性的佐证。

5.4 我踩过的一个坑：权值为 0 的字符

早期写哈夫曼树时，我没有过滤权值为 0 的字符，结果建树时把 0 也入堆，导致生成的编码表里多出很多无意义的短编码，WPL 也偏小。后来在入堆前加了weights[i] > 0判断，问题解决。如果你的实验数据里有字符出现次数为 0，记得跳过它们。另外，如果所有权值都是 0，程序会崩溃，所以入口处要检查至少有一个正权值。

希望帮到你。

本文还有配套的精品资源，点击获取