如何释放前缀树中的内存？ （ANSI C）

Question

我试图释放dict_free（）函数中的内存，但它不起作用，我不知道为什么。我错过了什么吗？无法弄清楚，什么是错的。

编辑： 如果我在dict_free（）中调用free（），我希望看到free'd指针指向NULL，但这不会发生。

这里是我的代码：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

typedef struct Dict 
{ 
    struct Dict *branches[256]; 
    int index; 

}Dict; 


void dict_insert_depth(unsigned char*,Dict *,int); 
void dict_insert(unsigned char*,Dict *); 

void dict_free(Dict *d) 
{ 
    if(d!=NULL){ 
    int i; 
    for(i=0; i<256; i++){ 
     if(d->branches[i] != NULL){ 
     dict_free(d->branches[i]); 
     free(d->branches[i]); 
     printf("Is it free?? %s\n",d==NULL?"yes":"no"); 
     } 
    } 
    } 
} 
/** 
* Insert word into dictionaR 
*/ 
void dict_insert(unsigned char *w, Dict *d) 
{ 
    dict_insert_depth(w,d,0); 
} 

void dict_insert_depth(unsigned char *w, Dict *d, int depth) 
{ 
    if(strlen(w) > depth){ 
    int ch = w[depth]; 

    if(d->branches[ch]==NULL){ 
     d->branches[ch] = malloc(sizeof(struct Dict)); 
     dict_insert_depth(w,d->branches[ch],depth+1); 

    }else{ 
     dict_insert_depth(w,d->branches[ch],depth+1); 
    } 
    } 
} 

/** 
* Check whether a word exists in the dictionary 
* @param w Word to be checked 
* @param d Full dictionary 
* @return If found return 1, otherwise 0 
*/ 
int in_dict(unsigned char *w, Dict *d) 
{ 
    return in_dict_depth(w,d,0); 
} 

int in_dict_depth(unsigned char *w, Dict *d, int depth) 
{ 
    if(strlen(w)>depth){ 
    int ch = w[depth]; 
    if(d->branches[ch]){ 
     return in_dict_depth(w, d->branches[ch], depth+1); 
    }else{ 
     return 0; 
    } 
    }else{ 
    return 1; 
    } 

} 

Answer 1

你免费的代码看起来不错，但它将无法释放根节点。

你对自由度的测试是错误的。 free不会将任何变量设置为NULL。通常，这是一个好主意，做的是明确的，所以你一定不要看已经释放的内存：

free(d->branches[i]); 
    d->branches[i] = NULL; // clobber pointer to freed memory 

要处理根节点的问题，而且可能有些清洁剂为好，这样做：

void dict_free(Dict *d) 
{ 
    if(d!=NULL){ 
    int i; 
    for(i=0; i<256; i++){ 
     if(d->branches[i] != NULL){ 
     dict_free(d->branches[i]); 
     d->branches[i] = NULL; 
     } 
    } 
    free(d); 
    } 
} 

Answer 2

dict_free(d->branches[i]); 
free(d->branches[i]); 
printf("Is it free?? %s\n",d==NULL?"yes":"no"); 

这将检查d，但你不会在环路修改d。由于您检查和不是上面的空，它总是打印否。

void dict_free(Dict* d) { 
    if (d) { 
    for(int i = 0; i < 256; i++) { 
     if (d->branches[i]) { 
     dict_free(d->branches[i]); 
     free(d->branches[i]); 

     d->branches[i] = 0; // mark this branch as freed 
     // important if d is reused, and since dict_free doesn't 
     // free(d), it could be 
     } 
    } 
    } 
} 

我已经按照你的现有代码不释放d，但你可能要改变的事情，这样的字典总是被分配以同样的方式（如添加dict_new功能）与dict_free也释放传递目的。