ch6-Tree (Word frequency count)

Chapter_6     Exercise_6-1     wordp

Exercise_6-2

---

---

tree.c     K&R, p. 140-143         download

#include <stdio.h> // for getchar(), putchar(), printf(), EOF, NULL
#include <string.h> // for strcmp(), strlen(), strcpy()
#include <ctype.h> // for isspace(), isalpha(), isalnum()

#define MAXWORD 100

struct tnode // tree node
{
char *word; // points to the text
int count; // number of occurrences
struct tnode *left; // left child (smaller)
struct tnode *right; // right child (bigger)
};

struct tnode * // add node to the tree
addtnode (struct tnode *, char *);
int treeprint(struct tnode *); // start with the root node
int getword(char *, int);

// word frequency count
int main()
{
int c;
struct tnode *root;
char word[MAXWORD];

root = NULL; // initialize

while ((c = getword(word, MAXWORD)) != EOF)
{
if (isalpha(c) || c == '_')
{root = addtnode(root, word);}
}

c = treeprint(root);
if (c > 0) // root != NULL
{
c--; // to account for the last incrementation in treeprint()
if (c % 5 != 4) {putchar('\n');}
}

return 0;
}

struct tnode *
nalloc(void); // allocate node
// duplicate string:
char * strDup(char *); // strdup() is declared by string.h

struct tnode *
addtnode(struct tnode *p, char *w)
{
int cond;

if (p == NULL) // a new word has arrived
{
p = nalloc(); // make a new node
p->word = strDup(w);
p->count = 1;
p->left = p->right = NULL;
}
else if ((cond = strcmp(w, p->word)) == 0)
{p->count++;} // repeated word
else if (cond < 0) // less than into left subtree
{p->left = addtnode(p->left, w);}
else // greater than into right subtree
{p->right = addtnode(p->right, w);}

return p;
}

// in-order print of tree with root p (left, node, right)
int treeprint (struct tnode *p)
{ // return count of nodes
static int i = 0;

if (p != NULL)
{
treeprint(p->left);
printf("(%d, %s),%s", p->count, p->word, (i % 5 == 4)? "\n" : " ");
i++;
treeprint(p->right);
}

return i;
}

#include <stdlib.h> // for malloc()

struct tnode *
nalloc(void) // allocate space for a tree node
{ // make a tnode
return (struct tnode *) malloc (sizeof(struct tnode));
}

char * strDup(char *s) // make a duplicate of s
{
char *p;
// we assume a char is stored on a byte
p = (char *) malloc (strlen(s) + 1); // +1 for ending '\0'

if (p != NULL)
{strcpy(p, s);}

return p;
}

int getch(void);
void ungetch(int);

// get next word or character from input
int getword(char *word, int lim)
{
int c;
char *w = word;

while (isspace(c = getch()))
{} // skip beginning whitespace

if (c != EOF)
{*w++ = c;}

if (!isalpha(c) && c != '_')
{
*w = '\0';
return c;
}

for ( ; --lim > 0; w++)
{
if (!isalnum(*w = getch()) && *w != '_')
{
ungetch(*w);
break; // out of for(), w++ is not executed
}
}

*w = '\0';
return word[0];
}

// buffer for ungetch():
int buf = EOF-1; // not a real character, not even EOF

int getch(void) // get a (possibly pushed-back) character
{
if (buf < EOF)
{
return getchar();
}

int temp = buf; // buf >= EOF
buf = EOF-1; // reset buf

return temp;
}
// push character back on input (make it available for the next getch()):
void ungetch(int c)
{
buf = c;
}
/*
gcc tree.c -o tree
./tree < tree.c
(9, EOF), (4, MAXWORD), (8, NULL), (4, _), (10, a),
(2, account), (2, add), (6, addtnode), (3, allocate), (2, arrived),
(2, assume), (2, available), (3, back), (2, beginning), (2, bigger),
(2, break), (8, buf), (2, buffer), (2, by), (2, byte),
(20, c), (15, char), (5, character), (3, child), (4, cond),
(7, count), (2, ctype), (2, d), (2, declared), (2, define),
(3, duplicate), (4, else), (2, ending), (2, even), (2, executed),
(12, for), (2, frequency), (2, from), (2, gcc), (3, get),
(6, getch), (3, getchar), (4, getword), (2, greater), (6, h),
(2, has), (5, i), (13, if), (3, in), (5, include),
(2, incrementation), (2, initialize), (3, input), (19, int), (3, into),
(4, is), (3, isalnum), (4, isalpha), (3, isspace), (2, it),
(2, last), (9, left), (2, less), (3, lim), (2, main),
(5, make), (4, malloc), (3, n), (4, nalloc), (3, new),
(3, next), (8, node), (2, nodes), (4, not), (2, number),
(2, o), (2, occurrences), (6, of), (3, on), (2, or),
(2, order), (2, out), (27, p), (2, points), (2, possibly),
(2, print), (3, printf), (2, push), (2, pushed), (3, putchar),
(2, real), (2, repeated), (2, reset), (11, return), (9, right),
(9, root), (7, s), (2, sizeof), (2, skip), (2, smaller),
(2, space), (2, start), (2, static), (2, stdio), (2, stdlib),
(2, stored), (4, strDup), (3, strcmp), (3, strcpy), (2, strdup),
(4, string), (3, strlen), (15, struct), (3, subtree), (1, talloc),
(3, temp), (2, text), (3, than), (6, the), (16, tnode),
(4, to), (9, tree), (7, treeprint), (1, trees), (5, ungetch),
(7, void), (15, w), (2, we), (3, while), (2, whitespace),
(3, with), (15, word),
*/

---

---

Chapter_6     Exercise_6-1     wordp

BACK_TO_TOP

Exercise_6-2