Smart questions
Smart answers
Smart people
Join Tek-Tips Forums
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Member Login




Remember Me
Forgot Password?
Join Us!

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips now!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

Join Tek-Tips
*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.
Jobs from Indeed

Link To This Forum!

Partner Button
Add Stickiness To Your Site By Linking To This Professionally Managed Technical Forum.
Just copy and paste the
code below into your site.

A binary tree and its pointers ... (PLEASE help)Helpful Member! 

ankan (Programmer) (OP)
28 Jul 01 12:11
PLEASE help in anyway you can. I've got fed up with trying to solve this.

Lets get to the point directly...
A simple binary tree...
struct tnode {
    char **word; /* this stores the different words */
    int count;   /* this keeps the count */      
    struct tnode *left;
    struct tnode *right;
};

A simpler objective... to store in the above tree and print out each group of words from an input buffer that have the first few (how many? given by the variable 'till') characters identical, in alphabetical order.
The words are sent to the function addtree:

struct tnode *addtree(struct tnode *p, char *w, int till)
{
    int cond;
    if(p==NULL) {  /* found new */
        p = (struct tnode *) malloc(sizeof(struct tnode));
        p->count = 1;
        p->word[(p->count)-1] = strdup(w);
        p->left = p->right = NULL;
    } else if((cond = strncmp(w, p->word[0], till)) == 0) { /* found a match */
        p->count++;
        p->word[(p->count)-1] = strdup(w);
        printf("Added to old... new: %s\n", w);
    } else if(cond < 0)
        p->left = addtree(p->left, w, till);
    else
        p->right = addtree(p->right, w, till);
return p;
}

The main fiunction ...
int main()
{
    struct tnode* root;
    int till = 6;
/* ... */
/* --------- snip ------ */
    root = NULL;
    while (getw(word, in) != EOF) /* getw() gets the next word from the input stream 'in' */
        if(isalpha(word[0]))
            root = addtree(root, word, till);
    treeprint(root);  /* a function traversing the binary tree for printing */
/* --------- snip ------ */
/* ... */
}

The Problem ... Its not running correctly. Sometimes it prints out only the last word. Sometimes the "This program has performed an illegal operation..." message crops up. And sometimes its not running at all!! There maybe a problem with the pointers. But where??
On stepping through with the Debugger it gave "Stopped at exception throw" error. And also the root->word (in main) gets changed with every call to the recursive function (although the address of root does not change, it should not anyway). But it seems (after much tracing through the code with the debugger) that the malloc function (bolded) in the recursive function gives the same address to p in each subsequent recursive call!!

Where did I go wrong? Give me a hint but please reply.
Can you help?? Please.

Note: I posted the above query in the C forum but since there was absolutely no response, I'm trying here.

Waiting.
Ankan.

Please do correct me if I am wrong.

Helpful Member!  Zyrenthian (Programmer)
30 Jul 01 13:52
the 2d pointer in the struct is your problem.  You define no dimentions so only one pointer to a string exists.  You would have to do somethng along the lines of

struct tnode{
  char* word[MAX_WORDS];
...
}

and on the insert

if p->count-1<MAX_WORDS // dont add it

Matt
ankan (Programmer) (OP)
30 Jul 01 15:55
Thankyou very much, Zyrenthian. You were right. The problem was that I did not allocate space for the whole thing first (how darn stupid of me!).
I assume that you meant "if p->count-1 > MAX_WORDS // dont add it".
However, I did not change the structure,
struct tnode{
  char **word;
...
}
since I wanted to allocate memory dynamically.

Here's what I did ultimately ...

struct tnode *addtree(struct tnode *p, char *w, int till)
{
    int cond;
    if(p == NULL) {
        if( (p = (struct tnode *) malloc(sizeof(struct tnode))) == NULL)
            return NULL;
        p->count = 1;
        if( (p->word = realloc(p->word, sizeof(p->word)+strlen(w))) == NULL) {
            free(p);
            return NULL;
        }

        if( (p->word[p->count - 1] = strdup(w)) == NULL) {
            free(p);
            return NULL;
        }
        strcpy(p->word[p->count - 1], w);
        p->left = p->right = NULL;
    }
    else if((cond = strncmp(w, p->word[0], till)) == 0) {
        p->count++;
        if( (p->word = realloc(p->word, sizeof(p->word)+strlen(w))) == NULL) {
            free(p);
            return NULL;
        }

        if( (p->word[p->count - 1] = strdup(w)) == NULL) {
            free(p);
            return NULL;
        }
        strcpy(p->word[p->count - 1], w);
    }
    else if(cond < 0)
        p->left = addtree(p->left, w, till);
    else
        p->right = addtree(p->right, w, till);
return p;
}

It seems to be working now (although, as yet i have checked only on small and simple inputs).
 Bye.
Ankan.

Please do correct me if I am wrong.
ankan (Programmer) (OP)
31 Jul 01 10:17
Make that
...
if( (p->word = realloc(p->word, sizeof(p->word)+strlen(w)+1)) == NULL) {
...

(the classical forgetting of the '\0'), and other small changes not worth mentioning.

Bye.
Ankan.

Please do correct me if I am wrong.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Back To Forum

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close