CODEWITHSUNDEEP
cdata-structurestree
Mahmoud ElMarakshy
Mahmoud ElMarakshy

Reputation: 13

trees data structure implementation in c

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);
}

Upvotes: 0

Views: 1054

Answers (3)

Arun
Arun

Reputation: 20383

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

Upvotes: 1

Rodrigo Villalba Zayas
Rodrigo Villalba Zayas

Reputation: 5616

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.

Upvotes: 0

yiding
yiding

Reputation: 3592

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.

Upvotes: 1

Related Questions