btree.cpp

图书馆管理系统

     //getch();
    }
/***********************************************************/
/*                  释放B树中所有结点                      */
/*         方法：从根结点开始按树的层次遍历进行            */
/***********************************************************/
 void ClearBTree(BTree *T)
 { int i;
   BTree p;
   QNode SeqQ[QSIZE];
   Qeue Q;
   Q.Front=Q.Rear=0;
   SeqQ[0].ptr=*T;
   Q.Rear=1;
   while(Q.Front!=Q.Rear)
      { p=SeqQ[Q.Front].ptr;
	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;
	       }
	free(p);
	}
    *T=NULL;
    return;
    }
/***********************************************************/
/*             从文件中读入B树的数据重建B树                */
/*         方法：从根结点开始按树的层次遍历进行            */
/* 注意：由于读入的B树数据在内存中的位置发生变化，必须重新 */
/*       申请存储空间，并重新建立结点间的父子关系。        */
/***********************************************************/
 BTree ReadBTree()
 { int i;
   BTree p,T,s;
   QNode SeqQ[QSIZE];
   Qeue Q;
   Q.Front=Q.Rear=0;
   FILE *fp;
   if(!(fp=fopen(BookIndexFile,"rb")))
     { printf("文件%s不存在\n",BookIndexFile);
       getch();
       return(NULL);
       }
    if(feof(fp)) return(NULL);
    T=(BTree)malloc(sizeof(BTNode));
    fread(T,sizeof(BTNode),1,fp);
    SeqQ[0].ptr=T;
    Q.Rear=1;
    while(Q.Front!=Q.Rear)
      { p=SeqQ[Q.Front].ptr;
	Q.Front=(Q.Front+1)%QSIZE;
	if(p->ptr[0])
	 { for(i=0;i<=p->keynum;i++) p->ptr[i]=NULL;
	   for(i=0;(!feof(fp))&&i<=p->keynum;i++)
	     { s=(BTree)malloc(sizeof(BTNode));
	       fread(s,sizeof(BTNode),1,fp);
	       p->ptr[i]=s;
	       s->parent=p;
	       if((Q.Rear+1)%QSIZE==Q.Front)
		{ printf("Qeue Overflow!\n");
		  getch();
		  ClearBTree(&T);
		  return(NULL);
		  }
	       SeqQ[Q.Rear].ptr=s;
	       Q.Rear=(Q.Rear+1)%QSIZE;
	       }
	    }
	}
    return(T);
    }
/***********************************************************/
/*          从文本文件中读入图书信息，建立B树索引          */
/*         以便于直接查找方式保存图书信息和B树数据         */
/***********************************************************/
 void BTinit()
 { int loc,i,count;
   Record RE;
   BTree T=NULL;
   FILE *fp1,*fp2;

   if(!(fp1=fopen(BookSoureFile,"r")))
     { printf("文件%s不存在\n",BookSoureFile);
       getch();
       return;
       }
   if(!(fp2=fopen(BookInfoFile,"wb")))
     { printf("文件%s不存在\n",BookInfoFile);
       getch();
       return;
       }
   fscanf(fp1,"%d",&count);
   fwrite(&count,sizeof(int),1,fp2);
   for(i=1;i<=count;i++)
     {
       fscanf(fp1,"%d",&(RE.code));
       fscanf(fp1,"%s",RE.bookname);
       fscanf(fp1,"%s",RE.author);
       fscanf(fp1,"%d%d",&(RE.instore),&(RE.allstore));
       printf("%d %s %s %d %d\n",RE.code,RE.bookname,RE.author,RE.instore,RE.allstore);
       fwrite(&RE,sizeof(Record),1,fp2);
       SearchBTree(T,RE.code);
       if(pResult->tag==0)
	 InsertBTree(&T, RE.code,pResult->pt, pResult->i,i);
       }
     getch();
     fclose(fp1);
     fclose(fp2);
     PrintBtree(T);
     StoreBTree(T);
     ClearBTree(&T);
     return;
    }
/***********************************************************/
/*            从根结点开始按树的层次结构输出B树            */
/***********************************************************/
void PrintBtree(BTree T)
  { int i,level,level1;
    BTree p;
    QNode SeqQ[QSIZE];
    Qeue Q;
    Q.Front=Q.Rear=0;
    if(T==NULL) return;
    level=1;
    SeqQ[0].level=1;
    SeqQ[0].ptr=T;
    Q.Rear=1;
    level1=0;
    while(Q.Front!=Q.Rear)
      { p=SeqQ[Q.Front].ptr;
	level=SeqQ[Q.Front].level;
	Q.Front=(Q.Front+1)%QSIZE;
	if(level!=level1)
	  { printf("\n%d:",level);
	    level1=level;
	    }
	for(i=1;i<=p->keynum;i++)
	  printf("%d ",p->key[i]);
	printf("  ");
	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].level=level+1;
	       SeqQ[Q.Rear].ptr=p->ptr[i];
	       Q.Rear=(Q.Rear+1)%QSIZE;
	       }
	}
     printf("\n");
     getch();
     return;
    }
 int Select(char *str)
  { char ch;
    printf("%s\n",str);
    printf("Input Y or N:");
    do{ ch=getch();
	}while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');
    printf("\n");
    if(ch=='Y'||ch=='y') return(1);
    else return(0);
    }
/***********************************************************/
/*         在以B树结构形式存储的文件中插入数据             */
/*   方法：将数据插入到图书信息文件的末尾，并调整B树索引   */
/***********************************************************/
 void InsertRecord()
 { int RecordLoc,key,count;
   long re;
   BTree T;
   Record r,r1;
   FILE *fp;
   T=ReadBTree();
   if(!T){
     if(Select("BTree is NULL,Rebuild BTree?"))
      { fp=fopen(BookInfoFile,"wb");
	count=0;
	fwrite(&count,sizeof(int),1,fp);
	fclose(fp);
	}
     else return;
     }
   if(!(fp=fopen(BookInfoFile,"rb+")))
     { printf("文件%s不存在\n",BookInfoFile);
       getch();
       return;
       }
   fseek(fp,0l,SEEK_SET);
   fread(&count,sizeof(int),1,fp);
   while(1){
     printf("Input book infomation:\n");
     printf("book code:");
     scanf("%d",&(r.code));
     printf("Book name:");
     scanf("%s",r.bookname);
     printf("author:");
     scanf("%s",r.author);
     printf("instore:");
     scanf("%d",&(r.instore));
     if(r.code<=0) break;
     SearchBTree(T,r.code);
     if(pResult->tag==1)
       {
	RecordLoc=pResult->pt->recptr[pResult->i];
	re=sizeof(int)+(RecordLoc-1)*sizeof(Record);
	fseek(fp,re,SEEK_SET);
	fread(&r1,sizeof(Record),1,fp);
	printf("The book exist in liberay,it is:\n");
	printf("%d %s %s %d %d\n",r.code,r.bookname,
	       r.author,r.instore,r.allstore);
	if(Select("replace?"))
	  { fseek(fp,re,SEEK_SET);
	    r.allstore=r.instore;
	    fwrite(&r,sizeof(Record),1,fp);
	    }
	}
     else{
	InsertBTree(&T, r.code,pResult->pt, pResult->i,++count);
	fseek(fp,0l,SEEK_END);
	r.allstore=r.instore;
	fwrite(&r,sizeof(Record),1,fp);
	}
     }

   fseek(fp,0l,SEEK_SET);
   fwrite(&count,sizeof(int),1,fp);
   fclose(fp);
   StoreBTree(T);
   ClearBTree(&T);
   }
/***********************************************************/
/*                从B树结构文件中删除记录                  */
/*           方法：不删除数据，只删除B树索引               */
/***********************************************************/
 void DeleteRecord()
 { int RecordLoc,key;
   long re;
   BTree T;
   Record r;
   FILE *fp;
   T=ReadBTree();
   PrintBtree(T);
   if(!T){
     printf("not create BTree!\n");
     getch();
     return;
     }
   if(!(fp=fopen(BookInfoFile,"rb")))
     { printf("文件%s不存在\n",BookInfoFile);
       getch();
       return;
       }
   while(1){
     printf("Input record key:");
     scanf("%d",&key);
     if(key<=0) break;
     SearchBTree(T,key);
     if(pResult->tag==1)
       {
	RecordLoc=pResult->pt->recptr[pResult->i];
	re=sizeof(int)+(RecordLoc-1)*sizeof(Record);
	fseek(fp,re,SEEK_SET);
	fread(&r,sizeof(Record),1,fp);
	printf("Deleted book is:");
	printf("%d %s %s %d %d\n",r.code,r.bookname,
	       r.author,r.instore,r.allstore);
	if(Select("Must Delete?"))
	  if(BTDelet(&T,r.code))
	     { printf("Delete Successful!\n");
	       getch();
	       }
	  else{ printf("Delete unsucessful!\n");
		getch();
	      }
	   }
	}
  fclose(fp);
  StoreBTree(T);
  PrintBtree(T);
  ClearBTree(&T);
 }
/***********************************************************/
/*                在B树结构文件中查找记录                  */
/*    方法：输入图书记录号，先在B树中查找，然后读取速据    */
/***********************************************************/
 void SearchRecord()
 { int RecordLoc,key;
   long re;
   BTree T;
   Record r;
   FILE *fp;
   T=ReadBTree();
   if(!T){
     printf("not create BTree!\n");
     getch();
     return;
     }
   if(!(fp=fopen(BookInfoFile,"rb")))
     { printf("文件%s不存在\n",BookInfoFile);
       getch();
       return;
       }
   while(1){
     printf("Input record key:");
     scanf("%d",&key);
     if(key<=0) break;
     SearchBTree(T,key);
     if(pResult->tag==1)
       {
	RecordLoc=pResult->pt->recptr[pResult->i];
	re=sizeof(int)+(RecordLoc-1)*sizeof(Record);
	fseek(fp,re,SEEK_SET);
	fread(&r,sizeof(Record),1,fp);
	printf("%d %s %s %d %d\n",r.code,r.bookname,
	       r.author,r.instore,r.allstore);
	getch();
	}
    }
  fclose(fp);
  ClearBTree(&T);
 }

 void PrintBTreeInLevel()
 { BTree T;
   T=ReadBTree();
   if(T) PrintBtree(T);
   ClearBTree(&T);
   return;
   }
 int nemu()
 {
    int num;
    printf("\n    ************* Balanced Tree Index ****************\n");
    printf("    *%15c1---Initial%23c\n",' ','*');
    printf("    *%15c2---Insert Record%17c\n",' ','*');
    printf("    *%15c3---Delete Record%17c\n",' ','*');
    printf("    *%15c4---Search Record%17c\n",' ','*');
    printf("    *%15c5---Print BTree In Level%10c\n",' ','*');
    printf("    *%15c6---Quit%26c\n",' ','*');
    printf("    **************************************************\n");
    printf("%15cSelcet 1,2,3,4,5,6: ",' ');
    do{
	scanf("%d",&num);
	}while(num<1 ||num>6);
    return(num);
  }

void main()
 { pResult=(Result *)malloc(sizeof(Result));
   while(1)
    {
	switch(nemu())
	{
	    case 1:
		BTinit();
		break;
	    case 2:
		InsertRecord();
		break;
	    case 3:
		DeleteRecord();
		break;
	    case 4:
		SearchRecord();
		break;
	    case 5:
		PrintBTreeInLevel();
		break;
	    case 6:
		free(pResult);
		return;
	}
    }
 }
 /*BTree InitBtree()
  { int i,key;
    BTree T=NULL;
    Result *q;
    i=1;
    do{
	printf("intput key:");
	scanf("%d",&key);
	if(key<=0) break;
	SearchBTree(T,key);
	InsertBTree(&T, key,pResult->pt, pResult->i,i++);
	}while(1);
   PrintBtree(T);
   getch();
   return(T);
   }*/
 /*void DelBTree(BTree *T)
 { int i,key;
    do{
	printf("intput key:");
	scanf("%d",&key);
	if(key<=0) break;
	SearchBTree(*T,key);
	if(pResult->tag)
	if(BTDelet(T,key))
	  { printf("Delete Successful!\n");
	    getch();
	    }
	else{ printf("Delete unsucessful!\n");
	      getch();
	      }
	PrintBtree(*T);
	}while(1);
   getch();
   return;
   }*/