By Ziggy


2009-02-26 00:47:05 8 Comments

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;

9 comments

@paxdiablo 2009-02-26 01:27:11

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.

@rimalonfire 2018-05-10 13:09:15

what about c++ can you please link the answers regarding c++

@paxdiablo 2018-05-10 13:12:20

@rimiro, the question was a C one. If you want the answer for a C++ variant, you should ask it as a question.

@m.eldehairy 2016-12-11 17:28:27

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

@Keynes 2016-05-24 18:43:17

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;

@vineetv2821993 2014-12-23 10:19:30

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 <data_type> <alias>;

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.

@melpomene 2018-02-28 01:38:02

Your explanation of the typedef syntax is incorrect (consider e.g. typedef int (*foo)(void);). Your View 1 and View 2 examples don't work: They make struct Cell an incomplete type, so you can't actually use child in your code.

@Shawn 2012-03-24 01:47:42

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.

@DARSHINI DESAI 2010-10-24 13:10:23

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; // <-self reference
};

@Sundar 2009-07-29 19:13:40

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

@Marsh Ray 2009-07-29 19:23:32

From the practical point of view, how big would such an instance of 'struct Cell' actually be?

@TonyK 2010-09-23 20:28:03

On most machines, four bytes bigger than itself.

@Benjamin Horstman 2009-07-29 19:05:30

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.

@MAKZ 2015-03-08 03:43:06

why did you write struct Cell; again ?

@Tyler Crompton 2015-10-02 22:36:57

@MAKZ because the typedef hasn't been executed by the compiler at the time that it's compiling the definition of struct Cell.

@YoYoYonnY 2016-03-07 19:06:23

@TylerCrompton if the above code block is put into a single C source file, then the typedef has been "executed by the compiler", making the extra struct Cell; redundant. If, however, for some reason you put the last two lines into a header file which you include before you define the Cell struct with the first four lines, then the extra struct Cell; is nececairy.

@Tomáš Zato 2016-11-26 23:03:08

This doesn't even compile under C99 standard.

@melpomene 2018-02-28 01:40:40

@YoYoYonnY No, you can still just write typedef struct Cell Cell; and it will make Cell an alias for struct Cell. It doesn't matter whether the compiler has seen struct Cell { .... } before.

@Andrew Grant 2009-02-26 00:52:27

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;

@fredoverflow 2015-12-30 13:28:44

@cs01 No, Cell is not in scope yet.

@noɥʇʎԀʎzɐɹƆ 2016-06-06 01:06:30

It would make sense. Python allows it and even allows serialization of such an object. Why not C++?

@Tomáš Zato 2016-11-26 23:02:43

I get warnings when I try to assign Cell* to cell->child.

@jazzpi 2017-02-03 15:31:02

@noɥʇʎԀʎzɐɹƆ Because Python abstracts away pointers so that you don't notice them. Since structs in C basically just store all of their values next to each other, it would be impossible to actually store a struct in itself (because that struct would have to contain another one and so on, leading to a memory structure of infinite size).

@wizzwizz4 2017-05-27 13:53:58

For an explanation of the use of struct Cell, see this answer.

Related Questions

Sponsored Content

28 Answered Questions

[SOLVED] When to use struct?

  • 2009-02-06 17:37:55
  • Alex Baranosky
  • 245522 View
  • 1296 Score
  • 28 Answer
  • Tags:   c# struct

24 Answered Questions

[SOLVED] When should you use a class vs a struct in C++?

  • 2008-09-10 16:29:54
  • Alan Hinchcliffe
  • 356246 View
  • 827 Score
  • 24 Answer
  • Tags:   c++ oop class struct ooad

12 Answered Questions

[SOLVED] typedef struct vs struct definitions

  • 2009-11-04 17:21:57
  • user69514
  • 599803 View
  • 703 Score
  • 12 Answer
  • Tags:   c struct typedef

15 Answered Questions

[SOLVED] Why should we typedef a struct so often in C?

  • 2008-10-31 07:14:03
  • Manoj Doubts
  • 464545 View
  • 353 Score
  • 15 Answer
  • Tags:   c struct typedef

11 Answered Questions

[SOLVED] Why isn't sizeof for a struct equal to the sum of sizeof of each member?

8 Answered Questions

[SOLVED] Difference between 'struct' and 'typedef struct' in C++?

  • 2009-03-04 20:41:12
  • criddell
  • 461906 View
  • 758 Score
  • 8 Answer
  • Tags:   c++ struct typedef

2 Answered Questions

[SOLVED] C: Incomplete definition of type struct

  • 2015-05-01 05:31:43
  • 齐天大圣
  • 6197 View
  • 1 Score
  • 2 Answer
  • Tags:   c struct

2 Answered Questions

[SOLVED] typedef struct in header file struct definition in c file

2 Answered Questions

[SOLVED] Issue initialising values for typedef field in struct - C

  • 2013-08-05 21:07:47
  • Racktash
  • 92 View
  • 0 Score
  • 2 Answer
  • Tags:   c struct typedef

2 Answered Questions

Sponsored Content