如何释放递归结构(trie)

Question

最终编辑

我释放内存的功能正常工作,正如milevyo所说,问题在于节点创建,我已经修复了.我现在有一个单独的问题,程序在正常运行时会出现段错误,但它无法在gdb或中复制valgrind.但是,这完全是一个单独的问题.

我发现这个段错误是因为我没有正确检查EOF字符.根据Cliff B在这个问题中的答案, 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子节点中的'th子节点0x0由于某种原因被设置为.虽然0x0应该等于NULL(如果我错了,请纠正我),我的free_all函数似乎想要进入0x0指针,这当然会导致段错误.任何人都可以阐明这可能发生的原因吗？

儿童的价值观[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),才出现segfaults.我已经验证通过在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);
}