如何释放递归结构（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*) 只是为了安全起见，尽管据我所知它不会影响代码的运行ning。

// 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

free_all功能正常。你要检查你设置为NULL所有children没有分配。这包括不是叶子的节点，但没有所有 27 children.

如果没问题，或者修复它不能解决段错误，则必须进行调试。

Answer 2

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

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);
}

如何释放递归结构（trie）

How to free recursive struct (trie)

c

free

recursion

struct

trie