CFGReader

Strange Dictionary

    A. First Edition

    This is first edition of my strange dictionary.

    B.The problem

In Comp354 we need a dictionary to be used in our project, so I just write such a small toy to enjoy
¡¡
myself.
¡¡
C.The idea of program
¡¡
A dictionary is just a storage where you can look up a string to see if it lies there. Usually we
¡¡
don't remove a word from our dictionary, do we? (However, in everyday life, we do remove some words
¡¡
from our dictionary.) Therefore, I would only give two methods: addWord, findWord. How to implement?
¡¡
The obvious method is to use a binary search tree, which I wrote before for several times. But it has
¡¡
one drawback: it wastes a lot of space. i.e. space and spaceship has same prefix, but in BST it is
¡¡
stored in two nodes. Why don't we just store letters in tree as nodes instead of strings? That is
¡¡
each node is a letter. For example, "space" is saved as "s", "p", "a", "c", "e". And for the last
¡¡
node "e", we use a flag to indicate word ends. "spaceship" will reuse most of structure of "space"
¡¡
except "ship" is added to tree with four more letters. And the ending letter "p" has a flag to say
¡¡
it is end. The searching will be very fast because in BST we use string comparison, here, we use
¡¡
char to char comparison. And what's more, we saved a lot space, especially when words has very
¡¡
similar prefix which is common in English.

    D.The major functions

    E.Further improvement

    F.File listing

    1. dictionary.h

    2. dictionary.cpp

    3. main.cpp (main)

    ¡¡

    file name: dictionary.h

    const int LetterCount=26;

    struct Letter
    {
    	char ch;
    	Letter* next;
    	Letter* son;
    	bool end;
    };

    class Dictionary
    {
    private:
    	Letter* root[52];
    	Letter* current;
    	Letter* findBrother(Letter* brother, char ch);
    	Letter* createLetter(char ch);
    	Letter* addSon(char ch);
    	int indexOf(char ch);
    public:
    	bool addWord(char* str);
    	bool findWord(char* str);
    	void readFile(const char* fileName);
    	Dictionary();
    };

    file name: dictionary.cpp

    #include <iostream>
    #include <fstream>

    #include "dictionary.h"

    using namespace std;

    void Dictionary::readFile(const char* fileName)
    {
    	char buffer[20];
    	ifstream f;
    	f.open(fileName);
    	while (!f.eof())
    	{
    		f>>buffer;
    		addWord(buffer);
    	}
    }

    bool Dictionary::findWord(char* str)
    {
    	char* ptr=str;
    	Letter* hold;
    	int index;
    	//not empty string
    	if (ptr!=NULL)
    	{
    		index = indexOf(*ptr);
    		if (index==-1)
    		{
    			return false;
    		}
    		current=root[index];
    		ptr++;

    		if (current->son==NULL)
    		{
    			//if string is a one-letter string
    			if (*ptr=='\0')
    			{
    				//and there is a one-letter word in dictionary
    				return current->end;
    			}
    			else
    			{
    				return false;
    			}
    		}
    		hold=current;//
    		current=current->son;

    		while (*ptr!='\0')
    		{
    			current=findBrother(current, *ptr);
    			if (current==NULL)
    			{
    				return false;
    			}
    			if (current->ch==*ptr)
    			{
    				hold=current;
    				current=current->son;
    			}
    			else
    			{
    				//not found
    				return false;
    			}
    			ptr++;
    		}
    		return hold->end;
    	}
    	//in my dictionary there is no empty string word
    	return false;
    }

    Letter* Dictionary::createLetter(char ch)
    {
    	Letter* ptr=new Letter;
    	ptr->ch=ch;
    	ptr->end=false;
    	ptr->next=NULL;
    	ptr->son=NULL;
    	return ptr;
    }

    //ch is not '\0'
    Letter* Dictionary::findBrother(Letter* brother, char ch)
    {
    	Letter* hold=brother;
    	if (brother==NULL)
    	{
    		return NULL;
    	}
    	while (hold->next!=NULL)
    	{
    		if (hold->ch==ch)
    		{
    			break;
    		}
    		hold=hold->next;
    	}
    	return hold;
    }

    Letter* Dictionary::addSon(char ch)
    {
    	//the word ends
    	if (ch=='\0')
    	{
    		current->end=true;
    	}
    	else
    	{
    		//need a new son
    		if (current->son==NULL)
    		{
    			current->son=createLetter(ch);
    			current=current->son;
    		}
    		else
    		{
    			//current->son is not NULL!!!
    			current=findBrother(current->son, ch);
    			//check if the current is the node
    			if (current->ch!=ch)
    			{
    				current->next=createLetter(ch);
    				current=current->next;//add brother
    			}
    			//else return current;!!!
    		}
    	}
    	return current;
    }

    //add word actually add letter by letter till NULL, nonsense!
    bool Dictionary::addWord(char* str)
    {
    	char* ptr=str;
    	int index;
    	if (*ptr!='\0')
    	{
    		index=indexOf(*ptr);
    		if (index==-1)
    		{
    			return false;
    		}
    		current=root[index];
    		do
    		{
    			ptr++;
    			current=addSon(*ptr);
    		} while (*ptr!='\0');
    		return true;
    	}
    	return false;
    }

    Dictionary::Dictionary()
    {
    	for (int i=0; i<LetterCount; i++)
    	{
    		root[i]=new Letter;
    		root[i]->ch='A'+i;
    		root[i]->next=NULL;
    		root[i]->son=NULL;
    	}
    	for (i=0; i<LetterCount; i++)
    	{
    		root[i+LetterCount]=new Letter;
    		root[i+LetterCount]->ch='a'+i;
    		root[i+LetterCount]->next=NULL;
    		root[i+LetterCount]->son=NULL;
    	}
    }

    int Dictionary::indexOf(char ch)
    {
    	if (ch-'A'>=0&&ch-'Z'<=0)
    	{
    		return ch-'A';
    	}
    	if (ch-'a'>=0&&ch-'z'<=0)
    	{
    		return ch-'a'+LetterCount;
    	}
    	return -1;
    }

    file name: main.cpp (main)

    #include <iostream>
    #include <fstream>
    #include "dictionary.h"

    using namespace std;

    int main()
    {
    	ifstream f;
    	char buffer[20];
    	Dictionary D;
    	D.readFile("c:\\nickdictionary.txt");

    	f.open("c:\\nickDictionaryTest.txt");
    	while (!f.eof())
    	{
    		f>>buffer;
    		if (D.findWord(buffer))
    		{
    			cout<<"dictionary has word :"<<buffer<<endl;
    		}
    		else
    		{
    			cout<<"dictionary has no word :"<<buffer<<endl;
    		}
    	}

    	return 0;
    }

    ¡¡

    Here is the result: The input file is "nickdictionary.txt" which should be place in root directory of your C

    drive. This file gives dictionary all words to add. Another file "nickdictionarytest.txt" is used to test

    if words is indeed stored in dictionary. Of course you know you can set up your own dictionary by using your own

    txt files. But words can only start with letters and my dictionary is case-sensitive.

    dictionary has word :a
    dictionary has word :A
    dictionary has no word :the1
    dictionary has word :following
    dictionary has no word :templatef
    dictionary has no word :iss
    dictionary has word :provided
    dictionary has word :for
    dictionary has word :use
    dictionary has word :with
    dictionary has word :the
    dictionary has no word :rational
    dictionary has no word :unified
    dictionary has no word :process.
    dictionary has word :text
    dictionary has word :enclosed
    dictionary has word :in
    dictionary has word :square
    dictionary has word :brackets
    dictionary has word :and
    dictionary has word :displayed
    dictionary has word :in
    dictionary has word :blue
    dictionary has word :italics
    dictionary has no word :style=infoBlue)
    dictionary has no word :isn't
    dictionary has word :included
    dictionary has word :to
    dictionary has word :provide
    dictionary has word :guidance
    dictionary has word :to
    dictionary has word :the
    dictionary has word :author
    dictionary has word :and
    dictionary has word :should
    dictionary has word :be
    dictionary has word :deleted
    dictionary has word :before
    dictionary has word :publishing
    dictionary has word :the
    dictionary has word :document.
    dictionary has word :a
    dictionary has word :paragraph
    dictionary has word :entered
    dictionary has word :following
    dictionary has word :this
    dictionary has word :style
    dictionary has word :will
    dictionary has word :automatically
    dictionary has word :be
    dictionary has word :set
    dictionary has word :to
    dictionary has word :normal
    dictionary has word :this
    dictionary has word :template
    dictionary has word :is
    dictionary has no word :directly
    dictionary has no word :inspired
    dictionary has word :by
    dictionary has word :the
    dictionary has no word :templates
    dictionary has word :provided
    dictionary has word :in
    dictionary has word :the
    dictionary has word :Rational
    dictionary has word :Unified
    dictionary has no word :Process,
    dictionary has word :and
    dictionary has word :are
    dictionary has no word :all
    dictionary has no word :available
    dictionary has word :for
    dictionary has no word :free
    dictionary has word :on
    dictionary has word :the
    dictionary has word :Rational
    dictionary has no word :Software
    dictionary has no word :web
    dictionary has no word :site.
    dictionary has word :All
    dictionary has no word :credit
    dictionary has no word :go
    dictionary has word :to
    dictionary has word :Rational
    dictionary has no word :Software,
    dictionary has no word :except
    dictionary has word :for
    dictionary has word :the
    dictionary has no word :edition
    dictionary has no word :that
    dictionary has no word :we
    dictionary has no word :made,
    dictionary has word :for
    dictionary has no word :which
    dictionary has word :Rational
    dictionary has no word :Software
    dictionary has word :is
    dictionary has word :not
    dictionary has no word :responsible
    dictionary has word :for
    dictionary has no word :ialog,
    dictionary has word :automatic
    dictionary has word :fields
    dictionary has word :may
    dictionary has word :be
    dictionary has word :updated
    dictionary has word :throughout
    dictionary has word :the
    dictionary has word :document
    dictionary has word :by
    dictionary has word :selecting
    dictionary has word :Edit>Select
    dictionary has word :All
    dictionary has no word :(or
    dictionary has word :Ctrl-A)
    dictionary has word :and
    dictionary has word :pressing
    dictionary has word :F9,
    dictionary has word :or
    dictionary has word :simply
    dictionary has word :between
    dictionary has word :displaying
    dictionary has word :the
    dictionary has word :field
    dictionary has word :names
    dictionary has word :and
    dictionary has word :the
    dictionary has word :A
    dictionary has word :paragraph
    dictionary has word :entered
    dictionary has word :following
    dictionary has word :this
    dictionary has word :style
    dictionary has word :a
    Press any key to continue