Tree Problem

This is a discussion on Tree Problem within the C Programming forums, part of the General Programming Boards category; How about char phone[20]; // just the one becoming char phone[5][20]; // upto 5 phones...

  1. #16
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    How about
    char phone[20]; // just the one

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

  2. #17
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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

  3. #18
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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)

  4. #19
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    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;

  5. #20
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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)

  6. #21
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    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

  7. #22
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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?

  8. #23
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    Once again, you've missed what I said by some small fraction

  9. #24
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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.

  10. #25
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    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;
    }

  11. #26
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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).

  12. #27
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    > 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

  13. #28
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    thanks for the explanation salem.

  14. #29
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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.

  15. #30
    Registered User
    Join Date
    Nov 2004
    Posts
    67
    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.

Page 2 of 3 FirstFirst 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Undirected graph and Binary Tree problem
    By arafat21 in forum C Programming
    Replies: 3
    Last Post: 05-02-2008, 05:52 AM
  2. BST delete again, but this time I think I'm close
    By tms43 in forum C++ Programming
    Replies: 9
    Last Post: 11-05-2006, 05:24 PM
  3. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21