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