K&R binary tree example using tsearch? 
Author Message
 K&R binary tree example using tsearch?

I'm trying to understand how tsearch can be used with the K&R binary tree
example. Where have I gone wrong in the following attempt?

Thanks, Tom

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <search.h>

struct tnode {
  char *word;
  int count;

Quote:
};

#define MAXWORD 20

void tprint(const void *node, VISIT time, const int lvl);
void nprint(struct tnode *node);
int tcompare(const void *s1, const void *s2);
int getword(char *, int);

main()
{
  struct tnode *root = NULL;
  struct tnode *srchret;
  struct tnode *srchkey;
  char word[MAXWORD];

  while (getword(word,MAXWORD) != EOF)
    if (isalpha(word[0])) {
      srchkey = (struct tnode *) malloc(sizeof(struct tnode));
      srchkey->count = 1;
      srchkey->word = strdup(word);
      srchret = tfind(srchkey, (void *) root, tcompare);
      if (srchret == NULL)
 printf("did not find %s\n", srchkey->word);
      srchret = tsearch(srchkey, (void **) &root, tcompare);
      printf("srchret = ");
      nprint(srchret);
      printf("srchkey = ");
      nprint(srchkey);
      printf("root    = ");
      nprint(root);
      srchret = tfind(srchkey, (void *) root, tcompare);
      if (srchret == NULL)
 printf("still did not find %s\n", srchkey->word);
    }
  printf("VISIT: 0=preorder, 1=postorder, 2=endorder, 3=leaf\n");
  twalk((void *) root, tprint);
  return 0;

Quote:
}

void tprint(const void *p, VISIT time, const int lvl)
{
  printf("VISIT = %d, lvl = %d ", time, lvl);
  nprint((struct tnode *) p);

Quote:
}

void nprint(struct tnode *node)
{
  printf("0x%08x 0x%08x 0x%08x", node, node->count, node->word);
  if (node->word)
    printf(" %s\n", node->word);
  else
    printf("\n");

Quote:
}

int tcompare(const void *s1, const void *s2)
{
  struct tnode *node1 = (struct tnode *) s1;
  struct tnode *node2 = (struct tnode *) s2;

  printf("node1   = ");
  nprint(node1);
  printf("node2   = ");
  nprint(node2);
  return strcmp(node1->word, node2->word);

Quote:
}

int getword (char *word, int lim)
{
  int c;
  char *w = word;

  while (isspace(c = getchar()))
    ;
  if(c != EOF)
    *w++ = (char) c;
  if (!isalpha(c)) {
    *w = NULL;
    return c;
  }
  for (; --lim > 0; w++)
    if(!isalnum(*w = (char) getchar())) {
      ungetc(*w, stdin);
      break;
    }
  *w = NULL;
  return word[0];

Quote:
}



Fri, 07 Nov 2003 05:20:28 GMT  
 K&R binary tree example using tsearch?

Quote:

> I'm trying to understand how tsearch can be used with the K&R binary tree
> example. Where have I gone wrong in the following attempt?

> Thanks, Tom

Hi Tom, the functions you use are not part of the c standard. I assume
your implementation is the same as the one I have (XPG).
First, you need to realize that the binary tree has an internal (and
private) structure that looks something like that:

struct bnode{
  void *data;
  struct bnode left;
  struct bnode right;
  /* what ever else */

Quote:
};

When tsearch needs to insert a new entry in the tree it allocates
one of these on the heap and returns a pointer to it. NOT a pointer
to the data! The same is true for find.
In order to access the data you need to dereference the returned
pointer twice. This works only because void *data is the first entry
in struct bnode. I'm not so sure about the legality though.

I've removed the useless casts of your code and redefined the type of
some variables.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>

struct tnode {
  char *word;
  int count;

Quote:
};

#define MAXWORD 20

void tprint(const void *node, VISIT time, const int lvl);
void nprint(const struct tnode *node);
int tcompare(const void *s1, const void *s2);
int getword(char *, int);

int main(void){

  void *root = NULL;
  struct tnode **srchret;
  struct tnode *srchkey;
  char word[MAXWORD];

  while (getword(word,MAXWORD) != EOF){
    if (isalpha(word[0])) {
      srchkey = malloc(sizeof *srchkey);
      /* you need to check for failure of malloc here */
      srchkey->count = 1;
      srchkey->word = strdup(word);
      /* strdup is non standard and can fail */
      srchret =  tfind(srchkey, &root, tcompare);
      if (srchret == NULL){
        printf("did not find %s\n", srchkey->word);
        srchret = tsearch(srchkey, &root, tcompare);
        if (srchret == NULL){
          printf("couldn't insert %s\n", srchkey->word);
          exit(0);
        }
      }else{
        /* this is what i think your count is for ? */
        (*srchret)->count++;
      }
      printf("srchret = ");
      nprint(*srchret);
    }
  }

  printf("VISIT: 0=preorder, 1=postorder, 2=endorder, 3=leaf\n");
  twalk(root, tprint);
  return 0;

Quote:
}

void tprint(const void *p, VISIT time, int lvl)
{
  struct tnode *node=*(void **) p;
  printf("VISIT = %d, lvl = %d ", time, lvl);
  nprint(node);

Quote:
}

void nprint(const struct tnode *node)
{
  printf("0x%08x 0x%08x 0x%08x", node, node->count, node->word);
  if (node->word)
    printf(" %s\n", node->word);
  else
    printf("\n");

Quote:
}

int tcompare(const void *s1, const void *s2)
{
  const struct tnode *node1 = s1;
  const struct tnode *node2 = s2;

  printf("node1   = ");
  nprint(node1);
  printf("node2   = ");
  nprint(node2);
  return strcmp(node1->word, node2->word);

Quote:
}

int getword (char *word, int lim)
{
  int c;
  char *w = word;

  while (isspace(c = getchar()))
    ;
  if(c != EOF)
    *w++ = (char) c;
  if (!isalpha(c)) {
    *w = NULL;
    return c;
  }
  for (; --lim > 0; w++)
    if(!isalnum(*w = (char) getchar())) {
      ungetc(*w, stdin);
      break;
    }
  *w = NULL;
  return word[0];

Quote:
}



Fri, 07 Nov 2003 08:00:49 GMT  
 K&R binary tree example using tsearch?

Quote:

> First, you need to realize that the binary tree has an internal (and
> private) structure that looks something like that:

> struct bnode{
>   void *data;
>   struct bnode left;
>   struct bnode right;

These should both be struct bnode *.

Quote:
>   /* what ever else */
> };

--
"You call this a *C* question? What the hell are you smoking?" --Kaz


Fri, 07 Nov 2003 08:36:37 GMT  
 K&R binary tree example using tsearch?

Quote:


> > First, you need to realize that the binary tree has an internal (and
> > private) structure that looks something like that:

> > struct bnode{
> >   void *data;
> >   struct bnode left;
> >   struct bnode right;

> These should both be struct bnode *.

Thanks for the correction, I think I need some coffee!
Tobias.


Fri, 07 Nov 2003 08:47:43 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Proposal: alt.binaries.examples.vb4 , alt.binaries.examples.vcpp , alt.binaries.examples.java

2. Binary Search Tree using dynamic memory allocation (URGENT request for example)

3. AVL tree (Binary Balanced tree) using C or C++

4. tsearch example

5. Knuth (6.2.2) Algorithm T- tsearch example

6. binary tree & symbol table modifications

7. heaps using linked binary tree

8. Need code for simple Phone book using Binary Trees

9. Create a binary tree using array

10. binary trees implementation using file(s)

11. tsearch & tdelete

12. Long Binary Datatype Using DAO & JET

 

 
Powered by phpBB® Forum Software