Listing 1: Generates a cross-reference of words

//
// xr.cpp
//
     
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
     
struct list_node
    {
    unsigned number;
    list_node *next;
    };
     
struct tree_node
    {
    char *word;
    list_node *first, *last;
    tree_node *left, *right;
    };
     
int get_token(char *s, size_t n);
     
tree_node *
add_tree(tree_node *t, char const *w, unsigned n);
     
void put_tree(tree_node const *t);
     
#define MAX_TOKEN 256
     
int main()
    {
    tree_node *xr = NULL;
    char token[MAX_TOKEN];
    unsigned ln = 1;
    while (get_token(token, MAX_TOKEN) != EOF)
        if (isalpha(token[0]) || token[0] == '_')
            xr = add_tree(xr, token, ln);
        else if (token[0] == '\n')
            ++ln;
    put_tree(xr);
    return 0;
    }
     
int get_token(char *s, size_t n)
    {
    int c;
    while ((c = fgetc(stdin)) != EOF)
        if (isalpha(c) || c == '_' || c == '\n')
            break;
    if (c == EOF)
        {
        *s = '\0';
        return EOF;
        }
    *s++ = c;
    n -= 2;
    if (c != '\n')
        {
        while (isalnum(c = fgetc(stdin)) || c == '_')
            if (n > 0)
                {
                *s++ = c;
                --n;
                }
        ungetc(c, stdin);
        }
    *s = '\0';
    return 1;
    }
     
tree_node *
add_tree(tree_node *t, char const *w, unsigned n)
    {
    int cmp;
    if (t == NULL)
        {
        t = new tree_node;
        t->word = new char [strlen(w) + 1];
        strcpy(t->word, w);
        t->first = new list_node;
        t->first->number = n;
        t->first->next = NULL;
        t->last = t->first;
        t->left = t->right = NULL;
        }
    else if ((cmp = strcmp(w, t->word)) < 0)
        t->left = add_tree(t->left, w, n);
    else if (cmp > 0)
        t->right = add_tree(t->right, w, n);
    else if (n != t->last->number)
        {
        t->last->next = new list_node;
        t->last = t->last->next;
        t->last->number = n;
        t->last->next = NULL;
        }
    return t;
    }
     
void put_tree(tree_node const *t)
    {
    list_node *p;
    if (t != NULL)
        {
        put_tree(t->left);
        printf("%12s:", t->word);
        for (p = t->first; p != NULL; p = p->next)
            printf(" %4d", p->number);
        printf("\n");
        put_tree(t->right);
        }
    }
     

     
//End of File