definición de estructura autorreferencial?

No he escrito C durante mucho tiempo, por lo que no estoy seguro de cómo debo hacer este tipo de cosas recursivas ... Me gustaría que cada celda contenga otra celda, pero aparece un error líneas de "campo 'hijo' tiene tipo incompleto". ¿Qué pasa?

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

Claramente, una celda no puede contener otra celda ya que se convierte en una recursión interminable.

Sin embargo, una celda PUEDE contener un puntero a otra celda.

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

En C, no puede hacer referencia al typedef que está creando dentro de la estructura misma. Debe usar el nombre de la estructura, como en el siguiente programa de prueba:

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

Aunque probablemente sea mucho más complicado que esto en el estándar, puedes considerarlo como el compilador que conoce sobre struct Cellla primera línea de la línea typedefpero no sabe tCellhasta la última línea :-) Así es como recuerdo esa regla.

Desde el punto de vista teórico, los idiomas solo pueden soportar estructuras autorreferenciales, no estructuras autoincluyentes.

Hay una forma de evitar esto:

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

struct Cell;
typedef struct Cell Cell;

Si lo declaras así, le dice al compilador que struct Cell y plain-ol'-cell son iguales. Entonces puedes usar Cell como de costumbre. Sin embargo, todavía tengo que usar struct Cell dentro de la declaración inicial.

Sé que esta publicación es antigua, sin embargo, para obtener el efecto que estás buscando, puedes probar lo siguiente:

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

En cualquiera de los dos casos mencionados en el fragmento de código anterior, DEBE declarar la estructura de la celda secundaria como un puntero. Si no lo hace, obtendrá el error "campo 'hijo' tiene tipo incompleto". La razón es que "struct Cell" debe definirse para que el compilador sepa cuánto espacio asignar cuando se usa.

Si intentas utilizar "struct Cell" dentro de la definición de "struct Cell", entonces el compilador aún no puede saber cuánto espacio se supone que ocupa "struct Cell". Sin embargo, el compilador ya sabe cuánto espacio ocupa un puntero y (con la declaración directa) sabe que "Cell" es un tipo de "struct Cell" (aunque todavía no sabe qué tan grande es una "struct Cell") ) Entonces, el compilador puede definir una "Celda *" dentro de la estructura que se está definiendo.

Veamos la definición básica de typedef. typedef se usa para definir un alias para un tipo de datos existente, ya sea definido por el usuario o incorporado.

typedef <data_type> <alias>;

por ejemplo

typedef int scores;

scores team1 = 99;

La confusión aquí es con la estructura autorreferencial, debido a un miembro del mismo tipo de datos que no se definió anteriormente. Entonces, de manera estándar, puede escribir su código como: -

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

Pero la última opción aumenta algunas líneas y palabras adicionales con lo que generalmente no queremos hacer (somos tan vagos, ya sabes;)). Así que prefiera la Vista 2.

Otro método conveniente es predefinir la estructura con la etiqueta de estructura como:

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

Una estructura que contiene una referencia a sí misma. Una ocurrencia común de esto en una estructura que describe un nodo para una lista de enlaces. Cada nodo necesita una referencia al siguiente nodo de la cadena.

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

Todas las respuestas anteriores son geniales, solo pensé en dar una idea de por qué una estructura no puede contener una instancia de su propio tipo (no una referencia).

Es muy importante tener en cuenta que las estructuras son tipos de 'valor', es decir, contienen el valor real, por lo que cuando declara una estructura, el compilador tiene que decidir cuánta memoria asignar a una instancia de la misma, por lo que pasa por todos sus miembros y agrega hasta su memoria para descubrir la memoria total de la estructura, pero si el compilador encontró una instancia de la misma estructura en el interior, entonces es una paradoja (es decir, para saber cuánta memoria necesita la estructura A, tiene que decidir cuánta memoria estructura A toma!).

Pero los tipos de referencia son diferentes, si una estructura 'A' contiene una 'referencia' a una instancia de su propio tipo, aunque todavía no sabemos cuánta memoria se le asigna, sabemos cuánta memoria se le asigna a una memoria dirección (es decir, la referencia).

HTH