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

 
#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); 


} 

: 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

Can't do binary searches on text files -- they contain random-length records, so there is no way to determine beforehand where the beginning of a randomly chosen record starts. And that is probably why the program uses linked lists -- read the file into memory and then you can do some sort of in-memory searching.

Thanks for the reply Stober. However, according to my book, it is possible to do it with a text file, but it's not very reassuring that someone like you with alot more coding experience than me says it can't be done :) ).

Thanks,
James

: Thanks for the reply Stober. However, according to my book, it is possible to do it with a text file, but it's not very reassuring that someone like you with alot more coding experience than me says it can't be done :) ).
:
: Thanks,
: James
:

maybe you misread or misunderstood your book.

: Thanks for the reply Stober. However, according to my book, it is possible to do it with a text file, but it's not very reassuring that someone like you with alot more coding experience than me says it can't be done :) ).
:
: Thanks,
: James
:


As stober says, you must read the whole file and place it in memory.
To to a binary search, the data must be sorted. So if the file isn't sorted, you must add the items to the linked list so that it becomes sorted, for example in alphabetic order.

A binary tree might be more efficient than a regular linked list, I don't know. You must balance it all the time, which make take a few extra ticks. Hash tables are usually the most efficient when dealing with large amounts of data.

This message was edited by Vilanye at 2005-10-10 15:12:21

---

: Thanks for the reply Stober. However, according to my book, it is possible to do it with a text file, but it's not very reassuring that someone like you with alot more coding experience than me says it can't be done :) ).
:
: Thanks,
: James
:


You can do it with a binary tree, but it might not make sense. Read a line(perhaps more then one line if it makes sense to do it), add that line to the tree, rinse and repeat. It would make sense to do it this way if it were numerical values,single word, or in a format that would lend itself to a sorting routine.

Here is a text file with integral values:

5
76
455
3
77
435
76
768
67
676
22
45
7
8
99
345422


You could create a binary tree with that. If it were random sentences, you could still build a tree with the data, but wouldn't make as much sense.

In short, if there is a way to determine which object/struct is less then or equal to, you can put it in a binary tree. Where the data comes from is irrelevant.

If you have so much data that it can not be stored in memory, you can use external storage, such as B-trees and manipulate them as if they were in a tree. This isn't a good option for smaller amounts of data, especially if it is accessed often, as disk IO is slow.
Just my 2 bits

Thanks for the replies so far guys. I've tried to make an attempt at the first part I need to program. How's it look?

Hi,


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

 
#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, it's 
               supposed to increment the count if not NULL I believe
               

        } 

: Thanks for the replies so far guys. I've tried to make an attempt at the first part I need to program. How's it look?
:
: Hi,
:
:
: 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
:
:
:

 
: #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, it's 
:                supposed to increment the count if not NULL I believe
:                
: 
:         } 
: 

:
:

Why do you use pointer-to-pointer? It doesn't make any sence.

So that the tree_search() function returns a pointer to the pointer leading to the node found by the search.

: So that the tree_search() function returns a pointer to the pointer leading to the node found by the search.
:

And why can't it return a pointer?

You're gonna have to call my book manufacturer for that one :) That's how it's set up in the book and I'm trying to stay on task with their exercises.

Your book suckz man, your coding is too complex,
find another book that could explain the process better
and without pointers to pointers :P.

: Your book suckz man, your coding is too complex,
: find another book that could explain the process better
: and without pointers to pointers :P.
:
:

I agree, I see that you are using that get_word() function you used in that linked-list program. It is from the book? As I pointed out then, isalpha() calls isdigit(), no need to call isdigit() one extra time.
An author of a C book should know this.

Hi again,

Yeah, the getword is from the book.

Anyways, I've made a lot of progress, but now I'm 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

#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 
	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 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);
}

: Hi again,
:
: Yeah, the getword is from the book.
:
: Anyways, I've made a lot of progress, but now I'm 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
:
:

: 
: #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 
: 	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 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);
: }
: 

:

I do not have time to read your whole code; however I noticed a mistake here:

: // binary tree search returning a pointer to the pointer leading to 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;
tpp is of type struct tnode ** but you're assigning a
struct tnode * value to it
: 				}
: 			else if (cmp<0){
: 				tpp=(*tpp)->left;
same thing
: 				}
: 			else if (cmp==0){
: 				break;
: 		    }
: }
: 
: 
: return(tpp);
: }

Take care, Steph.

Thanks for the reply Steph. However, I'm not sure how I should notate the double pointer. Any input?

Thanks,
James

: Thanks for the reply Steph. However, I'm not sure how I should notate the double pointer. Any input?
:
: Thanks,
: James
:


Then don't use it, because it still makes no sence.

How about some information I can use Lundin, haha. I'm trying to stay consistent with the book and that's how they have it, using double pointers. Anyone?

Thanks,
James

: How about some information I can use Lundin, haha. I'm trying to stay consistent with the book and that's how they have it, using double pointers. Anyone?
:
: Thanks,
: James
:

You still haven't told why you are using pointer-to-pointer. You just blindly do as they say in the book without reading the reason why? That function you wrote has absolutly no use for them.

I believe the first pointer points to the root and the next (double) pointer points to the left or right branch of the tree.

: I believe the first pointer points to the root and the next (double) pointer points to the left or right branch of the tree.
:

No it doesn't. As I see it, the only reason why they would use a double pointer is because they expect the function to dynamicly allocate something, then you would need a double pointer. Here is an example:

http://www.programmersheaven.com/c/MsgBoard/read.asp?Board=586&MsgID=312054&Setting=A9999F0001

: I believe the first pointer points to the root and the next (double) pointer points to the left or right branch of the tree.
:

It seems you did not understand something about pointers (the notation or something else). You should read or reread how to manipulate pointers before using trees. When you've got such a declaration:

struct node
{
struct node *left,*right;
int count;
char *word;
} tree;

, tree is a structure and the child nodes are accessed this way:

tree.left
tree.right

and their members this way:

tree.left->count
tree.right->word

Take care, Steph.

Here's the code u need to complete the god dam binary tree.

typedef struct nodeT {
        int key;
        struct nodeT *left,*right;
}nodeT,*treeT;
   
   

treeT NewTree(void) {//Funo para criar uma nova arvore
      treeT arv;
      arv = NULL;
      return(arv);     
}


treeT NewNode(int key) {//Funo para criar um novo n
  treeT arv = New(treeT);    
  arv->key = key;
  arv->left = NULL;
  arv->right = NULL;

  return(arv);
}
 


treeT insert(treeT arv, int key) {//Funo para inserir um novo n
  
  if (arv == NULL) {
    return(NewNode(key));
  }
  else {
    
    if (key <= arv->key) arv->left = insert(arv->left, key);
    else arv->right = insert(arv->right, key);

    return(arv); 
  }
}

Cheers, I've made this code a year ago, on a class of algorithms and data structures.

Hey guys,

Sorry to revive this damn thread :) but I got it working. Thanks for the help once again.

James

: Hi again,
:
: Yeah, the getword is from the book.
:
: Anyways, I've made a lot of progress, but now I'm 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
:
:

: 
: #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 
: 	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 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);
: }
: 

:
Hi,
I have a C++ Binary Tree library at www.5trees.com. In there you can use the tree class to count words in a file (and for many other things). The tree library took a couple of years to write and it has a lot of AVL code within. I have used it to write translators so counting words in a file is easy by comparison. Good Luck, Ben.