tree data structure: incomplete type error

Discussion in 'C Programming' started by xuthee, Jul 18, 2007.

  1. xuthee

    xuthee Guest

    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
    xuthee, Jul 18, 2007
    #1
    1. Advertising

  2. xuthee <> writes:

    > 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".

    --
    Ben.
    Ben Bacarisse, Jul 19, 2007
    #2
    1. Advertising

  3. xuthee

    xuthee Guest

    On Thu, 19 Jul 2007 10:32:50 +0100, Ben Bacarisse wrote:

    >> 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.

    >> #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).


    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
    xuthee, Jul 19, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Eric Smith

    structure containing incomplete array type

    Eric Smith, Apr 9, 2004, in forum: C Programming
    Replies:
    6
    Views:
    3,428
    Kevin Bracey
    Apr 13, 2004
  2. gk245
    Replies:
    2
    Views:
    1,199
    Christopher Benson-Manica
    May 6, 2006
  3. sharan
    Replies:
    4
    Views:
    689
    CBFalconer
    Oct 30, 2007
  4. sharan
    Replies:
    2
    Views:
    829
    SM Ryan
    Oct 31, 2007
  5. sharan
    Replies:
    1
    Views:
    688
    CBFalconer
    Oct 30, 2007
Loading...

Share This Page