c - 霍夫曼树触发断点

Question

我正在编写一个程序，给定哈夫曼树的根，遍历该树并返回一个Symbol数组，它代表树中每个字母的频率。< br/> Symbol 定义如下:

typedef struct {
    char chr;
    int counter;
} Symbol;

每个哈夫曼节点的定义如下:

struct HNode;
typedef struct HNode {
    char chr;
    struct HNode *left, *right;
} HNode;

我没有霍夫曼树的 add() 函数，所以我像这样手动制作它:

int main()
{
    Symbol * result;
    HNode root, left, right, leftleft, leftright, rightleft, rightright, leftleftleft, leftleftright;
    root.chr = '\0';
    left.chr = '\0';
    right.chr = '\0';
    leftleft.chr = '\0';
    leftleftleft.chr = 'c';
    leftleftright.chr = 'd';
    leftright.chr = 'e';
    rightleft.chr = 'b';
    rightright.chr = 'a';
    root.left = &left;
    root.right = &right;
    left.left = &leftleft;
    left.right = &leftright;
    right.left = &rightleft;
    right.right = &rightright;
    leftleft.left = &leftleftleft;
    leftleft.right = &leftleftright;
    leftleftleft.left = NULL;
    leftleftleft.right = NULL;
    leftleftright.left = NULL;
    leftleftright.right = NULL;
    leftright.left = NULL;
    leftright.right = NULL;
    rightleft.left = NULL;
    rightleft.right = NULL;
    rightright.left = NULL;
    rightright.right = NULL;    
    result = getSL(&root);
    while (result->chr != '\0')
    {
        printf("%c : %d\n", result->chr, result->counter);
        result++;
    }
    getchar();
    return 0;
}

树看起来像这样:

函数本身在树中递归运行，并将每个元素添加到动态分配的 Symbol 数组中:

Symbol * getSL(HNode * root)
{
    int length;
    Symbol * s, *scopy;
    length = 0;
    s = (Symbol *)calloc((2 + length) * sizeof(Symbol *), 1);
    if (!root) return NULL;
    if (root->left && root->right)
    {
        Symbol *s0, *s1;
        int s0Length, s1Length;
        s = (Symbol *) realloc(s, (2 + length) * sizeof(Symbol *));
        s0 = getSL(root->left);
        s1 = getSL(root->right);
        s0Length = 0;
        while ((s0 + s0Length)->chr != '\0')
        {
            s = (Symbol *)realloc(s, (2 + length) * sizeof(Symbol *));
            (s + length)->counter = (s0 + s0Length)->counter + 1;
            (s + length)->chr = (s0 + s0Length)->chr;
            length++;
            s0Length++;
        }
        s1Length = 0;
        while ((s1 + s1Length)->chr != '\0')
        {
            s = (Symbol *)realloc(s, (2 + length) * sizeof(Symbol *));
            (s + length)->counter = (s1 + s1Length)->counter + 1;
            (s + length)->chr = (s1 + s1Length)->chr;
            length++;
            s1Length++;
        }
        (s + length)->chr = '\0';
    }
    else
    {
        s->chr = root->chr;
        s->counter = 0;
        length++;
        (s + length)->chr = '\0';
    }

    scopy = s;
    while (scopy->chr != '\0')
    {
        printf("%c : %d\n", scopy->chr, scopy->counter);
        scopy++;
    }
    printf("----------------------------------------------\n");
    return s;
}

注意:如果您在 Debug模式下运行程序，分析会容易得多，因为我添加了一个循环，该循环在递归的每个阶段之后运行通过数组。

问题出在这个重新分配上:

s1Length = 0;
        while ((s1 + s1Length)->chr != '\0')
        {
            s = (Symbol *)realloc(s, (2 + length) * sizeof(Symbol *));
            (s + length)->counter = (s1 + s1Length)->counter + 1;
            (s + length)->chr = (s1 + s1Length)->chr;
            length++;
            s1Length++;
        }

它不会在某个阶段发生，但在最后阶段，它会发生。 它说它触发了一个断点，如果我尝试继续，它就会崩溃。

我完全不知道出了什么问题，非常感谢您的帮助。

提前非常感谢您。

Answer 1

您没有为 s 分配足够的内存。您似乎希望 s 指向 Symbol 数组，但您只为 Symbol* 数组分配空间:

s = (Symbol *)realloc(s, (2 + length) * sizeof(Symbol *));

这为多个指针分配了足够的空间，但使用 realloc 的结果就好像它指向多个 Symbol 结构的空间:

(s + length)->counter = (s1 + s1Length)->counter + 1;

如果 sizeof(Symbol) > sizeof(Symbol*) 这意味着您可能会写入超出分配的空间，从而损坏内存。

您可能想在分配中使用 sizeof(Symbol):

s = (Symbol *)realloc(s, (2 + length) * sizeof(Symbol));

(此外，没有必要强制转换 calloc/realloc 的返回值，我不确定为什么要分配 2+length 元素- 1+length 似乎就足够了。)