Реализация таблицы BST segfault (C) - PullRequest
Новая
       5

Реализация таблицы BST segfault (C)

0 голосов
/ 24 ноября 2018

Я пытался реализовать ассоциативный массив (int -> int) в C, используя бинарные деревья поиска.Тем не менее, моя текущая реализация надежно генерирует segfault, и я не совсем уверен, почему.Я прошу прощения, если проблема в чем-то очень простом, я просто упустил из виду.

Код: 

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

struct tree {
        int key;
        int value;
        struct tree *a;
        struct tree *b;
};

int summon (struct tree *t, int key) {
        if (t == NULL) {
                fprintf(stderr, "%s", "Key not in tree");
                exit(-1);
        } else {
                if (t -> key < key)
                        return summon(t -> a, key);
                else if (t -> key > key)
                        return summon(t -> b, key);
                else
                        return t -> value;
        }
}

struct tree _make (int key, int value) {
        struct tree ret;
        ret.key = key;
        ret.value = value;
        ret.a = ret.b = NULL;
        return ret;
}

void cast (struct tree *t, int key, int value) {
        if (key == t -> key) {
                t -> value = value;
        } else if (key > t -> key) {
                if (t -> a == NULL) {
                        struct tree n = _make(key, value);
                        t -> a = &n;
                } else {
                        cast(t -> a, key, value);
                }
        } else {
                if (t -> b == NULL) {
                        struct tree n = _make(key, value);
                        t -> b = &n;
                } else {
                        cast(t -> b, key, value);
                }
        }
}

int main (int argc, char **argv) {
        struct tree h = _make(5, 2);
        cast(&h, 16, 43);
        printf("%d", summon(&h, 16));
        return 0;
}

Я использую gcc в Ubuntu;GDB не полезно.

1 Ответ

0 голосов
/ 25 ноября 2018

В этом, например, 

if (t -> a == NULL) {
    struct tree n = _make(key, value);
    t -> a = &n;
}

вы сохраняете указатель на переменную с продолжительностью автоматического хранения в t->a.Однако время жизни n заканчивается на }, и t->a становится висящим указателем ;использование такого указателя в любом контексте приводит к неопределенному поведению.

Вам необходимо , чтобы использовать динамическое выделение памяти (malloc и др.) для этой задачи.

...