btree.h

基于 B- 树实现的图书管理系统1.rar

/*
    ADT BTree{
	   数据对象：D={n,A0,K1,A1,K2,A2,…,Kn,An}
	   数据关系：R1={}
	   void KeyTypeCopy(KeyType &bak,KeyType k)
	     初始条件：k存在
		 操作结果：将 k 中的全部值复制到 bak 中
	   int Search(BTree p, KeyType K)
	     初始条件：树结点 p 存在
		 操作结果：查找 k 在p中的位置，返回在p中的位置
	   Result SearchBTree(BTree T, KeyType K)
	     初始条件：T存在
		 操作结果：查找k在T中的位置，并以Result的结构体返回
	   void Insert(BTree &q, int i, KeyType x, BTree ap)
	     初始条件：q存在
		 操作结果：在m阶B-树q上结点ap的key[i]与key[i+1]之间插入关键字k
		           若引起结点过大，则沿双亲进行必要的结点分裂调整，使q还是m阶B-树
	   Status InsertBTree(BTree &T, KeyType K)
	     初始条件：k存在
		 操作结果：将k插入T树中
	   int position(BTree T)
	     初始条件：T存在
		 操作结果：返回T在双亲的第几个结点
	   Status fix(BTree &root,BTree p)
	     初始条件：root存在
		 操作结果：删除结点的时候调整树结点的个数，使树还是B-树
	   Status combine(BTree &root,BTree &p)
	     初始条件：root 存在
		 操作结果：当删除结点的时候不能向兄弟结点借的时候就合并，将双亲和兄弟结点合并成一个结点
	   void exchange(BTree &T,int i)
	     初始条件：T存在
		 操作结果：将T结点的第i个结点和右下最左结点交换，并将T的第i个结点删除
	   Status DeleteBTree(BTree &T,KeyType k)
	     初始条件：T存在
		 操作结果：将T中的k结点删除，如果存在就删除，否则就直接返回
	   void display(BTree T,int k)
	     操作结果：将B-树以层次的形式显示
	}ADT BTree
*/
#ifndef BITREE_H
#define BITREE_H

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<conio.h>
#include<dos.h>
#include<time.h>
#include <iostream>
#include <string>
using namespace std;

//******** 定义一些全局变量 *********
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define m 3 //表示是 2-3 树

//************ 借阅者的存储结构体 ************
typedef struct User{
	unsigned int number; //借书证号码
	int year;
	int month;
	int day;  //借书时间
	int dyear;  //截至日期的年
	int dmonth;   //截至日期的月
	int dday;   //截至日期的日
	struct User *next;  //下一个借阅者
}User; //定义用户的的信息
//********** 书的存储结构体 *******************
typedef struct Book{
	unsigned int key;     //图书的书号
    char bname[20]; // 书名
    char writter[20]; // 著者 
    unsigned int left;     // 现存量
    unsigned int total;     // 总存量
	User *user;  //借阅该书的人
}Book;  //定义书的信息
//********** B- 树的存储结构 *******************
typedef Book KeyType;
typedef struct BTNode{
	int keynum; //结点中关键字个数，即结点的大小
	struct BTNode *parent; //指向双亲结点
	KeyType key[m + 1];  //关键字向量， 0 号单元没有用
	struct BTNode *ptr[m + 1]; //子树指针向量
}BTNode,*BTree;
//************ 查找结果的存储结构体 ***********
typedef struct{
	BTNode *pt;  //指向找到的结点
 	int i;  //1……m，在结点中的关键字序号
	int tag; //B- 树的查找结果类型
}Result;
//************* 函数声明部分 *******************
//输入书的具体信息
void InBookMess(KeyType &book);
//输入书的关键字
void InBookKey(KeyType &book);
//显示书的具体信息,如果书存在就显示
void ShowBookMess(Book book);
//显示一个结点中所包含的全部信息,显示单个结点
string ShowBTNode(BTree p);
//显示,以层次的方法显示树的结点
string display(BTree T,int k);
//复制关键字的信息
void KeyTypeCopy(KeyType &bak,KeyType k);
//查找在某个结点中的位置
int Search(BTree p, KeyType K);
//查找
Result SearchBTree(BTree T, KeyType K);
//插入
void Insert(BTree &q, int i, KeyType x, BTree ap);
//分裂结点
void split(BTree &q, int s, BTree &ap);
//生成一个新的结点
void NewRoot(BTree &T, BTree p, KeyType x, BTree ap);
//将书的信息插入到 B- 树中
Status InsertBTree(BTree &T, KeyType K);
//删除结点,通过关键字 k 删除
Status DeleteBTree(BTree &T,KeyType k);
//删除树结点
Status DeleteBT(BTree &T,KeyType k);
//与右最左结点交换
void exchange(BTree &T,int i);
//用户借阅
Status BorrowBook(BTree T,KeyType k);
//注销对借阅者的登记，改变该书的显存量
Status ReturnBook(BTree T,KeyType k);
//日记 log 的写出
void writeLog(string mess);
//void writeLog(string mess,int num);
//将整型数据转换成字符串
string itos(int i);
//将字符数组转换成字符串
string ctos(char i[]);
//查找作者的全部书籍
Status searchAuthorB(BTree T);

#endif