c - 如何释放递归结构(trie)

Question

最终编辑

我释放内存的函数工作正常，正如 milevyo 所建议的那样，问题出在我已修复的节点创建上。我现在有一个单独的问题，程序在正常运行时出现段错误，但它不能在 gdb 或 valgrind 中重现。然而，这完全是一个单独的问题。

后来我发现这个段错误是因为我没有正确检查 EOF 字符。 As per Cliff B's answer in this question ，对 EOF 的检查仅发生在文件中的最后一个字符之后。结果，在加载字典文件的函数中，我将文件的最后一个字符分配给了一些 i(在本例中，根据 printf，它是 -1 > 调用)，并尝试创建和访问索引为 -1 的子节点。这导致了段错误，并且还导致我的卸载函数出现问题，无法卸载我创建的最后一个节点。

至于为什么我在gdb或valgrind中运行程序时没有出现段错误，我不知道。

编辑 3

在单步执行创建节点的加载函数时，我注意到一个意外行为。我相信问题出在这些代码行中的某处，这些代码行嵌入在 for 循环中。转换为 (node*) 只是为了安全起见，尽管据我所知它不会影响代码的运行。

// if node doesnt exist, calloc one, go to node
if (current_node->children[i] == NULL)
{
    current_node->children[i] = (node*) calloc(1, sizeof(node));
    nodes++;
}
current_node = current_node->children[i];

在逐步执行加载函数时，我看到我的 current_node->children[i] 似乎被正确地 calloc 了(所有子节点都设置为 NULL)，但是当我进入 current_node->children[i] 并检查它的子节点时(见下图)，我发现地址搞砸了。具体来说，由于某种原因，子节点中的第 i 个子节点被设置为 0x0。虽然 0x0 应该等于 NULL(如果我错了请纠正我)，但我的 free_all 函数似乎想要进入0x0 指针，这当然会导致段错误。任何人都可以阐明这是如何发生的吗？

Values of children[i]

编辑 2:我正在使用 calloc 创建我的节点

root = calloc(1, sizeof(node));

对于我的子节点，它们是在 for 循环中创建的，我在循环中迭代我正在读入的字典文件的字符。

if (current_node->children[i] == NULL)
{
    current_node->children[i] = calloc(1, sizeof(node));
    nodes++;
}

c 在这种情况下表示正在读入的单词的字符。我使用以下方法得到 i:

if (c == '\'')
    i = 26;
else if (isalpha(c))
    i = c - 97;

编辑:正如 milevyo 所建议的那样，我认为我的节点创建过程中出现了错误。这是因为如果我打印出地址，它会从 0x603250 到 0x603340 再到 0x603430 再到 0x603520，然后最后到 (nil)，在它出现段错误之前。我已经通过在 gdb 中打印出根节点的值来验证根节点是否正确传递。我会想办法解决的。

原始问题

我在尝试释放递归结构时遇到了段错误，但无法弄清楚原因，希望得到一些帮助。

我的结构定义如下:

typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

这是为了实现一个 trie 结构，为了拼写检查的目的，将字典加载到其中。拼写检查完成后，我需要释放分配给 trie 的内存。

这是我当前的函数，它应该在通过根节点时释放 trie，但这样做会出现段错误，尽管不会立即发生:

void free_all(node* curs)
{
    int i;

    // recursive case (go to end of trie)
    for (i = 0; i < 27; i++)
    {
        if (curs->children[i] != NULL)
        {
            free_all(curs->children[i]);
        }
    }

    // base case
    free(curs);
}

我可能哪里出错了？如果需要更多信息，请告诉我。

Answer 1

我想，根节点有问题(可能是空的)。如果没有，看看别处。例如在节点创建中。

void free_all(node* curs)
{
    int i;
    if(!curs) return;   // safe guard including root node. 

    // recursive case (go to end of trie)
    for (i = 0; i < 27; i++)
       free_all(curs->children[i]);


    // base case
    free(curs);
}