main.cpp

这是我们做的数据结构课程设计的一个内容

#include <stdlib.h>
#include <stdio.h>
#include<iomanip.h>
#include<string.h>
#include <conio.h>
#define m 1        // 定义一棵2m+1的三阶树 
#define PP printf("\n\t\t    ");
#define PPP printf("\t\t   ");


struct data      //记录借书和还书日期的结构体类型
{ int year;      //记录年
  int month;     //记录月
  int day;       //记录日
};

struct ReaderNode     //记录读者信息的结构体类型
{
  char num[20];      //记录读者的借书证号
  struct data  bro;          //记录读者的借书日期
  struct data  back;         //记录读者的还书日期
};

struct  BookNode     //记录书的信息的结构体类型
{
  char title[15];      //记录书名
  char writer[15];     //记录作者
  int current;      //书现存量
  int total;        //书总存量
  struct ReaderNode reader[20]; //借阅该书的读者记录
};


struct TreeNode      //B树的结构体类型
{
   int n;    			// 记录结点中的关键字个数 
   struct TreeNode *par;        // 指向父结点的指针域 
   int key[2*m];                // key[0...n-1],2m个关键字域 (注：关键字即书号)
   struct BookNode *rec[2*m];    // rec[0...n-1],2m个指向书的信息结点的指针域 
   struct TreeNode *ptr[2*m+1]; //ptr[0...n],2m+1个指向子结点的指针域 

};


void all(struct TreeNode *bth,int t);
struct BookNode *InputNode();
struct TreeNode *search(struct TreeNode *bth,int x,int *k,int *flag);
struct TreeNode *insert(struct TreeNode *bth);
struct TreeNode *del(struct TreeNode *bth);
void OutputNode(struct TreeNode *bth);
void borrow(struct TreeNode *bth);
void payback(struct TreeNode *bth);
char menu(void);






struct TreeNode *search(struct TreeNode *bth,int x,int *k,int *flag)
{ 
  struct TreeNode *p,*q;
  p=bth; *flag=0; q=p;     // 由头结点开始查找 
  while( p&& !(*flag))   // 当结点不为空且还没找到该关键字时不断向下查找 
  {
    *k=1;q=p;
    while( (*k < q->n) && ( q->key[*k-1] < x) ) *k=*k+1;  //比该结点关键字数少并且比x小时，找该结点下一个关键字
    if( q->key[*k-1]==x) *flag=1;  // 查找成功 
    else if( ( *k==q->n ) && ( q->key[*k-1] < x) ) {p=q->ptr[*k];if(p)p->par=q;else break;}  
    else { p=q->ptr[*k-1];if(p) p->par=q;*k=*k-1;} // 延第k个指针域找下一个个结点 
  }
  return(q);
}//函数返回包含关键字x的结点的储存地址，指针变量k指向的变量存放关键字x在存储结点
//中的位置，*flag的值为0时，表示查找失败，为1时，表示查找成功






void all(struct TreeNode * T,int k)//用递归调用方式遍历该树
{   
	struct TreeNode * q;
	int i;
	q=T;
	if(q)
	{
		for(i=0;i<k;i++)
		printf("  ");
		for(int j=0;j<q->n;j++)
			printf("%d  ",q->key[j]);
		printf("\n");
		k+=3;
		for(int l=0;l<=q->n;l++)
			all(q->ptr[l],k);
	}
}


struct TreeNode *insert(struct TreeNode *bth)
{
  int flag,j,k,t;
  int y,x,z;
  struct TreeNode *p,*q,*u,*s;
  struct BookNode *r,*l;
  printf("\n\t    请输入要插入的书的关键字: ");
  scanf("%d",&x);       // 输入需要插入的书的关键字 
  q=search(bth,x,&k,&flag);  //查找关键字该插入的地方
  if(flag==1)   //若找到有相同的关键字
  {   printf("\n\t    书库里有 %d 本这种书,你想增加多一本吗?(y/n)\n",(q->rec[k-1])->total);
      z=getch();
      if(z=='y'||z=='Y')        //是否加多一本同类的书入库
      {
	(q->rec[k-1])->total++; (q->rec[k-1])->current++;  //现存量和总存量各加一
	printf("\n\t    现在这种书的总存量为:%d 本",(q->rec[k-1])->total);
	printf("\n\t    并且书库内现有 %d 本这种书.",(q->rec[k-1])->current);
      }
      return(bth);  //返回头指针
    }
  r=InputNode();  //调用InputNode函数输入书的信息，接收返回新开辟的结点的地址bth
  if(bth==NULL) //若B树为空
    {
      bth=p=(struct TreeNode *)malloc(sizeof(struct TreeNode));//为根结点开辟一个TreeNode类型的空间
      p->n=1; p->key[0]=x; p->rec[0]=r;p->par=NULL;//插入关键字
      for(j=1;j<=2*m+1;j++) p->ptr[j-1]=NULL; //所有指针域置空
      return(p);  // 返回头指针 
    }

  p=NULL; t=0;  //t为分裂标志
  while(t==0)  //当分裂标志为仍0时循环
  {
    if(k==q->n) {y=x;l=r;u=p;} //要插入到该结点的最后，记录x和子结点指针
    else               //插入到该结点中间的某个位置
    {
      y=q->key[q->n-1]; l=q->rec[q->n-1];u=q->ptr[q->n]; //把最后一个关键字，书信息指针，子结点指针记录，以插入后不会因后移而被覆盖
      for(j=(q->n)-1; j>=k+1; j--) //插入位置后的元素全部后移
      {
	q->key[j]=q->key[j-1];q->rec[j]=q->rec[j-1];q->ptr[j+1]=q->ptr[j];
      }
      q->key[k]=x;q->rec[k]=r;q->ptr[k+1]=p; //插入x，书信息指针，子结点指针
      if(p!=NULL) p->par=q; //改变子结点的父结点的指针的指向
    }

    if(q->n<2*m)    //该结点的关键字数不超过最大关键字数，满足插入条件
    {
      q->n=(q->n)+1; //关键字数加1
      t=1;            //分裂标志置1，插入完成
      q->key[(q->n)-1]=y;  q->rec[(q->n)-1]=l; q->ptr[q->n]=u;    //把记录放到最后一个关键字域，书信息指针域，子结点指针域
      if(u!=NULL) u->par=q;   //改变子结点的指向父结点的指针的指向
    }
    else  //若该结点的关键字数大于最大关键字数，则需分裂
    {
      p=(struct TreeNode *)malloc(sizeof(struct TreeNode)); //开辟一个TreeNode类型的空间供分裂后存关键字
      p->n=m; q->n=m; p->par=q->par;   //设原结点和新结点关键字数各为m，并指明新结点的父结点和原结点相同
      x=q->key[m];r=q->rec[m];   //把中间的关键字记录，作下一次循环时在父结点插入用
      for(j=1;j<=m-1;j++)
      {
	p->key[j-1]=q->key[m+j];p->rec[j-1]=q->rec[m+j];p->ptr[j-1]=q->ptr[m+j];   //将原结点后半关键字，及相应的指针移到新结点中
	if(q->ptr[m+j]!=NULL) (q->ptr[m+j])->par=p;   //改变子结点的指向父结点的指针的指向

      }

      p->ptr[m-1]=q->ptr[2*m];    //原结点最后一个指向子结点的指针赋给新结点第m-1个指向子结点的指针
      p->ptr[m]=u;   //把记录下来的赋给新结点
      p->key[m-1]=y;
      p->rec[m-1]=l;

      if(u!=NULL) u->par=p;    //改变子结点的指向父结点的指针的指向
      for(j=m+2;j<=2*m+1;j++)
      {
	q->ptr[j-1]=NULL;p->ptr[j-1]=NULL;    //新旧结点插入关键字后相应子结点指针置空
      }

      if(q->par==NULL)           //若已经分裂到根结点
      {
	s=(struct TreeNode *)malloc(sizeof(struct TreeNode));   //开辟一个TreeNode类型的空间供头结点分裂用
	s->key[0]=x; s->rec[0]=r;
	s->ptr[0]=q; s->ptr[1]=p;
	s->n=1; s->par=NULL; q->par=s; p->par=s;  //插入相应的值和指针
	for(j=3;j<=2*m+1;j++) s->ptr[j-1]=NULL;
	bth=s; t=1;   //插入完成，置分裂标志1
      }
      else       //未分裂到根结点，则寻找父结点的插入位置
      {
	q=q->par; k=1;
	while((k<=q->n)&&(q->key[k-1]<x)) k=k+1;
	k=k-1;
      }
    }
  }
  return(bth);   //返回头结点的指针
}// 函数返回插入后B树的头指针 







struct TreeNode *del(struct TreeNode *bth)
{
  int flag,j,k,t;
  int x,y;
  struct TreeNode *u,*s,*p,*q;
  struct BookNode *l;//*r,
  printf("\n\t     请输入你想要删除的书的关键字: ");
  scanf("%d",&x);
  q=search(bth,x,&k,&flag);       //寻找删除关键字的位置
  if(flag==0) { printf("\n\t这本书不存在!\n"); return(bth);} //*无该关键字，出错返回
  p=q->ptr[k];         //找要删除关键字的右边的子结点
  if(p!=NULL)           //若要删除的关键字不在叶子结点上
  {
    while(p->ptr[0]!=NULL) p=p->ptr[0];  //则找该关键字的右子结点的最左子结点
    q->key[k-1]=p->key[0]; //找到后与把对应记录赋给该被删除的关键字
    q->rec[k-1]=p->rec[0];
    k=1;q=p;
  }

  for(j=k;j<=q->n-1;j++)    //删除位置后的关键字逐个向前移一位
  {
  q->key[j-1]=q->key[j];
  q->rec[j-1]=q->rec[j];
  }
  q->n=q->n-1;

  while ((q!=bth)&&(q->n<m))  //若删除该关键字后该结点的关键字数少于最少关键字数，并且该结点不是头结点
  {
    p=q->par;j=1;
    while(p->ptr[j-1]!=q) j=j+1;   //寻找该结点在父结点中的指针位置
    if((j<=p->n)&&((p->ptr[j])->n>m))    // 若右兄弟结点关键字数大于最少关键字数，则从右兄弟结点中借关键字
    {
      s=p->ptr[j];    //借右兄弟结点的最左边的关键字
      y=s->key[0];
      l=s->rec[0];
      u=s->ptr[0];
      for(k=1;k<=s->n-1;k++)   //其余关键字与相应的指针各左移一位
	{
	 s->key[k-1]=s->key[k];
	 s->rec[k-1]=s->rec[k];
	 s->ptr[k-1]=s->ptr[k];
	}
      s->ptr[s->n-1]=s->ptr[s->n]; //不要忘最后的指针也要移
      s->ptr[s->n]=NULL;
      s->n=s->n-1; q->n=q->n+1;    //改变两个结点中的关键字个数
      q->key[q->n-1]=p->key[j-1];   //父结点中的紧靠上移关键字的关键字下移到被删除结点的最后
      q->rec[q->n-1]=p->rec[j-1];
      q->ptr[q->n]=u;
      p->key[j-1]=y;            //借的关键字到父结点
      p->rec[j-1]=l;
      if(u!=NULL) u->par=q;     //改变被借关键字下一层结点中指向父结点的指针
    }
   else if((j>1)&&((p->ptr[j-2])->n>m))  //若左兄弟结点关键字数大于最少关键字数，则从左兄弟结点中借关键字
   {
     s=p->ptr[j-2];
     q->n=q->n+1;
     q->ptr[q->n]=q->ptr[q->n-1];

     for(k=q->n-1;k>=1;k--)      //空出被删除结点中第一个位置
       {
	q->key[k]=q->key[k-1];
	q->rec[k]=q->rec[k-1];
	q->ptr[k]=q->ptr[k-1];
       }
     q->key[0]=p->key[j-2];      //父结点中的紧靠上移关键字的关键字下移到被删除的结点的第一个
     q->rec[0]=p->rec[j-2];
     u=s->ptr[s->n];
     q->ptr[0]=u;
     if(u!=NULL) u->par=q;    //改变被借关键字下一层结点中指向父结点的指针
     p->key[j-2]=s->key[s->n-1];    //借的关键字到父结点
     p->rec[j-2]=s->rec[s->n-1];
     s->ptr[s->n]=NULL;
     s->n=s->n-1;
   }

   else    //左和右兄弟结点关键字数都不大于最少关键字数，则需要合拼
   {
     if(j==p->n+1)   //若该结点是其父结点的最右孩子
       { q=p->ptr[j-2]; s=p->ptr[j-1]; j=j-1;}  //赋一指针给左兄弟
     else s=p->ptr[j];   //否则指针赋给右孩子
     q->key[q->n]=p->key[j-1];    //把父结点关键字赋给子结点
     q->rec[q->n]=p->rec[j-1];