NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/lang/c/12231

Text File | 1992-08-12 | 3.4 KB | 75 lines

Newsgroups: comp.lang.c
Path: sparky!uunet!mcsun!sunic!ugle.unit.no!sigyn.idt.unit.no!bjornmu
From: [e-mail] (Bj|rn P. Munch)
Subject: Re: general tree
Message-ID: <[e-mail]>
Sender: [e-mail] (NetNews Administrator)
Reply-To: [e-mail] (Bj|rn P. Munch)
Organization: Div. of CS & Telematics, Norwegian Institute of Technology
References: <[e-mail]> <chuckb.713584418@milton> <[e-mail]> <[e-mail]>
Date: Wed, 12 Aug 92 19:25:29 GMT
Lines: 62

In article <[e-mail]>, [e-mail] (Qual Trak) writes:
|> In article <[e-mail]> [e-mail] (Bj|rn P. Munch) writes:
|> >In article <chuckb.713584418@milton>, [e-mail] (Chuck Bass) writes:
|> >|> [e-mail] (Bj|rn P. Munch) writes:
|> >|>
|> >|> >In article <[e-mail]>, [e-mail] (David Mikesell) writes:
|> >|> >|>
|> >|> >|> I am beginning work on a C program that will manipulate a general tree, i.e.
|> >|> >|> a tree in which each node can have an arbitrary number of children.  An ex-
|> >|> >|> ample declaration of the structure follows:
|> >|> >|>
|> >|> >|> struct node
|> >|> >|> {
|> >|> >|>     DATA        data;
|> >|> >|>     struct node *parent;
|> >|> >|>     struct node **children;
|> >|> >|> };
|> >|>
|> >|> >In stead of putting the children into an array (what do you do if this
|> >|> >array suddenly isn't big enough?), you may consider putting them in a
|> >|> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|> >|> This is a perfect time to use something like ... realloc.
|> >
|> >I also thought about realloc(), but soon realized this would be a
|> >rather bad idea.  Maybe I should have explained why...
|> >
|> >Remember: realloc() may move your array to another address.  If you
|> >have references to the children that were stored there (like parent
|> >pointers in _their_ children), then you're in deep trouble.
|> >
|>
|> Seems to me realloc () will work quite adequately if you reference the
|> children pointer explicitly thru the node - i.e.
|>     struct node *nodeptr, (nodeptr1;
|>
|>     nodeptr1 = nodeptr->children [0];
|>
|> Will always return you the same value even if nodeptr->children has been
|> realloced ();

Oops, my mistake.  "children" is an array of _pointers_ to nodes, so of
course it doesn't matter if they are moved by realloc().  The nodes
themselves do not move and the pointers are still valid.....

I still like the sibling list, though.  You may need one more pointer
dereferencing to get at each child, but you save the address
calculation needed for indexing.  Of course, if you often need to get
directly at child number N > 1, the array is far more efficient.

And if you look carefully, you will see that the array soultion
actually requires more space.  Both use three pointer per node, but
you may have more malloc() fragments, plus you need to store # of
children.

Well, I guess the most important factor is how this tree is going to
be used.  Either approach would be best in some cases.

---
Bj|rn P. Munch               | Dept. of Comp. Science & Telematics,
[e-mail]   | Norwegian Institute of Technology (NTH),
PhD Student                  | N-7034 Trondheim, Norway
 (some filler words here)    | Fingerable addr:  [e-mail]