#define m 5 /*B 树的阶,暂设为5*/ |
typedef struct NODE |
{ |
int keynum; /* 结点中关键码的个数,即结点的大小*/ |
struct NODE *parent; /*指向双亲结点*/ |
KeyTypekey[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 的插入位置信息*/ |
} |