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, May 01 '13 at 23:49

score 1 · Answer 1 · answered May 01 '13 at 23:37

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.

Arun · Accepted Answer · 2013-05-02T23:58:06.640

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

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, May 02 '13 at 00:33
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 :-) — rivimey, May 02 '13 at 00:36
Note that the suggestion to add `free(root->data)` caused the o/p to do this immediately after `root=malloc(...` (see http://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` — simonc, May 15 '13 at 09:34

Rodrigo Villalba Zayas · Answer 3 · 2013-05-02T00:04:09.633

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.

trees data structure implementation in c

3 Answers3