btree12.c

本系统完成了要求的所有功能

/*图书管理系统*/
/*语言：C         编译环境：VC++6.0*/
/*编写人：梁小秋  时间：2005年3月19*/

#define m 3
#include "stdio.h"
#include "malloc.h"
#include "graphics.h"
#include "dos.h"
#include "conio.h"
#define MAXSIZE 120

typedef struct book{
	int booknum;/*书号*/
	char name[20];   /*书名*/
	char writer[20];  /*作者*/
	int borrow[20];   /*借书证号*/
	int date[20][3];  /*还书日期*/
	int sum;  /*库存量*/
	int left; /*现在量*/
}BookType;

typedef struct node{
	int keynum;  /*关键字*/
	struct node *parent;  /*父结点*/
	int key[m+1];   /*关键字的个数，下标从1开始*/
	struct node *nptr[m+1];  /*指向其孩子结点*/
	BookType *eptr[m+1];   /*  指向其所对应的书的相关信息*/
}NodeType;

typedef struct {
	NodeType *pt;
	int i;
	int tag;
}result;

typedef struct {     /*队列，用于B树的显示*/
    NodeType *items[MAXSIZE];
    int rear,front;
	}queue;
queue *pq;



NodeType *T=NULL;
BookType *t=NULL;
int min=(m/2);/*最少关键字*/
int big=m-1;/*最大关键字*/
int fflag;

char ch[5];

void inttochar(int data,char c[])/*将整数转化为相应的字符串*/
{  int i=0,j=0;
   char temp;
   while(data>0)
     {  c[i++]=data%10+48;
	data=data/10;
     }
   c[i]='\0';
   i--;
   while(i>j)
     { temp=c[i];
       c[i]=c[j];
       c[j]=temp;
       i--;
       j++;
     }
}


void show(NodeType *tree,int x,int y,int level)/*显示B树的子程序*/
{  int i,w,h=60,count=0,v=8,s=10;
   if(tree==NULL)  return;
   w=640/level;
   for(i=1;i<=tree->keynum;i++)
      {  inttochar(tree->key[i],ch);
	 outtextxy(x+count,y,ch);
	 count+=s;
	 if(i<tree->keynum)
           { outtextxy(x+count,y,",");
	     count+=s;
           }
      }
   if(tree->keynum==2)
     {  if(tree->nptr[0]!=NULL)
	  { show(tree->nptr[0],x-w,y+h,level*3);    line(x,y+v,x-w,y+h-v);
	    show(tree->nptr[1],x+s,y+h,level*3);    line(x+s,y+v,x+s,y+h-v);
	    show(tree->nptr[2],x+w+2*s,y+h,level*3);line(x+2*s,y+v,x+w+s,y+h-v);
	  }
     }
   if(tree->keynum==1)
     {  if(tree->nptr[0]!=NULL)
	  { show(tree->nptr[0],x-w,y+h,level*3);    line(x,y+v,x-w,y+h-v);
	    show(tree->nptr[1],x+w,y+h,level*3);    line(x,y+v,x+w,y+h-v);
	  }
     }
}


void showbtree(NodeType *tree)/*调用显示B树的子程序显示B树*/
{  int gdriver=DETECT, gmode;
   initgraph(&gdriver, &gmode, "C:\\TurboC2");
   settextjustify(1,1);
   show(tree,300,40,4);
   getchar();   getchar();
   closegraph();
}


NodeType *split(NodeType *p,int s)/*分裂结点*/
{
	int j;
	NodeType *q;
	q=(NodeType *)malloc(sizeof(NodeType)); /*开辟一个新的结点*/
	q->keynum=m-s;
	q->parent=p->parent;
	q->nptr[0]=p->nptr[s];
	for(j=s+1;j<=m;j++)   /*将原来右或左结点中剩余的信息移入新结点中*/
	{
		q->key[j-s]=p->key[j];
		p->key[j]=0;
		q->eptr[j-s]=p->eptr[j];
		p->eptr[j]=NULL;
		q->nptr[j-s]=p->nptr[j];
		p->nptr[j]=NULL;
	}
	q->nptr[3]=NULL;  /*将无效的指置空*/
	q->nptr[2]=NULL;
	p->key[s]=0;
	p->eptr[s]=NULL;
	p->nptr[s]=NULL;

	p->keynum=s-1;   /*若原结点有孩子结点，则让它们指向新产生的结点*/
	if(q->nptr[0])
		for(j=0;j<=q->keynum;j++)
			q->nptr[j]->parent=q;
    return q;
}

int Search(NodeType *p,int kx)
{
	int n,k;
	n=p->keynum;
	for(k=1;k<=n;k++)
		if(p->key[k]==kx)
		{
	
			break;
		 }
		else if(kx<p->key[k])
			break;
	return k;
}

result SearchBtree(NodeType *t1,int k)  /*寻找关键字*/
{
	result rs;
	NodeType *p=t1,*q;
	int kk,found=0;
	q=NULL;
	while(p&&!found)/*判断插入的位置是否合法*/
	{
		kk=Search(p,k);  
		if(kk>0&&p->key[kk]==k)found=1;
		else{q=p;
		     p=p->nptr[kk-1];}
	}
	rs.tag=found;
	if(!found)p=q;
	if(found&&fflag==1){p->eptr[kk]->sum++;p->eptr[kk]->left++;}/*插入时，须改变书的总量*/
		if(found&&fflag==2){p->eptr[kk]->left--;}/* 借书时须更改现存量*/
	if(found&&fflag==3){p->eptr[kk]->left++;}   /*还书时更改现存量*/
	rs.pt=p;
	rs.i=kk;
	fflag=0;
	return rs;
}





Insert(NodeType *p,int j,int kx,BookType *bbook,NodeType *ptr)/*指向查找到的记录*/
{
	int k=p->keynum+1;
	p->keynum++;
	if(j<p->keynum)
	while(k!=j)
	{
		p->key[k]=p->key[k-1];
		p->eptr[k]=p->eptr[k-1];
		p->nptr[k]=p->nptr[k-1];
      
		k--;
	}
	p->key[j]=kx;
	bbook->sum=1;
	p->eptr[j]=bbook;
	p->nptr[j]=ptr;


}

NodeType *NewRoot(NodeType *t1,NodeType *stptr,int k,BookType *book )
{/*当为空树或根结点需分裂产生新的根结点*/
	NodeType *p;
	T=p=(NodeType *)malloc(sizeof(NodeType));
    p->keynum=1;
	p->key[1]=k;
	p->eptr[1]=book;
	p->nptr[0]=t1;
	p->nptr[1]=stptr;
	p->nptr[2]=NULL;
	p->nptr[3]=NULL;
	p->parent=NULL;
	if(t1!=NULL){
	t1->parent=p;
	stptr->parent=p;}
	return p;
}

int InsertBtree(NodeType *T1,BookType *t1)/*插入关键字*/
{
	int s;
	int finish=0;
	int k;
	result rs;
	NodeType *chptr=NULL;
	BookType *book=t1;
    k=t1->booknum;
	rs=SearchBtree(T1,k);
	if(!rs.tag)
	{
		chptr=NULL;
		while(rs.pt&&!finish)
		{
			Insert(rs.pt,rs.i,k,book,chptr);/*寻找关键字*/
		
			if(rs.pt->keynum<m)finish=1;/*找到合适的位置，且无须分裂*/
			else
			{   /*关键字太多，进行分裂*/
				s=(int)((m+1)/2); 
				k=rs.pt->key[s];
				book=rs.pt->eptr[s];
				chptr=split(rs.pt,s);
				rs.pt=rs.pt->parent;
				if(rs.pt)
				rs.i=Search(rs.pt,k);
			}
		}
		if(!finish)/*产生新的根结点*/
		{
			T1=NewRoot(T1,chptr,k,book);
			finish=1;
		
		}
		t->sum=1;t->left=2;
			showbtree(T1);
	}

	return(finish);
}

	
int delete1(NodeType *p,int k) /*删除关键字*/
{
	NodeType *q,*r;
	int j,move;
	p->keynum--;
	p->key[k]=0;/*清除*/
    p->eptr[k]=NULL;
	if(p->keynum>=min)/*直接删除，无需调整*/
	{
		while(k<p->keynum+1)  /* 调整删除后的结点*/
		{
			p->key[k]=p->key[k+1];
			p->eptr[k]=p->eptr[k+1];
			p->nptr[k-1]=p->nptr[k];
			p->nptr[k]=p->nptr[k+1];
			k++;
		
		}
        
        p->nptr[k]=NULL;
		p->key[k]=0;
		p->eptr[k]=NULL;
		return 1;
	}
	q=p->parent;
	if(q==NULL)return 1;
    while(1){/*其左右子树的关键数>2*/
	for(j=0;j<=q->keynum;j++)/*j，寻找为子树为位置*/
		if(q->nptr[j]==p)break;
    if((j-1)>=0&&q->nptr[j-1]->keynum>min)/*若存在左树，与左树调整*/
	{
		p->keynum++;             
		p->key[k]=q->key[j];   /*下移双亲结点中的关键字*/
		p->eptr[k]=q->eptr[j]; /*上移左树中最大的关键字到双亲结点中*/
		r=q->nptr[j-1];
		q->key[j]=r->key[r->keynum];
		q->eptr[j]=r->eptr[r->keynum];
		r->keynum--;
		r->key[r->keynum+1]=0;
		r->eptr[r->keynum+1]=NULL;
		r->nptr[r->keynum+1]=NULL;
		break;
	}
	else if((j+1)<=q->keynum&&q->nptr[j+1]->keynum>min)/*存在右树，与右树调整*/
	{
		p->keynum++;
		p->key[k]=q->key[j+1];  /*下移双亲结点中的关键字*/
		p->eptr[k]=q->eptr[j+1];
		r=q->nptr[j+1];          /* 上移左树中最大的关键字到双亲结点中*/
		q->key[j+1]=r->key[1];
		q->eptr[j+1]=r->eptr[1];
		r->keynum--;
        r->key[r->keynum]=r->key[r->keynum+1];
		r->eptr[r->keynum]=r->eptr[r->keynum+1];
        r->key[r->keynum+1]=0;
		r->eptr[r->keynum+1]=NULL;
		r->nptr[r->keynum-1]=r->nptr[r->keynum];
		r->nptr[r->keynum]=r->nptr[r->keynum+1];
		r->nptr[r->keynum+1]=NULL;
		break;
	}
    else/*两边都空或关键字数都等于1,进行合并，注意T*/
	{
		
			if((j-1)>=0)/*与左树合并*/