btree_build.cpp

1.B树的实现 2.ElfHash的实现 3.三种排序方式(插入

#include<iostream>
#include<fstream>
#include<string>
#include<direct.h>
using namespace std;

const int MaxM = 100;

template<typename T>
struct BTreeNode{
	int n;
	T keys[MaxM];
	bool leaf;
	BTreeNode *c[MaxM+1];
	int nc[MaxM+1];
	int linenum, tot;
};

template<typename T>
bool BTreeSearch(BTreeNode<T> *x, T k){

	int i = 1;

	while ((i <= x->n) && (k > x->keys[i-1])) i++;

	if ((i <= x->n) && (k == x->keys[i-1])) return true;

	if (x->leaf) return false;

	return BTreeSearch(x->c[i-1], k);

}

template<typename T>
void BTreeSplit(BTreeNode<T> *x, int i, BTreeNode<T> *y){

	BTreeNode<T> *z = new BTreeNode<T>;

	z->leaf = y->leaf;

	z->n = t - 1;

	for (int j=1; j<=t-1; ++j)
		z->keys[j-1] = y->keys[j+t-1];
	
	if (!y->leaf)
		for (int j=1;j<=t;++j){
			z->c[j-1] = y->c[j+t-1];
//			z->nc[j-1] = y->nc[j+t-1];
		}

	y->n = t-1;
	for (int j=x->n+1;j>=i+1;--j){
		x->c[j] = x->c[j-1];
//		x->nc[j] = x->nc[j-1];
	}

	x->c[i] = z;
//	x->nc[i] = z->n;
	for (int j=x->n;j>=i;--j)
		x->keys[j] = x->keys[j-1];

	x->keys[i-1] = y->keys[t-1];
	x->n = x->n + 1;
}

template<typename T>
void BTreeInsert_NFull(BTreeNode<T> *x, T k){
	int i = x->n;
	if (x->leaf){
		while ((i >= 1) && (k < x->keys[i-1])){
			x->keys[i] = x->keys[i-1];
			i--;
		}
		x->keys[i] = k;
		x->n = x->n + 1;
	}
	else{
		while ((i >= 1) && (k < x->keys[i-1])) i--;
		i++;
		if (x->c[i-1]->n == 2*t-1){
			BTreeSplit(x, i, x->c[i-1]);
			if (k > x->keys[i-1]) i++;
		}
		BTreeInsert_NFull(x->c[i-1], k);
	}
}


template<typename T>
void BTreeInsert(BTreeNode<T> *r, T k){
	if (BTreeSearch(r, k)) return;
	if (r->n == 2*t-1){
		BTreeNode<T> *s = new BTreeNode<T>;
		root = s;
		s->leaf = false;
		s->n = 0;
		s->c[0] =  r;
		//s->nc[0] = r->n;
		BTreeSplit(s, 1, r);
		BTreeInsert_NFull(s, k);
	}
	else 
		BTreeInsert_NFull(r, k);
}

template<typename T>
void BTree_Creat(BTreeNode<T> *x){
	x->leaf = true;
	x->n = 0;
}

//string infile[] = {"en-only.dic", "en_US-only.dic", "en_GB-only.dic", "en_CA-only.dic"};
string infile[] = {"input.txt"};


int M, t;
int LineNum;
BTreeNode<string> *root = new BTreeNode<string>;
int depth = 0;

template<typename T>
int Find(BTreeNode<T> *x, int dep){
	if (dep > depth) depth = dep;

	int tot = x->n;

	x->linenum = LineNum++;
	if (x->leaf) return (x->tot=tot);
	for (int i=0;i<=x->n;++i){
		x->nc[i] = Find(x->c[i], dep+1);
		tot += x->nc[i];
	}
	return x->tot = tot;
}

ofstream fout("output.out");

template<typename T>
void Print(BTreeNode<T> *x){
	fout.seekp(1000*x->linenum,ios::beg);
	fout<<x->n<<' '<<x->tot<<' ';
	if (x->leaf) fout<<"T "; else fout<<"F ";

	for (int i=0;i<x->n;++i){
		fout<<x->keys[i]<<' ';
	}
	
	if (x->leaf) return;

	for (int i=0;i<=x->n;++i)
		fout<<x->c[i]->linenum<<' '<<x->nc[i]<<' ';

	for (int i=0;i<=x->n;++i)
		Print(x->c[i]);
}

int main(){
	cin>>M;
	t = (M + 1)/2;
	BTree_Creat(root);

	for (int i=0;i<1;++i){
		ifstream fin(infile[i].c_str());
		string s;
		while (fin>>s)
			BTreeInsert(root, s);
	}

	Find(root, 0);
	Print(root);

	cout<<"The number of leaves: "<<root->tot<<endl;
	cout<<"The height of the B+ Tree: "<<depth<<endl;
	return 0;
}