?? bptree.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;





//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－聲明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 tnode
	{
		int no;						//本節點的數據個數
		int p_leaf_next[N];         //葉節點存放縱向地址
		T 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 &);					//建立索引文件
	void Buildtree(string &);				//建立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";

}


//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－模板類的其他成員函數－－－－－－－－－－－－－－－－－
//－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－



//－－－－－－－－－－－判斷內存中是否存在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(ckey,m_nodeposition->key[i])==0)
			{f=true;no.push_back(m_nodeposition->p_leaf_next[i]);break;}
	}
	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(ckey,m_nodeposition->key[i])==0)
			{f=true;break;}
	}
	if(f==ture)
	{
		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->leaf_next[j]);
		}
	}
	return no;
}

//－－－－－－－－－－－－－尋找>－－－－－－－－－－－－－－－－－－－

template<class T>
vector<int> Node<T>::Bsearch(T & key)
{
	
	bool f=false;int i;
	vector<int> no;
	Leaf_dfind(key);
	for(i=0;i<m_nodeposition->no;i++)				//找到在節點中的位置
	{
		if(compare(ckey,m_nodeposition->key[i])==0)
			{f=true;break;}
	}
	if(f==ture)
	{
		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 & key)
{
	bool f=false;int i;
	node* end;
	vector<int> no;
	Leaf_dfind(key);
	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==ture)
	{
12 3 下一頁
?? 文件大小 234 K
?? 上傳用戶 setixp
?? 所屬分類數據庫系統
??? 相關標簽

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

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

?? bptree.h

?? 快捷鍵說明
