Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Binary Trees

Chevy05Chevy05 Posts: 39Member
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
#include
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
", total_nodes);
printf("total_words %d
", total_words);
if(most_frequent)
printf("most frequent word <%s> count is %d
",
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
", argv[i]);
else
printf("<%s> count is %d
", 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
/* 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);


}


[/code]

«13

Comments

  • stoberstober Posts: 9,765Member ✭✭✭
    : 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

    [blue]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.[/blue]




  • Chevy05Chevy05 Posts: 39Member
    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
  • stoberstober Posts: 9,765Member ✭✭✭
    : 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.
  • LundinLundin Posts: 3,711Member
    : 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.
  • VilanyeVilanye Posts: 684Member
    [b][red]This message was edited by Vilanye at 2005-10-10 15:12:21[/red][/b][hr]
    : 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.
    [italic][blue]Just my 2 bits[/blue][/italic]



  • Chevy05Chevy05 Posts: 39Member
    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


    [code]
    #include
    #include
    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


    }
    [/code]





  • LundinLundin Posts: 3,711Member
    : 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
    :
    :
    : [code]
    : #include
    : #include
    : 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
    :
    :
    : }
    : [/code]
    :
    :

    Why do you use pointer-to-pointer? It doesn't make any sence.
  • Chevy05Chevy05 Posts: 39Member
    So that the tree_search() function returns a pointer to the pointer leading to the node found by the search.
  • LundinLundin Posts: 3,711Member
    : 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?
  • Chevy05Chevy05 Posts: 39Member
    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.
«13
Sign In or Register to comment.