在C语言中清理双向链表Trie结构

Question

我想要防止内存泄漏，所以我想要释放Trie。 以下是我尝试释放使用的内存。

// to see how many words are cleaned up.
static int teller_cleanup = 0;

struct ac {
    int value;
    char character; 
    char * word;
    struct ac *next;
    struct ac *previous;
    struct ac *child;
    struct ac *parent;
};

这是一个双向或四向链表，我不确定应该如何称呼它。

void cleaner(struct ac* a) {
    ac * temp = NULL;
    if (a != NULL) {
        if (a -> child == NULL && a -> next == NULL) {
            teller_cleanup ++;
            if (a -> parent != NULL) {
                temp = a -> parent;
            }
            else {
                temp = a -> previous;
             }
             free(a -> word);
             free(a);
             a = temp;
        }
        if (a -> child != NULL) {
            cleaner(a -> child);
        }
        if (a -> next != NULL) {
            cleaner(a -> next);
        }
     }
 }

int cleanup(struct ac* a) {
    // means that it is in the root
    // therfore it needs to go to the first node.
    if (a -> next == NULL && a -> parent == NULL) {
        a = a -> child;
    }
    cleaner(a);
    return teller_cleanup;
}

但是似乎它没有正常工作，它会给出一个错误：

double free or corruption (fasttop)：0x0000000000fffa70 ***

我不明白的是，当“child”和“next”都为“NULL”时，“a”就是最外层的节点。而我相信只有一个递归if语句可以到达其中一个最外层的节点。

我将尝试可视化trie：

[root]
   |
  \/
[h] -- > [b]
 |        |
\/       \/
[i]      [y] --> [e] 

因此，trie包含单词“hi”，“by”和“be”。根指向第一个单词的第一个字符，所有箭头都是双向的。从'h'到'b'是下一个，从'h'到'i'是子节点。

有人可以看出我做错了什么吗？非常感谢。

- bob

---

你应该只在自上而下或者自下而上的其中一种方式中释放父元素，不要两种方式都使用。如果你使用调试器来查看代码，则会注意到在a = a->parent; [...] if(a->next != NULL) ...之后，子元素已经被删除了。 - BeyelerStudios

请注意，点号“.”和箭头“->”运算符的优先级非常高，在传统的C编码风格中不应该在它们周围加上空格。 - Jonathan Leffler

Answer 1

我认为你在多个地方检查NULL的做法过于复杂。当你有多个递归时，比起在调用函数之前检查，更容易在进入函数后检查NULL。

此外，如果你通过指针传递一个本地变量给cleaner()，就可以避免使用全局变量teller_cleanup。

void cleaner(struct ac *a, int *teller_cleanup) 
{
    if (a != NULL) {
        cleaner(a->next, teller_cleanup);
        cleaner(a->child, teller_cleanup);
        free(a->word);
        free(a);
        (*teller_cleanup)++;
    }
}

int cleanup(struct ac *a)
{
    int teller_cleanup = 0;
    cleaner(a, &teller_cleanup);
    return teller_cleanup;
}

- user325117

---

嗯，它比我的实现做得更好，但出于某种原因我仍然有内存泄漏。感谢告诉我teller_cleanup，我没有想到过。 - bob