btree.cpp

图书馆管理系统

 #include <stdio.h>
 #include <conio.h>
 #include <string.h>
 #include <malloc.h>
 #include <math.h>
 #include <stdlib.h>

 #define M 3   //3阶

 #define FALSE 0
 #define TRUE 1
 #define OK 1
 #define QSIZE 30

 const char *BookSoureFile="booktxt.dat";
 const char *BookInfoFile="bookinfo.dat";
 const char *BookIndexFile="bookind.dat";

typedef int KeyType;

typedef struct record{
	int  code;
	char bookname[20];
	char author[12];
	int  instore;    //书本存储量
	int  allstore;
   }Record;

typedef struct BTNode{
	int keynum;              //节点所包含关键字个数
	struct BTNode *parent;   //父节点指针
	KeyType key[M+1];        //关键字
	struct BTNode *ptr[M+1]; //子树指针
	int recptr[M+1];         //对应的记录指针
    }BTNode,*BTree;

typedef struct{
    BTNode *pt;
    int i;
    int tag;
    }Result;

typedef struct{
   int level;
   BTNode *ptr;
   }QNode;

typedef struct{
   int Front;
   int Rear;
   }Qeue;
Result *pResult;
void PrintBtree(BTree T);
/*********************************************/
/*       在结点P中查找关键字为K的位置i       */
/*         p->key[i]<=k<p->key[i+1]          */
/*********************************************/
int Search(BTree p, KeyType k)
 {
    int i;
    for(i=1; i<=p->keynum; i++)
      if(p->key[i]>=k) break;
    if(k<p->key[i]) return(i-1);
    else if(i>p->keynum) return(p->keynum);
    else return(i);
    }
/*********************************************/
/*     在B树T中查找关键字为K的结点P和位置i   */
/*********************************************/
void SearchBTree(BTree T, KeyType K)
{ // 在m阶B树T上查找关键字K，返回结果(pt,i,tag)
  BTree p, q;
  int found, i;
  p=T;
  q=NULL;
  found=FALSE;
  i=0;	              //初始化，p指向待查结点，q指向p的双亲
  while (p&&!found){
    i=Search(p, K);  // 在p->key[1..keynum]中查找i，使得：p->key[i]<=K<p->key[i+1]
    if (i>0 && p->key[i]==K)
      found = TRUE;  // 找到待查关键字
    else {
	q=p;
	p=p->ptr[i];
	}
    }
  if (found) {       // 查找成功
     pResult->pt=p;
     pResult->i=i;
     pResult->tag=1;
    }
  else {               // 查找不成功
     pResult->pt = q;
     pResult->i = i;
     pResult->tag = 0;
     }
   return;
   }
/***************************************************/
/*    将x和ap分别插入到q->key[i+1]和q->ptr[i+1]    */
/***************************************************/
void Insert(BTree q,int i,KeyType x,BTree ap,int rec)
 {            
   int j;
   //将结点q中从i+1到q->keynum的内容都后移一个位置
   for (j=q->keynum; j>i; j--)
    {
      q->key[j+1]= q->key[j];
      q->recptr[j+1]=q->recptr[j];
      q->ptr[j+1]= q->ptr[j];
     }
   //在q中第i+1的位置插入相应内容
   q->key[i+1] =x;
   q->recptr[i+1]=rec;
   q->ptr[i+1] = ap;
   if (ap) ap->parent =q;
   q->keynum++;
   }
/***************************************************/
/*        将结点q以s为界分成两个结点q和ap          */
/***************************************************/
void split(BTree *q, int s, BTree *ap)
{ int i,j,n;
  n=(*q)->keynum;
  (*ap) = (BTree)malloc(sizeof(BTNode));
  (*ap)->ptr[0] = (*q)->ptr[s];
  for (i=s+1,j=1; i<=n; i++,j++)
    { (*ap)->key[j] = (*q)->key[i];
      (*ap)->recptr[j]=(*q)->recptr[i];
      (*ap)->ptr[j] = (*q)->ptr[i];
      }
   (*ap)->keynum = M-s;
   (*ap)->parent = (*q)->parent;
   for (i=0; i<=n-s; i++)
     if ((*ap)->ptr[i]) (*ap)->ptr[i]->parent = (*ap);
   (*q)->keynum = s-1;
   }
/***********************************************************/
/*    建立一个新的根结点，关键字为k，两个孩子结点为p和ap   */
/***********************************************************/
void NewRoot(BTree *T, BTree p, KeyType x, BTree ap,int rec)
{  (*T) = (BTree)malloc(sizeof(BTNode));
   (*T)->keynum = 1;
   (*T)->ptr[0] = p;
   (*T)->ptr[1] = ap;
   (*T)->key[1] = x;
   (*T)->recptr[1]=rec;
   if(p) p->parent= (*T);
   if(ap) ap->parent = (*T);
   (*T)->parent = NULL;
   }
/*********************************************************/
/*      在B树T结点q的key[i]与key[i+1]之间插入关键字K     */
/*      插入过程可能引起结点分裂调整，使T仍是m阶B树      */
/*********************************************************/
int InsertBTree(BTree *T, KeyType key, BTree q, int i,int rec)
 {  
   BTree ap;
   int j,finished, s;
   KeyType x;
   x=key;
   ap=NULL;
   finished=FALSE;
   while(q&&!finished)
    { Insert(q,i,x,ap,rec); //将x和ap分别插入到q->key[i]与q->key[i+1]之间
      if(q->keynum<M) finished=TRUE;
      else{
        s=(M+1)/2;
        split(&q,s,&ap);   //分裂B树结点
        x=q->key[s];
        rec=q->recptr[s];
        if (q->parent) {  // 在双亲结点*q中查找x的插入位置
 	  q=q->parent;
	  i = Search(q, x);
	  }
        else break;
       } // else
    } // while
  if(!finished)  //T是空树或根结点已分裂为结点*q和*ap
      NewRoot(T, q, x, ap,rec); // 生成新根结点*T,q和ap为子树指针
  return OK;
  } // InsertBTree

/**********************************************************/
/*                     删除B树结点                        */
/**********************************************************/
int BTDelet(BTree *T,KeyType k)
 { int i,j,n,n1,n2;
   BTree pm; //被删结点指针
   BTree pb;
   BTree pl; //被删结点左兄弟结点指针
   BTree pr; //被删结点左兄弟结点指针
   BTree pp;
   BTree q;
   Result *R;

   if((*T)==NULL) return 0;
   
//步骤1：确定关键字k在T中的位置
   SearchBTree(*T,k);
   pm=pResult->pt;
   i=pResult->i;
   if(pResult->tag==0) return 0;  //B树中不存在该关键字。

//步骤2：若被删关键字结点pm为叶子结点,则直接删除
   if(pm->ptr[i]==NULL)     
    {
      n=pm->keynum;
      for(j=i+1;j<=n;j++)
	{
	  pm->key[j-1]=pm->key[j];
	  pm->recptr[j-1]=pm->recptr[j];
	  }
      pm->keynum--;
      if(pm->keynum>=M/2) return(1);
      }

//步骤3：若被删关键字结点pm是非叶结点,将关键字左子树中最右的关键字代替自身
   else    
     {
	//寻找左子树中最右的关键字
	pb=pm;
	pm=pm->ptr[i-1];
	while(pm!=NULL)
	  {
	    q=pm;
	    pm=pm->ptr[pm->keynum];
	    }
	pm=q;
        //左子树中最右的关键字代替被删关键字
	pb->key[i]=pm->key[pm->keynum];
	pb->recptr[i]=pm->recptr[pm->keynum];
	pm->keynum--;
        if(pm->keynum>=M/2) return(1);
	}
//步骤4：如果被删关键字结点个数少于M/2,则调整删除后的结点
    while(1)
      {
	n=pm->keynum; 
//步骤4.1:被调整的结点为根结点
	if(pm->parent==NULL)
	 { if(n>0) return(1);
           q=*T;
	   *T=(*T)->ptr[0];
	   if(*T!=NULL)
	   (*T)->parent=NULL;
           free(q);
	   return 1;
	   }
//步骤4.2:被调整的结点为根结点,确定pm在父节点中的位置
	pp=pm->parent;
	i=0;
        while(pp->ptr[i]!=pm) i++;
	//若左兄弟结点有富裕关键字，则将左兄弟最大关键字上移父结点
        //父结点左关键字下移到结点左边
	if( i>0 && (pp->ptr[i-1]->keynum > M/2) )
	  {
	    pl=pp->ptr[i-1];
	    pl->keynum--;
	    for(j=n;j>=1;j--)   //被删节点关键字右移1个位置
	     {	pm->key[j+1]=pm->key[j];
		pm->recptr[j+1]=pm->recptr[j];
		pm->ptr[j+1]=pm->ptr[j];
		}
	    pm->ptr[1]=pm->ptr[0];
	    pm->key[1]=pp->key[i]; //父结点关键字下移
	    pm->recptr[1]=pp->recptr[i];

	    pm->ptr[0]=pl->ptr[pl->keynum+1]; //被删结点最左指针为左兄弟最右指针
	    if(pm->ptr[0]!=NULL)
		pm->ptr[0]->parent=pm;
	    pm->keynum++;

	    pp->key[i]=pl->key[pl->keynum+1];//左兄弟最右关键字上移
	    pp->recptr[i]=pl->recptr[pl->keynum+1];
	    return 1;
	    }
        //若右兄弟结点有富裕关键字，则将右兄弟最小关键字上移父结点
	// 父结点右关键字下移到结点右边
	if(i<pp->keynum&&pp->ptr[i+1]->keynum>M/2)//向右兄弟调整关键字
	   {
	     pr=pp->ptr[i+1];
	     pm->key[n+1]=pp->key[i+1]; //父结点关键字下移
	     pm->recptr[n+1]=pp->recptr[i+1];
	     pm->ptr[n+1]=pr->ptr[0];   ////被删结点最右指针为右兄弟最左指针
	     if(pm->ptr[n+1]!=NULL) pm->ptr[n+1]->parent=pm;
	     pm->keynum++;
	     pp->key[i+1]=pr->key[1];////右兄弟最左关键字上移
	     pp->recptr[i+1]=pr->recptr[1];
	     pr->ptr[0]=pr->ptr[1];
	     for(j=2;j<=pr->keynum;j++)
		{
		   pr->key[j-1]=pr->key[j];
		   pr->recptr[j-1]=pr->recptr[j];
		   pr->ptr[j-1]=pr->ptr[j];
		   }
	     pr->keynum--;
	     return 1;
	    }
      //左右兄弟都无富裕结点，则进行合并
      //如果被删关键字结点不是父结点的最左孩子，则与左兄弟合并
	 if(i>0) 
	 {
	   pl=pp->ptr[i-1];
	   n1=pl->keynum;
	   //下移父结点
	   pl->key[n1+1]=pp->key[i];
	   pl->recptr[n1+1]=pp->recptr[i];
	   //将被删关键字结点内容移至左兄弟右边
	   for(j=1;j<=n;j++)
	     {
		pl->recptr[n1+1+j]=pm->recptr[j];
		pl->key[n1+1+j]=pm->key[j];
		}
	   for(j=0;j<=n;j++)
	     {
		pl->ptr[n1+1+j]=pm->ptr[j];
		if(pl->ptr[n1+1+j]!=NULL)  pl->ptr[n1+1+j]->parent=pl;
		}
           pl->keynum=n1+n+1;
           
	   //删除被删关键字结点
	   free(pm);
           //双亲剩余数据均左移一个位置
	   for(j=i+1;j<=pp->keynum;j++)
	    {
		pp->key[j-1]=pp->key[j];
		pp->recptr[j-1]=pp->recptr[j];
		pp->ptr[j-1]=pp->ptr[j];
		}
	   pp->keynum--;
	   //如果父结点关键字个数>=M/2，则结束调整，否则继续对父结点进行调整
           if(pp->keynum>=M/2) return(1);
	   else pm=pp;
	   }
	//如果被删关键字结点是父结点的最左孩子，则与右兄弟合并
	 else
	 {
	   pr=pp->ptr[1]; //pr指向被删结点的右兄弟

           //右兄弟数据均后移n+1个位置
	   n2=pr->keynum;
	   for(j=n2;j>=1;j--)
	     {	pr->key[n+1+j]=pr->key[j];
		pr->recptr[n+1+j]=pr->recptr[j];
		pr->ptr[n+1+j]=pr->ptr[j];
		}
	    pr->ptr[n2]=pr->ptr[0];
	    //双亲第0个指针和第一个关键字合并至右兄弟中
	    pr->recptr[n+1]=pp->recptr[1];
	    pr->key[n+1]=pp->key[1];
            //被删结点中剩余关键字合并至右兄弟中
	    for(j=1;j<=n;j++)
	      {
		  pr->key[j]=pm->key[j];
		  pr->recptr[j]=pm->recptr[j];
		  }
	    //被删结点中剩余孩子指针合并至右兄弟中，并调整孩子结点的parent指针
	     for(j=0;j<=n;j++)
		{
		  pr->ptr[j]=pm->ptr[j];
		  if(pr->ptr[j]!=NULL)
		    pr->ptr[j]->parent=pr; //若该指针指向其他子树,则修改其子树的双亲域
		  }
	     pr->keynum=n2+n+1;

            //删除被删关键字结点
	     free(pm);

	     //双亲剩余数据均左移一个位置
	     pp->ptr[0]=pp->ptr[1];
	     for(j=2;j<=pp->keynum;j++)
		{
		  pp->key[j-1]=pp->key[j];
		  pp->recptr[j-1]=pp->recptr[j];
		  pp->ptr[j-1]=pp->ptr[j];
		  }
	     pp->keynum--;
           //如果父结点关键字个数>=M/2，则结束调整，否则继续对父结点进行调整
           if(pp->keynum>=M/2) return(1);
	   else pm=pp;
	   }
	}
   }
/***********************************************************/
/*                  将B树保存到文件中                      */
/*         方法：从根结点开始按树的层次遍历进行            */
/***********************************************************/
 void StoreBTree(BTree T)
 { int i;
   BTree p;
   QNode SeqQ[QSIZE];
   Qeue Q;
   Q.Front=Q.Rear=0;
   FILE *fp;
   if(!(fp=fopen(BookIndexFile,"wb")))
     { printf("文件%s不存在\n",BookIndexFile);
       getch();
       return;
       }
    SeqQ[0].ptr=T;
    Q.Rear=1;
    while(Q.Front!=Q.Rear)
      { p=SeqQ[Q.Front].ptr;
	fwrite(p,sizeof(BTNode),1,fp);
	//count++;
	Q.Front=(Q.Front+1)%QSIZE;
	if(p->ptr[0])
	  for(i=0;i<=p->keynum;i++)
	     { if((Q.Rear+1)%QSIZE==Q.Front)
		{ printf("Qeue Overflow!\n");
		  getch();
		  return;
		  }
	       SeqQ[Q.Rear].ptr=p->ptr[i];
	       Q.Rear=(Q.Rear+1)%QSIZE;
	       }
	}
     fclose(fp);
     //printf("l=%d,%d\n",sizeof(BTNode),count);