Возникли проблемы с Valgrind и реализацией функции min для BST - PullRequest
Новая
       11

Возникли проблемы с Valgrind и реализацией функции min для BST

0 голосов
/ 24 февраля 2020

Я реализовал bst с четырьмя функциями: add, inorderPrint, min и max. Предполагается, что min и max возвращают самые маленькие / самые большие значения в дереве, а также удаляют этот узел. Дерево может быть неуравновешенным. Ниже приведена реализация структуры моего узла, функции добавления, функции min, а также ошибки valgrind.

Ошибка Valgrind ниже: 

==2768== Invalid read of size 8
==2768==    at 0x108C13: removeSmallest (bst.c:43)
==2768==    by 0x108BDC: removeSmallest (bst.c:39)
==2768==    by 0x108945: main (problem2.c:25)
==2768==  Address 0x522d8a8 is 8 bytes inside a block of size 24 free'd
==2768==    at 0x4C30D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2768==    by 0x108C0B: removeSmallest (bst.c:42)
==2768==    by 0x108BDC: removeSmallest (bst.c:39)
==2768==    by 0x108945: main (problem2.c:25)
==2768==  Block was alloc'd at
==2768==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2768==    by 0x108A99: add (bst.c:9)
==2768==    by 0x108B08: add (bst.c:15)
==2768==    by 0x108918: main (problem2.c:21)
==2768==

Строка 43 равна (*root) = (*root)->right;

Строка 39 - return removeSmallest((&(*root)->left));

Строка 42 - free(*root);

Строка 9 - (*root) = (bst_node *)malloc(sizeof(bst_node));

Строка 15 - add(&((*root)->left), word);

Это структура узла в отдельном файле с именем bst.h 

typedef struct  bst_node {
    char * data;
    struct bst_node * right;
    struct bst_node * left;
} bst_node ;

Это файл для реализованных функций. 

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


void add ( bst_node ** root, char * word ) {
if ((*root) == NULL) {
    (*root) = (bst_node *)malloc(sizeof(bst_node));
    (*root)->data = word;
    (*root)->left = NULL;
    (*root)->right = NULL;
} else {
    if (strcmp(word, (*root)->data) < 0) {
        add(&((*root)->left), word);
    } else if (strcmp(word, (*root)->data) > 0) {
        add(&((*root)->right), word);
    }
}
}

void inorder ( bst_node * root ) {

if(root == NULL) {
    return;
}
inorder(root->left);
printf("  %s", root->data);
inorder(root->right);
}

char * removeSmallest (  bst_node ** root ){
char * answer;

if (*root == NULL) {
    return NULL;
} else {
    if ((*root)->left != NULL) {
        return removeSmallest((&(*root)->left));
    } else if ((*root)->right != NULL) {
        answer = (*root)->data;
        free(*root);
        (*root) = (*root)->right;
        return answer;

    } else {
        answer = (*root)->data;
        free((*root));
        *root = NULL;
        return answer;
    }
}
}

1 Ответ

1 голос
/ 24 февраля 2020

Вы пытаетесь использовать освобожденный указатель:

free(*root); (*root) = (*root)->right;

Я думаю, это должно быть

bst_node * new_root = (*root)->right; free(*root); (*root) = new_root;

...