C语言实现哈夫曼树失败：qsort函数触发段错误

我用C语言实现哈夫曼编码时触发了段错误，问题出在调用qsort()函数时。核心逻辑是：定义了两个数组，一个存储所有节点，另一个存储指向待合并树节点的指针，需要对指针数组排序以合并频率最低的两棵树。奇怪的是，compareFrequency函数访问结构体的frequency成员时会失败，但在函数外部访问该成员完全正常。相关代码是huffman.c中的compareFrequency函数和最后一个while循环，我已经用gdb调试过但仍未解决。

相关代码 #

main.c #

#include "huffman.h"
#include <stdio.h>

int main(int argc, char* argv[])
{
    FILE* inputP = fopen(argv[1], "rb");
    FILE* outputP = fopen(argv[2], "w");

    if (!(inputP && outputP)) return 1;

    encode(inputP, outputP);

    fclose(inputP);
    fclose(outputP);
    return 0;
}

huffman.h #

#ifndef HUFFMAN_H
#define HUFFMAN_H

#include <stdio.h>

typedef struct node node;

// static int compareFrequency(const void* a, const void* b);
void encode(FILE* input, FILE* output);

#endif

huffman.c #

#include "huffman.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
    node* left;
    node* right;
    unsigned int frequency;
    char* bytes;
};

static int compareFrequency(const void* a, const void* b)
{
    // Sort by frequency (higher first) or if equal by tree size (bigger first, only educated guess)
    if (((node*)a)->frequency < ((node*)b)->frequency) return 1;
    if (((node*)a)->frequency > ((node*)b)->frequency) return -1;
    if (strlen(((node*)a)->bytes) < strlen(((node*)b)->bytes)) return 1;
    if (strlen(((node*)a)->bytes) > strlen(((node*)b)->bytes)) return -1;
    return 0;
}

void encode(FILE* input, FILE* output)
{
    unsigned int possibleBytes[256] = { 0 }, differentTrees = 0, i;
    char currChar;

    // Count number of occurence of each individual byte
    while ((currChar = fgetc(input)) != EOF) {
        possibleBytes[currChar]++;
    }

    // Count number of different bytes
    for (i = 0; i < 256; i++) {
        if (possibleBytes[i]) differentTrees++;
    }

    // Make array filled with used bytes and their absolute frequency
    node* nodes = calloc(differentTrees * 2 - 1, sizeof(node));
    node* nodesP = nodes;

    for (i = 0; i < 256; i++) {
        if (possibleBytes[i]) {
            nodesP->bytes = calloc(2, sizeof(char));
            *nodesP->bytes = i;
            *(nodesP->bytes + 1) = '\0';
            nodesP->frequency = possibleBytes[i];
            nodesP++;
        }
    }

    // Fill trees array with nodes
    node** trees = calloc(differentTrees, sizeof(node*));
    // for (i = 0; i < differentTrees; i++) {
    //     printf("%c: %d\n", *(nodes + i)->bytes, (nodes + i)->frequency);
    // }

    node** treesP = trees;
    nodesP = nodes;
    for (i = 0; i < differentTrees; i++) {
        *treesP = nodesP;
        treesP++;
        nodesP++;
    }

    // Build tree
    node* lastTree;
    node* secondLastTree;

    while (differentTrees > 1) {
        lastTree = *trees + differentTrees - 1;
        secondLastTree = *trees + differentTrees - 2;
        // printf("%d\n", differentTrees);
        // printf("%p\n", nodesP);
        // printf("%p\n\n", lastTree);
        nodesP->left = lastTree;
        nodesP->right = secondLastTree;
        nodesP->frequency = lastTree->frequency + secondLastTree->frequency;
        nodesP->bytes
            = calloc(strlen(lastTree->bytes) + strlen(secondLastTree->bytes) + 1, sizeof(char));
        strcat(nodesP->bytes, lastTree->bytes);
        strcat(nodesP->bytes, secondLastTree->bytes);
        secondLastTree = nodesP;

        printf("%s\n", secondLastTree->bytes);
        differentTrees--;
        nodesP++;

        printf("%u\n\n", secondLastTree->frequency);
        qsort(*trees, differentTrees, sizeof(node*), &compareFrequency);
    }
}

Makefile #

CC = gcc
CFLAGS = -g
OBJ = main.o huffman.o

huffman: $(OBJ)
    $(CC) $(OBJ) -o $@

%.o: %.c
    $(CC) $(CFLAGS) -c $<


clean:
    rm *.o

问题根源及修复方案 #

核心错误点 #

1. qsort参数传入错误：trees是node**类型的指针数组，但你传给qsort的第一个参数是*trees（即第一个node*指针），这相当于告诉qsort去排序连续的node结构体，而非指针数组本身，直接导致内存越界。
2. 比较函数参数解析错误：qsort排序指针数组时，传给compareFrequency的a和b是指向数组元素的指针（即node**类型），但你直接将其强转为node*，相当于把指针地址当成了node结构体的地址，访问成员必然触发段错误。
3. 取最后两个元素的逻辑错误：*trees + differentTrees -1的写法只适用于连续的node结构体数组，而trees是指针数组，每个元素是独立的node指针，不能用这种方式偏移。
4. 排序逻辑与哈夫曼需求不符：哈夫曼树需要合并频率最低的两个节点，你原来的比较逻辑是降序排序，会导致每次合并最大的两个节点，逻辑完全错误。

修复后的关键代码修改 #

修改compareFrequency函数

static int compareFrequency(const void* a, const void* b)
{
    // 先解引用得到node指针
    node* nodeA = *(node**)a;
    node* nodeB = *(node**)b;

    // 按频率升序排序，保证每次取最小的两个节点
    if (nodeA->frequency < nodeB->frequency) return -1;
    if (nodeA->frequency > nodeB->frequency) return 1;
    
    // 频率相同时按bytes长度排序
    size_t lenA = strlen(nodeA->bytes);
    size_t lenB = strlen(nodeB->bytes);
    if (lenA < lenB) return -1;
    if (lenA > lenB) return 1;
    return 0;
}

修改qsort调用

// 传入指针数组本身，而非第一个元素
qsort(trees, differentTrees, sizeof(node*), compareFrequency);

修改取最后两个元素的逻辑

// 直接通过数组下标访问指针数组的元素
lastTree = trees[differentTrees - 1];
secondLastTree = trees[differentTrees - 2];

额外修复：文件读取的EOF判断问题

fgetc返回的是int类型（包含EOF的-1值），用char存储会导致EOF判断失效，修改为：

int currChar;
while ((currChar = fgetc(input)) != EOF) {
    possibleBytes[(unsigned char)currChar]++;
}

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