Thread: Tree Problem

How about
char phone[20]; // just the one

becoming
char phone[5][20]; // upto 5 phones

would 2 dimentinial arrays be the best way of doing it? i havnt done them before so i have no idea of how to implement one

would using hash tables be of any use to me? if so, does anyone know any good websites explaining how to implement one (i have tried searching the forums). i have been informed i have to use some kind of lookup table, is this the same as a hash table?! Or is it possible to used 2 dimentional arrays? any help appreciated (sorry for all the questions)

You can use whatever you like, but why didn't you try my suggestion?

Here's a more explicit hint

Code:

typedef struct tree
{
    char name[20];
    char phone[5][20];  // upto 5 phones
    int num_phones;  // number of phones in use
    struct tree *left;
    struct tree *right;
}Tree;

ok ive just tried what you said and i get 3 warnings;

1) Made Node function

Code:

 strncpy(t->phone,in2,19);

- 'char *' differes in level of indirection

2) Made Node function

Code:

 strncpy(t->phone,in2,19);

- different types for formal and actual parameters

3) search function

Code:

 else if(strcmp(what,root->name)==0) {return root->phone;}

-return function differs in level of indirection from char [5][20]

with the adjustments ive made to the tree structure where do i need to adjust the parameters etc? and do i need to make a function to count the number of telephone numbers each person has so i know how many to print out ? any help is greatly appreciated (thanks salem)

Well phone is now an array of strings, so you need something like

Code:

 strncpy(t->phone[t->num_phones],in2,19);
t->num_phones++;

Don't forget to initialise num_phones to zero

ok the program now compiles but when i run it , it crashes, here is my code:

Code:

 



#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree
{
    char name[20];
    char phone [5][20];
    int num_phones;
    struct tree *left;
    struct tree *right;
}Tree;    

Tree *makenode( char *in, char *in2, Tree *l, Tree *r)
{
    Tree *t=malloc(sizeof(Tree));
    t->left =l;
    t->right =r;
    strncpy(t->name,in,19);
    strncpy(t->phone[t->num_phones],in2,19);
    t->num_phones++;
    return t;
}    

Tree *insert( Tree *root, char *what, char *what2)
{
    if(root==NULL)
    {root=makenode(what,what2,NULL,NULL);}
    else if(strcmp(what, root->name)<0)
    {root->left =insert(root->left,what, what2);}
    else{root->right =insert(root->right,what,what2);
}
return root;
}     

char *search(Tree *root, char *what)
{
    if(root==NULL){return "NOT FOUND";}
    else if(strcmp(what,root->name)==0) {return root->phone[root->num_phones];}
    else if(strcmp(what,root->name)<0) {return search(root->left,what);}
    else{return search(root->right,what);}
}

int main(void)
{
    int i;
    char s[20];
    char b[20];
    int num_phones =0;
    Tree *tree =NULL;
    do{
        scanf("%s",s);
	if(strcmp(s,".")==0)
	{break;}
	scanf("%s",b);
   for(i=0;i<20;i++)
    {s[i]=toupper(s[i]);}

	if(strcmp(s,".")!=0);
        {tree=insert(tree, s,b);}
    }
    while(strcmp(s,".")!=0);
	do{
		printf("Type a name name please ");
        scanf("%s",s);
        for(i=0;i<20;i++)
        {s[i]=toupper(s[i]);}
        if(strcmp(s,".")!=0)
        {printf("%s\n", search(tree,s));}
    }while(strcmp(s,".")!=0);
return 0;
}

can anyone spot the error?

Once again, you've missed what I said by some small fraction

i've re-read all your posts and i still dont understand what you mean, i've done everything you've told me to do, i think my search function and my print function are wrong but i just dont know how to fix them and when your trying to learn c in your spare time, apart from forums there arent many places to ask people for help, all help is GREATLY appreciated.

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree {
    char name[20];
    char phone[5][20];
    int num_phones;
    struct tree *left;
    struct tree *right;
} Tree;

Tree *makenode(char *in, char *in2, Tree * l, Tree * r)
{
    Tree *t = malloc(sizeof(Tree));
    t->left = l;
    t->right = r;
    t->num_phones = 0;
    strncpy(t->name, in, 19);
    strncpy(t->phone[t->num_phones], in2, 19);
    t->num_phones++;
    return t;
}

Tree *insert(Tree * root, char *what, char *what2)
{
    if (root == NULL) {
        root = makenode(what, what2, NULL, NULL);
    } else if (strcmp(what, root->name) < 0) {
        root->left = insert(root->left, what, what2);
    } else {
        root->right = insert(root->right, what, what2);
    }
    return root;
}

/* returns a pointer to the found node, or NULL */
Tree *search(Tree * root, char *what)
{
    if (root == NULL) {
        return NULL;
    } else if (strcmp(what, root->name) == 0) {
        return root;
    } else if (strcmp(what, root->name) < 0) {
        return search(root->left, what);
    } else {
        return search(root->right, what);
    }
}

int main(void)
{
    int i;
    char s[20];
    char b[20];
    Tree *tree = NULL;

    do {
        scanf("%s", s);
        if (strcmp(s, ".") == 0) {
            break;
        }
        scanf("%s", b);
        for (i = 0; i < 20; i++) {
            s[i] = toupper(s[i]);
        }

        if (strcmp(s, ".") != 0) {  /* fixed trailing ; */
            Tree *found = search(tree, s);
            if ( found ) {
                /* new phone number for current person */
                strncpy( found->phone[found->num_phones], b, 20 );
                found->num_phones++;
            } else {
                /* first phone number for new person */
                tree = insert(tree, s, b);
            }
        }
    }
    while (strcmp(s, ".") != 0);

    do {
        printf("Type a name name please ");
        scanf("%s", s);
        for (i = 0; i < 20; i++) {
            s[i] = toupper(s[i]);
        }
        if (strcmp(s, ".") != 0) {
            Tree *found = search(tree, s);
            if ( found ) {
                int i;
                printf( "%s ", found->name );
                for ( i = 0 ; i < found->num_phones ; i++ ) {
                    printf("%s ", found->phone[i] );
                }
                printf( "\n" );
            }
        }
    } while (strcmp(s, ".") != 0);

    return 0;
}

thank you salem! your a genius. in my search function you have modified it to:

Code:

if(root==NULL) {return NULL;}

why am i now returning NULL? can't i just return "NOT FOUND" as the element has not been found(like before).

> why am i now returning NULL?
Because it's returning a pointer to the whole node (not any particular string in the node). Besides, with the additional functionality of multiple phone numbers, a single string is no longer sufficient.

Look at how search() is used in two different places

thanks for the explanation salem.

how would i go about making my program store the telephone numbers for each person as a list? would this not mean that the tree nodes have a list hanging of all the leafs? how would i change the tree structure for phone number? sorry , i know i have asked lots of questions,but this is the last for this topic.

i'm now trying to store each telephone number as a list so that the nodes of the tree have a list hanging of all the leafs. I've changed the tree structure so that it now stored the name and then a pointer to the linked list where the phone numbers are stored. I'm now very unsure about how to search for an item, i would have to search for the name, then taken the pointer to the linked list and sequentially print out the items in that list, i have attempted to do this , but i am getting errors such as 'conflictin type for insert' and a few warnings about passing pointers without a cast- what does this mean?

here is my code

Code:

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct tree
{
    char name[20];
    char *Element;
    struct tree *left;
    struct tree *right;
}Tree;  

typedef struct linked_list 
{
    char d;
    struct linked_list *next;
} Element;

Element* insert( char h, Element *t )
{
	Element* y = calloc( 1, sizeof( Element ) );
	y->d = h;
    if( t ) t->next = y;  
    return y;
} 

Tree *makenode( char *in, char *in2, Tree *l, Tree *r)
{
    Tree *t=malloc(sizeof(Tree));
    t->left =l;
    t->right =r;
    strncpy(t->name,in,19);
    /*Statement to copy pointer to linked list of phone numbers into tree*/
    return t;
}    

Tree *insert( Tree *root, char *what, char *what2)
{
    if(root==NULL)
    {root=makenode(what,Element,NULL,NULL);}
    else if(strcmp(what, root->name)<0)
    {root->left =insert(root->left,what,Element);}
    else{root->right =insert(root->right,what,Element);
}
return root;
}     

char *search(Tree *root, char *what)
{
    if(root==NULL){return "NOT FOUND";}
    else if(strcmp(what,root->name)==0) {return Element;}
    else if(strcmp(what,root->name)<0) {return search(root->left,what);}
    else{return search(root->right,what);}
}

int main(void)
{
    int i;
    char s[20];
    char d;
    Tree *tree =NULL;
    Element* head = NULL;
    Element* tail = NULL;
    Element* next;
   do{
        scanf("%s",s);
	if(strcmp(s,".")==0)
	{break;}
	scanf("%s",&d);
	for(i=0;i<20;i++)
    {s[i]=toupper(s[i]);}
   
    if(strcmp(s,".")!=0);
        {
          tree=insert(tree, s,*Element);
          tail = insert( d, tail );
              if( !head ) 
              {head = tail; } 
        }
    }while(strcmp(s,".")!=0);
	do{
		printf("Type a name name please ");
        scanf("%s",s);
        for(i=0;i<20;i++)
        {s[i]=toupper(s[i]);}
        if(strcmp(s,".")!=0)
        {     
    for( ; head ; head = next ) {
    printf( "%c", head->d );
    next = head->next;
    free( head );}
        }
      }while(strcmp(s,".")!=0);
return 0;
}

thanks.