pensamiento - definición de estructura autorreferencial?

neurosis autorreferencial

Question

No he estado escribiendo C por mucho tiempo, así que no estoy seguro de cómo debería hacer este tipo de cosas recursivas ... Me gustaría que cada celda contenga otra celda, pero me da un error a lo largo del las líneas de "campo ''niño'' tienen tipo incompleto". ¿Que pasa?

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

Answer 1

Desde el punto de vista teórico, los lenguajes solo pueden soportar estructuras autorreferenciales y no estructuras auto-inclusivas.

Answer 2

En C, no puede hacer referencia al typedef que está creando con 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 es probablemente mucho más complicado que esto en el estándar, puedes pensar que el compilador sabe sobre struct Cell en la primera línea del typedef pero no sabe acerca de tCell hasta la última línea :-) Así es como recuerdo esa regla .

Answer 3

Es evidente que una celda no puede contener otra celda, ya que se convierte en una recursión sin fin.

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

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

Answer 4

Hay una forma de evitar esto:

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

struct Cell;
typedef struct Cell Cell;

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

Answer 5

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;

Answer 6

Sé que esta publicación es antigua, sin embargo, para obtener el efecto que está buscando, puede intentar 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 su estructura de celda hija como un puntero. Si no lo hace, obtendrá el error "campo ''hijo'' tiene tipo incompleto ''. El motivo es que debe definirse "struct Cell" para que el compilador sepa cuánto espacio asignar cuando se utiliza.

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

Answer 7

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 es 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 declaras 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 dentro, entonces esto es una paradoja (es decir, para saber cuánta memoria tiene la estructura A, tiene que decidir cuánta memoria struct A takes!).

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

HTH

Answer 8

Una estructura que contiene una referencia a sí mismo. 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 en la cadena.

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

Answer 9

Veamos la definición básica de typedef. typedef use 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 define 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;)). Entonces, prefiera View 2.