home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / PASCAL / NVDC87.ZIP / BINTRE.ZIP / CHARFREQ.C next >
Encoding:
C/C++ Source or Header  |  1987-08-11  |  4.0 KB  |  97 lines
  1. /* CHARFREQ.C: Analyzes frequency of printable characters in a text
  2.                string, using a binary tree */
  3.  
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <alloc.h>
  7. #include <ctype.h>
  8.  
  9. /* NODE STRUCTURE */
  10. typedef struct ntag {
  11.   char         letter;                                /* key value */
  12.   int          freq;                                  /* frequency */
  13.   struct ntag *LLink, *RLink;                  /* linkage pointers */
  14. } NTYPE;
  15.  
  16. /* GLOBAL */
  17. static NTYPE  *root;                        /* entry to binary tree*/
  18. /* ---------------------- LOCAL FUNCTIONS ------------------------ */
  19. NTYPE  *found (char arg, NTYPE *node)   /* search for matching key */
  20. {
  21.   while (arg != node->letter)               /* loop while no match */
  22.     if (node == NULL)                          /* if hit a leaf... */
  23.       return (NULL);                             /* abandon search */
  24.     else                        /* else go left or right from here */
  25.       node = (arg < node->letter) ? node->LLink : node->RLink;
  26.   return (node);             /* when found match, return node addr */
  27. } /* ------------------------ */
  28. NTYPE *newnode (char arg, NTYPE *parent, NTYPE *node)  /* add node */
  29. {
  30.   if (node != NULL)             /* recur to find location for node */
  31.     if (arg < node->letter)      /* going left or right as appropr */
  32.       node = newnode (arg, node, node->LLink);
  33.     else
  34.       node = newnode (arg, node, node->RLink);
  35.   else {                            /* position found for new leaf */
  36.     node = (NTYPE*) malloc (sizeof (NTYPE));   /* alloc heap space */
  37.     node->LLink = node->RLink = NULL; /* leaf pointers always NULL */
  38.     node->letter = arg;                                 /* set key */
  39.     node->freq = 1;                            /* and count of one */
  40.     if (root != NULL)                      /* if not first node... */
  41.       if (arg < parent->letter)    /* set parent's correct pointer */
  42.         parent->LLink = node;
  43.       else
  44.         parent->RLink = node;
  45.   }
  46.   return (node);
  47. } /* ------------------------ */
  48. void inOrder (NTYPE *node)             /* output tree by key order */
  49. {
  50.   if (node != NULL) {
  51.     inOrder (node->LLink);                    /* keep working left */
  52.     printf ("\n%c       %d",                /* then print contents */
  53.              node->letter, node->freq);
  54.     inOrder (node->RLink);                /* now work to the right */
  55.   }
  56. } /* ------------------------ */
  57. void postOrder (NTYPE *node)              /* delete tree from heap */
  58. {
  59.   if (node != NULL) {
  60.     postOrder (node->LLink);                     /* do all to left */
  61.     postOrder (node->RLink);                       /* all to right */
  62.     free (node);                          /* and finally this node */
  63.   }
  64. } /* ---------------------- MAIN PROGRAM ------------------------- */
  65. main ()
  66. {
  67. char    c, text [80];
  68. int     n, p;
  69. NTYPE  *current;
  70.  
  71.   do {
  72.     puts ("\n\nType text to be analyzed:");
  73.     gets (text);
  74.     if ((n = strlen (text)) != 0) {       /* process if text typed */
  75.       for (p = 0; p < n; p++) {
  76.         c = toupper (text [p]);        /* get next letter, upshift */
  77.         if (isprint (c)) {                     /* see if printable */
  78.           if (root == NULL)             /* if first letter in text */
  79.             root = newnode (c, NULL, NULL);         /* create root */
  80.           else
  81.             if ((current = found (c, root)) != NULL)
  82.               current->freq++;               /* count if duplicate */
  83.             else
  84.               newnode (c, root, root);         /* else add to tree */
  85.         }                                 /* end of 'if printable' */
  86.       }                                         /* end of for loop */
  87.       /* PRINT FREQUENCY ANALYSIS */
  88.       puts ("\nFrequency of letters used:");
  89.       inOrder (root);
  90.  
  91.       /* DELETE TREE FROM HEAP */
  92.       postOrder (root);
  93.       root = NULL;
  94.     }                                                 /* end of if */
  95.   } while (n != 0);                                      /* repeat */
  96. }
  97.