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模式下运行程序，分析起来会容易得多，因为我在递归的每个阶段后添加了一个遍历数组的循环。

问题出在这个realloc中:

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 指向 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 似乎就足够了。)