B-树实现的中文词典

B-树作为查找作为查找存储结构，中文单词进行哈希，本中文词典规模在十万级别以上，最长逆向匹配算法实现中文分词。

/************************************************************************/
/*作者;康维鹏   时间:2010年1月10日                                      */
/************************************************************************/

#include “Btree.h“
#include 
#include 

/*构造函数*/
Btree::Btree（）
{
	levels=1;
	nodes=0;
	counts=0;
	root= mallocNode（）;
}

/*析构函数*/
Btree::~Btree（）
{
	if（root==NULL）
		return ;
	delAll（）;
	
}

/*分配新节点，并初始化*/
btree Btree::mallocNode（）
{
	btree newnode=（btree）malloc（sizeof（node））;
	for（int i=0;i<=2*M;i++）
	{
		newnode->key[i]=MIN;
		newnode->child[i]=NULL;
		newnode->val[i]=NULL;
	}
	newnode->child[2*M+1]=NULL;
	newnode->p=NULL;
	newnode->lev=1;
	newnode->num=0;
	nodes++;
	return newnode;
}

/*返回插入的键值数目*/
int Btree::getCount（）
{
	return counts;
}

/*返回节点数目*/
int Btree::getNode（）
{
	return nodes;
}

/*返回高度，以1开始计算*/
int Btree::getHeight（）
{
	return levels;
}

/*返回根节点*/
btree Btree::getRoot（）
{
	return root;
}

/*设定高度*/
int Btree::setHeight（int hight）
{
	return levels=hight;

}

/*设定键值数量*/
int Btree::setCount（int count）
{
	return counts=count;
}

/*设定节点总数*/
int Btree::setNode（int num）
{
	return nodes=num;
}

bool Btree::setRoot（btree bt）
{
	delAll（）;
	root=bt;
	return true;
}

/*查找键值是否存在*/
bool Btree::search（typekey key）
{
	btree bt=rootpt=root;
	if（search（keybtpt）==-1）
		return false;
	return true;
}

/*查找键值为key的val是否存在*/
bool Btree::search（typekey keyconst char *val）
{
	btree bt=rootpt=root;
	int mid=search（keybtpt）;
	if（mid==-1）
		return false;
	if（strcmp（bt->val[mid]->valval）!=0）
		return false;
	return true;
}

/*查找键值是否存在，以及保存在有关信息*/
int Btree::search（typekey key btree &btbtree &pt）
{
	if（root->num==0）
		return -1;
	if（bt==NULL）
		return -1;
	if（bt->num==0）
		return -1;

	/*直到叶节点为止*/
	while（1）
	{
		/*折半查找，效率较佳*/
		int low=0 high=bt->num-1 mid=（low+high）/2;
		for（;high >=low;）
		{
			if（key==bt->key[mid]）
			{
				/*找到则返回，保存信息*/
				pt=bt->p;
				return mid;
			}
			;
			if（key > bt->key[mid]）
			{
				low=mid+1;
				mid=（high+low）/2;
			}
			else
			{
				high=mid-1;
				mid=（high+low）/2;
			}
		}
		pt=bt;
		/*根据大小关系，选择子节点进行。这是因为在调整lowhighmid时可能漏判mid的情况*/
		if（key > bt->key[mid]）
			bt=bt->child[mid+1];
		else
			bt=bt->child[mid];
		if（bt==NULL）
			return -1;
	}
	return -1;
}

//使节点pt的第pos的孩子指向bt
bool Btree::apend（btree &ptint posbtree &bt）
{
	if（pt==NULL）
		return false;
	if（pos>pt->num）
		return false;
	pt->child[pos]=bt;
	if（bt!=NULL）
		bt->p=pt;
	return true;
	
}

/*插入新结点*/
bool Btree::insert（typekey key）
{
	return insert（keyNULL）;
}

/*插入新结点*/
bool Btree::insert（typekey keypword val）
{
	if（root->num==0）
	{
		root->key[0]=key;
		root->val[0]=val;
		root->num++;
		counts++;
		return true;
	}

	btree btpt;
	pt=root;
	bt=root;
	if（search（keybtpt）==-1）
	{
		if（insert（keyvalptbt））
		{
			counts++

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        264  2009-01-14 14:24  readme.txt

     文件    1863649  2010-01-12 13:52  dict.dat

     文件      13115  2009-01-14 13:51  Btree.cpp

     文件       2802  2009-01-14 13:21  Btree.h

     文件       7446  2009-01-14 13:38  Dict.cpp

     文件       1820  2009-01-14 13:51  Dict.h

     文件       3490  2010-01-12 13:56  Hash.cpp

     文件       1298  2010-01-12 13:56  Hash.h

     文件        857  2010-01-12 13:39  Node.h

     文件        814  2009-01-14 13:08  testDict.cpp

----------- ---------  ---------- -----  ----

              1895555                    10