myb+t.cpp

实现一个B*Tree的添加和查找

#define RELEASE_BT

#include <stdio.h>
#include <cstring>
#include <direct.h>
#include <stdlib.h>
#define Tkey char*
#ifdef DEBUG_BT
	#define PBTnode BTnode*
#endif
#ifdef RELEASE_BT
	#define PBTnode int
#endif
#define WIDTH 301
#define NAMELEN 5
#define PREFIX 3
#define MAXWORDLEN 30
#define MAXLIMIT 200
#define LOWLIMIT 133
#define MAXNO 10000

struct BTnode
{
	PBTnode self;
	bool leaf, live;
	PBTnode neighbor; // brother node in the same level
	int keyc;
	Tkey* keys;
	int* subcnt;
	PBTnode* sons;
};
/*
	leaf keyc -- 4bytes 
	datanum -- int 4bytes
	neighbor -- int 4bytes
	length of keys -- 4bytes
	sons -- (keyc + 1) * 4 bytes
	keys -- length of keys
*/
struct BTree
{
	BTnode* root;
	PBTnode rootAddress; // name of the root in this tree
	char* ID;
	int width; // the maxium number 
	int nodeno; // counter of name which is assigned to the node in this tree
};
/*
	rootAddress -- 4bytes
	width -- 4bytes
	nodeno -- 4bytes
	ID
*/

BTnode* keepnode[MAXNO];
int resource[MAXNO];
int rescnt=-1;
int iocnt;

void showError(char filename[])
{
   printf("Cannot open file %s !\n", filename);
   exit(1);
}

BTnode* BTnodeCreate(BTree* t, int count)
{
	BTnode* x = new BTnode;
	#ifdef RELEASE_BT
	t->nodeno+=count;
	x->self = t->nodeno;
	#endif
	#ifdef DEBUG_BT
	x->self = x;
	#endif
	x->live = true;
	x->leaf = false;
	x->keyc = 0;
	x->neighbor = 0;
	x->keys = new Tkey[t->width];
	for (int i = 0; i < t->width; ++i)
	    x->keys[i] = 0;
	x->sons = new PBTnode[t->width+1];
	for (int i = 0; i <= t->width; ++i)
	    x->sons[i] = 0;
	x->subcnt = new int[t->width+1];
	for (int i = 0; i <= t->width; ++i)
	    x->subcnt[i] = 0;
	return x;
}

BTree* BTCreate(const int width, const char ID[])
{
	BTree* t = new BTree;
	t->width = width;
	t->nodeno = 0;
	
	BTnode* x = BTnodeCreate(t, 1);
	x->leaf = true;
	t->root = x;
	t->rootAddress = t->root->self;
	
	t->ID = new char[strlen(ID)];
	strcpy(t->ID, ID); // ID copy
	
	return t;
}

char* GetFN(BTree* t, int no)
{
	int pre = strlen(t->ID)+7;
	int tmp = no;
	char* filename = new char[pre + NAMELEN];
	strcpy(filename, ".\\temp\\");
	strcat(filename, t->ID);
	for (int i = pre+NAMELEN-1; i >= pre; i--)
		{
			filename[i] = (char)(tmp%10 + 48);
			tmp = tmp / 10;
		}
	filename[pre+NAMELEN] = '\0';
	strcat(filename, ".btn\0");
	return filename;
}

void EmptyNode(BTnode* x)
{
	delete[] x->sons;
	delete[] x->subcnt;
	for (int i = 0; i < x->keyc; ++i) delete[] x->keys[i];
	delete[] x->keys;
	delete x;
}

void DiskRealWrite(BTree* t, BTnode* x)
{
	++iocnt;
	#ifdef RELEASE_BT
 		char* filename = GetFN(t, x->self);
		FILE* diskf;		
		if ((diskf = fopen(filename, "w")) == 0) showError(filename);
		
		PBTnode tmp[2];
		if (x->leaf) 
		   fprintf(diskf, "%d ",x->keyc);
		else
		   fprintf(diskf, "%d ",-x->keyc);
		fprintf(diskf, "%d ", x->neighbor);
		int i = 0;
		if (!x->leaf)
		{
			for (int i = 0; i <= x->keyc; ++i) fprintf(diskf, "%d ", x->sons[i]);
			for (int i = 0; i <= x->keyc; ++i) fprintf(diskf, "%d ", x->subcnt[i]);
		}
		for (i = 0; i < x->keyc; ++i)
			fprintf(diskf, "%s ", x->keys[i]);
		fclose(diskf);
		if (x != t->root)
			EmptyNode(x);
	#endif
}

void DiskWrite(BTree *t, BTnode *x)
{
	x->live = false;
	if (keepnode[x->self] == 0)
	{
		++rescnt;
		resource[rescnt] = x->self;
		keepnode[x->self] = x;
		if (rescnt == MAXLIMIT)
		{
			int i, up = rescnt;
			for (i = 0; i <= up && rescnt > LOWLIMIT; ++i)
				if (!keepnode[resource[i]]->live)
				{
					DiskRealWrite(t, keepnode[resource[i]]);
					keepnode[resource[i]] = 0;
					resource[i] = 0;
					--rescnt;
				}
			up = 0;
			for (i = 0; i <= rescnt; ++i)
			{
				while (resource[up] == 0) ++up;
				resource[i] = resource[up];
				++up;
			}
		}
	}
}

void DeconNode(BTnode *x)
{
	x->live = false;
	if (keepnode[x->self] == 0)
	{
		++rescnt;
		resource[rescnt] = x->self;
		keepnode[x->self] = x;
		if (rescnt == MAXLIMIT)
		{
			int i, up = rescnt;
			for (i = 0; i <= up && rescnt > LOWLIMIT; ++i)
				if (!keepnode[resource[i]]->live)
				{
					EmptyNode(x);
					keepnode[resource[i]] = 0;
					resource[i] = 0;
					--rescnt;
				}
			up = 0;
			for (i = 0; i <= rescnt; ++i)
			{
				while (resource[up] == 0) ++up;
				resource[i] = resource[up];
				++up;
			}
		}
	}
}

BTnode* DiskRead(BTree* t, PBTnode px)
{
	++iocnt;
	#ifdef RELEASE_BT
		if (keepnode[px] != 0) 
		{
			keepnode[px]->live = true;
			return keepnode[px];
		}
		char* filename = GetFN(t, px);
		FILE* diskf;
		if ((diskf = fopen(filename, "r")) == 0) return 0;

		BTnode* x = BTnodeCreate(t, 0);
		x->self = px;
		fscanf(diskf, "%d", &x->keyc);
		if (x->keyc > 0) x->leaf = true; else x->leaf = false;
		x->keyc = abs(x->keyc);
		fscanf(diskf, "%d", &x->neighbor);
		if (!x->leaf)
		{
			for (int i = 0; i <= x->keyc; ++i) fscanf(diskf, "%d", &x->sons[i]);
			for (int i = 0; i <= x->keyc; ++i) fscanf(diskf, "%d", &x->subcnt[i]);
		}
		
		char* buffer = new char[MAXWORDLEN];
		for (int i = 0; i < x->keyc; ++i)
		{
			fscanf(diskf, "%s", buffer);
			x->keys[i] = new char[strlen(buffer) + 1];
			strcpy(x->keys[i], buffer);
		}
		
		fclose(diskf);
		return x;
	#endif
	#ifdef DEBUG_BT
		return px;
	#endif
}

BTree* BTread(char ID[])
{
	BTree* t = new BTree;
	int lID = strlen(ID);
	t->ID = new char[lID];
	strcpy(t->ID, ID);
	
	char* filename = new char[lID + 11];
	strcpy(filename, ".\\temp\\");
	strcat(filename, ID);
	strcat(&filename[lID], ".bts\0");
	FILE* diskf;
  if ((diskf = fopen(filename, "r")) == 0) showError(filename);
	fscanf(diskf, "%d %d %d", &t->rootAddress, &t->width, &t->nodeno);
	fclose(diskf);
	
	t->root = DiskRead(t, t->rootAddress);
	return t;
}

void BTwrite(BTree* t)
{	
	int lID = strlen(t->ID);
	char* filename = new char[lID + 11];
	strcpy(filename, ".\\temp\\");
	strcat(filename, t->ID);
	strcat(&filename[lID], ".bts\0");
	FILE* diskf;
    if ((diskf = fopen(filename, "w")) == 0) showError(filename);
	
	fprintf(diskf, "%d %d %d ", t->rootAddress, t->width, t->nodeno);
	fprintf(diskf, "%s", t->ID);
	
	fclose(diskf);
}

void BTDecon(BTree* t)
{
	for (int i = 0; i <= rescnt; ++i)
		if (keepnode[resource[i]] != t->root)
			DiskWrite(t, keepnode[resource[i]]);
	DiskWrite(t, t->root);
	BTwrite(t);
}

void keyclone(Tkey& a, Tkey& b)
{
	a = new char[strlen(b) + 1];
	strcpy(a, b);
}

int keycmp(Tkey& a, Tkey& b)
{
/*		if (a < b) return -1;
		else
		if (a > b) return 1;
		else return 0;*/
	return strcmp(a, b);
}

void BTSplitChild(BTree* t, BTnode* x, int i, BTnode* y)
{
	int hw = t->width >> 1;
	
	BTnode* z;
	z = BTnodeCreate(t, 1);
	z->leaf = y->leaf;
	z->neighbor = y->neighbor;
	y->neighbor = z->self;
	y->keyc = hw;
	
	int j;
	if (y->leaf)
	{
		z->keyc = hw;
		for (j = 0; j < hw; ++j)
      z->keys[j] = y->keys[hw + j];
	}
	else
	{
		z->keyc = hw;
		for (j = 0; j < hw; ++j)
			z->keys[j] = y->keys[hw + j + 1];
		for (j = 0; j <= hw; ++j)
		{
			z->sons[j] = y->sons[hw + j + 1];
			z->subcnt[j] = y->subcnt[hw + j + 1];
		}
	}
	
	for (j = x->keyc + 1; j > i + 1; --j)
	{
		x->sons[j] = x->sons[j - 1];
		x->subcnt[j] = x->subcnt[j - 1];
	}
	x->sons[i + 1] = z->self;
	
	if (!z->leaf)
	{
		x->subcnt[i + 1] = 0;
		for (j = 0; j <= z->keyc; ++j)
			x->subcnt[i + 1] += z->subcnt[j];
	}
	else
		x->subcnt[i + 1] = z->keyc;
	x->subcnt[i] -= x->subcnt[i + 1];
	
	for (j = x->keyc; j > i; --j)
		x->keys[j] = x->keys[j - 1];
	if (y->leaf)
		keyclone(x->keys[i], y->keys[hw]);
	else
		x->keys[i] = y->keys[hw];
	++x->keyc;
	
	DiskWrite(t, z);
}

void BTInsertNonfull(BTree* t, BTnode* x, Tkey k)
{
	int i = 0, full = t->width;
	BTnode* y;
	while (1)
	{
		i = x->keyc - 1;
		if (x->leaf)
			{
	      while (i >= 0 && keycmp(k, x->keys[i])<0)
				{
					x->keys[i + 1] = x->keys[i];
					--i;
				}
				keyclone(x->keys[i + 1], k);
				++x->keyc;
				DiskWrite(t, x);
				break;
			}
		else
			{
				while (i >= 0 && (keycmp(k, x->keys[i])<0))
					--i;
				++i;
				y = DiskRead(t, x->sons[i]);
				if ((y->leaf && y->keyc == full - 1) || (!y->leaf && y->keyc == full))
					{
						BTSplitChild(t, x, i, y);
						if (keycmp(k, x->keys[i]) >= 0)
						{
							++i;
							DiskWrite(t, y);
							y = DiskRead(t, x->sons[i]);
						}
					}
				++x->subcnt[i];
				DiskWrite(t, x);
				x = y;
			}
	}
}
				
void BTInsert(BTree* t, Tkey k)
{
	BTnode* r = t->root;
 	if ((r->leaf && r->keyc == t->width - 1) || (!r->leaf && r->keyc == t->width))
		{
			BTnode* s = BTnodeCreate(t, 1);
			t->root = s;
			t->rootAddress = s->self;
			s->sons[0] = r->self;
			if (!r->leaf)
				for (int i = 0; i <= r->keyc; ++i)
					s->subcnt[0] += r->subcnt[i];
			else
				s->subcnt[0] += r->keyc;
			BTSplitChild(t, s, 0, r);
			DiskWrite(t, r);
			BTInsertNonfull(t, s, k);
		}
	else
	{
		BTInsertNonfull(t, r, k);
  }
}

void BTPrint(BTree* t)
{
     BTnode* pn = t->root;
     while (!pn->leaf) pn = DiskRead(t, pn->sons[0]);
     int i;
     while (pn != 0)
     {
           for (i = 0; i < pn->keyc; ++i)
               printf("%s ", pn->keys[i]);
           pn = DiskRead(t, pn->neighbor);
     }
     printf("\n");
}
           
BTree* t;

int BTSearch(BTree* t, Tkey k)
{
	BTnode* x = t->root;
	int i, count = 0;
	while (1)
	{
		if (x->leaf)
			{
				i = 0;
				while (i < x->keyc && keycmp(k, x->keys[i]) > 0)
				{
					++count;
					++i;
				}
				return count;
			}
		else
			{
				i = 0;
				while (i < x->keyc && keycmp(k, x->keys[i]) > 0)
				{
					count += x->subcnt[i];
					++i;
				}
				BTnode* tmp = x;
				x = DiskRead(t, x->sons[i]);
				#ifdef RELEASE_BT
				DeconNode(tmp);
				#endif
			}
	}							
}

void LoadFile(BTree* t, char filename[])
{
	FILE* filein =  fopen(filename, "r");
	char word[100];
	int count = 0;
	while (!feof(filein))
	{
		fscanf(filein, "%s", word);
		++count;
		if (count%1000 == 0) printf("Number of words which is now loaded: %d\n", count);
		BTInsert(t, word);
	}
	printf("Number of words which is now loaded: %d\n", count);
	fclose(filein);
}

int main()
{
	do
	{
		printf("Please select:\n");
		printf("1.Build B+Tree\n");
		printf("2.Search Key Word\n");
		printf("3.Quit\n");
		printf("Your choice [1\\2\\3]: ");
		char cmd[100];
		scanf("%s", cmd);
		if (cmd[0] == '1')
			{
				mkdir("temp");
				t = BTCreate(WIDTH, "BT");
				do
				{
					printf("Please input filename of dictionary:");
					scanf("%s", cmd);
					LoadFile(t, cmd);
					printf("Add dictionary again? [Y\\N]");
					scanf("%s", cmd);
				}
				while (cmd[0] == 'Y'|| cmd[0] == 'y');			
				BTDecon(t);
			}
		else
		if (cmd[0] == '2')
			{
				char word[100];
				t = BTread("BT");
				do
				{
					printf("Please input key word : ");
					scanf("%s", word);
					iocnt = 0;
					int bno = BTSearch(t, word);
					++word[strlen(word)-1];
					int eno = BTSearch(t, word);
					printf("The number of words having this prefix = %d\n", eno - bno);
					printf("The number of files read = %d\n", iocnt);
					printf("Search again? [Y\\N]");
					scanf("%s", cmd);
				}
				while (cmd[0] == 'Y'|| cmd[0] == 'y');			
			}
		else break;
	} while (1);
	return 0;
}