了解包含其自身类型的指针的结构

Question

struct node
{
     int         info;
     struct node *llink;
     struct node *rlink;
};

typedef node *nodep;

结构体本身内部有结构体指针意味着什么？
请详细解释一下上面的结构。

附注
我不是在谈论树逻辑。我正在谈论 C 结构体和指针的行为。

编辑1：

struct node *llink内存如何分配给它？这是一种还没有出现的类型？

Answer 1

指针只是对内存中某个位置（“地址”）的引用。对于节点，指向节点实例的指针是对内存中存储该节点实例的位置的引用。

对于定义的 struct 来说，如果您有一个驻留在一个内存位置的 node 实例，它可以指向另外两个 node 实例驻留在自己的内存位置（*llink、*rlink）。

使用现实世界的树作为比喻，*llink 和 *rlink 分别是指向树结构根节点的左“分支”和右“分支”的指针。这些指针本身可能会分支成更远更深的左“子树”和右“子树”。

阅读二叉树简介。

Answer 2

由于网络上存在一些关于“声明”与“定义”的矛盾信息，因此我将坚持这篇文章。

struct node
{

这是结构体“node”的定义的开始。它还引入了类型node。

     int         info;
     struct node *llink;
     struct node *rlink;

以下是一些字段声明。类型必须是已知的，并且它是已知的，因为它已经被引入了。 node 的实际大小无关紧要。

};

现在node的定义已经完成，它可以用作类型：

typedef node *nodep;

当定义一个node类型的变量时code>，内存被分配：

node n = {42, NULL, NULL};
// or
nodep np = (struct node *)malloc(sizeof(struct node));

---

对于 C++：但是如果您想在彼此内部使用两种类型怎么办？然后引入类型B，定义类型A，定义类型B：

class B;

class A
{
    class B *pointerToB;
};

class B
{
    class A *pointerToA;
};

->这应该显示想法，而不是生产代码。我不确定您是否可以在 C 中将它与上一个示例中的 struct 而不是 class 一起使用。如果这不是100%正确，请发表评论，我会纠正。

---

这是对这篇文章从头开始的一个很好的后续我的回答。 链接不再有效

Answer 3

此页面提供有关树数据结构是什么的信息：

http://en.wikipedia.org/wiki /Tree_(data_struction)

树节点保存数据值（info 成员）和指向左子树和右子树的指针（llink 和 rlink 指针）。子树也是节点，因此指针是指向结构节点对象的指针，使用指针可以遍历树，因为所有节点都通过指针链接。

Answer 4

二叉树可以这样递归地定义：

• 每个节点（没有子树的节点）本身就是一棵二叉树。
• 如果一个节点有左子树、右子树或两者都有，则它是二叉树。

结构节点的定义遵循二叉树的递归定义。

例如：

上图表示一棵二叉树。我们可以用以下方式在 C 中表示这个二叉树：

值为 2 的节点是没有子树的节点，可以表示为如下结构：

struct node* node2 = malloc(sizeof(struct node));
node2->info = 2;
node2->llink = NULL;
node2->rlink = NULL;

llink 的 NULL 值和rlink表示该节点没有子树。请注意，我们可以表示值为 5 的节点（左下角的节点，而不是右上角的节点）、11 和 4。

值为 6 的节点有两个子树（请记住，所有节点本身都是子树 ） ）并且，假设值分别为 5 和 11 的节点由 表示，

struct node* node5 = malloc(sizeof(struct node));
node5->info = 5;
node5->llink = NULL;
node5->rlink = NULL;

struct node* node11 = malloc(sizeof(struct node));
node11->info = 11;
node11->llink = NULL;
node11->rlink = NULL;

我们可以这样表示我们的节点：

struct node* node6 = malloc(sizeof(struct node));
node6->info = 6;
node6->llink = node5; /* Pointer to node with value 5 */
node6->rlink = node11; /* Pointer to node with value 11 */

对于二叉树的所有其他节点也是如此。

请注意，我们使用子树的指针。原因是使用 NULL 允许树具有有限数量的元素，否则，二叉树将需要无限量的内存（一个包含自身、包含自身、包含自身、包含自身的结构..需要无限量的内存）。

（图片取自 Wikipedia 文章 二叉树，具体来说，取自 http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/200px-Binary_tree.svg.png）