Page 1 of 1

Self-referential Structures page 140, 141, 142, 143

Posted: Thu May 18, 2017 10:39 pm
by BJT
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  4. #include <string.h>
  5. #define MAXWORD 100
  6.  
  7. struct tnode {
  8.     char *word;
  9.     int count;
  10.     struct tnode *left;
  11.     struct tnode *right;
  12. };
  13.  
  14. struct tnode *addtree(struct tnode *, char *);
  15. void treeprint(struct tnode *);
  16. int getword(char *, int);
  17.  
  18. /* word frequency count */
  19. int main()
  20. {
  21.     struct tnode *root;
  22.     char word[MAXWORD];
  23.     root = NULL;
  24.  
  25.     while (getword(word, MAXWORD) != EOF)
  26.         if (isalpha(word[0]))
  27.             root = addtree(root, word);
  28.  
  29.     treeprint(root);
  30.  
  31.     return 0;
  32. }
  33.  
  34. struct tnode *talloc(void);
  35. char *str_dup(char *s);
  36. /* addtree: add a node with w, at or below p */
  37. struct tnode *addtree(struct tnode *p, char *w)
  38. {
  39.     int cond;
  40.     if (p == NULL) /* a new word has arrived */
  41.     {
  42.         p = talloc(); /* make a new node */
  43.         p->word = str_dup(w);
  44.         p->count = 1;
  45.         p->left = p->right = NULL;
  46.     }
  47.     else if ((cond = strcmp(w, p->word)) == 0)
  48.         p->count++;    /* repeated word */
  49.     else if (cond < 0) /* less than into left subtree */
  50.         p->left = addtree(p->left, w);
  51.     else               /* greater than into right subtree */
  52.         p->right = addtree(p->right, w);
  53.  
  54.     return p;
  55. }
  56.  
  57. /* treeprint: in-order print of tree p */
  58. void treeprint(struct tnode *p)
  59. {
  60.     if (p != NULL)
  61.     {
  62.         treeprint(p->left);
  63.         printf("%4d %s\n", p->count, p->word);
  64.         treeprint(p->right);
  65.     }
  66. }
  67.  
  68. /* talloc: make a tnode */
  69. struct tnode *talloc(void)
  70. {
  71.     return (struct tnode *) malloc(sizeof(struct tnode));
  72. }
  73.  
  74. char *str_dup(char *s) /* make a duplicate of s */
  75. {
  76.     char *p;
  77.  
  78.     p = (char *) malloc(strlen(s)+1); /* +1 for '\0' */
  79.     if (p != NULL)
  80.         strcpy(p, s);
  81.  
  82.     return p;
  83. }
  84.  
  85. /* getword: get next word or character from input */
  86. int getword(char* word, int lim)
  87. {
  88.     int c, getch(void);
  89.     void ungetch(int);
  90.     char* w = word;
  91.  
  92.     while (isspace(c = getch()))
  93.         ;
  94.  
  95.     if (c != EOF)
  96.         *w++ = c;
  97.  
  98.     if (!isalpha(c) && c!='#' && c!='/'&& c!='_')
  99.     {
  100.         *w = '\0';
  101.         return c;
  102.     }
  103.  
  104.     if( (c=getch())=='/' || c=='*' )
  105.     {
  106.         *w++=c;
  107.         *w='\0';
  108.         return word[0];
  109.     }
  110.     else
  111.         ungetch(c);
  112.  
  113.     for ( ; --lim > 0; w++)
  114.         if (!isalnum(*w = getch()) && *w!='_' && *w!='*' )
  115.         {
  116.             ungetch(*w);
  117.             break;
  118.         }
  119.  
  120.     *w = '\0';
  121.     return word[0];
  122. }
  123.  
  124. #define MAX_ALLOC 100
  125. int alloc[MAX_ALLOC];
  126. int bufp=0;
  127.  
  128. int getch(void)
  129. {
  130.     return (bufp>0) ? alloc[--bufp]:getchar();
  131. }
  132.  
  133. void ungetch(int c)
  134. {
  135.     if(bufp>=MAX_ALLOC)
  136.         printf("No espace to allocate the character\n");
  137.     else
  138.         alloc[bufp++]=c;
  139. }

input

Code: Select all

const
int
float
int
goto
main
struct
goto
for

output

Code: Select all

   1 const
   1 float
   1 for
   2 goto
   2 int
   1 main
   1 struct