Как освободить память в дереве префиксов?(ANSI C) - PullRequest
Новая
       40

Как освободить память в дереве префиксов?(ANSI C)

1 голос
/ 23 сентября 2010

Я пытался освободить память в функции dict_free (), но она не работает, и я не знаю почему. Я что-то пропустил? Не могу понять, что не так.

Edit: Если я вызову 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;
  }

}

Ответы [ 2 ]

3 голосов
/ 23 сентября 2010

Ваш бесплатный код выглядит нормально, за исключением того, что он не сможет освободить корневой узел.

Ваш тест на свободу не верен.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);
  }
}
0 голосов
/ 23 сентября 2010 
dict_free(d->branches[i]);
free(d->branches[i]);
printf("Is it free??  %s\n",d==NULL?"yes":"no");

Это проверяет d, , но вы не изменяете 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 всегда выделялся одинаково (например, добавьте функцию dict_new), а dict_free также освобождает переданные объект.

...