home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / listings / v_09_03 / 9n03118a < prev    next >
Text File  |  1991-01-16  |  2KB  |  94 lines
  1.  
  2. /*
  3.  * xrt.c - cross-reference table implementation
  4.  */
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8.  
  9. #include "xrt.h"
  10.  
  11. typedef struct listnode listnode;
  12. struct listnode
  13.     {
  14.     unsigned number;
  15.     listnode *next;
  16.     };
  17.  
  18. typedef struct treenode treenode;
  19. struct treenode
  20.     {
  21.     char *word;
  22.     listnode *lines;
  23.     treenode *left, *right;
  24.     };
  25.  
  26. static void addnumber(treenode *t, unsigned n)
  27.     {
  28.     listnode *p;
  29.  
  30.     p = t->lines;
  31.     while (p->next != NULL && p->number != n)
  32.         p = p->next;
  33.     if (p->number != n)
  34.         {
  35.         p = p->next
  36.             = (listnode *)malloc(sizeof(listnode));
  37.         p->number = n;
  38.         p->next = NULL;
  39.         }
  40.     }
  41.  
  42. static treenode *addtree
  43.         (treenode *t, char *w, unsigned n)
  44.     {
  45.     int cond;
  46.  
  47.     if (t == NULL)
  48.         {
  49.         t = (treenode *)malloc(sizeof(treenode));
  50.         t->word =
  51.             strcpy((char *)malloc(strlen(w) + 1), w);
  52.         t->lines =
  53.             (listnode *)malloc(sizeof(listnode));
  54.         t->lines->number = n;
  55.         t->lines->next = NULL;
  56.         t->left = t->right = NULL;
  57.         }
  58.     else if ((cond = strcmp(w, t->word)) == 0)
  59.         addnumber(t, n);
  60.     else if (cond < 0)
  61.         t->left = addtree(t->left, w, n);
  62.     else
  63.         t->right = addtree(t->right, w, n);
  64.     return t;
  65.     }
  66.  
  67. static void printtree(treenode *t)
  68.     {
  69.     listnode *p;
  70.  
  71.     if (t != NULL)
  72.         {
  73.         printtree(t->left);
  74.         printf("%12s: ", t->word);
  75.         for (p = t->lines; p != NULL; p = p->next)
  76.             printf("%4d ", p->number);
  77.         printf("\n");
  78.         printtree(t->right);
  79.         }
  80.     }
  81.  
  82. static treenode *root = NULL;
  83.  
  84. void xrt_add(char *w, unsigned n)
  85.     {
  86.     root = addtree(root, w, n);
  87.     }
  88.  
  89. void xrt_print(void)
  90.     {
  91.     printtree(root);
  92.     }
  93.  
  94.