自引用结构体定义？

Question

我没有写很长时间的C语言，所以我不确定我应该如何处理这些递归问题... 我想每个单元格都包含另一个单元格，但我得到了类似于“字段'child'具有不完整的类型”的错误。怎么回事？

typedef struct Cell {
  int isParent;
  Cell child;
} Cell;

- Ziggy

---

实际上，它将“struct Cell”定义为“Cell”（这是一种常见的模式）。 - David Z

他可能在使用C++编译器。如果是真正的C，他也应该使用_Bool。 - nabiy

如果真的是C语言，他应该使用int。 - paxdiablo

为什么？C99有bool - 你只需要包含<stdbool.h>。 - Jonathan Leffler

C99可能有bool，但绝对不会是蓝色的 ;) - avakar

可能是重复问题C:在结构定义中使用指向结构的指针。 - Jonathan Leffler

Answer 1

很明显，一个 Cell 不能包含另一个 Cell ，否则它会变成无限递归。

然而，一个 Cell 可以包含指向另一个 Cell 的指针。

typedef struct Cell {
  bool isParent;
  struct Cell* child;
} Cell;

- Andrew Grant

---

不，Cell 目前不在范围内。 - fredoverflow

当我尝试将Cell*赋值给cell->child时，我会收到警告。 - Tomáš Zato

由于Python抽象了指针，所以你几乎不会注意到它们。在C语言中，由于结构体基本上只是将所有值存储在一起，因此实际上不可能将一个结构体存储在自身中（因为该结构体必须包含另一个结构体，依此类推，导致一个无限大小的内存结构）。 - jazzpi

有关使用 struct Cell 的解释，请参见此答案。 - wizzwizz4

注意 C11 §6.7.2.1 结构体和联合体说明符 ¶3：结构体或联合体不得包含具有不完整或函数类型的成员（因此，结构体不得包含自身的实例，但可以包含指向自身实例的指针），... - Jonathan Leffler

Answer 2

在C语言中，你不能在结构体内部引用正在创建的typedef类型。你必须使用结构体名称，就像以下测试程序一样：

#include <stdio.h>
#include <stdlib.h>

typedef struct Cell {
  int cellSeq;
  struct Cell* next; /* 'tCell *next' will not work here */
} tCell;

int main(void) {
    int i;
    tCell *curr;
    tCell *first;
    tCell *last;

    /* Construct linked list, 100 down to 80. */

    first = malloc (sizeof (tCell));
    last = first;
    first->cellSeq = 100;
    first->next = NULL;
    for (i = 0; i < 20; i++) {
        curr = malloc (sizeof (tCell));
        curr->cellSeq = last->cellSeq - 1;
        curr->next = NULL;
        last->next = curr;
        last = curr;
    }

    /* Walk the list, printing sequence numbers. */

    curr = first;
    while (curr != NULL) {
        printf ("Sequence = %d\n", curr->cellSeq);
        curr = curr->next;
    }

    return 0;
}

虽然在标准中可能比这更复杂，但你可以将它看作是编译器在 typedef 的第一行知道了关于 struct Cell 的信息，但直到最后一行才知道关于 tCell 的信息 :-) 这就是我记住这个规则的方式。

- Pax

---

C++方面怎么样？您能否请提供关于C++的答案链接？ - rooni

@rimiro，这个问题是关于C语言的。如果你想要C++版本的答案，你应该把它作为一个问题来提出。 - paxdiablo

Answer 3

从理论角度来看，编程语言只能支持自我引用结构而不是自我包含结构。

- Sundar

---

从实际角度来看，“struct Cell”的实例实际上有多大？ - Marsh Ray

在大多数计算机上，所占空间会比其本身多四个字节。 - TonyK

Answer 4

有一种方法可以绕过这个问题：

struct Cell {
  bool isParent;
  struct Cell* child;
};

struct Cell;
typedef struct Cell Cell;

如果你像这样声明它，就可以正确地告诉编译器struct Cell和plain-ol'-cell是相同的。因此，你可以像正常情况下一样使用Cell。不过，在初始声明本身内仍然必须使用struct Cell。

- Benjamin Horstman

---

为什么你又写了一遍 struct Cell;？ - MAKZ

@MAKZ 因为在编译“struct Cell”的定义时，编译器尚未执行typedef。 - Tyler Crompton

如果将以上代码块放入单个C源文件中，则typedef已经被“编译器执行”，从而使额外的 struct Cell; 多余。 但是，如果出于某种原因将最后两行放入头文件中，并在定义第一四行的 Cell 结构之前包含该头文件，则需要额外的 struct Cell;。 - yyny

这在C99标准下甚至都无法编译。 - Tomáš Zato

@YoYoYonnY 不，你仍然可以只写typedef struct Cell Cell;，它会将Cell作为struct Cell的别名。编译器是否之前看到过struct Cell { .... }并不重要。 - melpomene

@TomášZato - 是的，它可以在C90、C99、C11、C18下编译。 - Jonathan Leffler

Answer 5

预先使用结构标签对结构进行预定义，如下所示：

//declare new type 'Node', as same as struct tag
typedef struct Node Node;
//struct with structure tag 'Node'
struct Node
{
    int data;
    //pointer to structure with custom type as same as struct tag
    Node *nextNode;
};
//another pointer of custom type 'Node', same as struct tag
Node *node;

- Keynes

Answer 6

我知道这篇文章有些陈旧了，但是如果你想要达到你想要的效果，可以尝试以下方法:

#define TAKE_ADVANTAGE

/* Forward declaration of "struct Cell" as type Cell. */
typedef struct Cell Cell;

#ifdef TAKE_ADVANTAGE
/*
   Define Cell structure taking advantage of forward declaration.
*/
struct Cell
{
   int isParent;
   Cell *child;
};

#else

/*
   Or...you could define it as other posters have mentioned without taking
   advantage of the forward declaration.
*/
struct Cell
{
   int isParent;
   struct Cell *child;
};

#endif

/*
    Some code here...
*/

/* Use the Cell type. */
Cell newCell;

无论在上面的代码片段中提到的哪种情况下，您都必须将子Cell结构声明为指针。如果不这样做，则会出现“字段'child'具有不完整的类型”错误。原因是编译器必须定义“struct Cell”以便知道在使用时应分配多少空间。

如果您尝试在“struct Cell”的定义内部使用“struct Cell”，则编译器无法知道“struct Cell”应该占用多少空间。然而，编译器已经知道指针需要多少空间，并且（通过前向声明）它知道“Cell”是“struct Cell”的一种类型（尽管它尚不知道“struct Cell”的大小）。因此，编译器可以在正在定义的结构体中定义一个“Cell *”。

- Shawn

Answer 7

让我们先了解typedef的基本定义。typedef用于为现有数据类型定义一个别名，无论是用户自定义的还是内置的。

typedef <data_type> <alias>;

例如

typedef int scores;

scores team1 = 99;

这里的混淆出现在自我引用结构中，因为同一数据类型的成员还未定义。因此，您可以按照标准方式编写您的代码：

//View 1
typedef struct{ bool isParent; struct Cell* child;} Cell;

//View 2
typedef struct{
  bool isParent;
  struct Cell* child;
} Cell;

//Other Available ways, define stucture and create typedef
struct Cell {
  bool isParent;
  struct Cell* child;
};

typedef struct Cell Cell;

但是最后一种选项会增加一些额外的行和单词，通常我们不想这样做（你知道我们很懒 ;)）。所以更喜欢第二种视图。

- vineetv2821993

---

你对 typedef 语法的解释是错误的（考虑例如 typedef int (*foo)(void);）。你的 View 1 和 View 2 示例不起作用：它们使 struct Cell 成为不完整类型，因此你实际上无法在代码中使用 child。 - melpomene

Answer 8

一个包含对自身的引用的结构。这在描述链接列表节点的结构中很常见。每个节点都需要对链中下一个节点的引用。

struct node
{
       int data;
       struct node *next; // <-self reference
};

- DARSHINI DESAI

Answer 9

所有之前的答案都很好，我只是想提供一些关于为什么结构体不能包含其自身类型的实例（而不是引用）的见解。

非常重要的是要注意，结构体是“值”类型，即它们包含实际值，因此当您声明一个结构体时，编译器必须决定为其实例分配多少内存，所以它遍历所有成员并累加它们的内存以计算结构体的总内存，但如果编译器发现相同结构体的实例，则这是一个悖论（即为了知道结构体A需要多少内存，您必须决定结构体A需要多少内存！）。

但是，引用类型是不同的，如果结构体'A'包含对其自身类型实例的'引用'，尽管我们还不知道分配给它多少内存，但我们知道分配给内存地址的内存量（即引用）。

希望有所帮助。

- m.eldehairy