Binary Tree

Discussion in 'C Programming' started by Foodbank, Oct 9, 2005.

  1. Foodbank

    Foodbank Guest

    Hi all,

    I'm trying to do a binary search and collect some stats from a text
    file in order to compare the processing times of this program (binary
    searching) versus an old program using linked lists. I'm totally new
    to binary searches by the way. Can anyone help me with the commented
    sections below? Much of the code such as functions and printfs has
    already been completed. Any help is greatly appreciated.

    Thanks,
    James

    Code:
    #include <stdio.h>
    #include <malloc.h>
    struct tnode {			// specify the "shape" of a tnode structure ...
    	struct tnode *left;	// the left and right branch pointers
    	struct tnode *right;
    	int count;		// the word count as before
    	char *word;		// a pointer to the word
    } *root;			// declare the root pointer variable
    
    struct tnode **tree_search(struct tnode **, char *);
    void tree_stats(struct tnode *);
    int get_word(char *);
    
    int total_nodes, total_words, high;
    struct tnode *most_frequent;
    
    int main(int argc, char *argv[]) {
    	struct tnode **tpp;
    	char word_buff[100];	// the reusable word buffer
    	int i;
    	while(get_word(word_buff)) {
    		tpp = tree_search(&root, word_buff);
    		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    
    
    
    
    
    
    	}
    	tree_stats(root);
    	printf("total_nodes %d\n", total_nodes);
    	printf("total_words %d\n", total_words);
    	if(most_frequent)
    		printf("most frequent word <%s> count is %d\n",
    			most_frequent->word, most_frequent->count);
    	for(i = 1; i < argc; i++) {
    		tpp = tree_search(&root, argv[i]);
    		if((*tpp) == NULL)
    			printf("%s is NOT in the tree\n", argv[i]);
    		else
    			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    	}
    	return(0);
    }
    
    // binary tree search returning a pointer to the pointer leading to a
    hit
    struct tnode **tree_search(struct tnode **tpp, char *w) {
    	/***** CODE TO DO THE BINARY SRCH *****/
    	return(tpp);
    }
    
    // gather stats to check tree correctness
    void tree_stats(struct tnode *tp) {
    	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    
    
    
    
    
    }
    
    #include <ctype.h>
    /* Leave this routine EXACTLY as it stands */
    int get_word(char *s) {
    	int c;
    	do {
    		c = getchar();
    		if(c == EOF)
    			return(0);
    	} while(!isalpha(c) && !isdigit(c));
    	do {
    		if(isupper(c))
    			c = tolower(c);
    		*s++ = c;
    		c = getchar();
    	} while(isalpha(c) || isdigit(c));
    	*s = 0;
    	return(1);
    }
    
    
    Foodbank, Oct 9, 2005
    #1
    1. Advertising

  2. Foodbank

    Guest

    Foodbank schreef:

    > Hi all,
    >
    > I'm trying to do a binary search and collect some stats from a text
    > file in order to compare the processing times of this program (binary
    > searching) versus an old program using linked lists.


    A "binary search" does not involve any trees, it's a way of searching
    through *sorted* sequential lists.

    > I'm totally new
    > to binary searches by the way. Can anyone help me with the commented
    > sections below? Much of the code such as functions and printfs has
    > already been completed.


    Yes. All but the actual implementation of the tree-building and
    searching algo's, which are left to the student. I bet that's what the
    teacher gave you as an assignment.

    >Any help is greatly appreciated.


    >/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/

    <snip>
    >/***** CODE TO DO THE BINARY SRCH *****/

    <snip>
    >/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/


    Do your own homework, or at least let us see you trying.
    , Oct 9, 2005
    #2
    1. Advertising

  3. Foodbank

    Guest

    Foodbank wrote:
    > Hi all,
    >
    > I'm trying to do a binary search and collect some stats from a text
    > file in order to compare the processing times of this program (binary
    > searching) versus an old program using linked lists. I'm totally new
    > to binary searches by the way. Can anyone help me with the commented
    > sections below?


    Here's a couple links to how binary trees work. It's about numbers
    in a Collatz sequence instead of words but the same principles apply.
    In fact, I learned how to do this from the O'Reilly book "Practical
    C Programming" where the example processes a list of words. The
    solution
    I talk about uses a three pointer structure that allows me to create
    a binary tree that is simultaneously a linked list. Ignore that third
    pointer feature if it's not applicable to your problem.

    This is a quickie tutorial on binary trees

    <http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/40b6e1f3d696be54/cb42098abc4cf84e?hl=en#cb42098abc4cf84e>

    And this is how a binary tree is applicable to the problem of
    finding a duplicate number in a Collatz sequence.

    <http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/43c11da057cfb30c/6f35e1f30e0a3b43?hl=en#6f35e1f30e0a3b43>

    If none of this makes any sense, I can dig up my code examples,
    but right now they are coded to use GMP unlimited precision integers
    and won't directly plug into your program, but the principles should
    apply.

    > Much of the code such as functions and printfs has
    > already been completed. Any help is greatly appreciated.
    >
    > Thanks,
    > James
    >
    >
    Code:
    > #include <stdio.h>
    > #include <malloc.h>
    > struct tnode {			// specify the "shape" of a tnode structure ...
    > 	struct tnode *left;	// the left and right branch pointers
    > 	struct tnode *right;
    > 	int count;		// the word count as before
    > 	char *word;		// a pointer to the word
    > } *root;			// declare the root pointer variable
    >
    > struct tnode **tree_search(struct tnode **, char *);
    > void tree_stats(struct tnode *);
    > int get_word(char *);
    >
    > int total_nodes, total_words, high;
    > struct tnode *most_frequent;
    >
    > int main(int argc, char *argv[]) {
    > 	struct tnode **tpp;
    > 	char word_buff[100];	// the reusable word buffer
    > 	int i;
    > 	while(get_word(word_buff)) {
    > 		tpp = tree_search(&root, word_buff);
    > 		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    >
    >
    >
    >
    >
    >
    > 	}
    > 	tree_stats(root);
    > 	printf("total_nodes %d\n", total_nodes);
    > 	printf("total_words %d\n", total_words);
    > 	if(most_frequent)
    > 		printf("most frequent word <%s> count is %d\n",
    > 			most_frequent->word, most_frequent->count);
    > 	for(i = 1; i < argc; i++) {
    > 		tpp = tree_search(&root, argv[i]);
    > 		if((*tpp) == NULL)
    > 			printf("%s is NOT in the tree\n", argv[i]);
    > 		else
    > 			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    > 	}
    > 	return(0);
    > }
    >
    > // binary tree search returning a pointer to the pointer leading to a
    > hit
    > struct tnode **tree_search(struct tnode **tpp, char *w) {
    > 	/***** CODE TO DO THE BINARY SRCH *****/
    > 	return(tpp);
    > }
    >
    > // gather stats to check tree correctness
    > void tree_stats(struct tnode *tp) {
    > 	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    >
    >
    >
    >
    >
    > }
    >
    > #include <ctype.h>
    > /* Leave this routine EXACTLY as it stands */
    > int get_word(char *s) {
    > 	int c;
    > 	do {
    > 		c = getchar();
    > 		if(c == EOF)
    > 			return(0);
    > 	} while(!isalpha(c) && !isdigit(c));
    > 	do {
    > 		if(isupper(c))
    > 			c = tolower(c);
    > 		*s++ = c;
    > 		c = getchar();
    > 	} while(isalpha(c) || isdigit(c));
    > 	*s = 0;
    > 	return(1);
    > }
    > 
    > 
    , Oct 9, 2005
    #3
  4. Foodbank

    Guest

    wrote:
    > Foodbank wrote:
    > > Hi all,
    > >
    > > I'm trying to do a binary search and collect some stats from a text
    > > file in order to compare the processing times of this program (binary
    > > searching) versus an old program using linked lists. I'm totally new
    > > to binary searches by the way. Can anyone help me with the commented
    > > sections below?

    >
    > Here's a couple links to how binary trees work. It's about numbers
    > in a Collatz sequence instead of words but the same principles apply.
    > In fact, I learned how to do this from the O'Reilly book "Practical
    > C Programming" where the example processes a list of words. The
    > solution
    > I talk about uses a three pointer structure that allows me to create
    > a binary tree that is simultaneously a linked list. Ignore that third
    > pointer feature if it's not applicable to your problem.
    >
    > This is a quickie tutorial on binary trees
    >
    > <http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/40b6e1f3d696be54/cb42098abc4cf84e?hl=en#cb42098abc4cf84e>
    >
    > And this is how a binary tree is applicable to the problem of
    > finding a duplicate number in a Collatz sequence.
    >
    > <http://groups.google.com/group/Dymanic_Systems/browse_frm/thread/43c11da057cfb30c/6f35e1f30e0a3b43?hl=en#6f35e1f30e0a3b43>


    These links take you to the end of the threads. I meant for you to read
    the
    first message in each thread (the others drift away from the subject
    although
    you're certainly welcome to read them).


    >
    > If none of this makes any sense, I can dig up my code examples,
    > but right now they are coded to use GMP unlimited precision integers
    > and won't directly plug into your program, but the principles should
    > apply.
    >
    > > Much of the code such as functions and printfs has
    > > already been completed. Any help is greatly appreciated.
    > >
    > > Thanks,
    > > James
    > >
    > >
    Code:
    > > #include <stdio.h>
    > > #include <malloc.h>
    > > struct tnode {			// specify the "shape" of a tnode structure ...
    > > 	struct tnode *left;	// the left and right branch pointers
    > > 	struct tnode *right;
    > > 	int count;		// the word count as before
    > > 	char *word;		// a pointer to the word
    > > } *root;			// declare the root pointer variable
    > >
    > > struct tnode **tree_search(struct tnode **, char *);
    > > void tree_stats(struct tnode *);
    > > int get_word(char *);
    > >
    > > int total_nodes, total_words, high;
    > > struct tnode *most_frequent;
    > >
    > > int main(int argc, char *argv[]) {
    > > 	struct tnode **tpp;
    > > 	char word_buff[100];	// the reusable word buffer
    > > 	int i;
    > > 	while(get_word(word_buff)) {
    > > 		tpp = tree_search(&root, word_buff);
    > > 		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    > >
    > >
    > >
    > >
    > >
    > >
    > > 	}
    > > 	tree_stats(root);
    > > 	printf("total_nodes %d\n", total_nodes);
    > > 	printf("total_words %d\n", total_words);
    > > 	if(most_frequent)
    > > 		printf("most frequent word <%s> count is %d\n",
    > > 			most_frequent->word, most_frequent->count);
    > > 	for(i = 1; i < argc; i++) {
    > > 		tpp = tree_search(&root, argv[i]);
    > > 		if((*tpp) == NULL)
    > > 			printf("%s is NOT in the tree\n", argv[i]);
    > > 		else
    > > 			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    > > 	}
    > > 	return(0);
    > > }
    > >
    > > // binary tree search returning a pointer to the pointer leading to a
    > > hit
    > > struct tnode **tree_search(struct tnode **tpp, char *w) {
    > > 	/***** CODE TO DO THE BINARY SRCH *****/
    > > 	return(tpp);
    > > }
    > >
    > > // gather stats to check tree correctness
    > > void tree_stats(struct tnode *tp) {
    > > 	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    > >
    > >
    > >
    > >
    > >
    > > }
    > >
    > > #include <ctype.h>
    > > /* Leave this routine EXACTLY as it stands */
    > > int get_word(char *s) {
    > > 	int c;
    > > 	do {
    > > 		c = getchar();
    > > 		if(c == EOF)
    > > 			return(0);
    > > 	} while(!isalpha(c) && !isdigit(c));
    > > 	do {
    > > 		if(isupper(c))
    > > 			c = tolower(c);
    > > 		*s++ = c;
    > > 		c = getchar();
    > > 	} while(isalpha(c) || isdigit(c));
    > > 	*s = 0;
    > > 	return(1);
    > > }
    > > 
    > > 
    , Oct 9, 2005
    #4
  5. Foodbank

    Foodbank Guest

    Thanks guys for the links. That made me laugh when you said this was
    homework. I wish it were and I was still in school. However, I'm
    self-teaching myself C in order to switch from my electrical
    engineering based job (my degree in) into more of a programming based
    job (I know, I have a long way to go, haha). The program is an
    exercise from a book I'm reading.

    Thanks,
    Jams
    Foodbank, Oct 9, 2005
    #5
  6. Foodbank

    Malcolm Guest

    "Foodbank" <> wrote
    > I'm trying to do a binary search and collect some stats from a text
    > file in order to compare the processing times of this program (binary
    > searching) versus an old program using linked lists. I'm totally new
    > to binary searches by the way. Can anyone help me with the commented
    > sections below? Much of the code such as functions and printfs has
    > already been completed. Any help is greatly appreciated.
    >

    The idea of a binary search is this.

    We have a telephone directory, and want to find an arbitrary name - Gubbins.
    Open the directory in the middle. The middle entry will be a name like
    "Marks". If it is equal to "Gubbins" you have found your entry, if not, you
    know the name must be somewhere between the start of the directory and
    "Marks". Now go a quarter way through. This name is "Henry". Still above
    "Gubbins", so we know "Gubbins" is in the top quarter. When we check an
    eighth of the way through, we find "Evans". So Gubbins is in the second
    eighth of the directory. Split on the third sixteenth and you get "Groves".
    Gubbins is in the fourth sixteenth, between "Groves" and "Henry". Continue
    doing this until you have narrowed to a single entry.

    You will see that you eliminate half the possibilities each time, so you
    need log2(N) operations to complete the search. This is much faster than
    going through the directory sequentially.

    Unfortunately this algorithm only works if the directory entries are held in
    a sorted array. If we want to insert and delete entries, we have to move the
    array about to keep it sorted, which is expensive.

    The solution is to use a tree structure. We select an arbitrary entry about
    halfway along as the root. All the entries lower than it go in the left
    sub-tree, all the entries higher go in the right sub-tree. leaves have null
    children. We can easily add new members by growing new leaves, without
    rebuilding the whole tree. (The tree doesn't have to be perfectly balanced
    for the algorithm to work in reasonable time. Keeping the tree balanced is a
    whole new story we won't go into).

    The first thing to do is to write the routine that builds the tree. The
    first word you encounter goes in the root, the second becomes the right or
    the left leaf, and you just continue until you run out of leaves.
    Test the tree on a tiny dataset with only half a dozen words, and print it
    out so that you can see it is correct.

    Then write the function to search the tree, starting at the top and going
    down until it either hits a match or encounters a null pointer indicating it
    has fallen off a leaf.
    Malcolm, Oct 9, 2005
    #6
  7. Foodbank

    Foodbank Guest

    Hi,

    Am I on the right path in the section of the code that adds new nodes?
    I'm not finished, but trying to make an attempt. It's under the
    /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ section. I'm
    pretty sure that it's supposed to check if it's null and if so,
    allocates memory for a new node. Syntax is probably wrong, but was
    hoping for some input.

    Thanks,
    James

    Code:
    #include <stdio.h>
    #include <malloc.h>
    struct tnode {                  // specify the "shape" of a tnode
    structure ...
            struct tnode *left;     // the left and right branch pointers
            struct tnode *right;
            int count;              // the word count as before
            char *word;             // a pointer to the word
    
    } *root;                        // declare the root pointer variable
    
    struct tnode **tree_search(struct tnode **, char *);
    void tree_stats(struct tnode *);
    int get_word(char *);
    
    int total_nodes, total_words, high;
    struct tnode *most_frequent;
    
    
    int main(int argc, char *argv[]) {
            struct tnode **tpp;
            char word_buff[100];    // the reusable word buffer
            int i;
            while(get_word(word_buff)) {
                    tpp = tree_search(&root, word_buff);
                    /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
                   ///new code below here
                   if(root==NULL)
    			if(*tpp==NULL){
    				tpp=malloc(sizeof(struct tnode));
    				tpp->word = strdup(word_buff);
    				tpp->*left = NULL;
    				tpp->*right = NULL;
    			}
    		else statement here if there's a node there, increments count I
    think, not sure which variables to use
    			
            } 
    [code]
    Foodbank, Oct 11, 2005
    #7
  8. Foodbank

    Guest

    Foodbank wrote:
    > Hi,
    >
    > Am I on the right path in the section of the code that adds new nodes?
    > I'm not finished, but trying to make an attempt. It's under the
    > /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/ section. I'm
    > pretty sure that it's supposed to check if it's null and if so,
    > allocates memory for a new node. Syntax is probably wrong, but was
    > hoping for some input.


    I've include my version of the example binary tree program.
    It simply builds a tree from the command line arguments.

    A key difference is a recursive function to enter a word
    onto the tree. It starts at the root and follows left/right
    pointers until it either finds the word already on the tree
    or finds a NULL. Calling enter() with a NULL will add a node
    with count=1 since adding a node means this is the first
    occurence.

    When the word is found to be already on the tree, we just need
    to increment the count.

    Also in the program are a pair of print routines, one to print
    all the words in the tree with their frequency and another
    that shows how the path through the binary tree.

    And you will, of course, want to add a routine to free the
    allocated memory.

    Sample output:

    $ ./a the ice was here the ice was there the ice was all around
    it cracked and groaned and shrieked and howled like noises in a
    swound

    a (1) all (1) and (3) around (1) cracked (1) groaned (1)
    here (1) howled (1) ice (3) in (1) it (1) like (1) noises (1)
    shrieked (1) swound (1) the (3) there (1) was (3)

    L L L L L [a - 1]
    R U [all - 1]
    R L L [and - 3]
    R U [around - 1]
    R L [cracked - 1]
    R L [groaned - 1]
    R U U U U [here - 1]
    R L [howled - 1]
    R U U [ice - 3]
    R L L [in - 1]
    R U [it - 1]
    R L L [like - 1]
    R L [noises - 1]
    R U U [shrieked - 1]
    R L [swound - 1]
    R U U U U [the - 3]
    R L L [there - 1]
    R U [was - 3]
    R U U

    >
    > Thanks,
    > James
    >
    >
    Code:
    > #include <stdio.h>
    > #include <malloc.h>
    > struct tnode {                  // specify the "shape" of a tnode
    > structure ...
    >         struct tnode *left;     // the left and right branch pointers
    >         struct tnode *right;
    >         int count;              // the word count as before
    >         char *word;             // a pointer to the word
    >
    > } *root;                        // declare the root pointer variable
    >
    > struct tnode **tree_search(struct tnode **, char *);
    > void tree_stats(struct tnode *);
    > int get_word(char *);
    >
    > int total_nodes, total_words, high;
    > struct tnode *most_frequent;
    >
    >
    > int main(int argc, char *argv[]) {
    >         struct tnode **tpp;
    >         char word_buff[100];    // the reusable word buffer
    >         int i;
    >         while(get_word(word_buff)) {
    >                 tpp = tree_search(&root, word_buff);
    >                 /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    >                ///new code below here
    >                if(root==NULL)
    > 			if(*tpp==NULL){
    > 				tpp=malloc(sizeof(struct tnode));
    > 				tpp->word = strdup(word_buff);
    > 				tpp->*left = NULL;
    > 				tpp->*right = NULL;
    > 			}
    > 		else statement here if there's a node there, increments count I
    > think, not sure which variables to use
    >
    >         }
    > [code][/color]
    
    
    
    
    #include <stdio.h>
    #include <ctype.h>
    #include <string.h>
    #include <stdlib.h>
    
    //  gcc -g -I. c/foodbank.c
    
    struct node {
      struct node    *left;              // tree to the left
      struct node    *right;             // tree to the right
      unsigned int   count;              // # of occurences...
      char           *word;              // ...of this word
    };
    
    static struct node  *root = NULL;
    
    void memory_error(void)
    {
      fprintf(stderr, "Error:Out of memory\n");
      exit(8);
    }
    
    char *save_w(char *string)         // copy string to heap
    {
      char *new_string;
      new_string = malloc((unsigned) (strlen(string)+1));
      if (new_string == NULL)
         memory_error();
      strcpy(new_string,string);
      return (new_string);
    }
    
    void enter(struct node **node, char *word)
    {
      char          *save_w();
      int           comp;
    
      if ((*node) == NULL)
        {
          (*node) = malloc(sizeof(struct node));
          if ((*node) == NULL)
              memory_error();
          (*node)->left  = NULL;
          (*node)->right = NULL;
          (*node)->count = 1;             // new node = first occurence
          (*node)->word  = save_w(word);  // of this word
          return;
        }
      comp = strcmp((*node)->word,word);
      if (comp==0 )
        {
          (*node)->count++;              // word already in tree
          return;
        }
      if (comp<0)
          enter(&(*node)->right,word);  // recursively try to enter word
      else                              // until a NULL is found
          enter(&(*node)->left,word);
    }
    
    void print_tree(struct node *top)
    {
      if (top == NULL)
          return;
      print_tree(top->left);
      printf("%s (%d)  ", top->word,top->count);
      print_tree(top->right);
    }
    
    void print_tree_debug(struct node *top)
    {
      if (top == NULL)
          return;
      printf("L ");                                // go left
      print_tree_debug(top->left);
      printf("[%s - %d]\n", top->word,top->count);
      printf("R ");                                // go right
      print_tree_debug(top->right);
      printf("U ");                                // go up
    }
    
    int main(int argc, char *argv[])
    {
      unsigned int i;
    
      for (i=1; i<argc; i++)
          enter(&root,argv[i]);
    
      printf("\n");
      print_tree(root);
      printf("\n");
    
      printf("\n");
      print_tree_debug(root);
      printf("\n");
    
     return (0);
    }
    , Oct 11, 2005
    #8
  9. On 11 Oct 2005 15:26:31 -0700, ""
    <> wrote:

    snip

    >I've include my version of the example binary tree program.
    >It simply builds a tree from the command line arguments.
    >
    >A key difference is a recursive function to enter a word
    >onto the tree. It starts at the root and follows left/right
    >pointers until it either finds the word already on the tree
    >or finds a NULL. Calling enter() with a NULL will add a node
    >with count=1 since adding a node means this is the first
    >occurence.
    >
    >When the word is found to be already on the tree, we just need
    >to increment the count.
    >
    >Also in the program are a pair of print routines, one to print
    >all the words in the tree with their frequency and another
    >that shows how the path through the binary tree.
    >
    >And you will, of course, want to add a routine to free the
    >allocated memory.
    >

    snip

    >>
    Code:
    [/color]
    >
    >
    >
    >
    >#include <stdio.h>
    >#include <ctype.h>
    >#include <string.h>
    >#include <stdlib.h>
    >
    >//  gcc -g -I. c/foodbank.c
    >
    >struct node {
    >  struct node    *left;              // tree to the left
    >  struct node    *right;             // tree to the right
    >  unsigned int   count;              // # of occurences...
    >  char           *word;              // ...of this word
    >};
    >
    >static struct node  *root = NULL;[/color]
    
    Since you pass root to every function that needs it, there is no need
    for it to be at file scope.  This will prevent an unintended function
    from modifying it.
    [color=blue]
    >
    >void memory_error(void)
    >{
    >  fprintf(stderr, "Error:Out of memory\n");
    >  exit(8);[/color]
    
    EXIT_FAILURE would be more portable than 8.[color=blue]
    >}
    >
    >char *save_w(char *string)         // copy string to heap
    >{
    >  char *new_string;
    >  new_string = malloc((unsigned) (strlen(string)+1));
    >  if (new_string == NULL)
    >     memory_error();
    >  strcpy(new_string,string);
    >  return (new_string);
    >}
    >
    >void enter(struct node **node, char *word)
    >{
    >  char          *save_w();[/color]
    
    Marginally incorrect and error prone.  save_w was defined above.  That
    will serve as the prototype of any subsequent calls to the function.
    If you are going to repeat a declaration, repeat it exactly.
    [color=blue]
    >  int           comp;
    >
    >  if ((*node) == NULL)
    >    {
    >      (*node) = malloc(sizeof(struct node));
    >      if ((*node) == NULL)
    >          memory_error();
    >      (*node)->left  = NULL;
    >      (*node)->right = NULL;
    >      (*node)->count = 1;             // new node = first occurence
    >      (*node)->word  = save_w(word);  // of this word
    >      return;
    >    }
    >  comp = strcmp((*node)->word,word);
    >  if (comp==0 )
    >    {
    >      (*node)->count++;              // word already in tree
    >      return;
    >    }
    >  if (comp<0)
    >      enter(&(*node)->right,word);  // recursively try to enter word
    >  else                              // until a NULL is found
    >      enter(&(*node)->left,word);
    >}
    >
    >void print_tree(struct node *top)
    >{
    >  if (top == NULL)
    >      return;
    >  print_tree(top->left);
    >  printf("%s (%d)  ", top->word,top->count);
    >  print_tree(top->right);
    >}
    >
    >void print_tree_debug(struct node *top)
    >{
    >  if (top == NULL)
    >      return;
    >  printf("L ");                                // go left
    >  print_tree_debug(top->left);
    >  printf("[%s - %d]\n", top->word,top->count);
    >  printf("R ");                                // go right
    >  print_tree_debug(top->right);
    >  printf("U ");                                // go up
    >}
    >
    >int main(int argc, char *argv[])
    >{
    >  unsigned int i;
    >
    >  for (i=1; i<argc; i++)
    >      enter(&root,argv[i]);
    >
    >  printf("\n");
    >  print_tree(root);
    >  printf("\n");
    >
    >  printf("\n");
    >  print_tree_debug(root);
    >  printf("\n");
    >
    > return (0);
    >}[/color]
    
    
    <<Remove the del for email>>
    Barry Schwarz, Oct 12, 2005
    #9
  10. Foodbank

    Guest

    Barry Schwarz wrote:
    > On 11 Oct 2005 15:26:31 -0700, ""
    > <> wrote:
    >
    > snip
    >
    > >I've include my version of the example binary tree program.
    > >It simply builds a tree from the command line arguments.
    > >
    > >A key difference is a recursive function to enter a word
    > >onto the tree. It starts at the root and follows left/right
    > >pointers until it either finds the word already on the tree
    > >or finds a NULL. Calling enter() with a NULL will add a node
    > >with count=1 since adding a node means this is the first
    > >occurence.
    > >
    > >When the word is found to be already on the tree, we just need
    > >to increment the count.
    > >
    > >Also in the program are a pair of print routines, one to print
    > >all the words in the tree with their frequency and another
    > >that shows how the path through the binary tree.
    > >
    > >And you will, of course, want to add a routine to free the
    > >allocated memory.
    > >

    > snip
    >
    > >>
    Code:
    [/color]
    > >
    > >
    > >
    > >
    > >#include <stdio.h>
    > >#include <ctype.h>
    > >#include <string.h>
    > >#include <stdlib.h>
    > >
    > >//  gcc -g -I. c/foodbank.c
    > >
    > >struct node {
    > >  struct node    *left;              // tree to the left
    > >  struct node    *right;             // tree to the right
    > >  unsigned int   count;              // # of occurences...
    > >  char           *word;              // ...of this word
    > >};
    > >
    > >static struct node  *root = NULL;[/color]
    >
    > Since you pass root to every function that needs it, there is no need
    > for it to be at file scope.  This will prevent an unintended function
    > from modifying it.[/color]
    
    Where does it go? FWIW, I copied (and modified) this code out
    of the O'Reilly book "Practical C Programming" by Steve Oualline.
    I don't know enough to make a mistake that sophisticated.
    [color=blue]
    >[color=green]
    > >
    > >void memory_error(void)
    > >{
    > >  fprintf(stderr, "Error:Out of memory\n");
    > >  exit(8);[/color]
    >
    > EXIT_FAILURE would be more portable than 8.[/color]
    
    Ditto, didn't know there was such a constant.
    [color=blue][color=green]
    > >}
    > >
    > >char *save_w(char *string)         // copy string to heap
    > >{
    > >  char *new_string;
    > >  new_string = malloc((unsigned) (strlen(string)+1));
    > >  if (new_string == NULL)
    > >     memory_error();
    > >  strcpy(new_string,string);
    > >  return (new_string);
    > >}
    > >
    > >void enter(struct node **node, char *word)
    > >{
    > >  char          *save_w();[/color]
    >
    > Marginally incorrect and error prone.  save_w was defined above.  That
    > will serve as the prototype of any subsequent calls to the function.
    > If you are going to repeat a declaration, repeat it exactly.[/color]
    
    That one's partially my fault. The prototype is in the book,
    but it got inexplicably changed when I was modifying it.
    
    Thanks for pointing those out. I'm not a C programmer but
    occaisionally need to create C programs. I'm completely
    dependant on examples from books. Good to know that even
    the books aren't perfect.
    [color=blue]
    >[color=green]
    > >  int           comp;
    > >
    > >  if ((*node) == NULL)
    > >    {
    > >      (*node) = malloc(sizeof(struct node));
    > >      if ((*node) == NULL)
    > >          memory_error();
    > >      (*node)->left  = NULL;
    > >      (*node)->right = NULL;
    > >      (*node)->count = 1;             // new node = first occurence
    > >      (*node)->word  = save_w(word);  // of this word
    > >      return;
    > >    }
    > >  comp = strcmp((*node)->word,word);
    > >  if (comp==0 )
    > >    {
    > >      (*node)->count++;              // word already in tree
    > >      return;
    > >    }
    > >  if (comp<0)
    > >      enter(&(*node)->right,word);  // recursively try to enter word
    > >  else                              // until a NULL is found
    > >      enter(&(*node)->left,word);
    > >}
    > >
    > >void print_tree(struct node *top)
    > >{
    > >  if (top == NULL)
    > >      return;
    > >  print_tree(top->left);
    > >  printf("%s (%d)  ", top->word,top->count);
    > >  print_tree(top->right);
    > >}
    > >
    > >void print_tree_debug(struct node *top)
    > >{
    > >  if (top == NULL)
    > >      return;
    > >  printf("L ");                                // go left
    > >  print_tree_debug(top->left);
    > >  printf("[%s - %d]\n", top->word,top->count);
    > >  printf("R ");                                // go right
    > >  print_tree_debug(top->right);
    > >  printf("U ");                                // go up
    > >}
    > >
    > >int main(int argc, char *argv[])
    > >{
    > >  unsigned int i;
    > >
    > >  for (i=1; i<argc; i++)
    > >      enter(&root,argv[i]);
    > >
    > >  printf("\n");
    > >  print_tree(root);
    > >  printf("\n");
    > >
    > >  printf("\n");
    > >  print_tree_debug(root);
    > >  printf("\n");
    > >
    > > return (0);
    > >}[/color]
    > 
    > 
    > <<Remove the del for email>>[/color]
    , Oct 12, 2005
    #10
  11. Foodbank

    Foodbank Guest

    Thanks mensanator and everyone else who helped. I appreciate it. I'll
    try this out and see how things go.

    Regards,
    James
    Foodbank, Oct 12, 2005
    #11
  12. On 11 Oct 2005 21:06:57 -0700, ""
    <> wrote:

    >
    >Barry Schwarz wrote:
    >> On 11 Oct 2005 15:26:31 -0700, ""
    >> <> wrote:
    >>
    >> snip
    >>
    >> >I've include my version of the example binary tree program.
    >> >It simply builds a tree from the command line arguments.
    >> >
    >> >A key difference is a recursive function to enter a word
    >> >onto the tree. It starts at the root and follows left/right
    >> >pointers until it either finds the word already on the tree
    >> >or finds a NULL. Calling enter() with a NULL will add a node
    >> >with count=1 since adding a node means this is the first
    >> >occurence.
    >> >
    >> >When the word is found to be already on the tree, we just need
    >> >to increment the count.
    >> >
    >> >Also in the program are a pair of print routines, one to print
    >> >all the words in the tree with their frequency and another
    >> >that shows how the path through the binary tree.
    >> >
    >> >And you will, of course, want to add a routine to free the
    >> >allocated memory.
    >> >

    >> snip
    >>
    >> >>
    Code:
    >> >
    >> >
    >> >
    >> >
    >> >#include <stdio.h>
    >> >#include <ctype.h>
    >> >#include <string.h>
    >> >#include <stdlib.h>
    >> >
    >> >//  gcc -g -I. c/foodbank.c
    >> >
    >> >struct node {
    >> >  struct node    *left;              // tree to the left
    >> >  struct node    *right;             // tree to the right
    >> >  unsigned int   count;              // # of occurences...
    >> >  char           *word;              // ...of this word
    >> >};
    >> >
    >> >static struct node  *root = NULL;[/color]
    >>
    >> Since you pass root to every function that needs it, there is no need
    >> for it to be at file scope.  This will prevent an unintended function
    >> from modifying it.[/color]
    >
    >Where does it go? FWIW, I copied (and modified) this code out
    >of the O'Reilly book "Practical C Programming" by Steve Oualline.
    >I don't know enough to make a mistake that sophisticated.[/color]
    
    In this case, I would suggest it belongs in main.
    
    
    
    <<Remove the del for email>>
    Barry Schwarz, Oct 13, 2005
    #12
  13. Foodbank

    Guest

    Barry Schwarz wrote:
    > On 11 Oct 2005 21:06:57 -0700, ""
    > <> wrote:
    >
    > >
    > >Barry Schwarz wrote:
    > >> On 11 Oct 2005 15:26:31 -0700, ""
    > >> <> wrote:
    > >>
    > >> snip
    > >>
    > >> >I've include my version of the example binary tree program.
    > >> >It simply builds a tree from the command line arguments.
    > >> >
    > >> >A key difference is a recursive function to enter a word
    > >> >onto the tree. It starts at the root and follows left/right
    > >> >pointers until it either finds the word already on the tree
    > >> >or finds a NULL. Calling enter() with a NULL will add a node
    > >> >with count=1 since adding a node means this is the first
    > >> >occurence.
    > >> >
    > >> >When the word is found to be already on the tree, we just need
    > >> >to increment the count.
    > >> >
    > >> >Also in the program are a pair of print routines, one to print
    > >> >all the words in the tree with their frequency and another
    > >> >that shows how the path through the binary tree.
    > >> >
    > >> >And you will, of course, want to add a routine to free the
    > >> >allocated memory.
    > >> >
    > >> snip
    > >>
    > >> >>
    Code:
    > >> >
    > >> >
    > >> >
    > >> >
    > >> >#include <stdio.h>
    > >> >#include <ctype.h>
    > >> >#include <string.h>
    > >> >#include <stdlib.h>
    > >> >
    > >> >//  gcc -g -I. c/foodbank.c
    > >> >
    > >> >struct node {
    > >> >  struct node    *left;              // tree to the left
    > >> >  struct node    *right;             // tree to the right
    > >> >  unsigned int   count;              // # of occurences...
    > >> >  char           *word;              // ...of this word
    > >> >};
    > >> >
    > >> >static struct node  *root = NULL;
    > >>
    > >> Since you pass root to every function that needs it, there is no need
    > >> for it to be at file scope.  This will prevent an unintended function
    > >> from modifying it.[/color]
    > >
    > >Where does it go? FWIW, I copied (and modified) this code out
    > >of the O'Reilly book "Practical C Programming" by Steve Oualline.
    > >I don't know enough to make a mistake that sophisticated.[/color]
    >
    > In this case, I would suggest it belongs in main.[/color]
    
    Thanks.
    [color=blue]
    > 
    > 
    > 
    > <<Remove the del for email>>[/color]
    , Oct 13, 2005
    #13
  14. Foodbank

    Foodbank Guest

    Hey guys, I'm almost there, but getting a seg. fault. I have no idea
    why. I've commented where it's happening at the location that says:

    //*** SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0 ********

    As a refresher, this is the binary tree that counts words from a text
    file on the command line.

    Thank you in advance,
    Jim

    Code:
    
    #include <stdio.h>
    #include <malloc.h>
    struct tnode {			// specify the "shape" of a tnode structure
    	struct tnode *left;	// the left and right branch pointers
    	struct tnode *right;
    	int count;		// the word count as before
    	char *word;		// a pointer to the word
    } *root;			// declare the root pointer variable
    
    struct tnode **tree_search(struct tnode **, char *);
    void tree_stats(struct tnode *);
    int get_word(char *);
    
    int total_nodes, total_words, high;
    struct tnode *most_frequent;
    
    int main(int argc, char *argv[]) {
    	struct tnode **tpp;
    	char word_buff[100];	// the reusable word buffer
    	int i;
    	while(get_word(word_buff)) {
    		tpp = tree_search(&root, word_buff);
    		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    
    		if(*tpp!=NULL){
    			(*tpp)->count++;
    		}
    		else{
    			(*tpp)=malloc(sizeof(struct tnode));
    			(*tpp)->left=NULL;
    			(*tpp)->right=NULL;
    			(*tpp)->count=1;
    			(*tpp)->word=strdup(word_buff);
    		}
    
    	}
    	tree_stats(root);
    	printf("total_nodes %d\n", total_nodes);
    	printf("total_words %d\n", total_words);
    	if(most_frequent)
    		printf("most frequent word <%s> count is %d\n",
    			most_frequent->word, most_frequent->count);
    	for(i = 1; i < argc; i++) {
    		tpp = tree_search(&root, argv[i]);
    		if((*tpp) == NULL)
    			printf("%s is NOT in the tree\n", argv[i]);
    		else
    			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    	}
    	return(0);
    }
    
    // binary tree search returning a pointer to the pointer leading to a
    hit
    struct tnode **tree_search(struct tnode **tpp, char *w) {
    	/***** CODE TO DO THE BINARY SRCH *****/
    	int cmp;
    
    	while(*tpp){
    		cmp=strcmp(w,(*tpp)->word);
       //*****SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0  ********
    			if (cmp>0) {
    				tpp=(*tpp)->right;
    				}
    			else if (cmp<0){
    				tpp=(*tpp)->left;
    				}
    			else if (cmp==0){
    				break;
    		    }
    }
    
    
    return(tpp);
    }
    
    // gather stats to check tree correctness
    void tree_stats(struct tnode *tp) {
    	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    if(tp=NULL)
    	return;
    	total_words+=tp->count;
    	total_nodes++;
    	if(tp->count > high){
    		high=tp->count;
    		most_frequent=tp;
    	}
    }
    
    #include <ctype.h>
    /* Leave this routine EXACTLY as it stands */
    int get_word(char *s) {
    	int c;
    	do {
    		c = getchar();
    		if(c == EOF)
    			return(0);
    	} while(!isalpha(c) && !isdigit(c));
    	do {
    		if(isupper(c))
    			c = tolower(c);
    		*s++ = c;
    		c = getchar();
    	} while(isalpha(c) || isdigit(c));
    	*s = 0;
    	return(1);
    }
    
    Foodbank, Oct 13, 2005
    #14
  15. Foodbank

    Guest

    Foodbank wrote:
    > Hey guys, I'm almost there, but getting a seg. fault. I have no idea
    > why.


    I think a seg. fault means you have a bad pointer.

    I thought, perhaps, someone else would have posted the answer by now,
    but since that hasn't happened, I'll make a stab at it. Keep in mind
    I'm not an expert, so what follows are guesses (hopefully educated).

    > I've commented where it's happening at the location that says:
    >
    > //*** SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0 ********
    >
    > As a refresher, this is the binary tree that counts words from a text
    > file on the command line.
    >
    > Thank you in advance,
    > Jim
    >
    >
    Code:
    >
    > #include <stdio.h>
    > #include <malloc.h>
    > struct tnode {			// specify the "shape" of a tnode structure
    > 	struct tnode *left;	// the left and right branch pointers
    > 	struct tnode *right;
    > 	int count;		// the word count as before
    > 	char *word;		// a pointer to the word
    > } *root;			// declare the root pointer variable[/color]
    
    Root HAS to start out as a NULL pointer. I don't know if the
    preceeding initializes the pointer or not. I think you either
    need to initialize it here by
    
    } *root = NULL;
    
    assuming that's correct usage or else set it to null at the
    start of main()
    
    root = NULL
    
    [color=blue]
    >
    > struct tnode **tree_search(struct tnode **, char *);
    > void tree_stats(struct tnode *);
    > int get_word(char *);
    >
    > int total_nodes, total_words, high;
    > struct tnode *most_frequent;
    >
    > int main(int argc, char *argv[]) {
    > 	struct tnode **tpp;
    > 	char word_buff[100];	// the reusable word buffer
    > 	int i;
    > 	while(get_word(word_buff)) {
    > 		tpp = tree_search(&root, word_buff);
    > 		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    >
    > 		if(*tpp!=NULL){
    > 			(*tpp)->count++;
    > 		}
    > 		else{
    > 			(*tpp)=malloc(sizeof(struct tnode));
    > 			(*tpp)->left=NULL;
    > 			(*tpp)->right=NULL;
    > 			(*tpp)->count=1;
    > 			(*tpp)->word=strdup(word_buff);
    > 		}
    >
    > 	}
    > 	tree_stats(root);
    > 	printf("total_nodes %d\n", total_nodes);
    > 	printf("total_words %d\n", total_words);
    > 	if(most_frequent)
    > 		printf("most frequent word <%s> count is %d\n",
    > 			most_frequent->word, most_frequent->count);
    > 	for(i = 1; i < argc; i++) {
    > 		tpp = tree_search(&root, argv[i]);
    > 		if((*tpp) == NULL)
    > 			printf("%s is NOT in the tree\n", argv[i]);
    > 		else
    > 			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    > 	}
    > 	return(0);
    > }
    >
    > // binary tree search returning a pointer to the pointer leading to a
    > hit
    > struct tnode **tree_search(struct tnode **tpp, char *w) {
    > 	/***** CODE TO DO THE BINARY SRCH *****/
    > 	int cmp;
    >
    > 	while(*tpp){[/color]
    
    The other thing I don't know is whether NULL pointers evaluate
    to FALSE. If not, then you need to explicitly test for NULL in
    the while statement.
    [color=blue]
    > 		cmp=strcmp(w,(*tpp)->word);
    >    //*****SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0  ********
    > 			if (cmp>0) {
    > 				tpp=(*tpp)->right;
    > 				}
    > 			else if (cmp<0){
    > 				tpp=(*tpp)->left;
    > 				}
    > 			else if (cmp==0){
    > 				break;
    > 		    }
    > }
    >
    >
    > return(tpp);
    > }
    >
    > // gather stats to check tree correctness
    > void tree_stats(struct tnode *tp) {
    > 	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    > if(tp=NULL)
    > 	return;
    > 	total_words+=tp->count;
    > 	total_nodes++;
    > 	if(tp->count > high){
    > 		high=tp->count;
    > 		most_frequent=tp;
    > 	}
    > }
    >
    > #include <ctype.h>
    > /* Leave this routine EXACTLY as it stands */
    > int get_word(char *s) {
    > 	int c;
    > 	do {
    > 		c = getchar();
    > 		if(c == EOF)
    > 			return(0);
    > 	} while(!isalpha(c) && !isdigit(c));
    > 	do {
    > 		if(isupper(c))
    > 			c = tolower(c);
    > 		*s++ = c;
    > 		c = getchar();
    > 	} while(isalpha(c) || isdigit(c));
    > 	*s = 0;
    > 	return(1);
    > }
    > 
    , Oct 13, 2005
    #15
  16. Foodbank

    Flash Gordon Guest

    wrote:
    > Foodbank wrote:
    >
    >>Hey guys, I'm almost there, but getting a seg. fault. I have no idea
    >>why.

    >
    > I think a seg. fault means you have a bad pointer.


    Or overrunning the end of a buffer. Or a number of other things.

    > I thought, perhaps, someone else would have posted the answer by now,


    I didn't because I could see it retained a number of errors I had
    previously (and not many days before) posted corrections to. I can't
    remember if it was the same person, but it was obviously based on the
    same homework question. However, since someone else is showing some
    interest I decided to provide you with some feedback on lots of problems
    with it to help you learn what to avoid. I am almost certain there are
    further problems I have not pointed out.

    > but since that hasn't happened, I'll make a stab at it. Keep in mind
    > I'm not an expert, so what follows are guesses (hopefully educated).
    >
    >>I've commented where it's happening at the location that says:
    >>
    >>//*** SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0 ********
    >>
    >>As a refresher, this is the binary tree that counts words from a text
    >>file on the command line.
    >>
    >>Thank you in advance,
    >>Jim
    >>
    >>
    Code:
    >>
    >>#include <stdio.h>
    >>#include <malloc.h>[/color][/color]
    
    malloc.h is not a standard header, the standard header is stdlib.h
    [color=blue][color=green]
    >>struct tnode {			// specify the "shape" of a tnode structure
    >>	struct tnode *left;	// the left and right branch pointers
    >>	struct tnode *right;
    >>	int count;		// the word count as before
    >>	char *word;		// a pointer to the word
    >>} *root;			// declare the root pointer variable[/color]
    > 
    > Root HAS to start out as a NULL pointer. I don't know if the
    > preceeding initializes the pointer or not. I think you either
    > need to initialize it here by
    > 
    > } *root = NULL;[/color]
    
    It is declared at file scope and therefor will therefore be initialised 
    to a null pointer if no explicit initialisation is provided.
    [color=blue]
    > assuming that's correct usage or else set it to null at the
    > start of main()
    > 
    > root = NULL[/color]
    
    Not needed, your initialisation syntax was correct.
    [color=blue][color=green]
    >>struct tnode **tree_search(struct tnode **, char *);[/color][/color]
    
    All this use of pointers to pointers is confusing and pointless.
    
    struct tnode *tree_search(struct tnode *, char *);
    
    [color=blue][color=green]
    >>void tree_stats(struct tnode *);
    >>int get_word(char *);
    >>
    >>int total_nodes, total_words, high;
    >>struct tnode *most_frequent;
    >>
    >>int main(int argc, char *argv[]) {
    >>    struct tnode **tpp;[/color][/color]
    
         struct tnode *tpp;
    [color=blue][color=green]
    >>    char word_buff[100];	// the reusable word buffer[/color][/color]
    
    Don't use // syle comments on news groups, they won't survive line wrapping.
    [color=blue][color=green]
    >>    int i;
    >>    while(get_word(word_buff)) {
    >>        tpp = tree_search(&root, word_buff);[/color][/color]
    
    Don't use tabs on code posted to news groups. You have no idea how they 
    will be rendered and sometimes they even get stripped. I've replaces 
    them with spaces.
    
    You are not trying to modify the value of root, so why pass it's address?
             tpp = tree_search(root, word_buff);
    [color=blue][color=green]
    >>        /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    >>
    >>        if(*tpp!=NULL){
    >>            (*tpp)->count++;
    >>        }
    >>        else{
    >>            (*tpp)=malloc(sizeof(struct tnode));[/color][/color]
    
    Why the parenthesis? Also, why yous sizeof(type) when you can use sizeof 
    object and reduce the chance of error?
                   tpp=malloc(sizeof *tpp);
    With my changes you also need to remove a number of other dereferences.
    [color=blue][color=green]
    >>            (*tpp)->left=NULL;
    >>            (*tpp)->right=NULL;
    >>            (*tpp)->count=1;
    >>            (*tpp)->word=strdup(word_buff);[/color][/color]
    
    strdup is not a standard function.
    
    Also you need to add this node you've just created to your tree. It does 
    not happen by magic.
    [color=blue][color=green]
    >>        }
    >>
    >>    }
    >>    tree_stats(root);
    >>    printf("total_nodes %d\n", total_nodes);
    >>    printf("total_words %d\n", total_words);
    >>    if(most_frequent)
    >>    printf("most frequent word <%s> count is %d\n",
    >>           most_frequent->word, most_frequent->count);
    >>    for(i = 1; i < argc; i++) {
    >>        tpp = tree_search(&root, argv[i]);
    >>        if((*tpp) == NULL)
    >>            printf("%s is NOT in the tree\n", argv[i]);
    >>        else
    >>            printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    >>    }
    >>    return(0);[/color][/color]
    
    You don't need parenthesis here, return is not a function.
           return 0;[color=blue][color=green]
    >>}
    >>
    >>// binary tree search returning a pointer to the pointer leading to a
    >>hit[/color][/color]
    
    See what I meant about // comments not surviving line wrapping?
    [color=blue][color=green]
    >>struct tnode **tree_search(struct tnode **tpp, char *w) {
    >>    /***** CODE TO DO THE BINARY SRCH *****/
    >>    int cmp;
    >>
    >>    while(*tpp){[/color]
    > 
    > The other thing I don't know is whether NULL pointers evaluate
    > to FALSE. If not, then you need to explicitly test for NULL in
    > the while statement.[/color]
    
    You don't need to compare against NULL, although some people consider it 
    to be better style.
    [color=blue][color=green]
    >>        cmp=strcmp(w,(*tpp)->word);
    >>   //*****SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0  ********[/color][/color]
    
    Then you have a problem building your tree.
    [color=blue][color=green]
    >>        if (cmp>0) {
    >>            tpp=(*tpp)->right;
    >>        }
    >>        else if (cmp<0){
    >>            tpp=(*tpp)->left;
    >>				}
    >>        else if (cmp==0){
    >>            break;
    >>        }
    >>    }
    >>
    >>    return(tpp);[/color][/color]
    
    Again, no need for the parenthesis.
           return(tpp);
    [color=blue][color=green]
    >>}
    >>
    >>// gather stats to check tree correctness
    >>void tree_stats(struct tnode *tp) {
    >>    /***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    >>if(tp=NULL)
    >>    return;
    >>    total_words+=tp->count;
    >>    total_nodes++;
    >>    if(tp->count > high){
    >>        high=tp->count;
    >>        most_frequent=tp;
    >>    }[/color][/color]
    
    Functions modifying globals are horrible things. There are many far 
    better solutions.
    [color=blue][color=green]
    >>}
    >>
    >>#include <ctype.h>
    >>/* Leave this routine EXACTLY as it stands */
    >>int get_word(char *s) {
    >>    int c;
    >>    do {
    >>        c = getchar();
    >>        if(c == EOF)
    >>            return(0);
    >>    } while(!isalpha(c) && !isdigit(c));
    >>    do {
    >>        if(isupper(c))
    >>            c = tolower(c);
    >>        *s++ = c;[/color][/color]
    
    No protection against overflowing your buffer. Very bad.
    [color=blue][color=green]
    >>        c = getchar();
    >>    } while(isalpha(c) || isdigit(c));
    >>    *s = 0;
    >>    return(1);
    >>}
    >>

    --
    Flash Gordon
    Living in interesting times.
    Although my email address says spam, it is real and I read it.
    Flash Gordon, Oct 13, 2005
    #16
  17. On 12 Oct 2005 19:46:00 -0700, "Foodbank" <>
    wrote:

    >Hey guys, I'm almost there, but getting a seg. fault. I have no idea
    >why. I've commented where it's happening at the location that says:


    This should not be your real code. It doesn't compile. Are you
    ignoring the warnings? If you don't see the warnings, up the warning
    level of your compiler.

    >
    >//*** SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0 ********
    >
    >As a refresher, this is the binary tree that counts words from a text
    >file on the command line.
    >
    >Thank you in advance,
    >Jim
    >
    >
    Code:
    >
    >#include <stdio.h>
    >#include <malloc.h>[/color]
    
    Not a standard header.  malloc() is in stdlib.h.  You need string.h
    and ctype.h.
    [color=blue]
    >struct tnode {			// specify the "shape" of a tnode structure
    >	struct tnode *left;	// the left and right branch pointers
    >	struct tnode *right;
    >	int count;		// the word count as before
    >	char *word;		// a pointer to the word
    >} *root;			// declare the root pointer variable[/color]
    
    root is initialized by default to NULL.
    [color=blue]
    >
    >struct tnode **tree_search(struct tnode **, char *);
    >void tree_stats(struct tnode *);
    >int get_word(char *);
    >
    >int total_nodes, total_words, high;
    >struct tnode *most_frequent;
    >
    >int main(int argc, char *argv[]) {
    >	struct tnode **tpp;
    >	char word_buff[100];	// the reusable word buffer
    >	int i;
    >	while(get_word(word_buff)) {
    >		tpp = tree_search(&root, word_buff);
    >		/****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
    >
    >		if(*tpp!=NULL){
    >			(*tpp)->count++;
    >		}
    >		else{
    >			(*tpp)=malloc(sizeof(struct tnode));
    >			(*tpp)->left=NULL;
    >			(*tpp)->right=NULL;
    >			(*tpp)->count=1;
    >			(*tpp)->word=strdup(word_buff);[/color]
    
    Not a standard function.
    [color=blue]
    >		}
    >
    >	}
    >	tree_stats(root);
    >	printf("total_nodes %d\n", total_nodes);
    >	printf("total_words %d\n", total_words);
    >	if(most_frequent)
    >		printf("most frequent word <%s> count is %d\n",
    >			most_frequent->word, most_frequent->count);
    >	for(i = 1; i < argc; i++) {
    >		tpp = tree_search(&root, argv[i]);
    >		if((*tpp) == NULL)
    >			printf("%s is NOT in the tree\n", argv[i]);
    >		else
    >			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
    >	}
    >	return(0);
    >}
    >
    >// binary tree search returning a pointer to the pointer leading to a
    >hit
    >struct tnode **tree_search(struct tnode **tpp, char *w) {
    >	/***** CODE TO DO THE BINARY SRCH *****/
    >	int cmp;
    >
    >	while(*tpp){
    >		cmp=strcmp(w,(*tpp)->word);
    >   //*****SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0  ********[/color]
    
    Do you expect your compiler to parse this as / /*... (divide followed
    by start of comment) or // *... (one line comment)?  Don't use //
    comments for posting.  If the comment overflows the line in your
    newsreader, others cannot assemble your code.
    [color=blue]
    >			if (cmp>0) {
    >				tpp=(*tpp)->right;[/color]
    
    tpp is a pointer to pointer to struct.  (*tpp)->right is a pointer to
    struct.  The two are not compatible for implicit conversion.
    [color=blue]
    >				}
    >			else if (cmp<0){
    >				tpp=(*tpp)->left;
    >				}
    >			else if (cmp==0){
    >				break;
    >		    }
    >}
    >
    >
    >return(tpp);
    >}
    >
    >// gather stats to check tree correctness
    >void tree_stats(struct tnode *tp) {
    >	/***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
    >if(tp=NULL)[/color]
    
    You probably meant == here.
    [color=blue]
    >	return;
    >	total_words+=tp->count;
    >	total_nodes++;
    >	if(tp->count > high){
    >		high=tp->count;
    >		most_frequent=tp;
    >	}
    >}
    >
    >#include <ctype.h>
    >/* Leave this routine EXACTLY as it stands */
    >int get_word(char *s) {
    >	int c;
    >	do {
    >		c = getchar();
    >		if(c == EOF)
    >			return(0);
    >	} while(!isalpha(c) && !isdigit(c));
    >	do {
    >		if(isupper(c))
    >			c = tolower(c);
    >		*s++ = c;
    >		c = getchar();
    >	} while(isalpha(c) || isdigit(c));
    >	*s = 0;
    >	return(1);
    >}
    >



    <<Remove the del for email>>
    Barry Schwarz, Oct 14, 2005
    #17
  18. Foodbank

    Foodbank Guest

    Hi everyone,

    Just wanted to say thanks for the help on this one. Finally got it
    working.

    Take care,
    James
    Foodbank, Oct 15, 2005
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,078
  2. sharan
    Replies:
    4
    Views:
    670
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    814
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    673
    CBFalconer
    Oct 30, 2007
  5. Bogdan

    Binary tree search vs Binary search

    Bogdan, Oct 18, 2010, in forum: C Programming
    Replies:
    22
    Views:
    3,023
    Michael Angelo Ravera
    Oct 21, 2010
Loading...

Share This Page