基于哈夫曼树的文件压缩

Question

哈夫曼编码一直无法打印出来

for (int i = 0; i < count; i++) {
        if (result[i].code != NULL) {
            printf("字符: %c, 哈夫曼编码: %s\n", result[i].ch, result[i].code);
        }
        else {
            printf("字符: %c, 没有哈夫曼编码\n", result[i].ch);
        }
    }

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//哈夫曼树
typedef struct Hafuman {
    char ch;//字符
    int freq;//频度
    struct Hafuman* lchild, * rchild, * parent;//左孩子，右孩子,父节点
}Hafuman, * Hfmtree;

// 哈夫曼编码
typedef struct Hfmcode {
    char ch; // 字符
    char* code; // 编码字符串
}Hfmcode, * Hfmcodes;

//文件字符和权
typedef struct Wenjian {
    int character;//字符ASCII码值
    int freq;//权
}WJ;

//统计各字母出现频率
WJ* freqhuf(int* count, const char* filename) {//count初值为0，传过来用于统计多少种字符
    int freq[256] = { 0 };//用字符的ASCII码值作为下标,freq[ASCII]的值作为该字符的频率
    int i;
    int index;
    WJ* result;
    FILE* fpIn;
    int ch;

    fpIn = fopen(filename, "r");//读取字符
    ch = fgetc(fpIn);
    while (!feof(fpIn)) {
        freq[ch]++;
        ch = fgetc(fpIn);
    }
    fclose(fpIn);
    //统计多少种字符
    for (i = 0; i < 256; i++) {
        if (freq[i] != 0) {
            (*count)++;
        }
    }
    //将统计的结果，字符和其频率生成数组返回出去。
    result = (WJ*)calloc((2 * (*count) - 1), sizeof(WJ));
    for (i = 0, index = 0; i < 256; i++) {
        if (freq[i] != 0) {
            result[index].character = i;
            result[index++].freq = freq[i];
        }
    }
    
    return result;
}

//打印文件字符和权
void print(int* count,WJ* result) {
    int sum = *count;

    for (int i = 0; i < sum; i++) {//打印文件字符和权
        printf("ASCII值: %-5d对应字符：%-5c出现次数: %-5d\n", result[i].character, result[i].character, result[i].freq);
    }
}

//构建哈夫曼树
Hfmtree buildHuffmanTree(Hafuman* information, int count) {
    int degree = 2 * count - 1; // 哈夫曼树的节点数
    Hfmtree result = (Hfmtree)malloc(sizeof(Hafuman) * degree); // 存储哈夫曼树的指针
    int i, j;

    // 填充基本字符及其频度
    for (i = 0; i < count; i++) {
        result[i].freq = information[i].freq; // 设置字符的频率
        result[i].ch = information[i].ch; // 设置字符本身
        result[i].lchild = NULL; // 初始化左孩子,右孩子，父节点为空
        result[i].rchild = NULL;
        result[i].parent = NULL;
    }

    // 初始化哈夫曼树相关信息
    for (i = count; i < degree; i++) {
        result[i].freq = INT_MAX; // 设置初始频率为无限大
        result[i].ch = '#'; // 设置当前节点为特殊字符'#'
        result[i].lchild = NULL; // 初始化左孩子,右孩子，父节点为空
        result[i].rchild = NULL;
        result[i].parent = NULL;
    }

    // 构建哈夫曼树
    for (i = count; i < degree; i++) {
        int minIndex1 = -1; // 频率最小的节点索引
        int minIndex2 = -1; // 频率次小的节点索引

        // 找到频率最小和次小的节点
        for (j = 0; j < i; j++) {
            if (result[j].parent == NULL) {
                if (minIndex1 == -1 || result[j].freq < result[minIndex1].freq) {
                    minIndex2 = minIndex1;
                    minIndex1 = j;
                }
                else if (minIndex2 == -1 || (result[j].freq != result[minIndex1].freq && result[j].freq < result[minIndex2].freq)) {
                    if (result[j].lchild == NULL && result[j].rchild == NULL) {
                        minIndex2 = j;
                    }
                }
            }
        }

        result[i].freq = result[minIndex1].freq + result[minIndex2].freq; // 计算当前节点频率和
        result[i].ch = '#'; // 设置特殊字符'#'作为内部节点

        result[i].lchild = &result[minIndex1]; // 设置左子节点
        result[i].rchild = &result[minIndex2]; // 设置右子节点

        result[minIndex1].parent = &result[i]; // 设置父节点
        result[minIndex2].parent = &result[i];
    }

    return result; // 返回哈夫曼树的指针
}

// 递归构建哈夫曼编码
void buildHuffmanCode(Hfmtree hfmTree, char* prefix, int prefixLen, Hfmcodes hfmCodes) {
    // 到达叶子节点，保存哈夫曼编码
    if (hfmTree->lchild == NULL && hfmTree->rchild == NULL) {
        // 分配存储空间并复制前缀
        char* code = NULL;
        code = (char*)malloc(sizeof(char) * (prefixLen + 1));
        strncpy(code, prefix, prefixLen);
        code[prefixLen] = '\0';

        // 将哈夫曼编码添加到编码表中
        hfmCodes[hfmTree->ch].code = code;
        hfmCodes[hfmTree->ch].ch = hfmTree->ch;
        
        free(code);
    }
    else {
        // 左子树加0
        prefix[prefixLen] = '0';
        prefixLen++;
        buildHuffmanCode(hfmTree->lchild, prefix, prefixLen, hfmCodes);
        prefixLen--;

        // 右子树加1
        prefix[prefixLen] = '1';
        prefixLen++;
        buildHuffmanCode(hfmTree->rchild, prefix, prefixLen, hfmCodes);
        prefixLen--;
    }
}

// 构建哈夫曼编码表
Hfmcodes buildHuffmanCodes(Hfmtree hfmTree, int count) {
    Hfmcodes result = (Hfmcodes)malloc(sizeof(Hfmcode) * 256); // 分配空间存储哈夫曼编码表
    char* prefix = (char*)malloc(sizeof(char) * count); // 存储编码前缀
    memset(prefix, 0, count); // 初始化前缀

    int i;
    for (i = 0; i < count; i++) {
        result[i].code = NULL; // 初始化编码表中的每个编码
    }

    // 递归构建哈夫曼编码
    
    buildHuffmanCode(hfmTree, prefix, 0, result);

    free(prefix); // 释放前缀内存

    return result; // 返回哈夫曼编码表指针
}

int main() {
    int count = 0;
    const char* filename = "D:\\桌面\\学习学校\\作业\\数据结构\\实验用例\\实验.txt";
    const char* codeFilename = "D:\\桌面\\学习学校\\作业\\数据结构\\实验用例\\HuffmanCode.txt";
    WJ* hash;
    Hafuman information[256];
    Hfmtree tree;
    Hfmcodes result;

    hash = freqhuf(&count, filename);

    print(&count, hash);//打印

    for (int i = 0; i < count; i++) {
        information[i].ch = hash[i].character;
        information[i].freq = hash[i].freq;
    }

    tree = buildHuffmanTree(information, count);
    result = buildHuffmanCodes(tree, count);

    for (int i = 0; i < count; i++) {
        if (result[i].code != NULL) {
            printf("字符: %c, 哈夫曼编码: %s\n", result[i].ch, result[i].code);
        }
        else {
            printf("字符: %c, 没有哈夫曼编码\n", result[i].ch);
        }
    }

    return 0;
}

Answer 1

你的代码基于哈夫曼树实现了文件压缩。在构建哈夫曼编码时，你使用了递归的方式来遍历哈夫曼树，并将字符和对应的编码保存在编码表中。然而，你提到无法正确打印出哈夫曼编码。

我注意到你在构建哈夫曼编码表时没有为每个字符分配内存空间。在 buildHuffmanCode 函数中，你在找到叶子节点时，分配了内存空间来存储编码，但在之后立即释放了该内存空间。这导致了编码表中的指针指向无效的内存，因此无法正确打印出哈夫曼编码。

为了解决这个问题，你需要为每个字符分配足够的内存空间来存储哈夫曼编码。我修改了你的代码，解决了这个问题：

// 递归构建哈夫曼编码
void buildHuffmanCode(Hfmtree hfmTree, char* prefix, int prefixLen, Hfmcodes hfmCodes) {
    // 到达叶子节点，保存哈夫曼编码
    if (hfmTree->lchild == NULL && hfmTree->rchild == NULL) {
        // 分配存储空间并复制前缀
        char* code = (char*)malloc(sizeof(char) * (prefixLen + 1));
        strncpy(code, prefix, prefixLen);
        code[prefixLen] = '\0';

        // 将哈夫曼编码添加到编码表中
        hfmCodes[hfmTree->ch].code = code;
        hfmCodes[hfmTree->ch].ch = hfmTree->ch;
    }
    else {
        // 左子树加0
        prefix[prefixLen] = '0';
        prefixLen++;
        buildHuffmanCode(hfmTree->lchild, prefix, prefixLen, hfmCodes);
        prefixLen--;

        // 右子树加1
        prefix[prefixLen] = '1';
        prefixLen++;
        buildHuffmanCode(hfmTree->rchild, prefix, prefixLen, hfmCodes);
        prefixLen--;
    }
}