Thread: Trouble with pointers..

I'm sure this is a very common problem. No matter how many times I've delt with pointers, they always end up confusing me. Especially in c.

I'm trying to pass a pointer to the root of a binary tree in a function, have the function change/add to the contents of the children, then return the original pointer. Here is the code:

Code:

struct node*
addword(struct node* p, char *w)
{
    int cond;
    struct node* i = p; //create iterator pointer

    while (i != NULL) {
        if ((cond = strcmp(w, i->word)) == 0) {
            i->count++;
            return p;
        }
        else if (cond < 0) {
            i = i->left;
        }
        else {
            i = i->right;
        }
    }

    i = talloc(); // allocates new 'struct node'
    i->word = strdup(w);
    i->count = 1;
    i->left = i->right = NULL;

    return p;
}

I'm sure you can tell what I'm trying to do. I made a dummy pointer 'i' so I can iterate through my tree (ie i = i->right; ), then I can return the original pointer p. But no matter what I do to the pointer i, the pointer p does not change when it is returned. I know there is most likely a stupid mistake somewhere in here, but I've been playing with it for hours and reading countless pointer tutorials. I just can't seem to get it to work.

Can you guys help me out a bit?

Thanks,

Just want to clarify one or two things before...
You call your function with the root, right ? Something like...

Code:

struct node *root;

root = initTree(...);
root = addword(root, "hello world");

And then you ask why, when you try to print your tree after adding words, it prints an empty tree ? If it's your question (because, a root being a root, if you are in a simple non-balanced binary tree data structure, the root will always stay the same), well, it's because you aren't linking the allocated memory to the tree, simply.

Something like this would resolve your problem...

Code:

struct node*
addword(struct node* p, char *w)
{
    int cond;
    struct node* i = p; //create iterator pointer
    struct node *parent = NULL;

    // Here you should test the case of an empty tree (...)

    while (i != NULL) {
        if ((cond = strcmp(w, i->word)) == 0) {
            i->count++;
            return p;
        }
        else if (cond < 0) {
            parent = i;
            i = i->left;
        }
        else {
            parent = i;
            i = i->right;
        }
    }

    i = talloc(); // allocates new 'struct node'
    i->word = strdup(w);
    i->count = 1;
    i->left = i->right = NULL;

    if (cond < 0)
        parent->left = i;
    else
        parent->right = i;

    return p;
}

One way to do it. I didn't test, but it should work.
But i'm not sure to understand your question.

Originally Posted by foxman

Just want to clarify one or two things before...
You call your function with the root, right ? Something like...

Code:

struct node *root;

root = initTree(...);
root = addword(root, "hello world");

And then you ask why, when you try to print your tree after adding words, it prints an empty tree ? If it's your question (because, a root being a root, if you are in a simple non-balanced binary tree data structure, the root will always stay the same), well, it's because you aren't linking the allocated memory to the tree, simply.

Thanks for the reply. Yes, that is how I'm calling addword(). Except root starts out as NULL. so for the first call the function is just:

Code:

struct node*
addword2(struct node* p, char *w)
{
    int cond;
    struct node* i = p; //create iterator pointer
 
    i = talloc();
    i->word = strdup(w);
    i->count = 1;
    i->left = i->right = NULL;

    return p;
}

But it returns NULL.

Originally Posted by Overworked_PhD

I think the issue lies with

Code:

 struct node* i = p; //create iterator pointer

You originally have the local variable 'i' point to 'p'. Later on, you have 'i' point to some memory on the heap

Code:

i = talloc(); // allocates new 'struct node'

You then fill in the structure for 'i', but not for 'p' and then return what is pointed to by 'p'. Not withstanding indentation issues, I would probably do something like the following

Code:

struct node*
addword(struct node* p, char *w)
{
    int cond;

    if (p == NULL) {
        p = talloc();
        p->word = strdup(w);
        p->left = p->right = NULL;
     }else if ((cond = strcmp(w, p->word)) == 0) {
         p->count++;
     }else if (cond < 0) 
         p->left = addword(p->left, w);
      else 
         p->right = addword(p->right,w);
    }

    return p;
}

I have the variable 'p' point to some memory on the heap. I then fill in the structure that is pointed to by 'p'. When 'p' returns, it points to the allocated memory.

This is a homework assignment for cs-200. And the function you posted is the exact function I need to rewrite without recursion.

Well, the answer is just under your eyes... just open them a little bit...
Overworked_PhD gave some good explanations. Maybe you should reread what he wrote.

For my part, when i wrote,

Code:

// Here you should test the case of an empty tree (...)

Well, replace it by a part of the code Overworked_PhD gave.... and voila...

Code:

if (p == NULL)
{
        p = talloc();
        p->word = strdup(w);
        p->left = p->right = NULL;
        return p;     // I added this line
}

Should work just fine.

Awesome. You guys got me on the right track. Now I can work on some less trivial homework.

Is it just me or are pointers different in C than C++? I always though that if you pass a pointer into a function, whatever you did to the pointer in the function would have affect on the pointer that was passed. (Wow I worded that very weird).