New Page 1

    我的字典

    A.第一版

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

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

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

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

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

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

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

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

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

    3。 主要函数介绍：

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

>     B. saveToFile(const char* fileName)按照前序遍历树并把节点信息存入流文件保存在磁盘。

>     C. openFile(const char* fileName)打开文件并读取其中的字，经比较后插入搜索树。

>     D. void defaultVisit(Tree* node)默认的访问函数，用户可以自己定义自己的访问函数，只要带一个Tree*参数，并在遍历方法

>     void Tree::traverse(void (*visit)(Tree* node), TraverseOrder defaultOrder)中以visit参数形式传入。TraverseOrder

>      defaultOrder参数设定遍历的前序，中序，后序方式。

>     E. addNode(WordTree* node, FILE** stream)该函数为内部实现从磁盘读取某个节点信息的方法，存入的数据有三个：本身的序列

>     号，字串，以及父亲的序列号。根节点的父亲序列号设为-1。两个序列号都为-1表明文件结尾。

    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;
    }