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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/********************************************************
* words -- scan a file and print out a list of words *
* in ASCII order. *
* *
* Usage: *
* words <file> *
********************************************************/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h> /* ANSI Standard only */
struct node {
struct node *right; /* tree to the right */
struct node *left; /* tree to the left */
char *word; /* word for this tree */
};
/* the top of the tree */
static struct node *root = NULL;
main(int argc, char *argv[])
{
void scan(char *); /* scan the files for words */
void print_tree(struct node *);/* print the words in the file */
if (argc != 2) {
(void) fprintf(stderr, "Error:Wrong number of parameters\n");
(void) fprintf(stderr, " on the command line\n");
(void) fprintf(stderr, "Usage is:\n");
(void) fprintf(stderr, " words 'file'\n");
exit(8);
}
scan(argv[1]);
print_tree(root);
return (0);
}
/********************************************************
* scan -- scan the file for words *
* *
* Parameters *
* name -- name of the file to scan *
********************************************************/
void scan(char *name)
{
char word[100]; /* word we are working on */
int index; /* index into the word */
int ch; /* current character */
FILE *in_file; /* input file */
/* enter a word into the tree */
void enter(struct node **, char *);
in_file = fopen(name, "r");
if (in_file == NULL) {
(void) fprintf(stderr,
"Error:Unable to open %s\n", name);
exit(8);
}
while (1) {
/* scan past the whitespace */
while (1) {
ch = fgetc(in_file);
if (isalpha(ch) || (ch == EOF))
break;
}
if (ch == EOF)
break;
word[0] = ch;
for (index = 1; index < sizeof(word); index++) {
ch = fgetc(in_file);
if (!isalpha(ch))
break;
word[index] = ch;
}
/* put a null on the end */
word[index] = '\0';
enter(&root, word);
}
(void) fclose(in_file);
}
/********************************************************
* enter -- enter a word into the tree *
* *
* Parameters *
* node -- current node we are looking at *
* word -- word to enter *
********************************************************/
void enter(struct node **node, char *word)
{
int result; /* result of strcmp */
char *save_string(char *); /* save a string on the heap */
void memory_error(void); /* tell user no more room */
/* see if we have reached the end */
if ((*node) == NULL) {
(*node) = (struct node *) malloc(sizeof(struct node));
if ((*node) == NULL)
memory_error();
(*node)->left = NULL;
(*node)->right = NULL;
(*node)->word = save_string(word);
}
result = strcmp((*node)->word, word);
if (result == 0)
return;
if (result < 0)
enter(&(*node)->right, word);
else
enter(&(*node)->left, word);
}
/********************************************************
* save_string -- save a string on the heap *
* *
* Parameters *
* string -- string to save *
* *
* Returns *
* pointer to malloc-ed section of memory with *
* the string copied into it. *
********************************************************/
char *save_string(char *string)
{
char *new_string; /* where we are going to put string */
new_string = malloc((unsigned) (strlen(string) + 1));
if (new_string == NULL)
memory_error();
(void) strcpy(new_string, string);
return (new_string);
}
/********************************************************
* memory_error -- write error and die *
********************************************************/
void memory_error(void)
{
(void) fprintf(stderr, "Error:Out of memory\n");
exit(8);
}
/********************************************************
* print_tree -- print out the words in a tree *
* *
* Parameters *
* top -- the root of the tree to print *
********************************************************/
void print_tree(struct node *top)
{
if (top == NULL)
return; /* short tree */
print_tree(top->left);
(void) printf("%s\n", top->word);
print_tree(top->right);
}
|
