用哈夫曼编码与C语言实现文件压缩：从最小堆到位流全解析

简介：面向数据结构课程设计的一份完整实现方案：用哈夫曼编码实现文件压缩，配套C语言源码与实验报告，适合需要完成同类实验、复习哈夫曼树构建与二叉树遍历的在校生和自学者。压缩包共2个文件，分别为源代码文件和Word版实验报告，整体约433KB，代码与文档一一对应，便于边看原理边跑程序。已有4706人学习下载，属于经过较多学习者验证的参考资料。源代码定义了哈夫曼树节点结构、哈夫曼编码表结构，并封装初始化文件名、创建文件名、压缩文件等14个函数，覆盖从统计ASCII字符频率、构造哈夫曼树到写入编码实现压缩的完整流程；实验报告则交代了实验目的、设备环境、概要设计及类型定义，还给出菜单函数的设计思路。这套代码的模块划分清晰，结构体定义与核心算法均可在类似压缩项目中直接参考或复用。

1. 用哈夫曼编码做文件压缩：为什么这份C语言代码值得跑一遍

用哈夫曼编码做文件压缩，是我拆过的C语言项目里最值得跑一遍的练习。它不是复杂度最高的算法，却能让你看到“数据结构”怎么变成真实工具：先统计每个字节出现次数，再拿最小堆构造哈夫曼树，给高频字节分短编码、给低频字节分长编码，最后把变长码按位写进文件，解压时沿着树走到叶子还原字节。这份代码加报告的资源，覆盖了原理、实现、测试报告，适合正在学树与贪心算法的学生，也适合想快速上手C语言文件读写的开发者。项目会带你完整走一遍压缩与解压的闭环，跑通后你对指针、位运算和进制转换的感觉会明显不一样。

2. 架构设计与目录结构：C语言+最小堆如何组织代码和报告

2.1 顶层组织：代码和报告各司其职

拿到这份资源，第一眼通常是“代码+报告”两个大块。代码是一套能独立编译的小工程，报告则是面向答辩的文字材料，两者并不是简单重复：代码给出可运行实现，报告解释为什么这样设计、测试数据怎么选、出了哪些坑。常见组织方式是把算法文件平铺在根目录下，用一条 gcc 命令或者 Makefile 编译。下面是我见过最多的一种布局。

file_compressor/ ├── main.c # 入口，解析 -c/-d 参数，串联压缩/解压流程 ├── huffman.c/.h # 哈夫曼树构建、编码表生成、压缩/解压驱动 ├── heap.c/.h # 最小堆：每次取频次最小的两个节点 ├── bitio.c/.h # 位级写入/读取缓冲，解决“按bit写文件”问题 ├── testdata/ # 测试用的文本、二进制样例 └── report.md # 课程设计报告：原理、流程、压缩率对比、问题记录

这是我认为最清爽的结构：把位读写单独拆开，因为哈夫曼编码最大的麻烦不是树怎么建，而是怎么把变长编码按位写进文件、又按位读回来。heap.c单独成文件也是结构课作业里的“加分项”，因为课程要求通常包含优先队列实现，单独拆出来更好讲解。main.c只负责命令行交互和参数传递，不直接操作位流；huffman.c是核心业务逻辑；bitio.c是底层工具。这样做的直接好处是后续扩展：比如你想加“批处理压缩多个文件”，只需要改main.c的循环，算法部分不用动。

2.2 模块职责与数据流

压缩和解压是两条相反的流水线。压缩侧：打开原文件并统计每个字节的出现次数，把出现次数作为权值构建哈夫曼树，再从根到叶子生成每个字节的二进制串；随后把树结构写进压缩文件头部，最后把原文件逐字节转换成编码位流追加到文件。解压侧相反：从文件头读回树结构，然后逐位读取压缩数据，从树根出发，遇0走左子树、遇1走右子树，走到叶子就输出一个字节，继续读下一位。

数据流关系可以这样看：压缩时，count_frequency填满一个长度256的数组；然后所有频率非0的节点进入最小堆；堆里不断弹出两个最小节点并合并，直到堆中只剩一个根节点；用深度优先遍历生成编码表；最后encode_file把文件和编码表喂给BitWriter。解压时，BitReader从压缩文件中读出01字符串，decode_file沿树还原字节。

这里有一个容易忽略的架构决策：哈夫曼编码是变长码，编码表不是定长字节表，所以“文件里必须保存重建树所需的信息”，否则解压端拿不到编码规则。这份资源在文件头部写的是哈夫曼树的先序遍历结果，同时标记每个叶子字节的值；这是常见做法，而不是把整个256长度编码表原样存进去，因为后者会占用固定2KB以上，小文件很不划算。

2.3 关键选择：为什么用最小堆而不是排序构建

构建哈夫曼树时，公认做法是每次从频率集合中取两个最小值合并。取最小值可以用排序后顺序扫描，也可以每次线性找最小，但更标准的数据结构解法是用最小堆，把建堆复杂度压到 O(n)。在C语言里，自己实现一个小根堆是一个很典型的算法练习。

void heap_push(MinHeap *h, HNode *node) { int i = h->size++; while (i > 0 && h->data[(i - 1) / 2]->freq > node->freq) { h->data[i] = h->data[(i - 1) / 2]; // 父节点下移 i = (i - 1) / 2; } h->data[i] = node; }

heap_push从数组末尾开始向上调整，保持小根堆性质。h->data是HNode*指针数组，比较的是节点里的freq字段；上移节点时只移动指针，不复制节点结构，所以内存开销是可控的。使用最小堆后，建树过程每次弹出两个最小节点并合并，做 n-1 次合并即可完成整棵树。如果换用每次线性扫描找最小值，代码会短，但复杂度退化成 O(n^2)，数据量一大就能感觉到差别。

报告里通常会把“为什么选最小堆”写成“用堆实现优先队列，符合贪心算法每一步取全局最优”的说法。这里的贪心体现在：合并两个最小频率节点后，新节点频率重新进入堆，继续取下一对最小频率，最终得到带权路径长度最小的树。这个设计在课程答辩里是重点，重点讲清楚“每次取最小”就能讲明白哈夫曼编码的本质。

3. 核心代码拆解：一个字节从频率统计到落盘位流

3.1 统计频率：用256个计数器覆盖所有字节

压缩的第一步永远是把字节出现次数数清楚。C语言里不能直接用char做数组下标，因为有符号与无符号问题，常见做法是定义一个长度为256的unsigned long long数组，读到每个字节后，先把fgetc的返回值转换成unsigned char再自增。

void count_frequency(FILE *in, unsigned long long freq[256]) { int c; memset(freq, 0, sizeof(unsigned long long) * 256); while ((c = fgetc(in)) != EOF) { freq[(unsigned char)c]++; } }

这里fgetc返回int，是为了能区分普通字节和EOF=-1。如果直接用char c，在默认有符号的平台上，读取 0xFF 字节会返回 -1，和 EOF 混淆，导致统计错乱。所以“先判断 EOF，再转 unsigned char”是必须的顺序。unsigned long long做计数器可以处理几GB级别的文件，但要注意：如果文件超过 64 位计数范围，仍会溢出，对课程作业来说完全够用。

统计完之后，数组中很多位置是0。建树时只把频率不为0的节点送入最小堆，避免为256个空节点做无意义的合并。这一步也决定了后续解压时能否正确处理“文件中没有出现的字节”：树上不会有对应叶子，编码表中也不会有对应项。

3.2 构造哈夫曼树：每次弹出两个最小节点合并

堆已经就绪，接下来是核心的建树逻辑。循环条件是堆中节点数大于1，每次弹出左右两个节点，合并成父亲节点，再把父亲放回堆。合并次数固定为有效字符数 - 1。

HNode *build_huffman_tree(unsigned long long freq[256]) { MinHeap heap; heap_create(&heap, 256); for (int i = 0; i < 256; i++) { if (freq[i] > 0) { heap_push(&heap, new_node((unsigned char)i, freq[i])); } } while (heap.size > 1) { HNode *left = heap_pop(&heap); HNode *right = heap_pop(&heap); HNode *parent = new_node(0, left->freq + right->freq); parent->left = left; parent->right = right; heap_push(&heap, parent); } return heap_pop(&heap); // 堆里最后的节点就是根 }

new_node创建节点时，叶子节点保存字符ch，内部节点的ch设0。因为每个内部节点必然是左、右两个子树合并出来的，所以节点总数等于2 * leaf_count - 1；这个数量可以提前算出来，避免每次malloc频繁分配。我在实际写代码时，会把所有节点一次性分配到数组里，然后用空闲链表管理，这样释放时只需一次free，内存问题少很多。

代码里heap_pop弹出后，需要用最后一个元素补到堆顶，再向下调整恢复堆序。left和right哪个作为左子树、哪个作为右子树，并不影响压缩结果的正确性，只要解压时用同一套规则即可。为了保证一致性，建议统一规定“先弹出的作为左子树，后弹出的作为右子树”，报告里也写清楚这个约定。

3.3 生成编码表：深度优先从根到叶子记下01串

树建好后，要生成一张“字节→二进制字符串”的映射表。从根出发，往左走记一个'0'，往右走记一个'1'；走到没有左右孩子的叶子时，把当前路径复制到编码表对应位置。因为编码是变长的，路径字符串最长可能是255，所以需要一个临时char数组作为递归过程中的栈。

void build_code_table(HNode *root, char *path, int depth, char *codes[256]) { if (root == NULL) return; if (root->left == NULL && root->right == NULL) { codes[(unsigned char)root->ch] = malloc(depth + 1); if (depth == 0) { codes[(unsigned char)root->ch][0] = '0'; // 文件中只有一个字节的特殊情况 codes[(unsigned char)root->ch][1] = '\0'; } else { memcpy(codes[(unsigned char)root->ch], path, depth); codes[(unsigned char)root->ch][depth] = '\0'; } return; } if (root->left) { path[depth] = '0'; build_code_table(root->left, path, depth + 1, codes); } if (root->right) { path[depth] = '1'; build_code_table(root->right, path, depth + 1, codes); } }

这个递归里最重要的边界是depth == 0。当文件里所有字节都是同一个字符时，树只有一个叶子节点，根本走不到任何分支，路径字符串是空的。如果不做特殊处理，编码表对应位置会存一个空串，压缩时写不进去内容、解压时也没法对应。常见处理是把唯一字符的编码赋成"0"，并在文件头标记叶节点数量为1，这样解压端能还原。

codes数组长度256，索引就是无符号字节值。使用memcpy而不是直接strcpy，是因为递归路径path不一定是'\0'结尾，复制指定长度的字符后再手动补结束符更安全。每个叶子编码都是动态分配的，解压完成后需要统一释放，否则每个文件压缩一次就泄漏一小块内存。

3.4 按位写入压缩文件：从字符串到位流的最后一公里

哈夫曼编码得到的是 '0'/'1' 字符串，但文件系统的最小单位是字节。如果直接把"010101"存成文本，压缩率会变成原来8倍，完全失去意义。正确做法是把每个比特按顺序拼成一个字节，写满8位再输出。

void write_bits(BitWriter *bw, const char *bits) { for (int i = 0; bits[i] != '\0'; i++) { if (bits[i] == '1') { bw->buf |= (1 << bw->bit_pos); } bw->bit_pos++; if (bw->bit_pos == 8) { fputc(bw->buf, bw->fp); bw->buf = 0; bw->bit_pos = 0; } } }

BitWriter结构体里通常有unsigned char buf、int bit_pos和FILE *fp三个字段。bit_pos代表当前填到第几位；从0开始，最高位写1时用1 << bit_pos。写满一个字节立即输出，然后复位。这里要注意：文件末尾可能凑不满8位，压缩文件头需要额外保存“最后一个字节有效位数”，或者用padding位补0，并在解压时根据文件长度或文件头中的位数截断，否则会多解压出多余的0字节。

解压侧的read_bits逻辑相反：每次读取一位，先检查当前bit_pos是否为0，是则读一个新字节并重置计数；然后取出那一位，移动计数。同样的补位问题在解压时也要处理。很多压缩程序把“最后一个字节有效位数”写成1字节放在文件头末尾，这样简单可靠。

3.5 文件头设计：让解压端能重建同一棵树

压缩文件不能只放编码数据，必须有一个自描述的头。这份资源采用先序遍历方式序列化哈夫曼树：每个内部节点用一个标记字节表示（例如1），叶子节点用另一个标记（例如0）加上其对应的字节值。解压时按相同顺序读回并重建节点。

void write_tree(HNode *root, FILE *out) { if (root->left == NULL && root->right == NULL) { fputc(0, out); fputc(root->ch, out); } else { fputc(1, out); write_tree(root->left, out); write_tree(root->right, out); } }

write_tree的输出顺序是“内部节点先序”。读入端代码只需要配合标记判断当前是内部节点还是叶子，一路递归即可。每个叶子输出两个字节：1字节类型标记 + 1字节字符值；内部节点输出1字节类型标记。如果一个文件有 n 个不同字节，那么树序列化的长度约2n + 1字节，对大多数文本文件来说是可接受的开销。这里要注意fputc(root->ch, out)在叶子字符为0时也能正确输出一个0字节，因为读端依据类型标记而不是字符值来判断。

为了避免树结构过深导致递归栈溢出，哈夫曼树在最坏情况下深度接近256，递归调用深度可控。如果实在担心C语言递归栈，也可以改成显式栈做非递归先序遍历，但对课设项目来说递归足够，重点是把文件头和位流的读写逻辑对齐。

4. 运行与验证：命令行参数、压缩率与报告数据

4.1 编译与命令格式

这份资源没有依赖第三方库，直接用命令行编译就能跑。假设所有源文件都在当前目录，编译命令如下。

gcc -std=c99 -Wall -O2 main.c huffman.c heap.c bitio.c -o huf

-Wall打开警告，便于发现未初始化变量和类型转换问题；-O2让位运算和循环跑得更快。如果手边的编译器报错说memset未声明，在文件头部包含string.h，或者把-std=c99改成-std=gnu99。常见课设命令行格式是-c压缩、-d解压，后面跟输入文件和输出文件。

./huf -c report.txt report.huf ./huf -d report.huf report_restored.txt

第二条命令解压出的文件应当和原文件完全一致。验证是否一致，在类Unix环境用cmp，在Windows下可以用fc /B。

cmp report.txt report_restored.txt

cmp不输出任何内容说明两个文件逐字节相同；一旦有差异，会直接告诉你是第几个字节不同。这个验证一定要跑，因为压缩程序最容易出现“看着对了，实际丢了一个字节”的隐蔽问题。我建议把原文件和解压文件放到不同目录再比，避免误用同一个路径覆盖掉验证对象。

4.2 压缩率观察：不是所有文件都适合压缩

运行压缩后，最直观的结果是输出文件大小。拿一份几万字的课程报告做测试，常见压缩率可以参考下面表格：

哈夫曼编码的压缩能力来自“不同字符出现频率差异大”。英文文本中字母和空格频率极不平均，所以压缩率高；而zip、图片、音视频等已经做过熵编码，字节频率接近均匀分布，哈夫曼编码就几乎无效，甚至因为文件头开销导致压缩包变大。报告里应该主动写明这个边界，不然答辩时容易被追问。压缩率计算公式也很简单：(原文件大小 - 压缩文件大小) / 原文件大小 * 100%。注意要用“文件字节数”而不是“位数量”去算，否则会把编码位流误当成可读文本统计。

4.3 测试用例怎么选：覆盖边界比覆盖大小更重要

跑压缩程序时，我一般会准备四类测试文件：长文本，观察正常压缩率和速度；全相同字符文件，验证单个叶子节点的特殊处理；随机二进制文件，验证读文件头时不会把0x00字节当EOF，也验证位流在没补齐时不丢位；一个几百KB的图片，检验如果压缩率不高，程序是否会正确处理“无收益压缩”的场景。

报告里可以把这四类文件的测试结果放在一张表格里，并附带“压缩后大小、解压后是否一致、耗时”三列。这是最具说服力的客观数据，也比堆原理更能体现你真正跑通了代码。文件头里保存的树信息往往在小文件压缩后占据较高比例，测试时用1KB以下的小文本可以看到明显的“压缩后比压缩前大”现象，这同样是报告里的一个亮点：说明你没有回避局限。

4.4 失败时的排查顺序

如果cmp报出差异，不要急着改算法，先把问题范围缩小。第一步，只解压一个空文件或全同字符文件，确认文件头逻辑是否正常；第二步，用一个只有几个不同字符的小文本，手动算一遍编码，对照编码表是否一致；第三步，检查文件末尾位数，故意在压缩文件中截掉几个字节，看解压端是否能正确停在最后一个有效位。按这个顺序排查，百分之九十的差异都出在文件头或位流补位，而不是树本身。

5. 避坑与排查：写文件、位缓冲和内存管理的5个教训

5.1 现象：压缩后文件反而变大

原因：文件头开销加上低频字符编码变长，超过高频字符节省的位。小文件尤其明显，例如一个只有几百字节的文本，树序列化头可能占几十字节，压缩收益根本覆盖不了；随机字节文件则因为频率均匀，编码长度接近8位，还倒赔一个文件头。

解决：在compress_file入口加一个判断，如果压缩后的文件大小估算值大于原文件，就放弃压缩，直接把原文件复制一份并加个标志；或者在报告里说明“哈夫曼压缩适合冗余度高的大文件”。就代码而言，可以先统计频率后临时估算总编码位数，加上头部开销，再决定是否真正写压缩流。

5.2 现象：解压输出乱码或末尾多出字符

原因：写位流时最后不足8位在文件尾部用0补齐，但解压端没有记录原始有效位数，导致把补的0也解成字符；或者相反，少读了末尾的位，丢字符。也可能是文件头里的树顺序和解压端读树顺序不一致，例如先序写但后序读。

解决：在压缩文件头里增加一个固定字节，记录最后一个字节的有效位数是多少。解压时读到末尾，只取该字节的前 N 位，不到位就停止。同时建议每次改完树序列化逻辑后，用cmp做一次全量对比，先排除文件头问题再查位流。这个补位字段在报告里值得单独画一小节，它是从“能跑”到“跑对”的分水岭。

5.3 现象：读二进制文件时到0x1A就中断

原因：在文本模式打开文件时，某些平台会把0x1A（Ctrl+Z）当作EOF处理，二进制文件中出现该字节会提前截断；此外换行符也会被转换，破坏字节一致性。哈夫曼压缩的本质是字节级无损变换，任何打开模式不一致都会导致解压后和原文件对不上。

解决：所有打开文件的fopen模式都使用"rb"和"wb"，而不是"r"和"w"。这是C语言文件压缩必须养成的习惯。顺带一提，fgetc返回 int 判断 EOF 的判断方式在二进制模式也是安全的，关键是文件打开模式要对。报告里可以写一句“统一以二进制方式读写，避免平台换行符转换干扰位流”，这是很加分的细节。

5.4 现象：只有一种字符的文件压缩后解压失败

原因：如果文件全是字母A，那么哈夫曼树只有一个叶子节点，递归编码时不会进入左或右分支，得到的路径是空字符串；写文件头时也只写一个标记，但解压端在“从根向叶子走”的过程中无法处理“没有分支可走”的情况。

解决：在生成编码表时发现left == NULL && right == NULL，直接把该字符编码设为"0"；同时在文件头记录“叶子节点数量=1”。解压函数开头先判断是否为单叶子树，是就直接把根节点的字符重复输出若干次，因为压缩文件里剩余的比特数就是原文件字节数。这个问题非常容易踩到，建议在测试用例里强制加一个全同字符文件。

5.5 现象：程序长时间连续压缩多个文件后内存涨不停

原因：递归生成编码表时，每个叶子编码都通过malloc分配；建树时每个节点也是malloc。如果只负责压缩不释放，跑一次还好，跑几千个文件内存就崩了。很多同学在单个文件压缩时看不出来，但一旦在循环里重复调用compress_file，内存呈线性增长。

解决：在build_code_table结束后统一用free释放每一条编码字符串；在压缩或解压流程结束后递归释放整棵树。更推荐的方法是把所有树节点一次性分配到一个固定大小数组里，最后只释放一次，编码表则复用同一个字符串缓冲区来写文件，写完立刻释放。如果愿意，还可以在main.c加上内存统计，但课设阶段只要保证每轮流程不泄漏就够。

如果真遇到查不出来的问题，可以压缩一个小文件后用十六进制查看器打开压缩文件，对照文件头、补位字节、编码数据三段，逐字节核对预期值。这样做能快速定位是在写树时出错、写位流时出错，还是文件头长度字段写错。

6. 改造思路：把单文件压缩扩展成批处理与缓冲优化

拿到这份资源后，最容易见效的改造是替换bitio.c中的逐字节fputc，改成一次写满一个大缓冲区。原因是fputc每写入一个字节就触发一次系统调用，压缩一个大文件时大量时间花在I/O上。改法很简单：在BitWriter中增加一个unsigned char buffer[8192]和计数器，写满8位时先把字节放进buffer，满8192字节再fwrite出去。解压侧的BitReader同理，用fread一次读入一大块，而不是逐字节fgetc。

另一个实用的改造是支持多文件压缩。在main.c中把-c参数改为可以接收多个文件，循环调用compress_file；但要注意每个文件应当单独生成压缩文件，或者把多个文件的文件名和长度写进同一个压缩包头部。后者更能锻炼“元数据”设计能力：头部不只存一棵树，还要存文件数量、每个文件名、每个压缩流的长度。这样就能从“单文件工具”变成一个“迷你压缩工具”。

如果想让压缩率进一步提升，可以加入游程编码或者两级编码：先用RLE把连续重复字节转成计数，再对计数结果做哈夫曼编码。这个改造能很好处理全同字符文件，也能让某些图片和文本压缩率更高，但要注意多级编码会对文件头结构提出新要求，测试面也要跟着扩大。

我最想提醒的其实不是算法本身，而是回归验证。从那以后，我每次改完压缩逻辑，都会用随机生成的二进制文件跑一遍“压缩→解压→逐字节比对”，连换行符和BOM都不放过；这个习惯帮我挡住了不少位偏移的bug，希望帮到你。

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