self referential struct definition

Question

I haven t been writing C for very long  and so I m not sure about how I should go about doing these sorts of recursive things    I would like each cell to contain another cell  but I get an error along the lines of  field  child  has incomplete type   What s up   typedef struct Cell     int isParent    Cell child    Cell

User · Accepted Answer

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;

User · Answer

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

User · Answer

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

User · Answer

A Structure which contain a reference to itself  A common occurrence of this in a structure which describes a node for a link list  Each node needs a reference to the next node in the chain   struct node          int data         struct node  next      lt -self reference

User · Answer

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

User · Answer

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  lt stdio h gt   include  lt stdlib h gt   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- gt cellSeq   100      first- gt next   NULL      for  i   0  i  lt  20  i              curr   malloc  sizeof  tCell            curr- gt cellSeq   last- gt cellSeq - 1          curr- gt next   NULL          last- gt next   curr          last   curr                Walk the list  printing sequence numbers          curr   first      while  curr    NULL            printf   Sequence    d n   curr- gt cellSeq           curr   curr- gt 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

User · Answer

Lets go through basic definition of typedef  typedef use to define an alias to an existing data type either it is user defined or inbuilt   typedef  lt data type gt   lt alias gt     for example  typedef int scores   scores team1   99    Confusion here is with the self referential structure  due to a member of same data type which is not define earlier  So In standard way you can write your code as  -    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    But last option increase some extra lines and words with usually we don t want to do  we are so lazy you know        So prefer View 2

User · Answer

All previous answers are great   i just thought to give an insight on why a structure can t contain an instance of its own type  not a reference    its very important to note that structures are  value  types i e they contain the actual value  so when you declare a structure the compiler has to decide how much memory to allocate to an instance of it  so it goes through all its members and adds up their memory to figure out the over all memory of the struct  but if the compiler found an instance of the same struct inside then this is a paradox  i e in order to know how much memory struct A takes you have to decide how much memory struct A takes      But reference types are different  if a struct  A  contains a  reference  to an instance of its own type  although we don t know yet how much memory is allocated to it  we know how much memory is allocated to a memory address  i e the reference    HTH

User · Answer

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

[c] self referential struct definition?

Examples related to c

Examples related to recursion

Examples related to struct

Examples related to typedef