c - BST表实现段错误(C)

Question

我一直在尝试使用二叉搜索树在 C 中实现关联数组 (int -> int)。然而，我当前的实现可靠地产生了段错误，我不太清楚为什么。如果问题很简单，我只是忽略了，我深表歉意。

代码:

#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;
}

我在 Ubuntu 上使用 gcc； gdb 没有提供帮助。

Answer 1

例如，在此，

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

您正在将一个指向具有自动存储持续时间的变量的指针存储到t->a中。然而，n 的生命周期在 } 结束，并且 t->a 成为一个悬空指针；在任何上下文中使用此类指针都会导致未定义的行为。

您需要使用动态内存分配(malloc 等)来完成此任务。