用C语言实现哈夫曼编码图像压缩：从频率统计到位流打包

简介：以C语言实现的哈夫曼图像压缩与解压缩课程设计，完整演示基于像素频率统计、最小堆构建最优二叉树、左右分支赋0/1生成变长编码表，再到字节流打包压缩与解码还原的全过程。资源面向计算机相关专业学生，适合数据结构与算法分析课程设计、期末项目或竞赛训练，可直接作为可运行参考工程。压缩包共43个文件，约3.66MB，包含4个cpp与4个h源代码、4个bmp测试图像、2个huf压缩结果文件、可执行exe、Visual Studio工程和解决方案、README说明等，同时附带运行所需的中间文件，便于逐步对照调试。目前已有746人学习下载。借助该项目可熟悉哈夫曼树存储与重建、位运算与文件读写、压缩率验证等关键环节，是掌握无损压缩原理和C语言工程落地能力的实用素材。

1. 从位串到字节流：为什么哈夫曼压缩值得用C语言重写一遍

拿到一份图像，最常见的压缩思路是跑一遍通用压缩库，但课程设计或者底层工具链里，往往要求你亲手把哈夫曼编码从零写出来。原因很直接：哈夫曼编码是少数既能在理论上讲清楚、又能在C语言层面触及位操作、内存管理和文件格式设计全部环节的无损压缩算法。对图像数据而言，像素值的分布通常极不均匀，频度差异越大，哈夫曼编码的压缩收益就越明显。这个项目正好能覆盖从统计频率、构建最优二叉树到编码解码的完整链路，适合用来理解变长编码的边界条件，比如最后一比特的填充问题、树结构如何序列化，以及最小堆在贪心构建中的效率瓶颈。下面按我实际拆这个Huffman-master的源码顺序，把关键实现逐段过一遍。

2. 频率统计与最小堆初始化：哈夫曼树的地基

2.1 像素值频率表的结构设计

图像压缩的第一步不是构建树，而是先搞清每个像素值出现了多少次。对8位灰度图来说，像素值范围是0到255，但课程设计里常见的做法是直接开一个256长度的数组，用像素值当下标做计数。这种数组实现的频率表在C语言里访问是O(1)，而且天然有序，后面找最小频率节点时不用排序。

#define MAX_PIXEL 256 typedef struct { unsigned char pixel; // 像素值 unsigned long freq; // 出现频次 } FreqEntry; typedef struct { FreqEntry entries[MAX_PIXEL]; int used; // 实际出现的像素种类数 } FreqTable;

代码逻辑：先读图像文件头，拿到宽高和位深，然后遍历像素数据区，对每一个字节执行table[value]++。used记录非零频率的像素种类数，这个值决定后面堆的大小。注意这里的像素值用unsigned char而不是char，因为在做位运算和数组下标时会避免符号扩展的隐式bug。

参数说明：MAX_PIXEL 256对应8位灰度图的上限。如果输入的是24位真彩色图，需要分成R、G、B三个平面分别建表，或者将像素视为24位整数扩大数组到2^24，但后者内存占用约16MB，在单片机或嵌入式场景下不可取，常见做法是三分平面独立处理。

2.2 最小堆的实现与容量控制

构建哈夫曼树的贪心算法，每一步要取出频率最小的两个节点，维护这组节点最自然的结构就是最小堆。很多初学者用链表或数组每次遍历找最小，节点数量少时无所谓，但图像里像素种类可能达到255，每轮合并都要全量扫描，复杂度是O(n²)，大图会明显变慢。

typedef struct HTNode { unsigned char pixel; unsigned long freq; struct HTNode *left; struct HTNode *right; } HTNode; typedef struct { HTNode **data; // 指针数组 int size; int capacity; } MinHeap;

堆的初始化有两种路径：一种是把256个像素全部插入再逐个弹出，另一种是先统计出used个有效节点再建堆。后者更优，因为无频率节点参与建堆只会增加比较次数。

MinHeap* initHeap(int capacity) { MinHeap *h = (MinHeap*)malloc(sizeof(MinHeap)); h->data = (HTNode**)malloc(sizeof(HTNode*) * capacity); h->size = 0; h->capacity = capacity; return h; } void pushNode(MinHeap *h, HTNode *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; }

逻辑说明：pushNode采用上浮策略，插入时先将新节点放到堆尾，然后与父节点比较频率值，小于父节点就交换位置，直到满足堆序性质。这里用数组下标公式(i-1)/2定位父节点，比指针树更省内存且缓存友好。注意HTNode里同时保留pixel和freq两个字段，是因为内部节点没有像素值，只有频率，叶子节点才需要pixel来还原图像数据。

提示：在建堆前统计频率时，别忘了一个细节——图像为空或单色时，used可能为1，此时哈夫曼树只有一个根节点，需要特殊处理，否则压出来的位串是零长度，解压端无法重建。我一般会约定：单色图直接写一个标记字节，不进入哈夫曼流程。

3. 哈夫曼树构建与编码表生成：从频率到变长位串

3.1 贪心合并的循环实现

有了最小堆，构建树的循环就非常简洁：每次弹出两个节点，合成一个新节点，新节点频率为两者之和，左右孩子指向取出的两个节点，再推回堆中。循环终止条件是堆中只剩一个节点，就是哈夫曼树的根。

HTNode* buildHuffmanTree(MinHeap *h) { while (h->size > 1) { HTNode *n1 = popNode(h); HTNode *n2 = popNode(h); HTNode *parent = (HTNode*)malloc(sizeof(HTNode)); parent->pixel = 0; parent->freq = n1->freq + n2->freq; parent->left = n1; parent->right = n2; pushNode(h, parent); } return popNode(h); }

这里popNode的实现要注意：出堆时先取出堆顶，把最后一个元素挪到堆顶，然后做下沉调整。每次合并后新节点频率一定不小于已弹出的两个叶子，因此堆中剩余节点依然保持堆序。合并顺序的选择会影响树的形态，但不影响最终编码总长度，哈夫曼编码只保证前缀码性质，不保证唯一树形。

3.2 递归遍历生成变长编码表

树构建完成后，需要把每个叶子像素值对应的二进制编码存下来。标准做法是DFS遍历，左子树方向追加0，右子树方向追加1，走到叶子节点时把当前路径写入编码表。

#define MAX_CODE_LEN 32 typedef struct { unsigned char bits[MAX_CODE_LEN]; int len; } HuffCode; void buildCodeTable(HTNode *root, HuffCode *table, unsigned char *path, int depth) { if (!root->left && !root->right) { table[root->pixel].len = depth; memcpy(table[root->pixel].bits, path, depth); return; } if (root->left) { path[depth] = 0; buildCodeTable(root->left, table, path, depth + 1); } if (root->right) { path[depth] = 1; buildCodeTable(root->right, table, path, depth + 1); } }

参数说明：path是一个临时数组，递归到叶子时把路径拷贝进table对应条目。MAX_CODE_LEN定为32，理论上哈夫曼编码最长可能接近像素种类数，但8位灰度图最坏情况是256种频率相等，编码长度也不会超过255。保险起见可以按used + 1动态分配，但课程设计里固定32通常够用，真彩色分平面后单平面编码长度更有限。

上表是某张测试图的前几项编码示例，可以看到频率越高编码越短，这就是哈夫曼压缩的核心收益来源。

注意：递归深度最坏等于最长编码长度，普通图像不会超过几十层，但如果你拿到的图像像素种类极少且频率极端，递归栈仍安全。真正要警惕的是table数组下标用unsigned char隐式转成int的情况，部分编译器会警告char的符号性，建议强转。

3.3 位串打包写入文件

编码表生成后，图像数据逐字节查表，把变长编码拼接成连续的位流。C语言里最小可写单位是字节，所以位流必须在写入前按8位对齐。

typedef struct { unsigned char buffer; // 当前待写入的字节 int bitCount; // buffer 中已占用的位数 FILE *fp; } BitWriter; void writeBit(BitWriter *bw, int bit) { bw->buffer = (bw->buffer << 1) | (bit & 0x01); bw->bitCount++; if (bw->bitCount == 8) { fwrite(&bw->buffer, 1, 1, bw->fp); bw->buffer = 0; bw->bitCount = 0; } } void writeHuffCode(BitWriter *bw, HuffCode *code) { for (int i = 0; i < code->len; i++) { writeBit(bw, code->bits[i]); } }

逻辑说明：BitWriter维护一个字节缓冲，每次写入一位就左移一位再或上当前位。当bitCount达到8时立即落盘，然后归零继续。这种设计避免了逐位fwrite带来的系统调用开销，纯内存操作的速度参考：普通机械硬盘上压缩一张256×256灰度图，位写入阶段耗时不超过10毫秒。文件末尾不足8位时，flushBitWriter需要做一次左移补零再写出。

4. 解压端的树重建与逐位解码：从字节流回到像素

4.1 文件头的序列化格式

压缩文件不只是位串，还得把哈夫曼树的形状和叶子像素值存下来，否则解压端无法重建同一棵树。常见的做法是保存每个像素值的编码长度，再用长度和位串重建。Huffman-master 里采用了一种更紧凑的方式：先序遍历树，内部节点标记为0，叶子节点标记为1后跟一个字节像素值。

typedef struct { unsigned char tag; // 1=叶子, 0=内部 unsigned char pixel; // tag为1时有效 } TreeSerialNode; void serializeTree(HTNode *root, FILE *fp) { if (root->left || root->right) { unsigned char tag = 0; fwrite(&tag, 1, 1, fp); serializeTree(root->left, fp); serializeTree(root->right, fp); } else { unsigned char tag = 1; fwrite(&tag, 1, 1, fp); fwrite(&root->pixel, 1, 1, fp); } }

序列化的顺序必须与解码端递归重建的顺序完全一致，先写标记再写像素值，内部节点不写像素。解压时按同样的先序顺序读取，遇到tag==1就申请叶子节点并返回上层，遇到tag==0就继续递归构建两个孩子。

4.2 解码过程中的分支跳转

解码端从位串中逐位读取，从根节点开始按位走树。读到0走左子树，读到1走右子树，走到叶子节点时输出像素值，然后回根节点继续读下一位。

void decodeToImage(HTNode *root, unsigned char *compressedBits, long bitLength, unsigned char *output, int pixelCount) { HTNode *curr = root; int outIdx = 0; for (long i = 0; i < bitLength && outIdx < pixelCount; i++) { int bit = (compressedBits[i / 8] >> (7 - i % 8)) & 1; if (bit == 0) { curr = curr->left; } else { curr = curr->right; } if (curr->left == NULL && curr->right == NULL) { output[outIdx++] = curr->pixel; curr = root; } } }

关键点：位序约定要与压缩端保持一致。压缩端writeBit是左移写入，即字节高位先写入，解压端必须用7 - i % 8的方式取字节高位，顺序反了会解出完全错误的数据。这一点在联调时最容易出错，建议压缩和解压共用同一个readBit/writeBit头文件。

提示：位串末尾有填充位，解压循环要跳过无效填充。最稳妥的办法是在压缩文件里记录实际像素数量pixelCount，解码时输出够了就停，不要读到最后一个字节的填充位。

5. 内存释放与位对齐的排错技巧

5.1 递归释放整棵树的顺序

图像解压完成后，哈夫曼树占用的内存需要完全释放。二叉树节点是递归创建的，释放顺序必须左右子树先释放再释放根节点，否则会提前丢失子节点指针。

void freeTree(HTNode *root) { if (root == NULL) return; freeTree(root->left); freeTree(root->right); free(root); }

这段代码看起来简单，但实际低于5年经验的开发者常犯一个错：在释放左右子树之前就free(root)，导致访问非法地址。另一种常见误用是用循环或栈展开替代递归，但哈夫曼树深度有限，递归释放完全够用，没必要引入显式栈增加复杂度。

5.2 位流末尾对齐的正确写法

压缩结束前，BitWriter缓冲里可能残留不到8位的数据，此时需要补零到整字节。补零后解压端可能读到虚拟的0位，那会导致多走一次左子树甚至走到空指针。防止这种问题的办法有两个：一是压缩端在文件头写入有效位串的比特长度，解码端严格按长度控制循环；二是写入一个特殊的结束标记字符，类似文本里的EOF。

void flushBitWriter(BitWriter *bw) { if (bw->bitCount > 0) { while (bw->bitCount < 8) { bw->buffer = (bw->buffer << 1); bw->bitCount++; } fwrite(&bw->buffer, 1, 1, bw->fp); bw->buffer = 0; bw->bitCount = 0; } }

参数说明：这里逐个移位补零，而不是直接左移(8 - bitCount)位，代码可读性和调试便利性更好。补零完成后写入文件，bitCount置零，之后如果再执行写操作会从新字节开始，不会覆盖旧数据。

5.3 压缩率自检和常见坑位清单

写完后跑一张实际图像，对比原始大小和压缩文件大小的比例。8位灰度图的哈夫曼压缩率通常在60%到85%之间，如果压缩后文件比原图还大，优先检查频率差异是否过小，以及文件头是否过于臃肿。前面提到的先序树序列化方式，在像素种类多时占用空间偏大，比如256种全出现，树描述部分要存511个节点的标记和256个像素值，约768字节，对64×64的小图而言占比很高，但大图基本可忽略。

调试阶段建议先压缩一段短文本作为替代数据，文本的字符频率差异比图像更明显，更容易验证位操作逻辑。常见的坑包括：用有符号字符做位运算导致高位扩展、频率表统计时把文件头也统计进去、解码时根节点为空就访问左右子树。逐项排除后，再换回真实图像数据跑完整流程，会发现与文本压缩的代码路径完全一致，只是频率分布不同。

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