基于C语言实现哈夫曼树文件压缩：原理与完整步骤

程一诺

发布时间：2026-10-16| 6人浏览过

原创

本文介绍如何使用C语言结合哈夫曼树（Huffman Tree）进行文件压缩。核心逻辑包括统计文件字符权重以构建最优二叉树、生成无前缀的哈夫曼编码，以及将编码字符串按8位分组转换为标准ASCII字符写入新文件。该方法能有效利用字符频率差异减少存储空间。

哈夫曼编码的核心原理

哈夫曼树又称最优二叉树，是指对于具有 n 个带权叶子结点的二叉树，其带权路径长度（WPL）最小的那棵树。在文件压缩场景中，权值通常定义为字符出现的频率。权值越大（出现越频繁），该字符在树中的位置越靠近根节点，其对应的编码长度就越短。

传统的等长编码（如 ASCII 原码）每个字符占用固定位数，效率较低。哈夫曼编码是一种可变字长编码（VCL），具有以下关键优势：

唯一性（前缀性质）：任何一个字符的编码都不是另一个字符编码的前缀，确保了解压缩时的无二义性，无需分隔符即可正确译码。
高压缩率：高频字符使用短编码，低频字符使用长编码，整体 WPL 最小化。

如图所示，从根节点出发，左分支记为 0，右分支记为 1。到达叶子节点的路径即为该字符的二进制编码。例如：A: 00, B: 01, C: 1。

C语言实现文件压缩的关键步骤

第一步：读取文件与字符统计

首先需打开待压缩文件，遍历所有字符并统计各字符出现的次数。C语言中字符通常占 1 字节，可映射至 str[256] 数组作为频率统计表。

char ch;
while(feof(fp) == 0){
    fscanf(fp, "%c", &ch);
    str[ch]++;
}
// 提取实际存在的字符及其计数，用于后续建树
for(i = 0; i < 1024; i++){
    if(str[i] != 0){
        count[n++] = i; 
    }
}

第二步：构建哈夫曼树 (CreateHT)

将统计出的 n 个字符作为初始叶子节点放入数组前 n 个位置。随后从第 n+1 个位置开始，每次从未被选过的节点中找出两个权值（父节点指针 parent 为 -1）最小的节点，合并为一个新的父节点。

void CreateHT(HTNode *ht, int n){
    int i, j, lnode, rnode, n1, n2;
    // 初始化非叶子节点，总节点数为 2*n-1
    for(i = n; i < 2*n-1; i++){
        lnode = 65432; rnode = lnode; // 假设最大权值界限
        n1 = 0; n2 = 0;
        
        // 寻找当前权值最小的两个节点
        for(j = 0; j < i; j++){
            if(ht[j].parent == -1){
                if(ht[j].weight < lnode){
                    rnode = lnode;
                    n2 = n1;
                    lnode = ht[j].weight;
                    n1 = j; 
                } else if(ht[j].weight < rnode){
                    rnode = ht[j].weight;
                    n2 = j; 
                }
            } 
        }
        // 建立父子关系
        ht[n1].parent = i;
        ht[n2].parent = i;
        
        ht[i].weight = lnode + rnode; // 父节点权值为子节点之和
        ht[i].parent = -1;
        ht[i].lchild = n1;
        ht[i].rchild = n2;
    }
}

第三步：生成哈夫曼编码表

根据构建好的树结构，从叶子节点向上回溯至根节点，记录路径上的 0/1。为了便于快速替换，结果通常存储在一个二维数组中：huffmanCode[叶子索引][编码字符串]。

CreateHT(ht, node);
char strarr[256][256];
int aa, bb;
// 初始化编码数组
for(aa=0; aa<256;aa++)
    for(bb=0;bb<256;bb++)
        strarr[aa][bb]=-1; 

// 为每个出现的字符获取对应的哈夫曼编码
for(k = 0; k < node; k++){
    huffmanCode(ht, k, strarr[k]);
}

第四步：文本替换与二进制流转换

这是压缩的核心环节。原程序中使用了一个较为直接的字符串替换逻辑，将原始字符替换为其生成的 0/1 序列。由于 0/1 序列是变长的，实际写入时需要维护一个动态的目标缓冲区。

void replace(char oldstr[], char key[], char rep[]){
    int oldstrLen, lengthOfKey, lengthOfRep, i, j, flag;
    char tmp[1000]; 
    oldstrLen = strlen(oldstr);
    lengthOfKey = strlen(key);
    lengthOfRep = strlen(rep);
    
    for( i = 0; i <= oldstrLen - lengthOfKey; i++){
        flag = 1;
        for(j = 0; j < lengthOfKey; j++){
            if(oldstr[i + j] != key[j]){
                flag = 0; 
                break;
            }
        }
        if(flag){
            strcpy(tmp, oldstr);
            strcpy(&amp;tmp[i], rep);           // 插入新编码
            strcpy(&amp;tmp[i + lengthOfRep], &amp;oldstr[i + lengthOfKey]); // 拼接剩余部分
            strcpy(oldstr, tmp);
            i += lengthOfRep - 1;             // 移动指针跳过已处理部分
            oldstrLen = strlen(oldstr);
        }
    }
}

第五步：8位分组与二进制转ASCII

C语言的 FILE 写入是以“字节”为单位的，无法直接写入单比特的 0 或 1。因此，必须将生成的 0/1 长字符串按 每 8 位一组 进行划分，不足 8 位时补 0。将这 8 位二进制数转换为十进制，再映射为对应的 ASCII 字符写入文件。

辅助转换函数示例如下：

int retTen(char str[]){
    int ten = 0;
    int t = 0;
    for(t = 0; t < strlen(str); t++){
        ten += (str[t]-'0') * pow(2, strlen(str) - t - 1); 
    } 
    return ten;
}

经过这一步骤，原本的一串 0/1 字符变成了紧凑的二进制数据块，写入目标文件即实现了压缩效果。

验证压缩结果

压缩完成后，可以通过对比源文件和目标文件的文件大小来计算压缩率。公式参考：压缩率 = 压缩后文件大小 / 原文件大小。

int oldFileSize = getFileSize(path);
int newFileSize = getFileSize(Gopath);

printf("\n");
printf("压缩成功!,文件已压缩至%s\n", Gopath); 
// 注意类型转换防止精度丢失
printf("该文件压缩率为：%.2lf\n", (double)newFileSize/(double)oldFileSize);