Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Tree implementation, ideas for keyboard input method needed (http://www.velocityreviews.com/forums/t808106-tree-implementation-ideas-for-keyboard-input-method-needed.html)

Bubba 01-16-2012 10:01 PM

Tree implementation, ideas for keyboard input method needed
 
Greetings,

nodes of my ordered tree are implemented like this:

typedef struct __celltype {
labeltype label;
struct __celltype *first_child;
struct __celltype *next_sib;
struct __celltype *last_child;
int zadnji;
} celltype;
typedef celltype *node;
typedef celltype *TREE;

where first_child points to first sibling of the node, next_sib points to
next sibling and last_child points to last sibling in the node. Data
zadnji is true if the node is last child of any other node.

Labeltype is char.

Here's the whole implementation:

#include <stdlib.h>
#include <stdio.h>
#define LAMBDA NULL
#define labeltype char

typedef struct __celltype {
labeltype label;
struct __celltype *first_child;
struct __celltype *next_sib;
struct __celltype *last_child;
int zadnji; /*last*/
} celltype;

typedef celltype *node;
typedef celltype *TREE;

node MAKE_ROOT(labeltype l, TREE *T) {
if (!(*T = (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
(*T)->label=l;
(*T)->first_child=NULL;
(*T)->next_sib=NULL;
(*T)->last_child=NULL;
(*T)->zadnji=0;
return *T;
}

node INSERT_CHILD(labeltype l, node i, TREE *T){
node temp;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
if (!(i->first_child= (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
if (i->first_child==NULL) {
i->first_child->label=l;
i->first_child->first_child=NULL;
i->first_child->next_sib=NULL;
i->first_child->last_child=NULL;
i->first_child->zadnji=1;
}
if (i->first_child!=NULL) {
temp=i->first_child;
i->first_child->label=l;
i->first_child->first_child=NULL;
i->first_child->next_sib=temp;
i->first_child->last_child=NULL;
i->first_child->zadnji=0;
}
return i->first_child;
}

node ROOT(TREE T){
return T;
}

node INSERT_SIBLING(labeltype l, node i, TREE *T){
node temp;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
if (!(i->next_sib= (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
if (i==ROOT(*T)) {
printf("Taj cvor je korijen.");
exit(1);
}
if(i->zadnji==1){
i->zadnji=0;
i->next_sib->label=l;
i->next_sib->first_child=NULL;
i->next_sib->next_sib=NULL;
i->next_sib->last_child=NULL;
i->next_sib->zadnji=1;
}
if(i->zadnji==0){
temp=i->next_sib;
i->next_sib->label=l;
i->next_sib->first_child=NULL;
i->next_sib->next_sib=temp;
i->next_sib->last_child=NULL;
i->next_sib->zadnji=0;
}
return i->next_sib;
}

node PARENT(node i,TREE T){
node c, d;
if (i==ROOT(T)) return LAMBDA;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
for (c=T->first_child; c!=NULL; c=c->next_sib)
if (c==i) return T;
for (c=T->first_child; c!=NULL; c=c->next_sib){
d=PARENT(i,c);
if (d!=NULL) return d;
}
return NULL;
}

void DELETE(node i, TREE *T) {
node c,d,e,f,temp;
if (i==ROOT(*T)) {
printf("Taj cvor je korijen."); /*is root*/
exit(1);
}
if (!i) {
printf("Nema tog cvora."); /*no node*/
exit(1);
}
if (i->first_child!=NULL) {
printf("Taj cvor ima djece."); /*has sib*/
exit(1);
}
c=PARENT(i,*T);
if (c->first_child==c->last_child) {
free(i);
c->first_child=NULL;
c->last_child=NULL;
}
if (i==c->first_child) {
temp=i->next_sib;
free(i);
c->first_child=temp;
}
if(i==c->last_child) {
d=c->first_child;
while(d!=c->last_child) {
if (d->next_sib==i) {
d->next_sib=NULL;
d->zadnji=1;
break;
}
d=d->next_sib;
}
free(i);
c->last_child=d;
}
if ((i!=c->first_child) && (i!=c->last_child)){

for (d=c->first_child; d!=NULL; d=d->next_sib){
if(d->next_sib==i) e=d;
if(i->next_sib==d) f=d;
}
free(i);
e->next_sib=f;
}
}

node FIRST_CHILD(node i, TREE T){
if (i->first_child==NULL) return NULL;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->first_child;
}

node NEXT_SIBLING(node i, TREE T){
if (i->next_sib==NULL) return NULL;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->next_sib;
}

labeltype LABEL(node i, TREE T) {
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->label;
}

void CHANGE_LABEL(labeltype l, node i, TREE *T){
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
i->label=l;
}

void POSTORDER(node i, TREE T) {
node c;
for(c=FIRST_CHILD(i,T); c!=LAMBDA; c=NEXT_SIBLING(c,T))
POSTORDER(c,T);
printf("%c ", LABEL(i,T));
}


int main(void)
{
return 0;
}



Now I need a sane way to input a tree from keyboard. What would be the
easiest one?

Thanks in advance!

--
"If you lie to the compiler,
it will get its revenge."
Henry Spencer
2.718281828459045235360287471352662497757247093699 959574966967627.com

Keith Thompson 01-16-2012 10:27 PM

Re: Tree implementation, ideas for keyboard input method needed
 
Bubba <nickname@banelli.biz.invalid> writes:

Just so you know, I'm not going to address your actual question, at
least for now. I do have some comments on your coding style.

> nodes of my ordered tree are implemented like this:
>
> typedef struct __celltype {
> labeltype label;
> struct __celltype *first_child;
> struct __celltype *next_sib;
> struct __celltype *last_child;
> int zadnji;
> } celltype;


Identifiers starting with underscores are reserved to the implementation
in most contexts. Identifiers starting with two underscores are
reserved in all contexts. You should never define such identifiers
yourself (unless you're writing code for a C compiler or library
implementation).

It's not necessary to use a typedef for a struct type. You could just
declare it as:

struct celltype {
...
};

and simply refer to it as "struct celltype". If you feel the need to
have a one-word name for the type, there's no need to use different
identifiers for the tag and typedef:

typedef struct celltype {
...
} celltype;

> typedef celltype *node;
> typedef celltype *TREE;


Typedefs for pointer types are generally a bad idea. The problem is
that they hide the fact that the type is a pointer. That's ok if it's a
truly opaque type, meaning that client code will not use any pointer
operations on it.

And logically, a pointer to a "celltype" isn't a node; it points to a node.

[...]
> node MAKE_ROOT(labeltype l, TREE *T) {


All-caps names are conventionally used for macros. It's better style
to call the function "make_root".

And in fact I'd declare this as:

struct celltype *make_root(labeltype label, struct celltype **t);

Note that "l" is a poor identifier; it's too easily confused with the
digit "1".

> if (!(*T = (celltype*) malloc(sizeof(celltype)))) {


The cast is unnecessary, and could be harmful (in certain circumstances,
it can inhibit important warnings). malloc() returns a void* result,
which can be implicitly converted to any pointer type (other than a
pointer-to-function type).

A good idiom is:

if ((*T = malloc(sizeof **T) != NULL) {

> printf("Nema dovoljno memorije.");


Error mesages should be printed to stderr and terminated with "\n".

> exit(1);


exit(1) doesn't necessarily indicate failure. Use exit(EXIT_FAILURE)
instead.

[...]

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Ben Bacarisse 01-16-2012 10:29 PM

Re: Tree implementation, ideas for keyboard input method needed
 
Bubba <nickname@banelli.biz.invalid> writes:

> Greetings,
>
> nodes of my ordered tree are implemented like this:
>
> typedef struct __celltype {


__celltype is a reserved name. celltype__ would be fine but then so
would celltype.

> labeltype label;
> struct __celltype *first_child;
> struct __celltype *next_sib;
> struct __celltype *last_child;
> int zadnji;
> } celltype;
> typedef celltype *node;
> typedef celltype *TREE;
>
> where first_child points to first sibling of the node, next_sib points to
> next sibling and last_child points to last sibling in the node. Data
> zadnji is true if the node is last child of any other node.
>
> Labeltype is char.
>
> Here's the whole implementation:
>
> #include <stdlib.h>
> #include <stdio.h>
> #define LAMBDA NULL
> #define labeltype char
>
> typedef struct __celltype {
> labeltype label;
> struct __celltype *first_child;
> struct __celltype *next_sib;
> struct __celltype *last_child;
> int zadnji; /*last*/
> } celltype;
>
> typedef celltype *node;
> typedef celltype *TREE;
>
> node MAKE_ROOT(labeltype l, TREE *T) {
> if (!(*T = (celltype*) malloc(sizeof(celltype)))) {


What's the cast for? I'd write:

if ((*T = malloc(sizeof **T)) == NULL)

That way you know, at first glance, that the size is correct.

> printf("Nema dovoljno memorije.");
> exit(1);
> }


This code (allocate or fail with a message) is repeated lots of times.
Is a clear candidate for being a function.

> (*T)->label=l;
> (*T)->first_child=NULL;
> (*T)->next_sib=NULL;
> (*T)->last_child=NULL;
> (*T)->zadnji=0;
> return *T;
> }
>
> node INSERT_CHILD(labeltype l, node i, TREE *T){


You are using an uncommon naming convention (uppercase function names)
and unusual layout. Is there are a reason for this?

> node temp;
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> if (!(i->first_child= (celltype*) malloc(sizeof(celltype)))) {
> printf("Nema dovoljno memorije.");
> exit(1);
> }
> if (i->first_child==NULL) {
> i->first_child->label=l;


This is obviously wrong. If i->first_child == NULL, you can't talk
about i->first_child->label.

> i->first_child->first_child=NULL;
> i->first_child->next_sib=NULL;
> i->first_child->last_child=NULL;
> i->first_child->zadnji=1;
> }
> if (i->first_child!=NULL) {


"else"?

> temp=i->first_child;
> i->first_child->label=l;
> i->first_child->first_child=NULL;
> i->first_child->next_sib=temp;
> i->first_child->last_child=NULL;
> i->first_child->zadnji=0;
> }
> return i->first_child;
> }


The lack of spaces and the confusion caused by using tabs is making this
hard to read so I'll stop here.

<snip code>

> Now I need a sane way to input a tree from keyboard. What would be the
> easiest one?


I'd use parentheses:

(a b c)
(a (x (u v) z))

If you need to indicate "next_sib", use some
marker character:

(a b* c)

--
Ben.

Bubba 01-16-2012 10:36 PM

Re: Tree implementation, ideas for keyboard input method needed
 
Keith Thompson's log on stardate 16 sij 2012

I hoped for something like this in the first place, so thank you in
advance!

> Identifiers starting with underscores are reserved to the
> implementation in most contexts. Identifiers starting with two
> underscores are reserved in all contexts. You should never define
> such identifiers yourself (unless you're writing code for a C
> compiler or library implementation).


What are the repercussions of choosing wrong number of underscores? :)

>> node MAKE_ROOT(labeltype l, TREE *T) {

>
> All-caps names are conventionally used for macros. It's better style
> to call the function "make_root".


I'm aware of that, thanks, it will be corrected.

> And in fact I'd declare this as:
> struct celltype *make_root(labeltype label, struct celltype **t);


Could you please clarify the need for double pointer?

> Note that "l" is a poor identifier; it's too easily confused with the
> digit "1".


True again!

>> if (!(*T = (celltype*) malloc(sizeof(celltype)))) {

> The cast is unnecessary, and could be harmful (in certain
> circumstances, it can inhibit important warnings). malloc() returns
> a void* result, which can be implicitly converted to any pointer type
> (other than a pointer-to-function type).


I read some posts here about malloc's (non)casting. I'll do as you
suggested.

> A good idiom is:
> if ((*T = malloc(sizeof **T) != NULL) {


Ok.

>> printf("Nema dovoljno memorije.");

> Error mesages should be printed to stderr and terminated with "\n".
>> exit(1);

> exit(1) doesn't necessarily indicate failure. Use exit(EXIT_FAILURE)
> instead.


Thanks, I'll apply those too!

--
"If you lie to the compiler,
it will get its revenge."
Henry Spencer
2.718281828459045235360287471352662497757247093699 959574966967627.com

Bubba 01-16-2012 10:38 PM

Re: Tree implementation, ideas for keyboard input method needed
 
Ben Bacarisse's log on stardate 16 sij 2012

> The lack of spaces and the confusion caused by using tabs is making this
> hard to read so I'll stop here.


Wow, this went wrong - I agree; I'll procede as you Keith suggested and
report back with sorted out code!

Thanks!

--
"If you lie to the compiler,
it will get its revenge."
Henry Spencer
2.718281828459045235360287471352662497757247093699 959574966967627.com

Kaz Kylheku 01-16-2012 10:44 PM

Re: Tree implementation, ideas for keyboard input method needed
 
On 2012-01-16, Bubba <nickname@banelli.biz.invalid> wrote:
> #define LAMBDA NULL


While this is a valiant effort, I recommend nothing less than:

#define PASTE(X, Y) X ## Y
#define XPASTE(X, Y) PASTE(X, Y)
#define MKTOKEN(A, B, C, D) XPASTE(XPASTE(A, B), XPASTE(C, D))
#define LAMBDA MKTOKEN(N, U, L, L)

Now you've REALLY defined a useless synonym for a useless synonym for zero,
in style!

Also, don't foget:

/* right-associatively-pasted lambda */
#define R_MKTOKEN(A, B, C, D) XPASTE(A, XPASTE(B, XPASTE(C, D)))
#define R_LAMBDA R_MKTOKEN(N, U, L, L)

/* left-associatively-pasted lambda */
#define L_MKTOKEN(A, B, C, D) XPASTE(XPASTE(XPASTE(A, B), C), D)
#define L_LAMBDA L_MKTOKEN(N, U, L, L)

Benchmark all three to see which LAMBDA null pointer constant runs faster!

Kaz Kylheku 01-16-2012 10:53 PM

Re: Tree implementation, ideas for keyboard input method needed
 
On 2012-01-16, Bubba <nickname@banelli.biz.invalid> wrote:
> Keith Thompson's log on stardate 16 sij 2012
>
> I hoped for something like this in the first place, so thank you in
> advance!
>
>> Identifiers starting with underscores are reserved to the
>> implementation in most contexts. Identifiers starting with two
>> underscores are reserved in all contexts. You should never define
>> such identifiers yourself (unless you're writing code for a C
>> compiler or library implementation).

>
> What are the repercussions of choosing wrong number of underscores? :)


The repercussions are that any of your compiler or library headers are
completely free to have things like this in them:

#define __celltype blorch[

This namespace does not belong to you, but to the implementors.

(Since C doesn't have namespaces, we have to draw these borders within the
identifiers themselves.)

Even if you haven no clash now with __celltype, you could have one tomorrow,
when you include some header that you did not previously include, port your
program to a different system, or upgrade (or downgrade) to a different version
of the compiler or any of your libraries, etc.

Eric Sosman 01-16-2012 10:58 PM

Re: Tree implementation, ideas for keyboard input method needed
 
On 1/16/2012 5:01 PM, Bubba wrote:
> Greetings,
>
> nodes of my ordered tree are implemented like this:
>
> typedef struct __celltype {


A minor point: `__celltype' is a reserved identifier, and if
the implementation decides to use the identifier for its own
purposes (which it's at liberty to do without warning you), chaos
is likely to ensue. Use an identifier from the name space belonging
to the programmer -- `celltype' is fine, yes, even though you're also
going to use `celltype' as a typedef alias for `struct celltype'.

> labeltype label;
> struct __celltype *first_child;
> struct __celltype *next_sib;
> struct __celltype *last_child;
> int zadnji;
> } celltype;
> typedef celltype *node;
> typedef celltype *TREE;


Another minor point: It's been my experience that typedef aliases
for pointer types usually cause confusion. "Usually" is not "always,"
but I think you'd be better off without these aliases. The fact that
you have two identical aliases suggests that a certain amount of
confusion may already have crept in: When would you use `node' and
when would you use `TREE', and what difference are you trying to
express by choosing one or the other?

> where first_child points to first sibling of the node, next_sib points to
> next sibling and last_child points to last sibling in the node.


I'll assume you mean that `first_child' and `last_child' point
to the first and last *children* of the node, not to its first and
last siblings.

> next sibling and last_child points to last sibling in the node. Data
> zadnji is true if the node is last child of any other node.
>
> Labeltype is char.
>
> Here's the whole implementation:
>
> #include<stdlib.h>
> #include<stdio.h>
> #define LAMBDA NULL
> #define labeltype char
>
> typedef struct __celltype {
> labeltype label;
> struct __celltype *first_child;
> struct __celltype *next_sib;
> struct __celltype *last_child;
> int zadnji; /*last*/
> } celltype;
>
> typedef celltype *node;
> typedef celltype *TREE;
>
> node MAKE_ROOT(labeltype l, TREE *T) {
> if (!(*T = (celltype*) malloc(sizeof(celltype)))) {


Yet more minor points: First, it's not necessary to cast the
result of malloc(). Second, the code relies on `TREE' being an
alias for `celltype*', which means you're not actually getting any
value out of the `TREE' alias. Here's a better paradigm, no matter
what type of data `T' points to:

if (!(*T = malloc(sizeof(**T))) ...

> printf("Nema dovoljno memorije.");
> exit(1);


Minor points: Put a newline '\n' at the end of the message,
and use exit(EXIT_FAILURE) instead of exit(1).

As a matter of design, it is usually not a good idea for a
"low-level" function to make such a drastic decision about the
fate of the entire program. Normally, it's better to indicate
failure in some other way, and let the higher-level caller decide
how to deal with it; the higher-level caller has more "knowledge"
of the state of the entire program. Even if the eventual action
is to exit(), the caller might want to do something else first.
Observe that malloc() does not terminate your program when it
fails, but instead reports the failure and lets the program make
its own choice; consider following that pattern in your own code,
especially in functions near the "leaves."

> }
> (*T)->label=l;
> (*T)->first_child=NULL;
> (*T)->next_sib=NULL;
> (*T)->last_child=NULL;
> (*T)->zadnji=0;
> return *T;


Yet another confusion of aliases: This line relies on
`TREE' being the same as `node'. In one function you've used
three different names for exactly the same type! Do you think
this makes the code easier or harder to read?

There's also a design oddity. The function returns its
result via two different channels: It stores the new pointer
at the location pointed to by `T', and it also returns the
same pointer as the function value. There's nothing actually
"wrong" with this, but it's unusual enough to raise an eyebrow.
Usually, you'll want to use just one channel to export a result;
functions like time() are the exception, not the rule.

> }
>
> node INSERT_CHILD(labeltype l, node i, TREE *T){
> node temp;
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> if (!(i->first_child= (celltype*) malloc(sizeof(celltype)))) {
> printf("Nema dovoljno memorije.");
> exit(1);
> }
> if (i->first_child==NULL) {


Okay, here's an actual problem: Observe that (1) the code in
this part of the `if' statement will never execute, and (2) if it
somehow did execute you'd be trying to store data where the NULL
pointer points!

> i->first_child->label=l;
> i->first_child->first_child=NULL;
> i->first_child->next_sib=NULL;
> i->first_child->last_child=NULL;
> i->first_child->zadnji=1;
> }
> if (i->first_child!=NULL) {


... and here's another part of the same problem: This code
will always execute, and will wind up producing an endless loop
in your data structure: That is, `i->first_child->next_sib' will
point back to `i->first_child' again. Any siblings that might
already have existed are now lost forever.

> temp=i->first_child;
> i->first_child->label=l;
> i->first_child->first_child=NULL;
> i->first_child->next_sib=temp;
> i->first_child->last_child=NULL;
> i->first_child->zadnji=0;
> }
> return i->first_child;
> }
>
> node ROOT(TREE T){
> return T;
> }
>
> node INSERT_SIBLING(labeltype l, node i, TREE *T){
> node temp;
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> if (!(i->next_sib= (celltype*) malloc(sizeof(celltype)))) {
> printf("Nema dovoljno memorije.");
> exit(1);
> }
> if (i==ROOT(*T)) {
> printf("Taj cvor je korijen.");
> exit(1);
> }
> if(i->zadnji==1){
> i->zadnji=0;
> i->next_sib->label=l;
> i->next_sib->first_child=NULL;
> i->next_sib->next_sib=NULL;
> i->next_sib->last_child=NULL;
> i->next_sib->zadnji=1;
> }
> if(i->zadnji==0){
> temp=i->next_sib;
> i->next_sib->label=l;
> i->next_sib->first_child=NULL;
> i->next_sib->next_sib=temp;
> i->next_sib->last_child=NULL;
> i->next_sib->zadnji=0;
> }
> return i->next_sib;
> }
>
> node PARENT(node i,TREE T){


If you expect to navigate from child to parent, wouldn't it
be easier to store that link directly in the node than to do a
recursive search for it?

> node c, d;
> if (i==ROOT(T)) return LAMBDA;
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> for (c=T->first_child; c!=NULL; c=c->next_sib)
> if (c==i) return T;
> for (c=T->first_child; c!=NULL; c=c->next_sib){
> d=PARENT(i,c);
> if (d!=NULL) return d;
> }
> return NULL;
> }


I'm running out of energy, and won't say much more; absence
of commentary should not be construed as approval! One thing that
stands out is that you've duplicated the node-building operation
(allocate memory and initialize the struct) in about five places;
it would be much simpler (and easier!) to write just one function
to do this job, and to call it from wherever it's needed. You've
got three functions whose job is to create a new struct and attach
it in various ways; consider separating the "create" and "attach"
operations, and I think you'll have shorter and cleaner code.

> void DELETE(node i, TREE *T) {
> node c,d,e,f,temp;
> if (i==ROOT(*T)) {
> printf("Taj cvor je korijen."); /*is root*/
> exit(1);
> }
> if (!i) {
> printf("Nema tog cvora."); /*no node*/
> exit(1);
> }
> if (i->first_child!=NULL) {
> printf("Taj cvor ima djece."); /*has sib*/
> exit(1);
> }
> c=PARENT(i,*T);
> if (c->first_child==c->last_child) {
> free(i);
> c->first_child=NULL;
> c->last_child=NULL;
> }
> if (i==c->first_child) {
> temp=i->next_sib;
> free(i);
> c->first_child=temp;
> }
> if(i==c->last_child) {
> d=c->first_child;
> while(d!=c->last_child) {
> if (d->next_sib==i) {
> d->next_sib=NULL;
> d->zadnji=1;
> break;
> }
> d=d->next_sib;
> }
> free(i);
> c->last_child=d;
> }
> if ((i!=c->first_child)&& (i!=c->last_child)){
>
> for (d=c->first_child; d!=NULL; d=d->next_sib){
> if(d->next_sib==i) e=d;
> if(i->next_sib==d) f=d;
> }
> free(i);
> e->next_sib=f;
> }
> }
>
> node FIRST_CHILD(node i, TREE T){
> if (i->first_child==NULL) return NULL;
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> return i->first_child;
> }
>
> node NEXT_SIBLING(node i, TREE T){
> if (i->next_sib==NULL) return NULL;
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> return i->next_sib;
> }
>
> labeltype LABEL(node i, TREE T) {
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> return i->label;
> }
>
> void CHANGE_LABEL(labeltype l, node i, TREE *T){
> if (!i) {
> printf("Nema tog cvora.");
> exit(1);
> }
> i->label=l;
> }
>
> void POSTORDER(node i, TREE T) {
> node c;
> for(c=FIRST_CHILD(i,T); c!=LAMBDA; c=NEXT_SIBLING(c,T))
> POSTORDER(c,T);
> printf("%c ", LABEL(i,T));
> }
>
>
> int main(void)
> {
> return 0;
> }
>
>
>
> Now I need a sane way to input a tree from keyboard. What would be the
> easiest one?


You could use parentheses to enclose groups of siblings:

(A(B,C),D,E(F(G,H),I),J)

could encode a tree that might also be diagrammed as

A
+- B
+- C
D
E
+- F
+- G
+- H
+- I
J

But first, fix your code!

--
Eric Sosman
esosman@ieee-dot-org.invalid

Ben Bacarisse 01-16-2012 11:01 PM

Re: Tree implementation, ideas for keyboard input method needed
 
Keith Thompson <kst-u@mib.org> writes:
<snip>
> A good idiom is:
>
> if ((*T = malloc(sizeof **T) != NULL) {


There's a missing ')' of course:

if ((*T = malloc(sizeof **T)) != NULL) {

<snip>
--
Ben.

James Kuyper 01-16-2012 11:06 PM

Re: Tree implementation, ideas for keyboard input method needed
 
On 01/16/2012 05:36 PM, Bubba wrote:
> Keith Thompson's log on stardate 16 sij 2012
>
> I hoped for something like this in the first place, so thank you in
> advance!
>
>> Identifiers starting with underscores are reserved to the
>> implementation in most contexts. Identifiers starting with two
>> underscores are reserved in all contexts. You should never define
>> such identifiers yourself (unless you're writing code for a C
>> compiler or library implementation).

>
> What are the repercussions of choosing wrong number of underscores? :)


Theoretically: the behavior of your program is undefined. This means
that the C standard places no restrictions on the behavior of the
resulting program. That's a bad thing, if there's any particular
behavior you want your program to have, since it might not have that
behavior. It's an even worse thing if there are any things your program
could do that you don't want it to do (such as erasing all of your
files), because there's a chance that it might do one of those things.

Practically: identifiers are reserved to the implementation, so they can
by used by the implementation for it's own purpose, without worrying
about the possibility that user code might interfere. Consider what
could go wrong with your program if __celltype is defined by the
implementation, inside stdlib.h, for some purpose. The best possible
outcome is that the compiler will notice two different conflicting
definitions for __celltype, and complain. The worst possibility is that
__celltype is defined in some way that produces no warning messages when
you misuse it.

>> And in fact I'd declare this as:
>> struct celltype *make_root(labeltype label, struct celltype **t);

>
> Could you please clarify the need for double pointer?


Please don't refer to that as a "double pointer". It's a pointer to a
pointer. a "double pointer" could be interpreted as referring to a
"double*".

I'll let Keith answer the rest of your question in more detail, since
it's his suggestion.
--
James Kuyper


All times are GMT. The time now is 10:11 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.