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








                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)