Двоичное дерево поиска - утечка памяти при вставке - PullRequest
Новая
       38

Двоичное дерево поиска - утечка памяти при вставке

0 голосов
/ 18 декабря 2018

Я пытаюсь создать двоичное дерево поиска и вставить новый узел итеративным способом.Это все работает хорошо, за исключением того, что я получаю утечку памяти в этой функции.

Valgrind говорит, что 7 блоков (я добавляю 7 узлов) отсутствуют.Я не мог видеть, где моя утечка.Я был бы признателен за еще один взгляд на мой код.

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {
    bst_node* current = bst->root;

    bst_node* parent = NULL;

    bst_node* new = (bst_node *)malloc(sizeof(bst_node));
    new->phone  = phone;
    new->left   =   new->right  =   new->parent =   NULL;
    new->name = malloc(sizeof(char) * (strlen(name)+1));
    strncpy(new->name,name,(strlen(name)+1));

    while(current != NULL) {

        parent = current;

        if(phone < current->phone) {
            current = current -> left;
        }
        else if(phone > current->phone) {
            current = current -> right;
        } else {
            free(new);
            printf("Diese Nummer ist schon bekannt \n");
            return;
        }
    }

    new->parent = parent;

    if(parent == NULL) {
        bst->root = new;
    }
    else if(new->phone < parent->phone) {
        parent->left = new;
    }
    else {
        parent->right = new;
    }
}

Бесплатные методы: 

void bst_free_subtree(bst_node* node) {
if (node == NULL) return;

bst_free_subtree(node->left);
bst_free_subtree(node->right);
printf("\n Deleting node: %lu \t %s", node->phone,node->name);
free(node);}

void bst_free_tree(bstree* bst) {
    if(bst != NULL && bst->root != NULL) {
        bst_free_subtree(bst->root);
        bst->root = NULL;
    }
}

1 Ответ

0 голосов
/ 19 декабря 2018

Как мы все обсуждали в комментариях, утечка памяти заключается в том, что вы не освобождаете выделенные вами строки node->name.Вам необходимо добавить еще два free к вашему коду:

  • в bst_insert_node, в случае, когда вы не можете вставить узел, free(new->name) перед вами free(new)
  • в bst_free_subtree, free(node->name) перед вами free(node)

Существует также ошибка, выделяющая место для скопированной строки, как в вашем ответе.Вместо этого может быть проще всего просто new->name = strdup(name), который будет выполнять выделение и копирование за один раз.

В качестве отступления, если это телефонные номера, то Я бы, вероятно, сохранил их какстроки, а не целые числа (или libphonenumber , если вы хотите использовать всю свинью, но не C ++, а C), и если есть проблема при ее вставке, то лучше вернуть ошибку в вызывающий код(например, вернуть true, если вставлено, false, если нет), и пусть это вызывает ошибки, а не печатать из этого кода.

...