Thread: names and numbers in binary trees

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    67

    names and numbers in binary trees

    i am trying to create a list of phone numbers and names that has the following input:
    name number
    name number
    name number
    .

    what i need is for a person to enter data in that format and terminate input by pressing '.' on a newline. after that a program should ask a user to enter a name and in return display a number.
    i have created such program but i am stuck on how to make it display number for a given name. currently when user inputs a name it returns a name. How do i make it return a number?
    thanks

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    A hashmap would be good for this.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by mike_g View Post
    A hashmap would be good for this.
    As long as you don't need to also print a sorted list on name - as a hashed list will not be in alphabetical order.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    Registered User
    Join Date
    Dec 2007
    Posts
    67
    i am a beginner in C so i haven't covered hash tables yet...
    here is what i wrote so far
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    
    typedef struct tree { char thisnode[10]; struct tree *left; struct tree *right;} Tree;
    
    Tree *makenode (char *in, Tree *l, Tree *r)
    {
    	Tree *t = malloc( sizeof(Tree));
    	t -> left = l;
    	t -> right = r;
    	strncpy (t -> thisnode, in, 9);
    	return t;
    }
    
    Tree *insert (Tree *root, char *what)
    {
    	if (root ==NULL){
    		root = makenode (what, NULL, NULL);
    		}else if (strcmp (what, root -> thisnode) < 0){
    		root -> left = insert (root -> left, what);
    		}else{
    		root -> right = insert(root -> right, what);
    		}
    		return root;
    }
    
    char *search (Tree *root, char *what)
    {
    	if (root ==NULL){
    		return "Not Found";
    	}else if (strcmp(what, root -> thisnode) == 0){
    	return root -> thisnode;
    	}else if (strcmp(what, root -> thisnode) < 0 ) {
    		return search (root -> left, what);
    		}else{
    		return search (root -> right, what);
    		}
    }
    
    int main (void)
    {
    	char s[30]; Tree *tree = NULL;
    	do {
    	scanf( " &#37;s", s);
    	if (strcmp(s, ".") != 0){
    		tree = insert (tree, s);
    		}
    	} while (strcmp(s, ".") != 0);
    	do{
    	printf("Type a name please:"); 
    	scanf(" %s",s);
    	if (strcmp(s,".") != 0){
    		printf("%s\n", search (tree,s ));
    	}
    	}while (strcmp(s, ".") != 0);
    }

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So what exactly is the problem you are having with the code?

    I expect that a 10 char string may be a bit short, but other than that, I don't see anything immediately wrong.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    67
    oops changed that. There is nothing wrong with the code as it is. The problem i am having is rooted in the fact that i know how to build trees with numbers or names; i just never built one with both. So i cant visualise the tree in my head. For example if i enter a NAME space NUMBER, i assume it creates a root with name and a branch with number, so when i enter a new NAME space NUMBER at newline it repeats the same process. But how can it compare a numeric value to alpha value and decide whether it is larger or smaller so it can place it in the left or right node? So to answer your question: at present the code prints NAME instead of the NUMBER. How do I change it so it prints NUMBER? thanks

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Ok, so you need to split the "name" and "number" components, and have a "name" and "number" entry in your nodes.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    67
    ok so you mean something like this:

    scanf("&#37;s", L);
    scanf("%s", N)

    would that work??

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I'm not a great fan of using scanf() for input, but yes, something like that.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with strings and numbers ;[
    By majindox in forum C++ Programming
    Replies: 7
    Last Post: 05-17-2006, 12:34 AM
  2. New at C
    By bigsmiles4ya in forum C Programming
    Replies: 3
    Last Post: 01-24-2006, 06:51 PM
  3. help with trees
    By dacbo in forum C Programming
    Replies: 2
    Last Post: 12-06-2005, 02:37 PM
  4. binary
    By webturtle0 in forum A Brief History of Cprogramming.com
    Replies: 52
    Last Post: 12-05-2002, 02:46 AM
  5. character strings and reading in a file...
    By Unregistered in forum C Programming
    Replies: 14
    Last Post: 07-30-2002, 09:51 AM