Самореферентное определение структуры?

Question

Я не писал C очень долго, и поэтому я не уверен, как мне следует делать подобные рекурсивные вещи... Я хотел бы, чтобы каждая ячейка содержала другую ячейку, но я получаю сообщение об ошибке строки "поля 'child' имеют неполный тип". Что происходит?

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

Answer 1

Ясно, что ячейка не может содержать другую ячейку, поскольку она становится бесконечной рекурсией.

Однако ячейка МОЖЕТ содержать указатель на другую ячейку.

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

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;
}

Хотя это, вероятно, намного сложнее, чем это в стандарте, вы можете думать об этом как о компиляторе, знающем о struct Cell на первой строке typedef но не зная о tCell до последней строки:-) Вот так я помню это правило.

Answer 3

С теоретической точки зрения, Языки могут поддерживать только самоссылочные структуры, но не самодостаточные структуры.

Answer 4

Есть способ обойти это:

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

struct Cell;
typedef struct Cell Cell;

Если вы объявите это так, это правильно сообщит компилятору, что struct Cell и plain-ol'-cell одинаковы. Таким образом, вы можете использовать Cell, как обычно. Тем не менее, все же придется использовать struct Cell внутри самого исходного объявления.

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;

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 *" в структуре, которая определяется.

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;

Но последний вариант увеличивает количество лишних строк и слов, обычно мы этого не хотим (мы так ленивы, вы знаете;)) . Поэтому предпочитаю View 2.

Answer 8

Структура, которая содержит ссылку на себя. Это часто встречается в структуре, которая описывает узел для списка ссылок. Каждому узлу нужна ссылка на следующий узел в цепочке.

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

Answer 9

Все предыдущие ответы великолепны, я просто подумал, почему структура не может содержать экземпляр своего типа (не ссылку).

очень важно отметить, что структуры являются типами "значений", то есть они содержат фактическое значение, поэтому, когда вы объявляете структуру, компилятор должен решить, сколько памяти выделить его экземпляру, чтобы он прошел через все его члены и добавил их память, чтобы выяснить всю память структуры, но если компилятор нашел экземпляр той же структуры внутри, то это парадокс (то есть, чтобы узнать, сколько занимает структура памяти A, вы должны решить, сколько памяти структура А занимает!).

Но ссылочные типы различны, если структура "A" содержит "ссылку" на экземпляр своего собственного типа, хотя мы еще не знаем, сколько памяти выделено для него, мы знаем, сколько памяти выделено для памяти адрес (т.е. ссылка).

НТН