c - 在这种情况下我将如何声明一个新结构？

Question

这就是我现在的代码(只是一个简单的 BST)

typedef struct bsn{
    int val;
    struct bsn *left, *right;
} bsn_t;

typedef struct bst{
    bsn_t *root;
    int size;
} bst_t;

我的问题是，对于我将要使用的函数，输入是这样的地址

void init( bst_t * tree )

我将如何使用它？这是我现在拥有的，但我不确定它是否正确

tree->size = 0;
tree->root = NULL;

还有其他功能，比如

bool insert( bst_t *tree, int val )

我想声明一个要使用的临时节点。这行得通吗？

bsn_t temp = (bsn_t *) malloc (sizeof (bsn_t));

我的最后一个问题是如何检查节点是否为空。我试过了

bsn_t visitor = (bsn_t*)malloc(sizeof(bsn_t));
visitor = *tree->root;

然后做

if (visitor != NULL)

但是当我编译的时候它说

'!=': illegal for struct

请帮忙..

Answer 1

在你的树中，节点之间的连接和来自外部的连接，即根，都是指针。它们指向使用 malloc 在堆上分配的节点。

如果您定义一个局部变量，例如:

bsn_t temp;

你得到一个栈上的节点，这个节点在函数返回后将失效。在您的情况下，您永远不需要在堆栈上创建节点。您应该始终使用指向节点的指针，这些节点指向现有节点、新分配的节点或不指向任何节点 (NULL)。

所以:

bsn_t *temp = malloc (sizeof (bsn_t));

(我已经删除了对(bsn_t *) 的强制转换。奇怪的是，在原始代码中，您将malloc 的返回值强制转换为一个指针分配给结构时键入。)

关于你的第二个问题，你的代码:

bsn_t visitor = (bsn_t*)malloc(sizeof(bsn_t));
visitor = *tree->root;

有几个地方是错误的。首先，如上所述，visitor 应该是指向节点的指针，而不是节点结构。

然后访问者应该从树的根向下移动。通过这样做，它不会创建任何新节点，因此根本不需要 malloc。请记住，malloc 为您提供堆上的新内存，实际上创建了一个节点。 visitor 只是指向现有对象。一个对象可以有多个指向它们的指针。

即使 malloc 是正确的做法，您也不应该 malloc 然后覆盖保存(到目前为止)指向 ne 内存的句柄的指针.

您还弄错了 *。 visitor 是一个指针，tree->root 也是一个指针，因此不需要取消引用。您所做的是将根目录的内容复制到本地结构。

你想要做的是这样的:

bsn_t *visitor = tree->root;

while (visitor != NULL) {
    // Do stuff

    visitor = visitor->right;    // or left, whatever
}

在声明和使用中使用星号可能会造成混淆。在声明中，您使用 start 使一个事物成为指针:

bsn_t node;      // uninitialised node struct on the stack
bsn_t *pnode;    // uninitialised pointer to node

之后，当你使用指针变量时，朴素的名字指的是指针。星号表示您取消引用它以获取指针指向的内容。当你使用结构时，你通常不会看到很多星星，因为 -> 语法是首选，但 node->left 本质上与 相同(*node).left.