tree data structure: incomplete type error

[xuthee]

Hi Group,

I want to set up a tree data structure. Each tree node is supposed to
store a number of links to its children. I'd like to utilize linked
list
to store pointers to node's children.

Unfortunately I'm having problems allocating code into headers and
implementation files. Compilation fails with the following:

$ gcc -Wall tree.c list.c main.c
tree.c:9: error: field 'ChildrenList' has incomplete type
main.c: In function 'main':
main.c:5: error: storage size of 'tree' isn't known
main.c:5: warning: unused variable 'tree'

Any hint will be appreciated.

....and the source code is:

--- main.c ---

#include "tree.h"

int main(int argc, char *argv[])
{
struct TreeNode tree;

return 0;
}


--- list.h ---

#ifndef __LIST_H__
#define __LIST_H__

struct ListNode;

#endif // __LIST_H__


--- list.c ---

#include "list.h"
#include "tree.h"

typedef struct TreeNode *ListElement;

struct ListNode
{
ListElement Element;
struct ListNode *Next;
};


--- tree.h ---

#ifndef __TREE_H__
#define __TREE_H__

struct TreeNode;

#endif // __TREE_H__


--- tree.c ---

#include "tree.h"
#include "list.h"

typedef int TreeElement; // stub

struct TreeNode
{
TreeElement Element;
struct ListNode ChildrenList;
};

Cheers,
xuthee

 

[Ben Bacarisse]

Hi Group,

I want to set up a tree data structure. Each tree node is supposed to
store a number of links to its children. I'd like to utilize linked
list
to store pointers to node's children.

Unfortunately I'm having problems allocating code into headers and
implementation files. Compilation fails with the following:

$ gcc -Wall tree.c list.c main.c
tree.c:9: error: field 'ChildrenList' has incomplete type

Are you asking what an "incomplete type" is? To a first approximation
it means "I know ChildrenList is a structure, but not enough about it
to actually make one".

You probably want

struct ListNode *ChildrenList;

in tree.c but that is only a guess.

main.c: In function 'main':
main.c:5: error: storage size of 'tree' isn't known

and here the compiler is saying much the same thing. All it knows
about 'tree' is that it should be a 'struct TreeNode' and all it has
seen about that is:

struct TreeNode;

from tree.h. Not much for it to go on. Unless the compiler has seen
a full definition of a structure, you will not be able to declare
a variable of that type. You can declare pointers to structures of as
yet incomplete types, but that is all -- you won't be ale to do
anything with them except pass them about.[1]

#ifndef __LIST_H__
#define __LIST_H__

All these names are not yours to use (they are "in the
implementation's name space"). A better convention is H_LIST. The H_
comes first so you don't run into problems with files whose names
start with an 'e' (macros names that start E... are also reserved for
the implementation).

[1] This is not bad in itself. It is how one hides the implementation
of a type in C. See the recent threads on "encapsulation".

 

[xuthee]

I want to set up a tree data structure. Each tree node is supposed to
store a number of links to its children. I'd like to utilize linked
list
to store pointers to node's children.

[...]

You probably want

struct ListNode *ChildrenList;

in tree.c but that is only a guess.

[...]

a variable of that type. You can declare pointers to structures of as
yet incomplete types, but that is all -- you won't be ale to do
anything with them except pass them about.[1]

Yeah, I think I should read some more about encapsulation in C. It in
fact might be a better idea to store just pointers to structures.

All these names are not yours to use (they are "in the
implementation's name space"). A better convention is H_LIST. The H_
comes first so you don't run into problems with files whose names
start with an 'e' (macros names that start E... are also reserved for
the implementation).

I have spotted this convention somewhere, some time ago and just picked it
up. However, your approach seems to be reasonable. Will think about this.

Thanks Ben!

Cheers,
xuthee