trees data structure implementation in c

Question

this code was perfectly working when i was using integers now i want to insert strings so i changed the comparisons to strcomp and its not woorking any help appreciated link for the full code http://pastebin.com/6j1haZRF

struct node * insert(struct node *root, char x[])
{

if(!root)
{
    root=(struct node*)malloc(sizeof(struct node));
    root->data = x;
    root->left = NULL;
    root->right = NULL;
    return(root);
}
if((a=strcmp(root->data,x))>0){
    root->left = insert(root->left,x);
}
else
{
    if(strcmp(root->data,x)<0)
        root->right = insert(root->right,x);
}
return(root);
}

When you say it has stopped working, do you mean it runs but doesn't get the result you expect? Do you get any errors? — xagyg
– xagyg, Commented May 1, 2013 at 23:49

Arun · Accepted Answer · 2013-05-02 23:58:06Z

1

For the following structure

struct node{
    char * data;
    struct node *left;
    struct node *right;

} *root=NULL,*temp;

you would have to separately allocate memory for data.

Just the following would not work

    root=(struct node*)malloc(sizeof(struct node));
    root->data = x;

Solution strategy 1: Allocate memory according to need. I.e. allocate enough memory to hold the string for that node. Here, the code has to properly manage node->data, i.e. suitably allocate and de-allocate.

free( root->data );         // free previously allocated memory, if any
root->data = strdup( x );   // equivalent to malloc and memcpy

As an improvement, the memory request for data may be included in the malloc for node, thereby (a) avoiding memory fragmentation, (b) avoiding (per-malloc) overhead, (c) avoiding extra work while releasing memory (free() of node would free memory of data).

struct node {
    struct node *left;
    struct node *right;
    char * data;
};
size_t const xLen = strlen( x );
root = malloc( sizeof *root + xLen );
strncpy( root + sizeof root->left + sizeof root->right, x, xLen );

Solution strategy 2: Have the node contain necessary memory for the string. This way, there is no hassle to allocate and deallocate separately for the string. However, on the flip side, the upper limit becomes same for all strings. (It is a trade-off.)

char data[ MaxDataLen ];     // earlier, enum { MaxDataLen = 80 };
strncpy( root->data, x, MaxDataLen - 1 ); // copy chars 
root->data[ MaxDataLen - 1 ] = 0;         // NULL termination

edited May 2, 2013 at 23:58

answered May 1, 2013 at 23:37

Arun

20.6k12 gold badges54 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

rivimey Over a year ago

Good points, but don't call free() on memory that might have come from a malloc() without being cleared or set. Sometimes malloc gives you zeroed memory, mostly it doesn't.

rivimey Over a year ago

The thing with storing the string in the node could be improved. Having a maxdatalen is so last century! What you can do instead is malloc memory for node + strlen in one chunk, then store the string beyond the end of the node data, and then set the string pointer to the right place. Coding that will certainly test your knowledge of C pointer manipulation :-)

simonc Over a year ago

Note that the suggestion to add free(root->data) caused the o/p to do this immediately after root=malloc(... (see stackoverflow.com/q/16560267/311966). Unsurprisingly , trying to free an uninitialised pointer crashes. It'd be worth updating your answer to be clearer about when to use free

yiding · Accepted Answer · 2013-05-01 23:37:09Z

1

Your input buffer x is mutated every time you call scanf. Unlike the integer case, where assigning will copy the integer, in this case assigning only copies the pointer to your string. you should assign a copy of the buffer as the data, perhaps with something like

root->data = strdup(x);

You will also have to free this with free when destroying your tree.

answered May 1, 2013 at 23:37

yiding

3,59921 silver badges17 bronze badges

Comments

Rodrigo Villalba Zayas · Accepted Answer · 2013-05-02 00:04:09Z

0

The solution would be to allocate memory for node->data string every time you insert a Node or declare the following structure.

struct node{
   char data[MaxData];
   struct node *left;
   struct node *right;

}*root=NULL,*temp;

The problem is that you have memory allocated for only one string (char a[10]), the first time your insert function will work, but the second time you are overwriting the variable a, and in your insert function you don't have a test case for string equals so it returns null.

edited May 2, 2013 at 0:04

answered May 1, 2013 at 23:50

Rodrigo Villalba Zayas

5,6362 gold badges25 silver badges36 bronze badges

Collectives™ on Stack Overflow

trees data structure implementation in c

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related