递归释放C中的TRIE结构

Question

我目前正在尝试使用 recursive function 成功释放 TRIE structure，但没有成功，但我发现我正在失去记忆。

trie结构定义为：

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

并且我在全局声明了以下节点*：

node* trie = NULL;
node* root = NULL;

第二个仅用于跟踪根节点，第一个用于从文件接收单词。到目前为止，除了内存丢失之外，在不释放堆内存的情况下编译我的程序时没有出现任何错误。

实现 unload( ) 函数后，我开始遇到 Segmentation Fault 个错误。

查看我的代码片段：

/*
Frees node by node recursively
*/

bool freeSpace(node* child)
{   
    for (int i = 0; i < 27; i++)
    {
        if(trie->children[i] != NULL)
        {
            freeSpace(trie->children[i]);
        }
    }
    free(trie);
    return true;
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */ 
bool unload()
{

    if(root != NULL)
    {
        trie = root;
        freeSpace(trie);

        if(freeSpace(trie))
            return true;
        else
            return false;
    }
    else
    {
        return false;
    }

}

也许我的代码在返回值和验证方面不是很聪明，但我现在的主要问题是保证递归按预期工作并且没有内存泄漏或分段错误发生。有什么建议吗？

提前致谢！

Answer 1

仔细查看您的代码。你真的在任何地方使用函数的参数吗？你实际上总是在每次迭代时查看全局 trie 指针，这不是你想要做的。

要解决此问题，请更改您的代码，以便查看作为参数传入的节点及其子节点，而不是全局 trie 指针。

您还有一个问题需要注意，那就是您处理空指针的方式。现在，您假设参数指针不为空，然后在重复之前检查每个子节点是否为非空。但是，如果 trie 本身一开始就是 null 怎么办？我会考虑创建一个基本案例来检查 trie 是否为空，如果是，则不执行任何操作。然后，您可以在进行递归调用之前消除检查，现在可以适当地防范另一个边缘情况。

Answer 2

这是您的代码片段的修改版本，它更有意义：

/*
Frees node by node recursively
*/

void freeSpace(node* t)
{   
    for (int i = 0; i < 27; i++)
    {
        if(t->children[i] != NULL)
        {
            freeSpace(t->children[i]);
        }
    }
    free(t);
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */ 
bool unload()
{

    if(root != NULL)
    {
        trie = root;
        freeSpace(trie);
        return true;
    }
    else
    {
        return false;
    }

}

freeSpace 函数已更改为使用参数作为要释放的 trie 的基础。您的原始版本有一个未使用的参数 child，而是使用了全局变量 trie，这没有意义。

不需要 freeSpace 到 return 一个值，因为它所做的都是免费的东西，它只是 return 一个固定值 true。我将其 return 类型更改为 void.

您的 unload 函数在同一个对象上调用 freeSpace 两次，因此我删除了其中一个调用。

Answer 3

我认为你的 freeSpace() 函数应该使用 child parameter 而不是 trie。它应该是这样的。

bool freeSpace(node* child){   
    for (int i = 0; i < 27; i++)
    {
        if(child->children[i] != NULL)
        {
            freeSpace(child->children[i]);
        }
    }
    free(child);
    return true;
}

递归释放C中的TRIE结构

Freeing TRIE structure in C recursively

c

recursion

trie