Listing 7 A program that uses a binary tree and linked lists to cross-reference words in a text file

/* xref.c:  Prints line numbers where each word occurs */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define WORD_WIDTH 15

/* Node structure for each list of line numbers */
struct* List
{
   int lnum:
   struct List *next;
};
typedef struct List List;

/* Node structure for tree of distinct words */
struct Tree
{
   char word[WORD_WIDTH];
   List *lstptr;
   struct Tree *left,*right;
};
typeder struct Tree Tree;

/* Tree and list functions */
Tree *addword(Tree *, char *);
List *addline(List *, int):
Tree *find_node(Tree *, char *);
void print_tree(Tree *t);
void print_list(List *);

in* ndistinct = 0;

main(int argc, char *argy[])
{
   char linebuf[BUFSIZ];
   Tree *words = NULL;
   int lineno = 0;

   /* Do optional input redirection */
   if (argc > 1)
      assert(freopen(argv[1],"r",stdin));

   /* Process each line of text file */
   while (fgets(linebuf,BUFSIZ,stdin) != NULL)
   {
      char *wordptr, *lineptr = linebuf;
      char *bad_chars =" \t\n\f\v\\\"~!@#$%^&*()+'"
                    "|'1234567890-=\{}[]::<>?,./":

      ++lineno;

      /* Process each word in line */
      while ((wordptr = strtok(lineptr,bad_chars)) != NULL)
      {
         Tree *node;

         words = addword(words.wordptr);
         node = find_node(words,wordptr);
         node->lstptr = addline(node->lstptr,lineno);
         lineptr = NULL;
      }
   }

   /* Print results */
   printf("No. of distinct words: %d\n\n",ndistinct);
   print_tree(words);
   return 0;
}

Tree *addword(Tree *tp, char *word)
{
   if (tp == NULL)
   {
      /* Add new entry */
      ++ndistinct;
      tp = malloc(sizeof(Tree));
      strncpy(tp->word,word,WORD_WIDTH)[WORD_WIDTH] = '\0';
      tp->left = tp->right = NULL;
      tp->lstptr = NULL;
   }
   else if (strcmp(tp->word,word) < 0)
      tp->right = addword(tp->right,word);
   else if (strcmp(tp->word,word) > 0)
      tp->left = addword(tp->left,word);

   return tp;
}

List *addline(List *lp. int n)
{
   if (lp == NULL)
   {
      /* Append new line number to list */
      List *newp = malloc(sizeof(List));
      assert(newp);
      newp->lnum = n;
      newp->next = NULL;
      return newp;
   }
   else if (lp->lnum != n)
      lp->next = addline(lp->next,n);

   return lp;
}

void print_tree(Tree *tp)
{
   if (tp != NULL)
   {
      /* Inorder traversal */
      print_tree(tp->left);
      printf("%-*.*s: ",WORD_WIDTH,WORD_WIDTH,tp->word);
      print_list(tp->lstptr); putchar('\n');
      print_tree(tp->right);
   }
}
   }
}

void print_list(List *lp)
{
   const int NUM_WIDTH = 5;
   const int INDENT = WORD_WIDTH + 2;
   const int NUMS_PER_LINE = 8;
   int count;

   for (count = 0; lp != NULL; lp = lp->next, ++count)
   {
      printf("%*d",NUM_WIDTH,lp->lnum);
      if ((count+1) % NUMS_PER_LINE == 0
          && lp->next != NULL)
         printf("\n%*c",INDENT,' ');
   }
}

Tree *find_node(Tree *tp, char *s)
{
   /* Binary search for word */
   if (strcmp(tp->word,s) > 0)
      return find_node(tp->left,s);
   else if (strcmp(tp->word,s) < 0)
      return find_node(tp->right,s);
   else
      return tp;
}

/* End of File */