1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
/* wf1 - print word frequencies; uses structures */
struct node {
int count; /* frequency count */
struct node *left; /* left subtree */
struct node *right; /* right subtree */
char *word; /* word itself */
} words[2000];
int next; /* index of next free entry in words */
struct node *lookup();
main() {
struct node *root;
char word[20];
root = 0;
next = 0;
while (getword(word))
lookup(word, &root)->count++;
tprint(root);
return 0;
}
/* err - print error message s and die */
err(s) char *s; {
printf("? %s\n", s);
exit(1);
}
/* getword - get next input word into buf, return 0 on EOF */
int getword(buf) char *buf; {
char *s;
int c;
while ((c = getchar()) != -1 && isletter(c) == 0)
;
for (s = buf; c = isletter(c); c = getchar())
*s++ = c;
*s = 0;
if (s > buf)
return (1);
return (0);
}
/* isletter - return folded version of c if it is a letter, 0 otherwise */
int isletter(c) {
if (c >= 'A' && c <= 'Z')
c += 'a' - 'A';
if (c >= 'a' && c <= 'z')
return (c);
return (0);
}
/* lookup - lookup word in tree; install if necessary */
struct node *lookup(word, p) char *word; struct node **p; {
int cond;
char *malloc();
if (*p) {
cond = strcmp(word, (*p)->word);
if (cond < 0)
return lookup(word, &(*p)->left);
else if (cond > 0)
return lookup(word, &(*p)->right);
else
return *p;
}
if (next >= 2000)
err("out of node storage");
words[next].count = 0;
words[next].left = words[next].right = 0;
words[next].word = malloc(strlen(word) + 1);
if (words[next].word == 0)
err("out of word storage");
strcpy(words[next].word, word);
return *p = &words[next++];
}
/* tprint - print tree */
tprint(tree) struct node *tree; {
if (tree) {
tprint(tree->left);
printf("%d\t%s\n", tree->count, tree->word);
tprint(tree->right);
}
}
/* strcmp - compare s1 and s2, return <0, 0, or >0 */
int strcmp(s1, s2) char *s1, *s2; {
while (*s1 == *s2) {
if (*s1++ == 0)
return 0;
++s2;
}
if (*s1 == 0)
return -1;
else if (*s2 == 0)
return 1;
return *s1 - *s2;
}
|
