20.8 The Rest of the Program
Now that we have the data structure defined, all we need to complete the
program is a few more functions. The main function checks for the
correct number of arguments and then calls the scanner and the
print_one routine.
The scan function reads the file and breaks
it into words. It uses the standard macro isalpha.
The macro returns 1 if its argument is a letter and 0 otherwise. It
is defined in the standard include file cctype.
After a word is found, the function enter is
called to put the word in the tree.
Example 20-3 is the listing of
words.cpp.
Example 20-3. words/words.cpp
/********************************************************
* words -- scan a file and print out a list of words *
* in ASCII order. *
* *
* Usage: *
* words <file> *
********************************************************/
#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#include <cstdlib>
class tree {
private:
// The basic node of a tree
class node {
private:
node *right; // tree to the right
node *left; // tree to the left
public:
std::string word; // word for this tree
friend class tree;
};
// the top of the tree
node *root;
// Enter a new node into a tree or sub-tree
void enter_one(node *&node, const std::string& word);
// Print a single node
void print_one(node *top);
public:
tree( ) { root = NULL;}
// Add a new word to our tree
void enter(std::string& word) {
enter_one(root, word);
}
// Print the tree
void print( ) {
print_one(root);
}
};
static tree words; // List of words we are looking for
/********************************************************
* scan -- scan the file for words *
* *
* Parameters *
* name -- name of the file to scan *
********************************************************/
void scan(const char *const name)
{
std::string new_word; // word we are working on
int ch; // current character
std::ifstream in_file; // input file
in_file.open(name, std::ios::in);
if (in_file.bad( )) {
std::cerr << "Error:Unable to open " << name << '\n';
exit(8);
}
while (true) {
// scan past the whitespace
while (true) {
ch = in_file.get( );
if (std::isalpha(ch) || (ch == EOF))
break;
}
if (ch == EOF)
break;
new_word = ch;
while (true)
{
ch = in_file.get( );
if (!std::isalpha(ch))
break;
new_word += ch;
}
words.enter(new_word);
}
}
int main(int argc, char *argv[])
{
if (argc != 2) {
std::cerr << "Error:Wrong number of parameters\n";
std::cerr << " on the command line\n";
std::cerr << "Usage is:\n";
std::cerr << " words 'file'\n";
exit(8);
}
scan(argv[1]);
words.print( );
return (0);
}
/********************************************************
* tree::enter_one -- enter a word into the tree *
* *
* Parameters *
* new_node -- current node we are looking at *
* word -- word to enter *
********************************************************/
void tree::enter_one(node *&new_node, const std::string& word)
{
// see if we have reached the end
if (new_node == NULL) {
new_node = new node;
new_node->left = NULL;
new_node->right = NULL;
new_node->word = word;
}
if (new_node->word == word)
return;
if (new_node->word < word)
enter_one(new_node->right, word);
else
enter_one(new_node->left, word);
}
/********************************************************
* tree::print_one -- print out the words in a tree *
* *
* Parameters *
* top -- the root of the tree to print *
********************************************************/
void tree::print_one(node *top)
{
if (top == NULL)
return; // short tree
print_one(top->left);
std::cout << top->word << '\n';
print_one(top->right);
}
I once made a program that read the dictionary into memory using a
tree structure and then used it in a program that searched for
misspelled words. Although trees are supposed to be fast, this
program was so slow you would think I had used a linked
list. Why?
Hint: Graphically construct a tree
using the words "able,"
"baker,"
"cook,"
"delta," and
"easy" and look at the result.
| 
No comments:
Post a Comment