C语言哈夫曼编码熵编解码程序出现段错误，求排查原因

问题描述 #

参考网络实现的C语言哈夫曼编码程序，运行时持续触发zsh段错误。经逐段注释排查，确认问题出在encode函数中。程序预期输出正确的哈夫曼编码表、编码字符串及解码后的原字符串，但实际输出编码表后即崩溃。

常见错误点与分析 #

结合哈夫曼编码encode函数的典型实现，段错误通常由以下原因导致：

• 叶子节点判断逻辑错误：仅判断单侧子树为空就认定为叶子节点，导致访问非叶子节点的无效data字段，触发非法内存访问。
• 编码表未初始化：code_table数组元素为野指针，赋值时引发内存错误。
• 编码缓冲区溢出：栈上分配的编码缓冲区过小，递归生成编码时超出栈空间。
• 空指针访问：传入encode的哈夫曼树根节点为空，或递归过程中访问了未分配的子节点。

示例错误代码片段 #

// 存在问题的encode函数
void encode(HuffmanNode *root, int depth, char *code, char **code_table) {
    if (root == NULL) return;
    // 错误：仅判断左子树为空，未处理仅右子树为空的情况
    if (root->left == NULL) {
        code[depth] = '\0';
        // 未检查code_table是否初始化，直接赋值
        code_table[(unsigned char)root->data] = malloc(strlen(code)+1);
        strcpy(code_table[(unsigned char)root->data], code);
        return;
    }
    code[depth] = '0';
    encode(root->left, depth+1, code, code_table);
    code[depth] = '1';
    encode(root->right, depth+1, code, code_table);
}

修复方案 #

1. 修正叶子节点判断逻辑 #

必须同时判断左右子树为空才认定为叶子节点，避免访问非叶子节点的无效数据：

void encode(HuffmanNode *root, int depth, char *code, char **code_table) {
    if (root == NULL) return;
    // 正确判断叶子节点：左右子树均为空
    if (root->left == NULL && root->right == NULL) {
        code[depth] = '\0';
        unsigned char idx = (unsigned char)root->data;
        // 检查内存分配是否成功
        code_table[idx] = malloc(strlen(code) + 1);
        if (code_table[idx] == NULL) {
            perror("malloc failed");
            exit(EXIT_FAILURE);
        }
        strcpy(code_table[idx], code);
        return;
    }
    code[depth] = '0';
    encode(root->left, depth+1, code, code_table);
    code[depth] = '1';
    encode(root->right, depth+1, code, code_table);
}

2. 初始化编码表 #

在调用encode前，确保code_table所有元素初始化为NULL，避免野指针：

// 全局初始化或动态分配后初始化
char *code_table[256] = {NULL};

3. 确保编码缓冲区足够大 #

栈上分配的编码缓冲区需覆盖哈夫曼树的最大可能深度（ASCII字符的哈夫曼树深度不超过256）：

char code[256]; // 替代过小的固定数组，或用malloc动态分配

4. 前置空指针检查 #

调用encode前，验证根节点和编码表的有效性：

if (root == NULL || code_table == NULL) {
    fprintf(stderr, "Invalid parameters for encode function\n");
    exit(EXIT_FAILURE);
}

验证结果 #

修改后程序可正常输出哈夫曼编码表、编码字符串，解码后得到与原输入一致的字符串，不再触发段错误。

内容的提问来源于stack exchange，提问作者user21085283