Listing 3: cross_reference.cpp Cross-reference implementation that defines list_node and tree_node

#include <stdio.h>
#include <string.h>
     
#include "cross_reference.h"
     
namespace cross_reference
    {
    struct list_node;
    }
     
struct cross_reference::list_node
    {
    unsigned number;
    list_node *next;
    };
     
struct cross_reference::tree_node
    {
    char *word;
    list_node *first, *last;
    tree_node *left, *right;
    };
     
cross_reference::tree_node *cross_reference::xr
    = NULL;
     
cross_reference::tree_node *
cross_reference::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 cross_reference::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 */