self referential struct definition?

Question

Clearly a Cell cannot contain another Cell as it becomes a never-ending recursion.

However a Cell CAN contain a pointer to another Cell.

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

In C, you cannot reference the typedef that you're creating withing the structure itself. You have to use the structure name, as in the following test program:

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

Although it's probably a lot more complicated than this in the standard, you can think of it as the compiler knowing about struct Cell on the first line of the typedef but not knowing about tCell until the last line :-) That's how I remember that rule.

From the theoretical point of view, Languages can only support self-referential structures not self-inclusive structures.

There is sort of a way around this:

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

struct Cell;
typedef struct Cell Cell;

If you declare it like this, it properly tells the compiler that struct Cell and plain-ol'-cell are the same. So you can use Cell just like normal. Still have to use struct Cell inside of the initial declaration itself though.

I know this post is old, however, to get the effect you are looking for, you may want to try the following:

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

In either of the two cases mentioned in the code fragment above, you MUST declare your child Cell structure as a pointer. If you do not, then you will get the "field 'child' has incomplete type" error. The reason is that "struct Cell" must be defined in order for the compiler to know how much space to allocate when it is used.

If you attempt to use "struct Cell" inside the definition of "struct Cell", then the compiler cannot yet know how much space "struct Cell" is supposed to take. However, the compiler already knows how much space a pointer takes, and (with the forward declaration) it knows that "Cell" is a type of "struct Cell" (although it doesn't yet know how big a "struct Cell" is). So, the compiler can define a "Cell *" within the struct that is being defined.

Another convenient method is to pre-typedef the structure with,structure tag as:

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