释放一棵特里树
Freeing a trie tree
所以我在网上找到了一些 trie 树的例子,并决定试用它们来帮助我正在开发的游戏,该游戏将包含字典中所有单词的 trie 树。我在网上找到的例子没有任何 freeTree 的实现来避免内存泄漏,所以我想自己做一个。但是我已经有一段时间没有使用 c 并且 运行 遇到了问题。
char keys[][8] = {"the", "a", "there", "answer", "any",
"by", "bye", "their"};
char output[][32] = {"Not present in trie", "Present in trie"};
struct TrieNode *root = getNode();
// Construct trie
int i;
for (i = 0; i < ARRAY_SIZE(keys); i++){
insert(root, keys[i]);
}
// Search for different keys
printf("%s --- %s\n", "the", output[search(root, "the")] );
printf("%s --- %s\n", "these", output[search(root, "these")] );
printf("%s --- %s\n", "their", output[search(root, "their")] );
printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );
freeTree(root);
printf("test after free\n");
printf("%s --- %s\n", "the", output[search(root, "the")] );
printf("%s --- %s\n", "these", output[search(root, "these")] );
printf("%s --- %s\n", "their", output[search(root, "their")] );
printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );
这是一个简单的测试im 运行 free后的结果和之前一样
the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie
test after free
the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie
这是我使用的结构
struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE];
bool isLeaf;
};
和免费实施
void freeChildren(struct TrieNode *node){
int i;
if (node->isLeaf == false){
for (i=0;i<ALPHABET_SIZE;i++){
if (node->children[i] != NULL){
freeChildren(node->children[i]);
}
}
}
if (node != NULL){
node = NULL;
free(node);
}
}
void freeTree(struct TrieNode *root){
freeChildren(root);
free(root);
}
当我创建一个新的树节点时,我为它分配了内存,所以我知道我需要释放。
我认为你的问题出在这部分:
if (node != NULL){
node = NULL;
free(node);
}
好吧,您需要释放它然后将其设置为 NULL。否则你已经失去了地址。
void freeChildren(struct TrieNode *node){
int i;
if (node != NULL && node->isLeaf == false){//NULL check important only for the root
for (i=0;i<ALPHABET_SIZE;i++){
if (node->children[i] != NULL){
freeChildren(node->children[i]);
node->children[i] = NULL]; //you have to remove the address, otherwise it stays, just is no longer allocated (but it is still possible to access it, though it might crash or do whatever else)
}
}
}
if (node != NULL){ //again only root could be NULL
free(node);//this has to go first
//node = NULL; this has no meaning, as this is the local variable, not the place you passed it to
}
}
void freeTree(struct TrieNode *root){
freeChildren(root);
// free(root); this is already done in the freeChildren
// you might want to realloc the root there though, as otherwise you don't have anything allocated to root
root = NULL;
}
所以我在网上找到了一些 trie 树的例子,并决定试用它们来帮助我正在开发的游戏,该游戏将包含字典中所有单词的 trie 树。我在网上找到的例子没有任何 freeTree 的实现来避免内存泄漏,所以我想自己做一个。但是我已经有一段时间没有使用 c 并且 运行 遇到了问题。
char keys[][8] = {"the", "a", "there", "answer", "any",
"by", "bye", "their"};
char output[][32] = {"Not present in trie", "Present in trie"};
struct TrieNode *root = getNode();
// Construct trie
int i;
for (i = 0; i < ARRAY_SIZE(keys); i++){
insert(root, keys[i]);
}
// Search for different keys
printf("%s --- %s\n", "the", output[search(root, "the")] );
printf("%s --- %s\n", "these", output[search(root, "these")] );
printf("%s --- %s\n", "their", output[search(root, "their")] );
printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );
freeTree(root);
printf("test after free\n");
printf("%s --- %s\n", "the", output[search(root, "the")] );
printf("%s --- %s\n", "these", output[search(root, "these")] );
printf("%s --- %s\n", "their", output[search(root, "their")] );
printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );
这是一个简单的测试im 运行 free后的结果和之前一样
the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie
test after free
the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie
这是我使用的结构
struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE];
bool isLeaf;
};
和免费实施
void freeChildren(struct TrieNode *node){
int i;
if (node->isLeaf == false){
for (i=0;i<ALPHABET_SIZE;i++){
if (node->children[i] != NULL){
freeChildren(node->children[i]);
}
}
}
if (node != NULL){
node = NULL;
free(node);
}
}
void freeTree(struct TrieNode *root){
freeChildren(root);
free(root);
}
当我创建一个新的树节点时,我为它分配了内存,所以我知道我需要释放。
我认为你的问题出在这部分:
if (node != NULL){
node = NULL;
free(node);
}
好吧,您需要释放它然后将其设置为 NULL。否则你已经失去了地址。
void freeChildren(struct TrieNode *node){
int i;
if (node != NULL && node->isLeaf == false){//NULL check important only for the root
for (i=0;i<ALPHABET_SIZE;i++){
if (node->children[i] != NULL){
freeChildren(node->children[i]);
node->children[i] = NULL]; //you have to remove the address, otherwise it stays, just is no longer allocated (but it is still possible to access it, though it might crash or do whatever else)
}
}
}
if (node != NULL){ //again only root could be NULL
free(node);//this has to go first
//node = NULL; this has no meaning, as this is the local variable, not the place you passed it to
}
}
void freeTree(struct TrieNode *root){
freeChildren(root);
// free(root); this is already done in the freeChildren
// you might want to realloc the root there though, as otherwise you don't have anything allocated to root
root = NULL;
}