Как освободить память в дереве префикса? (ANSI C)
-
04-10-2019 - |
Вопрос
Я пытался освободить память в функции Dict_free (), но не работает, и я не знаю, почему. Я что-то пропустил? Не могу выяснить, что не так.
Редактировать: Если я позвоню бесплатно () в Dict_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;
}
}
Решение
Ваш бесплатный код выглядит нормально, за исключением того, что он не сможет освободить корневой узел.
Ваш тест на Free-Ness не так. 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);
}
}
Другие советы
dict_free(d->branches[i]);
free(d->branches[i]);
printf("Is it free?? %s\n",d==NULL?"yes":"no");
Это проверки 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) с DICK_Free также освобождающим пропущенного объекта.