C malloc 堆栈与堆问题

Question

我正在用 C 实现二叉搜索树的插入功能，但遇到 malloc 问题。

首先，我有一个树和节点结构

typedef struct Node {
    double value;

    struct Node *parent;
    struct Node *right_child;
    struct Node *left_child;
} Node;

typedef struct Tree {
    struct Node *root;
} Tree;

这是我的插入函数，用于将值插入树中。

void insert(Tree *t, double v) {

    Node *n = malloc(sizeof(Node));
    n->left_child = malloc(sizeof(Node));
    n->right_child = malloc(sizeof(Node));
    n->parent = malloc(sizeof(Node));
    n->value=v;

    Node *x = t->root, *y = NULL;

    //follow tree down until we reach a leaf of the tree
    while (x) {

        //save last non-NULL value. We will insert node n as a child to this leaf.
        y = x;

        if (n->value < x->value) {
            x = x->left_child;
        } else {
            x = x->right_child;
        }
    }

    //The parent of the node to insert is the leaf we reached
    n->parent = y;

    //If n is greater than y then it is its right child and vice-versa.
    if (n->value > y->value) {
        y->right_child = n;
    } else {
        y->left_child = n;
    }

}

还有我的主要方法

int main(void) {

    Node n1;

    n1.value = 4;
    n1.parent = NULL;
    n1.left_child = NULL;
    n1.right_child = NULL;

    Tree t;

    t.root = &n1;

    insert(&t,2.0);

    printf("In order traversal\n");
    inOrderTraversalNode(t.root);

    return EXIT_SUCCESS;
}

当我打印顺序遍历代码时，我得到了未定义的行为（例如：26815615859885194199148049996411692254958731641184786755447122887443528060147093953603748596333806855380063716372972101707507765623893139892867298012168192.000000）而不是正确的遍历。

我很确定问题出在 insert 方法中的 Node 创建。我假设问题是新节点存在于堆栈上，然后在 insert 函数退出时被销毁 - 这就是遍历期间导致未定义行为的原因。但是，我认为 malloc 将变量存储在堆上并使其在全局可用。或者也许节点在堆上但指针在堆栈上？有人可以告诉我哪里出错了吗？

Answer 1

通过malloc分配的内存中的初始内容未定义。

首先，删除导致内存泄漏的n->parent = malloc(sizeof(Node));。

其次，改变

  n->left_child = malloc(sizeof(Node));
  n->right_child = malloc(sizeof(Node));

到

  n->left_child = NULL;
  n->right_child = NULL;

以便程序能够正确识别树叶。

Answer 2

尝试使用 calloc 而不是 malloc。问题是 malloc 没有将值初始化为零，它仅分配了 space。 calloc 将您请求的 space 归零。因此，当您到达一个无效的指针时，您偶尔会跳转到内存的随机部分，但也不是 NULL。

malloc 朋友肯定是在堆上分配的，你的想法是对的；他们 return 是指向内存中 space 的指针，其大小至少是您要求的，绝对可以安全地读取和写入。但是，由于在您使用 malloc 时该值并未从一开始就清零，因此您无法保证存储在结构中的指针实际上指向有效位置。

编辑：另外，其他张贴者是对的：您正在做的事情肯定存在内存泄漏。没听清楚。

C malloc 堆栈与堆问题

C malloc stack vs heap issue

c

heap-memory

stack-memory

binary-search-tree