btree.h

our homework big project

//b+tree.h--class definition for the b+ tree


#ifndef BTREE_H_
#define BTREE_H_

#include<iostream>
#include<string>
#include<fstream>
#include<iomanip>
#include<cstdlib>
#include<vector>
using namespace std;
const int N=5;
#define NULL 0




//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－声明b＋树的模板类－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－


template<class T>
class Node     
{
public:
	typedef struct node
	{
		int no;						//本节点的数据个数
		int flag;                   //叶节点的标志
		int p_leaf_next[N];         //叶节点存放纵向地址
		T key[N];                   //存放关键字
		node* p_node_next[N];       //非叶节点存放纵向地址           
		node* p_fathernode;         //存放父节点地址
		node* p_next;               //节点存放横向地址
		node* brother;              //删除时用到的兄弟节点
	};	


	typedef struct inode
	{
		int no;						//本节点的数据个数
		int p_leaf_next[N];         //叶节点存放纵向地址
		int key[N];                   //存放关键字
	};

	typedef struct fnode
	{
		int no;						//本节点的数据个数
		int p_leaf_next[N];         //叶节点存放纵向地址
		float key[N];                   //存放关键字
	};

	typedef struct cnode
	{
		int no;						//本节点的数据个数
		int p_leaf_next[N];         //叶节点存放纵向地址
		char* key[N];               //存放关键字
	};



	//constructor 
	Node();
	~Node();

	//others
	bool Isleaf(node* & node);						//检测是否叶节点
	bool Isroot(const node* & nodeposition);		//检测是否根结点
	void Ini(node* & p);							//节点初始化
	void Leaf_ifind(T & the_key);					//叶结点查找函数（插入时）
	void Leaf_dfind(T & the_key);					//叶结点查找函数（删除时）

	vector<int> Eqsearch( T  key);
	vector<int> Neqsearch( T  key);
	vector<int> Besearch( T  key);
	vector<int> Bsearch( T  key);
	vector<int> Ssearch( T  key);
	vector<int> Sesearch(T  key);

	
	void Insert_node(T ,const int & );			//数据插入（用于float与int）－－－可调用－－－
	void Resize_leaf();								//分裂叶节点（用于float与int）
	void Resize_nleaf();							//分裂非叶节点（用于float与int）
		
	void Del_data(T & ckey);						//删除－－－可调用－－－－－－
	void del(T & k);								//
	void del(T & k,const T & t);					//
	void Merge();									//删除中调整合并
	void Show();
	int compare(const char* &,const char* &);		//－－－－－－－－－－－－－－	
	int compare(const int &,const int &);			//处理int,float,char的多态问题
	int compare(const float &,const float &);		//－－－－－－－－－－－－－－

	void Index(string &,int);					//建立索引文件
	void Buildtree(string &,int);				//建立b＋树
	void Index(string &,float);				//建立索引文件---重载
	void Buildtree(string &,float);			//建立b＋树－－－重载
	void Index(string &,char);					//建立索引文件－－重载
	void Buildtree(string &,char);				//建立b＋树－－－重载
	bool Justify();

	

private:
	
	node* m_nodehead;									
	node* m_noderoot;								//实例的根结点
	node* m_nodeposition;							
	int m_total;									//记录数据的总数
	bool m_opf;										//标志是否操作过
};




//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－声明模板类的成员函数－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－



//－－－－－－－－－－－构造函数－－－－－－－－－－－－－


template<class T>
Node<T>::Node()
{
	m_total=0;
	m_nodehead=new node;
	m_opf=false;
	m_nodehead->p_next=NULL;
	m_nodehead->brother=NULL;
	m_nodehead->p_fathernode=NULL;
	for(int i=0;i<N;i++)
	{
		m_nodehead->p_node_next[i]=NULL;
		m_nodehead->p_leaf_next[i]=NULL;
		m_nodehead->key[i]=NULL;
	}
	m_nodehead->p_node_next[N-1]=NULL;
	m_nodehead->p_leaf_next[N-1]=NULL;
	m_nodehead->no=0;
	m_nodehead->flag=1;
	m_noderoot=m_nodehead;
	m_nodeposition=m_nodehead;
};


//－－－－－－－－－－－析构函数－－－－－－－－－－－－－


template<class T>
Node<T>::~Node()
{
	node* temp=m_noderoot;
	node* temp1;node* temp2;
	for(;Isleaf(temp)==0;)
	{
		temp1=temp;
		temp=temp->p_node_next[0];
		for(;temp1->p_next!=NULL;)
		{
			temp2=temp1;
			temp1=temp1->p_next;
			delete temp2;
			temp2=NULL;
		}
		delete temp1;
		temp1=NULL;
		temp2=NULL;
	}
	for(;temp->p_next!=NULL;)
	{
		temp1=temp;
		temp=temp->p_next;
		delete temp1;
		temp1=NULL;
	}
	delete temp;
	temp=NULL;
	cout<<"haha";
/*	if(m_nodehead==m_noderoot&&m_noderoot==m_nodeposition)delete m_nodehead;
	else if(m_nodeposition==m_noderoot&&m_noderoot!=m_nodehead){delete m_nodehead;delete m_noderoot;}
	else if(m_nodeposition==m_nodehead&&m_noderoot!=m_nodehead){delete m_noderoot;delete m_nodehead;}
	else if(m_noderoot==m_nodehead&&m_nodeposition!=m_noderoot){delete m_nodehead;delete m_nodeposition;}
	else
	{
		delete m_noderoot;
		delete m_nodehead;
		delete m_nodeposition;
	}*/
}


//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－模板类的其他成员函数－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－



//－－－－－－－－－－－判断内存中是否存在b＋树－－－－－－－－－－－－－－－－



template<class T>
bool Node<T>::Justify()
{
	if(m_opf==true)return true;
	else
		return false;
}



//－－－－－－－－处理int，float，char的多态在各函数中处理比较大小－－－－－


template<class T>
int Node<T>::compare(const float & a,const float & b)
{
	if((a-b)>-0.001&&(a-b)<0.001)return 0;
	else if((a-b)>-0.001)return 1;
	else 
		return -1;
}

template<class T>
int Node<T>::compare(const char* & a,const char* & b)
{
	if(b==NULL)b="";
	if((string)a==(string)b)return 0;
	else if((string)a>(string)b)return 1;
	else 
		return -1;
}

template<class T>
int Node<T>::compare(const int & a,const int & b)
{
	if(a==b)return 0;
	else if(a>b)return 1;
	else
		return -1;
}


//－－－－－－－－－－－－－－－初始化－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－开辟新节点时赋初值－－－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Ini(node* & p)		
{
	p->p_next=NULL;
	p->brother=NULL;
	p->p_fathernode=NULL;
	p->no=NULL;
	p->flag=0;
	for(int i=0;i<N;i++)
	{
		p->p_node_next[i]=NULL;
		p->p_leaf_next[i]=NULL;
		p->key[i]=NULL;
	}
}


//－－－－－－－－－－－－－－－根节点判断－－－－－－－－－－－－－－－－－－


template<class T>
bool Node<T>::Isroot(const node* & nodeposition)
{
	
	if(nodeposition->p_fathernode==NULL)
		return 1;
	else
		return 0;
}


//－－－－－－－－－－－－－－－－叶节点判断－－－－－－－－－－－－－－－－－


template<class T>
bool Node<T>::Isleaf(node* & cnode)
{
	if(cnode->flag==0)
		return false;
	else
		return true;
}


//－－－－－－－－－－－－－－寻找叶节点（插入时）－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Leaf_ifind(T & the_key)
{
	bool f=false;
	m_nodeposition=m_noderoot;
	
	while(Isleaf(m_nodeposition)==0)						//还没到叶节点则继续向下找到叶节点就中止
	{
		for(int i=0;i<m_nodeposition->no;i++)				//在各层节点中寻找相应的位置				
		{
			f=false;
			if(compare(the_key,m_nodeposition->key[i])==0||
				compare(the_key,m_nodeposition->key[i])==-1)//找到后指针指向下层节点并跳出循环
			{
				m_nodeposition=m_nodeposition->p_node_next[i];	 
				f=true;
				break;											 
			}
		}
		if(f==false)break;
	}
	if(f==false)											//寻找的值比任意值都大就指向最右边的叶节点
	{
		for(;Isleaf(m_nodeposition)==0;)					//一路上顺便替换最大值
		{
			m_nodeposition->key[m_nodeposition->no-1]=the_key;
			m_nodeposition=m_nodeposition->p_node_next[m_nodeposition->no-1];
		}
	}
}


//－－－－－－－－－－－－－－寻找叶节点（删除时）－－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Leaf_dfind(T & the_key)
{
	bool f=false;
	m_nodeposition=m_noderoot;
	
	while(Isleaf(m_nodeposition)==0)							//还没到叶节点则继续向下找到叶节点就中止
	{
		for(int i=0;i<m_nodeposition->no;i++)					//在各层节点中寻找相应的位置				
		{
			f=false;
			if(compare(the_key,m_nodeposition->key[i])==0||
				compare(the_key,m_nodeposition->key[i])==-1)	//找到后指针指向下层节点并跳出循环
			{
				m_nodeposition=m_nodeposition->p_node_next[i];	 
				f=true;
				break;											 
			}
		}
		if(f==false)break;
	}
	if(f==false)												  //寻找的值比任意值都大就指向最右边的叶节点
	{
		for(;Isleaf(m_nodeposition)==0;)
		{
			m_nodeposition=m_nodeposition->p_node_next[m_nodeposition->no-1];
		}
	}
}


//－－－－－－－－－－－－－－寻找相等的值－－－－－－－－－－－－－－－－


template<class T>
vector<int> Node<T>::Eqsearch(T key)
{
	bool f=false;
	vector<int> no;

	Leaf_dfind(key);
	for(int i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(key,m_nodeposition->key[i])==0)
			{f=true;no.push_back(m_nodeposition->p_leaf_next[i]);break;}
	}
	if(f==false)
		no.push_back(-1);
	return no;
}


//－－－－－－－－－－－－－－寻找不相等－－－－－－－－－－－－－－－－－


template<class T>
vector<int> Node<T>::Neqsearch(T  key)
{
	vector<int> no;
	for(m_nodehead=m_noderoot;m_nodehead!=NULL;m_nodehead=m_nodehead->p_node_next[0])
		m_nodeposition=m_nodehead;
	for(;m_nodeposition!=NULL;m_nodeposition->p_next)
	{
		for(int i=0;i<m_nodeposition->no;i++)
		{
			if(m_nodeposition->key[i]!=key)
				no.push_back(m_nodeposition->p_leaf_next[i]);
		}
	}
	return no;
}


//－－－－－－－－－－－－寻找>=－－－－－－－－－－－－－－－－－－－－－－


template<class T>
vector<int> Node<T>::Besearch(T  key)
{
	bool f=false;int i;
	vector<int> no;
	Leaf_dfind(key);
	for(i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(key,m_nodeposition->key[i])==0)
			{f=true;break;}
	}
	if(f==true)
	{
		for(;i<m_nodeposition->no;i++)
		{
			no.push_back(m_nodeposition->p_leaf_next[i]);
		}
		for(m_nodeposition=m_nodeposition->p_next;m_nodeposition!=NULL;m_nodeposition=m_nodeposition->p_next)
		{
			for(int j=0;j<m_nodeposition->no;j++)
				no.push_back(m_nodeposition->p_leaf_next[j]);
		}
	}
	return no;
}

//－－－－－－－－－－－－－寻找>－－－－－－－－－－－－－－－－－－－

template<class T>
vector<int> Node<T>::Bsearch(T  ckey)
{
	
	bool f=false;int i;
	vector<int> no;
	Leaf_dfind(ckey);
	for(i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
			{f=true;break;}
	}
	if(f==true)
	{
		for(;i+1<m_nodeposition->no;i++)
		{
			no.push_back(m_nodeposition->p_leaf_next[i+1]);
		}
		for(m_nodeposition=m_nodeposition->p_next;m_nodeposition!=NULL;m_nodeposition=m_nodeposition->p_next)
		{
			for(int j=0;j<m_nodeposition->no;j++)
				no.push_back(m_nodeposition->p_leaf_next[j]);
		}
		
	}
	return no;
}

//－－－－－－－－－－－－－－－－寻找<=－－－－－－－－－－－－－－－－－


template<class T>
vector<int> Node<T>::Sesearch(T  ckey)
{
	bool f=false;int i;
	node* end;
	vector<int> no;
	Leaf_dfind(ckey);
	for(m_nodehead=m_noderoot;m_nodehead!=NULL;m_nodehead=m_nodehead->p_node_next[0])
		;
	for(i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
			{f=true;end=m_nodeposition;break;}
	}
	if(f==true)
	{
		for(m_nodeposition=m_noderoot;m_nodeposition!=end;m_nodeposition=m_nodeposition->p_next)
		{
			for(int j=0;j<m_nodeposition->no;j++)
				no.push_back(m_nodeposition->p_leaf_next[j]);
		}
		for(int x=0;x<=i;x++)
			no.push_back(m_nodeposition->p_leaf_next[x]);
		
	}
	return no;
}


//－－－－－－－－－－－－－－－－寻找<－－－－－－－－－－－－－－－－－


template<class T>
vector<int> Node<T>::Ssearch(T  ckey)
{
	bool f=false;int i;
	node* end;
	vector<int> no;
	Leaf_dfind(ckey);
	for(m_nodehead=m_noderoot;m_nodehead!=NULL;m_nodehead=m_nodehead->p_node_next[0])
		;
	for(i=0;i<m_nodeposition->no;i++)				//找到在节点中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
			{f=true;end=m_nodeposition;break;}
	}
	if(f==true)
	{