?? btree.h

?? our homework big project
?? H
?? 第 1 頁 / 共 3 頁
字號:
12 3 下一頁
//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;						//本節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)
		int flag;                   //葉節(jié)點(diǎn)的標(biāo)志
		int p_leaf_next[N];         //葉節(jié)點(diǎn)存放縱向地址
		T key[N];                   //存放關(guān)鍵字
		node* p_node_next[N];       //非葉節(jié)點(diǎn)存放縱向地址           
		node* p_fathernode;         //存放父節(jié)點(diǎn)地址
		node* p_next;               //節(jié)點(diǎn)存放橫向地址
		node* brother;              //刪除時(shí)用到的兄弟節(jié)點(diǎn)
	};	


	typedef struct inode
	{
		int no;						//本節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)
		int p_leaf_next[N];         //葉節(jié)點(diǎn)存放縱向地址
		int key[N];                   //存放關(guān)鍵字
	};

	typedef struct fnode
	{
		int no;						//本節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)
		int p_leaf_next[N];         //葉節(jié)點(diǎn)存放縱向地址
		float key[N];                   //存放關(guān)鍵字
	};

	typedef struct cnode
	{
		int no;						//本節(jié)點(diǎn)的數(shù)據(jù)個(gè)數(shù)
		int p_leaf_next[N];         //葉節(jié)點(diǎn)存放縱向地址
		char* key[N];               //存放關(guān)鍵字
	};



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

	//others
	bool Isleaf(node* & node);						//檢測是否葉節(jié)點(diǎn)
	bool Isroot(const node* & nodeposition);		//檢測是否根結(jié)點(diǎn)
	void Ini(node* & p);							//節(jié)點(diǎn)初始化
	void Leaf_ifind(T & the_key);					//葉結(jié)點(diǎn)查找函數(shù)（插入時(shí)）
	void Leaf_dfind(T & the_key);					//葉結(jié)點(diǎn)查找函數(shù)（刪除時(shí)）

	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 & );			//數(shù)據(jù)插入（用于float與int）－－－可調(diào)用－－－
	void Resize_leaf();								//分裂葉節(jié)點(diǎn)（用于float與int）
	void Resize_nleaf();							//分裂非葉節(jié)點(diǎn)（用于float與int）
		
	void Del_data(T & ckey);						//刪除－－－可調(diào)用－－－－－－
	void del(T & k);								//
	void del(T & k,const T & t);					//
	void Merge();									//刪除中調(diào)整合并
	void Show();
	int compare(const char* &,const char* &);		//－－－－－－－－－－－－－－	
	int compare(const int &,const int &);			//處理int,float,char的多態(tài)問題
	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;								//實(shí)例的根結(jié)點(diǎn)
	node* m_nodeposition;							
	int m_total;									//記錄數(shù)據(jù)的總數(shù)
	bool m_opf;										//標(biāo)志是否操作過
};




//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－聲明模板類的成員函數(shù)－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－



//－－－－－－－－－－－構(gòu)造函數(shù)－－－－－－－－－－－－－


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


//－－－－－－－－－－－析構(gòu)函數(shù)－－－－－－－－－－－－－


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


//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－模板類的其他成員函數(shù)－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－



//－－－－－－－－－－－判斷內(nèi)存中是否存在b＋樹－－－－－－－－－－－－－－－－



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



//－－－－－－－－處理int，float，char的多態(tài)在各函數(shù)中處理比較大小－－－－－


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


//－－－－－－－－－－－－－－－初始化－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－開辟新節(jié)點(diǎn)時(shí)賦初值－－－－－－－－－－－－－－－－－


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


//－－－－－－－－－－－－－－－根節(jié)點(diǎn)判斷－－－－－－－－－－－－－－－－－－


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


//－－－－－－－－－－－－－－－－葉節(jié)點(diǎn)判斷－－－－－－－－－－－－－－－－－


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


//－－－－－－－－－－－－－－尋找葉節(jié)點(diǎn)（插入時(shí)）－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Leaf_ifind(T & the_key)
{
	bool f=false;
	m_nodeposition=m_noderoot;
	
	while(Isleaf(m_nodeposition)==0)						//還沒到葉節(jié)點(diǎn)則繼續(xù)向下找到葉節(jié)點(diǎn)就中止
	{
		for(int i=0;i<m_nodeposition->no;i++)				//在各層節(jié)點(diǎn)中尋找相應(yīng)的位置				
		{
			f=false;
			if(compare(the_key,m_nodeposition->key[i])==0||
				compare(the_key,m_nodeposition->key[i])==-1)//找到后指針指向下層節(jié)點(diǎn)并跳出循環(huán)
			{
				m_nodeposition=m_nodeposition->p_node_next[i];	 
				f=true;
				break;											 
			}
		}
		if(f==false)break;
	}
	if(f==false)											//尋找的值比任意值都大就指向最右邊的葉節(jié)點(diǎn)
	{
		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];
		}
	}
}


//－－－－－－－－－－－－－－尋找葉節(jié)點(diǎn)（刪除時(shí)）－－－－－－－－－－－－－－－－


template<class T>
void Node<T>::Leaf_dfind(T & the_key)
{
	bool f=false;
	m_nodeposition=m_noderoot;
	
	while(Isleaf(m_nodeposition)==0)							//還沒到葉節(jié)點(diǎn)則繼續(xù)向下找到葉節(jié)點(diǎn)就中止
	{
		for(int i=0;i<m_nodeposition->no;i++)					//在各層節(jié)點(diǎn)中尋找相應(yīng)的位置				
		{
			f=false;
			if(compare(the_key,m_nodeposition->key[i])==0||
				compare(the_key,m_nodeposition->key[i])==-1)	//找到后指針指向下層節(jié)點(diǎn)并跳出循環(huán)
			{
				m_nodeposition=m_nodeposition->p_node_next[i];	 
				f=true;
				break;											 
			}
		}
		if(f==false)break;
	}
	if(f==false)												  //尋找的值比任意值都大就指向最右邊的葉節(jié)點(diǎn)
	{
		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++)				//找到在節(jié)點(diǎn)中的位置
	{
		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++)				//找到在節(jié)點(diǎn)中的位置
	{
		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++)				//找到在節(jié)點(diǎn)中的位置
	{
		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++)				//找到在節(jié)點(diǎn)中的位置
	{
		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++)				//找到在節(jié)點(diǎn)中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
			{f=true;end=m_nodeposition;break;}
	}
	if(f==true)
	{
12 3 下一頁
?? 文件大小 234 K
?? 上傳用戶 setixp
?? 所屬分類數(shù)據(jù)庫系統(tǒng)
??? 相關(guān)標(biāo)簽

#homework #project #our #big
?? 快捷鍵說明

復(fù)制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

?? btree.h

?? 快捷鍵說明
