已分配但未分配的结构

Question

我正在尝试在 C/C++ 中实现 BST。

注意：在此 class 中，提交的文件应具有 .cpp 文件扩展名，并且应使用 C++ 编译器进行编译，但应该是“哲学上”的 C（printf()， malloc()，等等），允许某些 C++ 特性（原生 bools，等等）。这也意味着解决 C++ 限制（转换 malloc() 的结果，将 const 添加到字符串等）。这条线很模糊，所以为了安全起见，我采用了 C 风格 - 这是一个个人项目，我希望能够通过简单地调整几个关键函数来在需要时回收。

我有一个函数 pushBST() 调用 pushBSTNode():

bool pushBST(BST* tree, const char* val_cstr, int val_int) {
    if (tree == NULL) return false;

    BSTData* data = createBSTData(val_cstr, val_int);
    if (data == NULL) return false;
    return pushBSTNode(tree->root, tree->root, data);
}

bool pushBSTNode(BSTNode* node, BSTNode* parent, BSTData* data) {
    if (node == NULL) {
        node = createBSTNode(data, parent);
        if (node == NULL) return false;
        return true;
    } else {
        // ...
    }
}

我的想法是抽象出使用 pushBST() 将数据推送到 BST，只需要树本身和原始数据。但是，这不起作用，尽管 return 是真的。在 VSCode 中用 GDB 窥视它告诉我有问题，但我不太明白。

调用函数最初按预期工作：

if (tree == NULL) return false; // So it doesn't choke on a void pointer, passed

BSTData* data = createBSTData(...); // It packed the data correctly, passed
if (data == NULL) return false; // Report a failure if the data failed to pack, passed.

此时，我可以看到变量是正确的：树存在并且数据中包含正确的值。接下来是实际推送它的功能：

if (node == NULL) { // tree->root was indeed NULL, passed
    node = createBSTNode(...); // This allocates a node and assigns it the packed data, passed
    if (node == NULL) return false; // The node exists, passed
    return true; // Therefore, this should have worked
}

传入的node指的是tree->root，所以应该在那里分配了一个节点结构。在那个函数的最后确实确实node变量有数据而且数据是正确的（变量parent是错误的，但我稍后会处理它）。然而，在 returning 到主推送功能时，我看到变量没有改变。变量 tree->root 仍然是 NULL，但现在它有一个 return 值，表明假定成功。

关于哪里出了问题以及如何解决它有什么想法吗？

这是我使用的测试程序：

main.cpp:

#include <stdio.h>

#include "bstree.hpp"

int main() {
    myds::bst::BST* tree = myds::bst::createBST();
    myds::bst::pushBST(tree, "yeet val 1", 5);
    myds::bst::pushBST(tree, "yeet val 2", 3);
    myds::bst::pushBST(tree, "yeet val 3", 4);
    myds::bst::pushBST(tree, "yeet val 4", 1);
    myds::bst::pushBST(tree, "yeet val 5", 2);
    printf("Hello World!\n");
    return 0;
}

bstree.hpp:

#ifndef BSTREE_HPP
#define BSTREE_HPP

#include <stddef.h>

namespace myds::bst {
    struct BSTData {
        char val_cstr[16];
        int val_int
    };

    struct BSTNode {
        BSTData* data;

        BSTNode* parent;
        BSTNode* left;
        BSTNode* right;
    };

    struct BST {
        BSTNode* root;
    };

    BSTData* createBSTData(const char* val_cstr, int val_int);
    BSTNode* createBSTNode(BSTData* data, BSTNode* parent);
    BST* createBST();

    bool pushBSTNode(BSTNode* node, BSTNode* parent, BSTData* data);
    bool pushBST(BST* tree, const char* val_cstr, int val_int);
}

#endif

bstree.cpp:

#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#include "bstree.hpp"

namespace myds::bst {
    BSTData* createBSTData(const char* val_cstr, int val_int) {
        BSTData* data = (BSTData*) malloc(sizeof(BSTData));
        if (data == NULL) return NULL;

        strcpy(data->val_cstr, val_cstr);
        data->val_int = val_int;

        return data;
    }

    BSTNode* createBSTNode(BSTData* data, BSTNode* parent) {
        BSTNode* node = (BSTNode*) malloc(sizeof(BSTNode));
        if (node == NULL) return NULL;

        node->data = data;

        node->parent = parent;
        node->left = NULL;
        node->right = NULL;

        return node;
    }

    BST* createBST() {
        BST* tree = (BST*) malloc(sizeof(BST));
        if (tree == NULL) return NULL;

        tree->root = NULL;

        return tree;
    }

    bool pushBSTNode(BSTNode* node, BSTNode* parent, BSTData* data) {
        if (node == NULL) {
            node = createBSTNode(data, parent);
            if (node == NULL) return false;
            return true;
        } else {
            ssize_t delta = compareBSTData(data, node->data);
            if (delta < 0) {
                // data is smaller than current node, should go to left side of node
                return pushBSTNode(node->left, node, data);
            } else if (delta == 0) {
                // data == node, cannot store duplicate values
                return false;
            } else if (delta > 1) {
            // data is larger than current node, should go to the right side of node
                return pushBSTNode(node->right, node, data);
            }
        }

        return false; // silence clang
    }

    bool pushBST(BST* tree, const char* val_cstr, int val_int) {
        if (tree == NULL) return false;

        BSTData* data = createBSTData(val_cstr, val_int);
        if (data == NULL) return false;
        bool retval = pushBSTNode(tree->root, tree->root, data);
        return retval;
    }
}

Answer 1

用于树传播的指针需要通过引用传递。如果按值传递（无引用），则在函数完成后，在 CreateBSTNode 函数范围内所做的任何更改都将丢失。

pushBSTNode(BSTNode* &node, BSTNode* &parent, BSTData* &data)

已分配但未分配的结构

Structure allocated but not assigned

c++

c

binary-search-tree