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


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

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

9 ответов:

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

однако ячейка может содержать указатель на другую ячейку.

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

В 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 до последней строчки :-) вот как я помню это правило.

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

есть своего рода способ обойти это:

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

struct Cell;
typedef struct Cell Cell;

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

Я знаю, что этот пост старый, однако, чтобы получить эффект, который вы ищете, вы можете попробовать следующее:

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

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

Если вы попытайтесь использовать " ячейку структуры "внутри определения" ячейки структуры", тогда компилятор еще не может знать, сколько места" ячейка структуры " должна занимать. Однако компилятор уже знает, сколько места занимает указатель, и (с прямым объявлением) он знает, что "ячейка" является типом "ячейки структуры" (хотя он еще не знает, насколько велика "ячейка структуры"). Таким образом, компилятор может определить "ячейку *" в структуре, которая определяется.

давайте рассмотрим основное определение 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;

но последний вариант увеличить некоторые дополнительные строки и слова с Обычно мы не хотим делать (мы такие ленивые вы знаете ;)). Так что предпочитаю вид 2.

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

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

еще одним удобным способом является предварительное определение типа структуры,тэг структуру:

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

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

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

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

HTH