définition de structure auto-référentielle ?

Question

Je n'écris pas en C depuis très longtemps, et je ne suis donc pas sûr de la façon dont je dois procéder pour faire ce genre de choses récursives... Je voudrais que chaque cellule contienne une autre cellule, mais je reçois une erreur du type "field 'child' has incomplete type". Qu'est-ce qui se passe ?

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

PS (Ziggy est aussi clairement perturbé par le typedef : il a typedefé Cell à Cell et se demande pourquoi)

Answer 1

Il est clair qu'une cellule ne peut pas contenir une autre cellule car cela devient une récursion sans fin.

Cependant, une cellule peut contenir un pointeur vers une autre cellule.

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

Answer 2

En C (contrairement au C++ où c'est peut-être possible, je n'ai pas vérifié), vous ne pouvez pas référencer le typedef que vous créez avec la structure elle-même. Vous devez utiliser le nom de la structure, comme dans le programme de test suivant :

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

Bien que ce soit probablement beaucoup plus compliqué que cela dans la norme, on peut considérer que le compilateur connaît les éléments suivants struct Cell sur la première ligne de la typedef mais sans savoir tCell jusqu'à la dernière ligne :-) C'est ainsi que je me souviens de cette règle.

Answer 3

D'un point de vue théorique, les langues ne peuvent supporter que des structures autoréférentielles et non des structures auto-inclusives.

Answer 4

Il y a une sorte de moyen de contourner ce problème :

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

struct Cell;
typedef struct Cell Cell;

Si vous le déclarez comme cela, cela indique correctement au compilateur que struct Cell et plain-ol'-cell sont les mêmes. Vous pouvez donc utiliser Cell comme d'habitude. Cependant, vous devez toujours utiliser struct Cell dans la déclaration initiale elle-même.

Answer 5

Je sais que ce post est ancien, mais pour obtenir l'effet que vous recherchez, vous pouvez essayer ce qui suit :

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

Dans l'un des deux cas mentionnés dans le fragment de code ci-dessus, vous DEVEZ déclarer votre structure Cell enfant comme un pointeur. Si vous ne le faites pas, vous obtiendrez l'erreur "field 'child' has incomplete type". La raison en est que la "struct Cell" doit être définie pour que le compilateur sache combien d'espace il doit allouer lorsqu'elle est utilisée.

Si vous essayez d'utiliser "struct Cell" à l'intérieur de la définition de "struct Cell", le compilateur ne peut pas encore savoir combien d'espace "struct Cell" est censé prendre. Cependant, le compilateur sait déjà combien d'espace prend un pointeur, et (avec la déclaration forward) il sait que "Cell" est un type de "struct Cell" (bien qu'il ne sache pas encore quelle est la taille d'un "struct Cell"). Le compilateur peut donc définir un "Cell *" dans la structure en cours de définition.