rmandel@grad1.cis.upenn.edu (03/16/90)
I'm kind of new to C, and have a problem which is probably obvious to any connoisseur: How do you declare a linked list or binary tree type? The following obvoiusly doesn't work because of the forward reference to 'node': typedef struct { int label; node *fwd; } node; I managed to 'trick' the compiler (I'm using TC2.0) by making "fwd" be a pointer to an int, but then USING it in the above sense. I don't like this, though --- how do you do it ELEGANTLY? Also, another problem arises when I insert something in a (similarly defined) binary tree: Say I want to insert the value FOO into the tree defined as typedef struct { int label; int *left, *right; } btree; and say, bt is defined as btree *bt, Now to insert FOO, I pass in the value FOO as well as the binary tree where it must go: insert (FOO, bt); where "insert" is defined as void insert (int val, btree *bt) { if (bt == NULL) { bt = (btree *) malloc (sizeof(btree)); bt -> label = val; bt -> left = bt -> right = NULL; } else if (val < bt -> label) insert (val, bt -> left); else insert (val, bt -> right); } Th problem is that because 'bt' is the actual value passed to each recursive call to 'insert', it is put on the stack, and discarded when we 'bubble up' through the recursion! I was thinking of passing a pointer to a pointer to a btree, but this is even more kludgy and incomprehensible than my first problem! What am I doing wrong? How do you do this? Any help/code fragments would be GREATLY appreciated. Thanks, -Robbie Mandelbaum
apippin@polyslo.CalPoly.EDU (Pinhead@Spikes) (03/16/90)
Add then rmandel@grad1.cis.upenn.edu () babbles...
~How do you declare a linked list or binary tree type?
Try:
typedef struct _node nodeptr;
struct _node {
int i;
nodeptr right;
nodeptr left;
}
This works on a Sun 3, Pyramid and Macintoys.
aBp.
--
Andy Pippin -*- apippin@polyslo.CalPoly.EDU -*- Conserve water, drink bier.
chris@mimsy.umd.edu (Chris Torek) (03/16/90)
The first thing to do is forget about typedef (until later, after you declare the data structures at least): struct btree { int value; struct btree *left; struct btree *right; }; Later (actually, after typing this much) you can go back and add the typedef: typedef struct btree { int value; struct btree *left; struct btree *right; } btree; The key to getting forward pointer declarations is using the `struct' style declarations. The typedef name does not exist when you need it, but the keyword `struct' allows undefined and partially define names after it, provided that the thing being declared is a pointer: struct a { int aval; struct b *bp; }; struct b { int bval; struct a *ap; }; Without allowing forward (partial) declarations, there would be no way to write structures a and b above. Note that if there *is* a `struct b' around before the `struct a' declaration, the `bp' field in `struct a' will point to the *wrong* struct b. That is: struct b { int some_int; }; void function() { struct a { int aval; struct b *bp; } a; struct b { int bval; struct a *ap; } b; <...code...> } Now `a.bp' points to a `struct b' that has one `some_int' field, rather than one `bval' field and one `struct a *' field. The solution is to add a partial declaration for struct b ahead of the one for struct a: void function() { struct b; /* tell compiler there is a new one coming up */ struct a { int aval; struct b *bp; } a; struct b { int bval; struct a *ap; } b; <...code...> } This time `a.bp' points to the new `struct b' instead of the old one. As for your binary tree implementation: I would likely use pointers to pointers, but then I write declarations like int (*(*bloog[10])(char *, void (*)(int, int (*)(void))))[4]; without flinching. :-) Chris -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@cs.umd.edu Path: uunet!mimsy!chris
frotz@drivax.UUCP (Frotz) (03/17/90)
rmandel@grad1.cis.upenn.edu writes: ] I'm kind of new to C, and have a problem which is probably obvious ] to any connoisseur: ] How do you declare a linked list or binary tree type? Try: typedef struct _node_ /* where _node_ is the struct "tag" */ { int value; struct _node_* left; /* The compiler knows about "tag" */ struct _node_* right; /* It doesn't know about "node" yet. */ } node; ] Th problem is that because 'bt' is the actual value passed to each ] recursive call to 'insert', it is put on the stack, and discarded ] when we 'bubble up' through the recursion! Try always returning the tree root. You may or may not be interested in the return value within the routine. If you do, you can add logic to try to balance the tree and thereby pass the new tree root up to the caller. If, however, you ignore the return value internally your tree may become imbalanced. e.g. node* insert( node* root, value ); --Frotz @Digital Research, Incorporated amdahl!drivax!frotz Graphics Business Unit (408) 647-6570 (msg) 70 Garden Court, B15 (408) 649-3896 Monterey, California 93940 Ask for John Fa'atuai
karl@haddock.ima.isc.com (Karl Heuer) (03/22/90)
In article <1990Mar16.112415.803@hellgate.utah.edu> kbreinho%ug.utah.edu@cs.utah.edu (Keith Breinholt) writes: >In article <23127@mimsy.umd.edu> chris@mimsy.umd.edu (Chris Torek) writes: >>As for your binary tree implementation: I would likely use pointers to >>pointers, but then I write declarations like >> int (*(*bloog[10])(char *, void (*)(int, int (*)(void))))[4]; >>without flinching. :-) > >... Do you really think someone would want to [maintain] crap like that? Actually, I have to agree. Since a pointer-to-entire-array is so much weaker than a pointer-to-element, I would assume that the existence of even a single function returning such a type (not to mention an array of pointers to such functions) is evidence that, in this project, "int[4]" is an important construct and should probably have had its own typedef. Of course, that has to have been an exaggerated example--did you miss the smiley? A more serious example would be extern void (*signal(int, void (*)(int)))(int); , which is probably the most complex declaration you'd encounter in practice. Though I personally don't bother with "typedef void (*sighandler_t)(int)", I don't look down on those who do. But for the original problem, a pointer-to-pointer seems to be the natural solution, and anybody who can't understand such a construct needs to practice a bit more before trying to write production-quality code. Karl W. Z. Heuer (karl@ima.ima.isc.com or harvard!ima!karl), The Walking Lint
news@awdprime.UUCP (USENET News) (03/23/90)
In article <25fff2a9.36f0@polyslo.CalPoly.EDU> apippin@polyslo.CalPoly.EDU (Pinhead@Spikes) writes: -Add then rmandel@grad1.cis.upenn.edu () babbles... ->How do you declare a linked list or binary tree type? -Try: - - typedef struct _node nodeptr; - struct _node { - int i; - nodeptr right; - nodeptr left; - } Lest we confuse the masses, I think that should have read: typedef struct _node *nodeptr; ^ | NOTE THE *. We thank you for your support, -- sanders For every message of the day, a new improved message will arise to overcome it. Reply-To: cs.utexas.edu!ibmaus!auschs!sanders.austin.ibm.com!sanders (ugh!)
erlkonig@walt.cc.utexas.edu (Christopher North-Keys) (03/29/90)
(line "#" is corrected as per the first followup)
-Add then rmandel@grad1.cis.upenn.edu () babbles...
->How do you declare a linked list or binary tree type?
-Try:
-
# typedef struct _node *nodeptr;
- struct _node {
- int i;
- nodeptr right;
- nodeptr left;
- }
Try:
typedef struct _node {
int i;
struct _node *left;
struct _node *right;
} *nodeptr;
------------------------------------/\----------------------------------------
Seo: Harp[@Mcc.Com] / \/\ ^*^ Christopher North-Keys
Tha mi gu trang a'cluich. / \ \ Assoc. Systems Analyst, MCC
--------------------------------(disclaimer)----------------------------------