c中清理双链表Trie结构
Cleaning double linked list Trie structure in c
我想防止内存泄漏,所以我想释放 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;
};
它是一个双向或 4 向链表,不确定我应该如何调用它。
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;
}
但是好像不能正常使用。它给出了一个错误:
双重释放或损坏(fasttop):0x0000000000fffa70 ***
我似乎没有得到什么,因为当 'child' 和 'next' 都是 'NULL' 时,'a' 是最外面的节点。而且我相信只有一个回溯 if 语句可以转到这些最外层节点之一。
我将尝试可视化 trie:
[root]
|
\/
[h] -- > [b]
| |
\/ \/
[i] [y] --> [e]
所以 trie 包含单词 hi、by 和 be。 root 指向第一个单词的第一个字符,所有箭头都是双链接的。从 'h' 到 'b' 是下一个,从 'h' 到 'i' 是 child.
有人能看出我做错了什么吗?将不胜感激。
我认为您在多个地方检查 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;
}
我想防止内存泄漏,所以我想释放 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;
};
它是一个双向或 4 向链表,不确定我应该如何调用它。
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;
}
但是好像不能正常使用。它给出了一个错误:
双重释放或损坏(fasttop):0x0000000000fffa70 ***
我似乎没有得到什么,因为当 'child' 和 'next' 都是 'NULL' 时,'a' 是最外面的节点。而且我相信只有一个回溯 if 语句可以转到这些最外层节点之一。
我将尝试可视化 trie:
[root]
|
\/
[h] -- > [b]
| |
\/ \/
[i] [y] --> [e]
所以 trie 包含单词 hi、by 和 be。 root 指向第一个单词的第一个字符,所有箭头都是双链接的。从 'h' 到 'b' 是下一个,从 'h' 到 'i' 是 child.
有人能看出我做错了什么吗?将不胜感激。
我认为您在多个地方检查 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;
}