我的字典

A.第一版

这个小程序是最初的版本。

1。 程序基本说明：这是一个字典程序。我用二叉搜索树来存字，同时，从文件读取新字并插入，将当前的数据存入流文件，保存，当下次程序运行

	时候再从磁盘文件读入原来的树的信息。

2。 程序思路：我的树采用继承的方式，

	A. 最base的树class Tree实现最基本的功能，如：遍历（分前序，中序，后序），并可以靠传入函数指针完成遍历

	中对每一个节点的方法。以及所有基本的访问，添加左右儿子，父亲，各种属性，如名字，健值，序列号等等方法。并重载了大于，小

	于，等于的操作符，并将大部分方法设为虚方法，以便后代重载。

	B. BinaryTree主要实现了二叉搜索树的插入，删除，前一个，后一个的方法。

	C. WordTree实现了字典中的所有方法（详见3）。并重载了比较符运算，大小比较方法函数，健值设定方法。	

3。 主要函数介绍：

     A.  readFromFile(const char* fileName)从磁盘文件中顺序读入每个节点的信息重新建树。

4。 不足之处：

	A. 不知道为了什么，我按照顺序存储后，流文件的feof()函数变得不可用了，只好自己在文件结尾处写入-1， -1来识别。

	B. 写的时候忘记支持unicode，结果不支持汉字，等以后改吧。

	C. 有一个疑惑，我存了大约400个字，结果文件竟然有7K,平均一个单词有十几个字母长？不明白？

	D. 还要增加查询功能。（让我喘口气，为了文件结束标志的问题，我累得两天多了。）

5。 下载执行程序。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <ctime>

using namespace std;


const MaxWordLength = 255;

enum TraverseOrder
{
	PREORDER, MIDORDER, POSTORDER
};


class Tree
{
private:	
	Tree* pLeft;
	Tree* pRight;
	Tree* pParent;
	char* pName;
	int index;
	static int treeCounter;
	static Tree* pRoot;
	void preWalk(Tree* node, void (*visit)(Tree* node));
	void midWalk(Tree* node, void (*visit)(Tree* node));
	void postWalk(Tree* node, void (*visit)(Tree* node));
protected:
	void* pKey;
public:
	Tree* left();
	Tree* right();
	Tree* parent();
	virtual void* key();
	virtual void setKey(void* newKey);
	void setRoot(Tree* node);
	const char* name();
	const int getIndex();
	void setLeft(Tree* leftSon);
	void setRight(Tree* rightSon);
	void setParent(Tree* father);
	void setIndex(const int number);
	virtual	int compare(const void* otherKey); 
	void setName(const char *str);
	void giveBirth();
	virtual bool operator>(Tree&);
	virtual bool operator==(Tree&);
	virtual bool operator<(Tree&);	
	Tree();
	virtual ~Tree();
	static Tree* root() {return pRoot;}
	const int count();
	void traverse(void ( *visit)(Tree* node), TraverseOrder defaultOrder= MIDORDER);
};





void defaultVisit(Tree* node);

class BinaryTree: public Tree
{
private:

public:
	void remove(BinaryTree* node);
	BinaryTree* next();
	BinaryTree* prev();
	bool insert(BinaryTree* node);
	virtual ~BinaryTree();
};

class WordTree: public BinaryTree
{
private:
	static int wordLength;
	static int wordCounter;
	WordTree* addNode(WordTree* node, FILE** stream);
protected:
	void setWordCounter();
	void readWord(FILE** file);
	void addWord(char* buffer);
public:
	
	WordTree* readNode(WordTree* node, FILE** stream);
	WordTree* readFromFile(const char* fileName);
	void saveNode(WordTree* node, FILE** stream);
	virtual int compare(const void *otherKey);
	void setWordLength(const int newLength);
	static const int getWordLength();
	virtual void setKey(void* newKey);
	virtual bool operator>(Tree&);
	virtual bool operator==(Tree&);
	virtual bool operator<(Tree&);
	void openFile(const char* fileName);
	WordTree(const char * fileName);
	WordTree();
	int wordCount();
	virtual void setName(const char *str);
	void saveToFile(const char* fileName);
	~WordTree();


};


int count=0;


int main()
{
	WordTree *ptr = new WordTree;
	char choice[6], fileName[30];

	ptr = ptr->readFromFile("c:\\nickback.txt");
	cout<<"quit? or input?\nEnter your choice: \n";
	cin>>choice;
	while (strcmp(choice, "quit")!=0&&strcmp(choice, "input")!=0)
	{
		cout<<"quit? or input?\n Enter your choic: \n";
		cin>>choice;
	}
	if (strcmp(choice, "quit")==0)
	{
		cout<<"The total number of words in dictionary is "<<ptr->wordCount();
		return 0;
	}
	else
	{
		if (strcmp(choice, "input")==0)
		{
			cout<<"\nnow input file name here(input 'quit' to exit):\n";
			cin>>fileName;
			while (strcmp(fileName, "quit")!=0)
			{
				ptr->openFile(fileName);
				cout<<"\nnow input file name here(input quit to exit):\n";
				
				cin>>fileName;
			}
			cout<<"\nDo you want to see contents?(yes or no)\n";
			
			
			cin>>choice;
			if (strcmp(choice, "yes")==0)
			{
				ptr->traverse(defaultVisit, PREORDER);
			}
			cout<<"The total number of words in dictionary is "<<ptr->wordCount();
			ptr->saveToFile("c:\\nickback.txt");
		}
	}

	return 0;
}

int WordTree::wordCounter = 0;
int WordTree::wordLength = 20;


BinaryTree::~BinaryTree()
{

}


WordTree::~WordTree()
{
	
}

void WordTree::setWordCounter()
{
	wordCounter ++;
}

const int WordTree::getWordLength()
{
	return wordLength;
}

WordTree* WordTree::addNode(WordTree* node, FILE** stream)
{
	char buffer[MaxWordLength];
	int index, pIndex, number;
	WordTree *domino;
	char *ptr=buffer, ch;
	
	number = fread((void*)(&index), sizeof(int), 1, *stream);
	number = fread((void*)(&pIndex), sizeof(int), 1, *stream);

	if (index==-1&&pIndex==-1)
	{
		return NULL;
	}

	do
	{
		ch = fgetc(*stream);
		*ptr = ch;
		ptr++;
	}
	while(ch!='\0');

	setWordCounter();  //add a word

	if (pIndex== -1)  //this is root
	{			
		node->setIndex(index);
		node->setName(buffer);
		node->setRoot(node);
		return node;
	}

	while (pIndex!=node->getIndex())
	{	
		if (node->parent()==NULL)
		{
			return NULL;
		}
		node= (WordTree*)node->parent(); 
	}


	if (node!=NULL&&pIndex==node->getIndex())
	{
		domino = new WordTree;
		domino->setIndex(index);
		domino->setName(buffer);
		domino->setParent(node);
		if (*domino<*node)
		{
			node->setLeft(domino);
		}
		else
		{
			node->setRight(domino);
		}
		
		return domino;
	}
	else
	{
		return NULL;
	}
}


WordTree* WordTree::readNode(WordTree* node, FILE** stream)
{	
	WordTree* domino = node;

	while (domino!=NULL)
	{
		domino = addNode(domino, stream);
	}
	return (WordTree*)node->root();  //this is ugly as I have to remove those sentinal 
}

WordTree* WordTree::readFromFile(const char* fileName)
{
	FILE* stream;

	if ((stream=fopen(fileName, "r+b"))==NULL)
	{
		cout<<"unable to open file "<<fileName<<endl;
		return NULL;
	}
	else
	{
		WordTree* ptr= new WordTree;
		return readNode(ptr, &stream);	
	}
	fclose(stream);
}

void WordTree::saveNode(WordTree* node, FILE** stream)
{
	int first, second, number;

	first = node->getIndex();

	number = fwrite((void*)(&first), sizeof(int), 1, *stream);
	if (node->parent()==NULL)
	{
		second = -1;		
	}
	else
	{
		second = node->parent()->getIndex();		
	}
	number = fwrite((void*)(&second), sizeof(int), 1, *stream);
	number = fwrite((void*)(node->name()),sizeof(char), strlen(node->name()), *stream);
	number = fputc('\0', *stream);//I have to put this '/n' otherwise there is always problem!
}

	
void traverseTree(WordTree* node, FILE** stream)
{
	if (node!=NULL)
	{
		node->saveNode(node, stream);
		traverseTree((WordTree*)node->left(), stream);
		traverseTree((WordTree*)node->right(), stream);
	}
}

void writeEnd(FILE** stream)
{
	int temp1=-1, temp2=-1;
	fwrite((void*)(&temp1), sizeof(int), 1, *stream);
	fwrite((void*)(&temp2), sizeof(int), 1, *stream);
}

void WordTree::saveToFile(const char* fileName)
{
	void traverseTree(WordTree* node, FILE ** stream);
	void writeEnd(FILE** stream);

	WordTree *domino;
	
	FILE * stream;

	
	if ((stream=fopen("c:\\nickback.txt", "w+b"))==NULL)
	{
		cout<<"unable to save to file "<<fileName<<endl;
	}
	else
	{
		domino = (WordTree*)root();
		traverseTree((WordTree*)domino, &stream);
	}
	writeEnd(&stream);
	fclose(stream);
}

	
const int Tree::count()
{
	return treeCounter;
}

void WordTree::setWordLength(const int newLength)
{
	if (newLength>MaxWordLength)
	{
		cout<<"exceed max word length."<<endl;
	}
	else
	{
		wordLength = newLength;
	}
}

int WordTree::compare(const void*otherKey)
{
	return strcmp((char*)key(), (char*)otherKey);
}

int WordTree::wordCount()
{
	return wordCounter;
}

WordTree::WordTree()
{

}

void WordTree::openFile(const char* fileName)
{
	FILE * stream;	
	if ((stream=fopen(fileName, "r+b"))==NULL)
	{
		cout<<"unable open file!"<<endl;
	}
	else
	{
		readWord(&stream);
	}
	fclose(stream);
}

void WordTree::readWord(FILE **stream)
{
	char buffer[MaxWordLength];
	char *ptr = buffer;
	char ch;
	int counter =0;

	
	while (!feof(*stream))
	{
		ptr = buffer;
		counter =  0;
		ch = toupper(fgetc(*stream));
		while (isalnum(ch)&&!feof(*stream)&&counter<wordLength)
		{
			*ptr = ch;
			ch = toupper(fgetc(*stream));
			ptr++;
			counter++;
		}

		if (ptr!=buffer)
		{
			*ptr='\0';
			addWord(buffer);
		}	
	}
}

void WordTree::addWord(char * buffer)
{
	WordTree * newTree= new WordTree;

	newTree->setName(buffer);
	if (insert(newTree))
	{
		setWordCounter();
	}
	else
	{
		newTree->setKey((void*)NULL);
		delete newTree;
	}
}

void WordTree::setName(const char *str)
{
	Tree::setName(str);
	setKey((void*)name());
}

int Tree::treeCounter= 0;

WordTree::WordTree(const char* fileName)
{
	WordTree::WordTree();
	openFile(fileName);
}

void WordTree::setKey(void * newKey)
{
	pKey = newKey;
}

bool WordTree::operator <(Tree& second)
{
	if (strcmp((char*)key(), (char*)second.key())<0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool WordTree::operator ==(Tree& second)
{
	if (strcmp((char*)key(), (char*)second.key())==0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool WordTree::operator >(Tree& second)
{
	if (strcmp((char*)key(), (char*)second.key())>0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void defaultVisit(Tree* node)
{
	cout<<"\n\n";
	cout<<"default visiting tree index:"<<node->getIndex()<<endl;
	cout<<"and tree name is:"<<node->name()<<endl;
	if (node->parent()!=NULL)
	{
		cout<<"its parent is:"<<node->parent()->name()<<endl;
		if (node==node->parent()->left())
		{
			cout<<"and it is left son."<<endl;
		}
		else
		{
			cout<<"and it is right son"<<endl;
		}
	}
	else
	{
		cout<<"it has no parent"<<endl;
	}
	cout<<"\n\n";
}


void Tree::preWalk(Tree* node, void (*visit)(Tree* node))
{
	if (node!=NULL)
	{	
		visit(node);
		preWalk(node->left(), visit);		
		preWalk(node->right(), visit);
	}
}



void Tree::postWalk(Tree* node, void (*visit)(Tree* node))
{
	if (node!=NULL)
	{
		postWalk(node->left(), visit);
		postWalk(node->right(), visit);
		visit(node);
	}
}

void Tree::midWalk(Tree* node, void (*visit)(Tree* node))
{
	if (node!=NULL)
	{
		midWalk(node->left(), visit);
		visit(node);
		midWalk(node->right(), visit);
	}
}


void Tree::traverse(void (*visit)(Tree* node), TraverseOrder defaultOrder)
{
	Tree *domino;
	domino = root();

	switch(defaultOrder)
	{
	case PREORDER:
		preWalk(domino, visit);
		break;
	case MIDORDER:
		midWalk(domino, visit);
		break;
	case POSTORDER:
		postWalk(domino, visit);
		break;
	}
}

Tree* Tree::pRoot = NULL;

void BinaryTree::remove(BinaryTree* node)
{
	BinaryTree* ptr=NULL;

	if (node->left()==NULL || node->right()==NULL)
	{
		if (node->left()!=NULL)
		{
			node->parent()->setLeft(node->left());
			node->left()->setParent(node->parent());
		}
		if (node->right()!=NULL)
		{
			node->parent()->setRight(node->right());
			node->right()->setParent(node->parent());
		}
	}
	else
	{
		ptr = node->next();
		remove(ptr);
		ptr->setParent(node->parent());
		if (node->parent()==NULL)
		{
			node->setRoot(ptr);			
		}
		else
		{
			if (node==node->parent()->left())
			{
				node->parent()->setLeft(ptr);
			}
			else
			{
				node->parent()->setRight(ptr);
			}
			ptr->setLeft(node->left());
			ptr->setRight(node->right());
		}
	}
}


bool Tree::operator==(Tree& second)
{
	if (this->compare(second.key())==0)
	{
		return true;
	}
	else
	{
		return false;
	}	
}

bool Tree::operator <(Tree& second)
{
	if (this->compare(second.key())<0)
	{
		return true;
	}
	else
	{
		return false;
	}	
}


bool Tree::operator >(Tree& second)
{
	if (this->compare(second.key())>0)
	{
		return true;
	}
	else
	{
		return false;
	}	
}

int Tree::compare(const void * otherKey)
{
	return *((int*)(key()))- *((int*)(otherKey));
}

void* Tree::key()
{
	return pKey;
}

void Tree::setKey(void *newKey)
{
	pKey = malloc(sizeof(int));
	*(int*)(pKey) = *(int*)(newKey);
}



void Tree::setRoot(Tree *node)
{
	pRoot = node;
}

bool BinaryTree::insert(BinaryTree* node)
{
	Tree* ptr, *dummy;

	ptr = root();
	dummy = ptr;
	while (ptr!=NULL)
	{
		dummy = ptr;
		if (*ptr>*node)
		{				
			ptr = ptr->left();
		}
		else
		{
			if (*ptr<*node)
			{
				ptr=ptr->right();
			}
			else
			{
				if (*ptr==*node)
				{
					return false;				
				}
			}
		}
	}

	node->setParent(dummy);

	if (dummy==NULL)
	{
		setRoot(node);		
	}
	else
	{
	//	node->setRoot(dummy->root());
		if (*dummy>*node)
		{
			dummy->setLeft(node);
		}
		else
		{
			if (*dummy<*node)
			{
				dummy->setRight(node);
			}
		}  //if "== ", donot insert;
	}
	return true;
}
				
void Tree::setLeft(Tree* leftSon)
{
	pLeft = leftSon;
}

void Tree::setRight(Tree* rightSon)
{
	pRight = rightSon;
}

void Tree::setParent(Tree* father)
{
	pParent = father;
}


void Tree::giveBirth()
{
	Tree* leftTree = new Tree;
	Tree* rightTree = new Tree;
	char str[128];

	leftTree->setIndex(this->getIndex() *2 );
	rightTree->setIndex(this->getIndex() * 2 + 1);

	this->setLeft(leftTree);
	this->setRight(rightTree);

	leftTree->setParent(this);
	rightTree->setParent(this);

	strcpy(str, "left son of ");
	strcat(str, this->name());

	leftTree->setName(str);

	strcpy(str, "right son of ");
	strcat(str, this->name());

	rightTree->setName(str);

	leftTree->setParent(this);
	rightTree->setParent(this);

	if (root()==NULL)
	{
		setRoot(this);
		setParent(NULL);
	}
	/*
	else
	{
		leftTree->setRoot(root());
		rightTree->setRoot(root());
	}
	*/
}


void Tree::setIndex(const int number)
{
	index = number;
}

const int Tree::getIndex()
{
	return index;
}

const char* Tree::name()
{
	return pName;
}

void Tree::setName(const char *str)
{
	if (str!=NULL)
	{
		pName = (char *)malloc(strlen(str)+1);
		strcpy(pName, str);
	}
}

Tree::Tree()
{
	setIndex(treeCounter);
	treeCounter++;
	pLeft = NULL;
	pRight = NULL;
	pParent = NULL;
	pName = NULL;
	pKey = NULL;
}

Tree::~Tree()
{
	if (pName!=NULL)
	{
		free(pName);
	}
	if (pKey!=NULL)
	{
		free(pKey);
	}
}

Tree* Tree::left()
{
	return pLeft;
}

Tree* Tree::right()
{
	return pRight;
}

Tree* Tree::parent()
{
	return pParent;
}

BinaryTree* BinaryTree::next()
{
	Tree* result = NULL;

	if (right()!=NULL)
	{
		result = right();
		while (result->left!=NULL)
		{
			result = result->left();
		}
	}
	else
	{
		if (parent()!= NULL)
		{
			result = this;
			while(result->parent()!=NULL&&result==result->parent()->right())
			{
				result = result->parent();
			}
		}
		//result = null
	}
	return (BinaryTree*)result;
}

BinaryTree* BinaryTree::prev()
{
	Tree* result = NULL;
	if (left()!=NULL)
	{
		result = left();
		while (result->right()!=NULL)
		{
			result = result->right();
		}
	}
	else
	{
		if (parent()!=NULL)
		{
			result = this;
			while (result->parent()!=NULL&&result==result->parent()->left())
			{
				result = result->parent();
			}
		}
	}
	return (BinaryTree*)result;
}