Suitable data structure?
Adrian Ferramosca
information?
I have a number of generations, the number of which is open-ended.
The first generation has one entry. Each generation can launch 0, 1
or 2 child generations. Therefore the second generation can have 0,
1, 2, 3 or 4 entries. Each of these generations can in turn launch 0,
1 or 2 child generations. Therefore the third generation can contain
anything from 0 to 8 entries. And so on. Each entry is an object of
the same type, say of type Gen. Also I need to be able to quickly get
to a certain element in the tree structure, so there needs to be a
navigational mechanism.
I've been toying with an extension of the linked list idea, which
would probably work, but wondered if there was any better structure
available to do this?
Adrian
Tobias Oed
> What would be a recommended data structure for holding the following
> information?
>
> I have a number of generations, the number of which is open-ended.
> The first generation has one entry. Each generation can launch 0, 1
> or 2 child generations. Therefore the second generation can have 0,
> 1, 2, 3 or 4 entries. Each of these generations can in turn launch 0,
> 1 or 2 child generations. Therefore the third generation can contain
> anything from 0 to 8 entries. And so on. Each entry is an object of
> the same type, say of type Gen. Also I need to be able to quickly get
> to a certain element in the tree structure, so there needs to be a
> navigational mechanism.
What you have is called a binary tree. You could implement your own
starting with something like
struct node{
void *data;
struct node *right;
struct node *left;
};
or use somebody else's implementation. Ben Pfaff's libavl comes to mind, I
don't have the url of his page handy but if you google for libavl and/or
ben pfaff, I'm sure it's one of the first hits.
Tobias.
Ben Pfaff
> What would be a recommended data structure for holding the following
> information?
>
> I have a number of generations, the number of which is open-ended.
> The first generation has one entry. Each generation can launch 0, 1
> or 2 child generations. Therefore the second generation can have 0,
> 1, 2, 3 or 4 entries. Each of these generations can in turn launch 0,
> 1 or 2 child generations. Therefore the third generation can contain
> anything from 0 to 8 entries. And so on. Each entry is an object of
> the same type, say of type Gen. Also I need to be able to quickly get
> to a certain element in the tree structure, so there needs to be a
> navigational mechanism.
A tree?
Ben Pfaff
> Adrian Ferramosca wrote:
>
> > What would be a recommended data structure for holding the following
> > information?
> >
> > I have a number of generations, the number of which is open-ended.
> > The first generation has one entry. Each generation can launch 0, 1
> > or 2 child generations. Therefore the second generation can have 0,
> > 1, 2, 3 or 4 entries. Each of these generations can in turn launch 0,
> > 1 or 2 child generations. Therefore the third generation can contain
> > anything from 0 to 8 entries. And so on. Each entry is an object of
> > the same type, say of type Gen. Also I need to be able to quickly get
> > to a certain element in the tree structure, so there needs to be a
> > navigational mechanism.
>
> What you have is called a binary tree.
Not really. In a binary tree there is a distinction between left
and right subtrees. e.g., in a binary *search* tree the left
subtree contains data values smaller than the root and the right
subtree contains data values larger than the root. But in this
case it sounds like there's no real distinction between a node's
descendants. That's a plain "tree" with at most two-way (binary)
branching, but not a "binary tree" in the usual computer science
meaning of the term.
> Ben Pfaff's libavl comes to mind, I don't have the url of his
> page handy but if you google for libavl and/or ben pfaff, I'm
> sure it's one of the first hits.
libavl implements binary search trees. It enforces BST ordering
rules and limits the maximum height of a BST for efficency. It
will only be useful for dealing with ordered tables, not with
generational structures.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Tobias Oed
> Tobias Oed <tob...@physics.odu.edu> writes:
>
>> Adrian Ferramosca wrote:
>>
>> > What would be a recommended data structure for holding the following
>> > information?
>> >
>> > I have a number of generations, the number of which is open-ended.
>> > The first generation has one entry. Each generation can launch 0, 1
>> > or 2 child generations. Therefore the second generation can have 0,
>> > 1, 2, 3 or 4 entries. Each of these generations can in turn launch 0,
>> > 1 or 2 child generations. Therefore the third generation can contain
>> > anything from 0 to 8 entries. And so on. Each entry is an object of
>> > the same type, say of type Gen. Also I need to be able to quickly get
>> > to a certain element in the tree structure, so there needs to be a
>> > navigational mechanism.
>>
>> What you have is called a binary tree.
>
> Not really. In a binary tree there is a distinction between left
> and right subtrees. e.g., in a binary *search* tree the left
> subtree contains data values smaller than the root and the right
> subtree contains data values larger than the root. But in this
> case it sounds like there's no real distinction between a node's
> descendants. That's a plain "tree" with at most two-way (binary)
> branching, but not a "binary tree" in the usual computer science
> meaning of the term.
Thanks for correcting my poor terminology on this Ben.
Tobias.
Michael Metcalf
"Adrian Ferramosca" <adr...@bjahouston.com> wrote in message
news:204e7041.02022...@posting.google.com...
.
>
> I've been toying with an extension of the linked list idea, which
> would probably work, but wondered if there was any better structure
> available to do this?
>
Explained", which shows a tree for which each node has a name, an arbitrary
number of children and an arbitrary number of siblings. The code can be
downloaded by ftp from ftp.numerical.rl.ac.uk from the directory pub/MandR.
The file name is pointer.f90.
Best of luck,
Mike Metcalf
Adrian Ferramosca
Thanks for the reply, I'll take a look. In the meantime I came up
with something like:
module Generations
type Gen
integer :: Generation ! generation number
integer :: iSib ! index to child in this
generation
integer :: nChildren
type(Gen), pointer :: Child(:) ! pointer to an array of
children which are also Gen objects
type(Gen), pointer :: Parent ! pointer to parent object
end type Gen
type(Gen), pointer :: MyGenerations ! pointer to the first
generation
contains
integer function HowManyChildren()
... and other functions to search, etc
end module Generations
Adrian
Finny Merrill
Ferramosca) wrote:
3 pfaffs for no source code.
5 pfaffs for question completely unrelated to C
1 pfaff for inappropriate cross-post
/*
non-standard pfaff count,
recommend crosspost to c.l.c++ be promoted to 3 pfaffs and a
simple 1 pfaff for "inappropriate cross-posting", i.e.:
- 1 pfaff for inapporpriate cross-posting (for each newsgroup)
3 pfaff bonus for each newsgroup that has something to do with C++
*/
>
>Adrian
--
"Pedants make the best programmers" - Richard Heathfield
"That is probably a misquote, but
I like it nonetheless" - Finny Merrill
Indent-o-meter
01234567
^
CBFalconer
However what he wants is essentially a binary tree, except the
right node is labelled "sibling" and the left is labelled
"descendent". Also look up red-black trees.
--
Chuck F (cbfal...@yahoo.com) (cbfal...@XXXXworldnet.att.net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:u...@ftc.gov (for spambots to harvest)
Ben Pfaff
> Ben Pfaff wrote:
> >
> > Tobias Oed <tob...@physics.odu.edu> writes:
> >
> > > Adrian Ferramosca wrote:
> > >
> > > > I have a number of generations, the number of which is open-ended.
> > > > The first generation has one entry. Each generation can launch 0, 1
> > > > or 2 child generations. Therefore the second generation can have 0,
> > > > 1, 2, 3 or 4 entries. Each of these generations can in turn launch 0,
> > > > 1 or 2 child generations. Therefore the third generation can contain
> > > > anything from 0 to 8 entries. And so on. Each entry is an object of
> > > > the same type, say of type Gen. Also I need to be able to quickly get
> > > > to a certain element in the tree structure, so there needs to be a
> > > > navigational mechanism.
> > >
> > > What you have is called a binary tree.
> >
> > Not really. In a binary tree there is a distinction between left
> > and right subtrees.
>
> However what he wants is essentially a binary tree, except the
> right node is labelled "sibling" and the left is labelled
> "descendent". Also look up red-black trees.
What he wants is a tree. One way to implement a tree is by way
of a binary tree. There are easier ways to do it, especially for
the case that he's got where there's at most two-way branching at
each node. Red-black trees will not help, because they are
binary *search* trees and will rearrange and mangle his data in
exciting new ways as he adds node.
Here's a hierarchy:
1. Trees
1.1. Trees that branch at most n ways at each node
2. Binary trees
2.1. Binary search trees
2.1.1. Red-black trees
A RB tree is a BST; a BST is a binary tree. But a binary tree is
not a tree, and neither is a red-black tree.
--
"This is a wonderful answer. It's off-topic, it's incorrect, and
it doesn't answer the question." --Richard Heathfield
Arjen Markus
What about a heap? This resembles a tree in a way, but it is more
organised like a set of generations. I know one particularly nice
description: on Libes, "Obfuscated C and other mysteries"
Do not let the title scare (nor the intentionally horrible pieces
of C that are abundantly decribed). The chapter on heap searching
is very nice indeed.
You can implement a heap as an array indexed like:
1, 1+1--1+2, 1+2+1--1+2+4, 1+2+4+1--1+2+4+8, ...
well, you get the drift.
Regards,
Arjen
Kamilche
> What would be a recommended data structure for holding the following
> information?
>
I have a similar need, and I toying with the idea of a single hash
table in memory containing all the items in the hierarchical data
structure. Each entry would be assigned a unique ID in the table, have
a field to point to its parent, point to all its children, and include
the data structure next. I made it in VB about 6 months ago, it seemed
to work slick. Now that I'm learning C, the obvious next step is to
reprogram it using C.
It took me about a week of head banging and heavy thinking to come up
with this. I need an easy way to store it and send it across the
network, and many relationships are difficult to express in 'tcp' or
on disk, as opposed to in memory. But this fills the need quite
nicely.
After shoving through that design barrier, I discovered that if I had
known the first thing in XML, it was almost the same as an XML
hierarchical recordset, with the addition of one field - the parent
field. :-P Oh well, you live and learn.