b树的算法.c

B树的相关算法。源程序

#define	m	5		/*B树的阶，暂设为5*/ typedef	struct NODE{ 	int	keynum;		/*结点中关键码的个数，即结点的大小*/ 	struct  NODE  *parent;   /*指向双亲结点*/ 	KeyType key[m+1];		/*关键码向量，0号单元未用*/ 	struct  NODE  *ptr[m+1];   /*子树指针向量*/ 	record	*recptr[m+1];   /*记录指针向量*/
	}NodeType;			/*B树结点类型*/

typedef	struct{
	NodeType   *pt;		/*指向找到的结点*/
	int      i;		/*在结点中的关键码序号，结点序号区间[1…m]*/
	int      tag;		/* 1:查找成功，0:查找失败*/
	}Result;			/*B树的查找结果类型*/

Result  SearchBTree(NodeType *t,KeyType kx)
{	/*在m阶B树t上查找关键码kx，反回(pt,i,tag)。若查找成功，则特征值tag=1，*/
/*指针pt所指结点中第i个关键码等于kx；否则，特征值tag=0,等于kx的关键码记录*/
/*应插入在指针pt所指结点中第i个和第i+1个关键码之间*/
	p=t;q=NULL;found=FALSE;i=0;	/*初始化，p指向待查结点，q指向p的双亲*/
	while(p&&!found)
	{	n=p->keynum;i=Search(p,kx); 	/*在p-->key[1…keynum]中查找*/
		if(i>0&&p->key[i]= =kx) found=TRUE;  /*找到*/
		else	{q=p;p=p->ptr[i];}
	}
	if(found)	return (p,i,1);		/*查找成功*/
	else	return (q,i,0);			/*查找不成功，反回kx的插入位置信息*/
}

int InserBTree(NodeType **t,KeyType kx,NodeType *q,int i) {	/*在m阶B树*t上结点*q的key[i],key[i+1]之间插入关键码kx*/     /*若引起结点过大，则沿双亲链进行必要的结点分裂调整，使*t仍为m阶B树*/
x=kx;ap=NULL;finished=FALSE;
while(q&&!finished)
{	Insert(q,i,x,ap);   /*将x和ap分别插入到q->key[i+1]和q->ptr[i+1]*/
	if(q->keynum<m)   finished=TRUE;	/*插入完成*/
	else
	{	/*分裂结点*p*/
		s=m/2;split(q,ap);x=q->key[s];
	/*将q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新结点*ap*/
		q=q->parent;
		if(q)	i=Search(q,kx);  /*在双亲结点*q中查找kx的插入位置*/
			
	}/*else*/
}/*while*/
if(!finished)  /*(*t)是空树或根结点已分裂为*q*和ap*/
	NewRoot(t,q,x,ap);  /*生成含信息(t,x,ap)的新的根结点*t,原*t和ap为子树指针*/
}