btree_search.cpp

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

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

int filesum, nodesum;

const int MaxM = 100;
ifstream fin("output.out");


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

BTreeNode<string> *root;
BTreeNode<string> *ci;

template<typename T>
void DiskRead(BTreeNode<T> *x, int line){
	fin.seekg(line * 1000, ios::beg);

	fin>>x->n;
	fin>>x->tot;
	char cc;
	fin>>cc;
	if (cc=='F') x->leaf = false; else x->leaf = true;
	for (int i=0;i<x->n;++i){
		fin >> x->keys[i];
	}
	for (int i=0;i<=x->n;++i){
		fin >> x->c[i] >> x->nc[i];
	}
}

template<typename T>
int BTreeSearch(BTreeNode<T> *x, T &k){
	int count = 0;

	int i = 1;

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

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

	if (x->leaf) return count;

	DiskRead(ci, x->c[i-1]);
	filesum++;
	nodesum+= ci->tot;
	return count+BTreeSearch(ci, k);
}


void init(){
	root = new BTreeNode<string>;
	ci = new BTreeNode<string>;
	fin>>root->n;
	fin>>root->tot;
	char cc;
	fin>>cc;
	if (cc=='F') root->leaf = false; else root->leaf = true;
	for (int i=0;i<root->n;++i){
		fin >> root->keys[i];
	}
	for (int i=0;i<=root->n;++i){
		fin >> root->c[i] >> root->nc[i];
	}
	return;
}

int main(){
	string ss;
	cin>>ss;
	
	init();
	string st = ss + char(125);
	cout<<BTreeSearch(root, st)- BTreeSearch(root, ss)<<endl;
	//cout<<BTreeSearch(root, ss)<<endl;// - BTreeSearch(root, ss)<<endl;
	cout<<"The number of read files: "<<filesum<<endl;
	cout<<"The number of words: "<<nodesum<<endl;
	return 0;
}