B-树问题
本人搞不懂下面的程序出错在哪里。希望那位大虾帮帮忙，讲解下，，万分感谢！！！/*B-树
*查找
*插入
*删除
*/
#include<stdio.h>
#include<stdlib.h>
#define m 3
typedef struct node
{
int n;
int v[2*m];
struct node *prt;
struct node *link[2*m+1];
}NODE;
NODE * lookup(NODE *h, int *k, int *flag, int x)
{
NODE *p,*q;
p=h;
q=p;
*flag=0;
while (p != NULL && *flag == 0)
{
q=p;
*k=1;
while (*k < q->n && q->v[*k-1] < x)
{
*k=*k+1;
}
if (q->v[*k-1] == x)
{
*flag=1;
}
else
{
if (*k == q->n && q->v[*k-1] < x)
{
p=q->link[*k];
}
else
{
p=q->link[*k-1];
*k=*k-1;
}
}
}
return q;
}
void insert(NODE **h, int x)
{
NODE *p,*q,*u,*s;
int i,k,flag,y,t;
if (*h == NULL)
{
*h=(NODE *)malloc(sizeof(NODE));
for (i=0; i < 2*m+1; i++)
{
(*h)->link[i]=NULL;
}
(*h)->prt=NULL;
(*h)->n=1;
(*h)->v[0]=x;
return ;
}
q=lookup(*h,&k,&flag,x);
if (flag == 1)
{
return ;
}
p=NULL;
t=0;
while (t == 0)
{
if (q->n == k)
{
y=x;
u=p; /*这里的P表示空指针或是新建的右指针*/
}
else
{
y=q->v[q->n-1];
u=q->link[q->n];
for (i=q->n-1; i > k; i--)
{
q->v[i]=q->v[i-1];
q->link[i+1]=q->link[i];
}
q->v[k]=x;
q->link[k+1]=p;/*这里的P表示空指针或是新建的右指针*/
if (p != NULL)
{
p->prt=q;
}
}
if (q->n < 2*m)
{
q->n=q->n+1;
q->v[q->n-1]=y;
q->link[q->n]=u;
if (u != NULL)
{
u->prt=q;
}
t=1;
}
else
{/*1*/
p=(NODE *)malloc(sizeof(NODE));
p->n=m;
q->n=m;
p->prt=q->prt;
x=q->v[m];
for (i=0; i < m-1; i++)
{
p->v[i]=q->v[i+m+1];
p->link[i]=q->link[i+m+1];
if (q->link[i+m+1] != NULL)
{
q->link[i+m+1]->prt=p;
}
}
p->v[m-1]=y;
p->link[m-1]=q->link[2*m];
p->link[m]=u;
if (u != NULL)
{
u->prt=p;
}
for (i=m+1; i < 2*m+1; i++)
{
q->link[i]=NULL;
p->link[i]=NULL;
}
if (q->prt == NULL)
{
s=(NODE *)malloc(sizeof(NODE));
s->n=1;
s->v[0]=x;
s->link[0]=q;
s->link[1]=p;
s->prt=NULL;
for (i=2; i < 2*m+1; i++)
{
s->link[i]=NULL;
}
*h=s;
p->prt=s;
q->prt=s;
t=1;
}
else
{
q=q->prt;
k=1;
while (k <= q->n && q->v[k-1] < x)
{
k++;
}
k--;
}
}/*1*/
}/*第一个while*/
return ;
}
void dell(NODE **h, int x)
{
NODE *p,*q,*s,*u;
int i,j,y,k,flag,t;
q=lookup(*h,&k,&flag,x);
if (flag == 0)
{
return ;
}
p=q->link[k];
if (p != NULL)
{
while (p->link[0] != NULL)
{
p=p->link[0];
}
q->v[k-1]=p->v[0];
q=p;
k=1;
}
for (i=k; i < q->n; i++)//
{
q->v[i-1]=q->v[i];
}
q->n=q->n-1;
while (q != *h && q->n < m)
{
p=q->prt;
j=1;
while (j < p->n && p->link[j-1] != q)
{
j++;
}
if (j <= p->n && (p->link[j])->n > m) /*右借*/
{
s=p->link[j];
y=p->v[j-1];
p->v[j-1]=s->v[0];
u=s->link[0];
for (i=1; i < s->n; i++)
{
s->v[i-1]=s->v[i];
s->link[i-1]=s->link[i];
}
s->link[s->n-1]=s->link[s->n];
s->link[s->n]=NULL;
s->n=s->n-1;
q->n=q->n+1;
q->v[q->n-1]=y;
q->link[q->n]=u;
if (u != NULL)
{
u->prt=q;
}
}
else
{
if (j > 1 && p->link[j-2]->n > m) /*左借*/
{
s=p->link[j-2];
y=p->v[j-2];
u=s->link[s->n];
s->link[s->n]=NULL;
p->v[j-2]=s->v[s->n-1];
s->n=s->n-1;
q->n=q->n+1;
q->link[q->n]=q->link[q->n-1];
for (i=q->n-1; i > 0; i--)
{
q->v[i]=q->v[i-1];
q->link[i]=q->link[i-1];
}
q->v[0]=y;
q->link[0]=u;
if (u != NULL)
{
u->prt=q;
}
}
else /*合并*/
{
if (j == p->n+1)
{
q=p->link[j-2];
s=p->link[j-1];
j--;
}
else
{
s=p->link[j];
}
q->v[q->n]=p->v[j-1];
for (i=0; i < s->n; i++)
{
q->v[q->n+i+1]=s->v[i];
q->link[q->n+i+1]=s->link[i];
if (s->link[i] != NULL)
{
s->link[i]->prt=q;
}
}//
q->v[q->n]=p->v[j-1];
t=q->n+1;
for (i=0; i < s->n; i++)
{
q->v[t+i]=s->v[i];
q->link[t+i]=s->link[i];
if (s->link[i] != NULL)
{
s->link[i]->prt=q;
}
}
q->n=2*m;
q->link[t+s->n]=s->link[s->n];
if (s->link[s->n] != NULL)
{
s->link[s->n]->prt=q;
}
free(s);
for (i=j; i < p->n; i++)
{
p->v[i-1]=p->v[i];
p->link[i]=p->link[i+1];
}
p->n=p->n-1;
s=q;
q=p;
}
}
}
if (q == (*h) && q->n == 1)
{
free(*h);
(*h)=s;
(*h)->prt=NULL;printf("error");
if (s->n == 1)
{printf("error");
(*h)=NULL;
free(s);
s=NULL;
}
}
return ;
}
int main()
{
NODE *h=NULL,*p;
int i,k,flag;
for (i=1; i < 51; i++)
{
insert(&h,i);
p=lookup(h,&k,&flag,i);
printf("%d %d %d \n",p->v[k-1],k,flag);
}
for (i=50; i > 2;i--)
{
dell(&h,i);
p=lookup(h,&k,&flag,i);
printf("%d %d %d \n",i,k,flag);
}
return 0;
}
