library.cpp

b树的C++实现,运用模板实现B树 简单明了

/*
题目：设计一个图书管理系统
要求：
1、每种书的登录内容为：书号、书名、著者、存量状态；
2、所有的业务活动是通过书号进行，用B树对书号建立索引；
3、系统的功能如下
⑴ 采编入库，
⑵ 清除库存，
⑶ 借阅，
⑷ 归还，
⑸ 显示。
说明：以5阶B树为例。 
*/
#include <iostream>
#include <string>
#include <Queue>
using namespace std;

class Book
{
	friend bool operator<(const Book &left,const Book &right);
	friend bool operator>(const Book &left,const Book &right);
	friend bool operator==(const Book &left,const Book &right);
	friend ostream& operator<<(ostream & os,const Book &right);

public:
	Book()
	{
		this->amount = 0;
		this->author = "";
		this->bookName = "";
		this->bookNumber = "";
		this->state = false;
	}

	Book(string bookNumber,string bookName,string author,int amount)
		:bookNumber(bookNumber),bookName(bookName),author(author),amount(amount)
	{
		if(amount > 0)
		{
			this->state = true;
		}
	}

	int get_amount() const;
	void set_amount(int num);
	string get_number() const;
	string get_name() const;
	string get_author() const;
	bool get_state() const;
	void set_state(bool state);
private:
	string bookNumber;
	string bookName;
	string author;
	bool state;
	int amount;
};


int Book::get_amount() const
{
	return amount;
}

void Book::set_amount(int num)
{
	amount = num;
}

string Book::get_author() const
{
	return author;
}

string Book::get_name() const
{
	return bookName;
}

string Book::get_number() const
{
	return bookNumber;
}

bool Book::get_state() const
{
	return state;
}

void Book::set_state(bool State)
{
	state = State;
}

bool operator<(const Book &left,const Book &right)
{
	return left.bookNumber < right.bookNumber;
}

bool operator>(const Book &left,const Book &right)
{
	return left.bookNumber > right.bookNumber;
}

bool operator==(const Book &left,const Book &right)
{
	return left.bookNumber == right.bookNumber;
}

ostream& operator<<(ostream& os,const Book &right)
{
	os<<right.get_number()<<'\t'<<right.get_name()<<'\t'<<right.get_author()<<'\t'<<right.get_amount()<<'\t';
	if(right.get_state() == false)
	{
		os<<"借出"<<endl;
		//cout<<right.get_amount()<<endl;
	}
	if(right.get_state()  == true)
	{
		os<<"在馆"<<endl;
		//cout<<right.get_amount()<<endl;
	}
	return os;
}

enum Error_code{success,not_present,overflow,duplicate_error,already_in,already_out,error};

template<class Type,int order>
struct B_node
{
	B_node()
	{
		count = 0;
	}
	int count;
	Type data[order - 1];
	B_node<Type,order> *branch[order];
};

template<class Type,int order>
class B_tree
{
public:
	B_tree()
	{
		root = NULL;
	}
	Error_code search_node(B_node<Type,order> *current,const Type &target,int &position);//ensure if the target is in the current node
	Error_code recursive_search_tree(B_node<Type,order> *current,Type &target);
	Error_code search_tree(Type &target);
	Error_code insert(const Type &new_entry);
	Error_code push_down(B_node<Type,order> *current,const Type &new_entry,Type &median,B_node<Type,order> *&right_branch);
	void push_in(B_node<Type,order> *current,const Type &entry,B_node<Type,order> *right_branch,int position);//insert if it has extra spaces
	void split_node(B_node<Type,order> *current,const Type &extra_entry,B_node<Type,order> *extra_branch,int position,B_node<Type,order> *&right_half,Type &median);
	
	void remove_data(B_node<Type,order> *current,int position);
	void copy_in_predecessor(B_node<Type,order> *current,int position);
	void restore(B_node<Type,order> *current,int position);
	void move_left(B_node<Type,order> *current,int position);
	void move_right(B_node<Type,order> *current,int position);
	void combine(B_node<Type,order> *current,int position);
	Error_code recursive_remove(B_node<Type,order> *current,const Type &target);
	Error_code remove(const Type &target);

	void level_scan(B_node<Type,order>* root);
	void recursive_inorder(B_node<Type,order>* root);

	B_node<Type,order>*&GetRoot()
	{
		return root;
	}
	
	Error_code borrow(const Type &target,int number);
	Error_code recursive_borrow(B_node<Type,order> *current,const Type &target,int number);
	Error_code return_book(const Type &target,int number);
	Error_code recursive_return(B_node<Type,order> *current,const Type &target,int number);
	virtual ~B_tree(){}
private:
	B_node<Type,order> *root;
};

//插入部分
template<class Type,int order>
Error_code B_tree<Type,order>::search_node(B_node<Type,order> *current,const Type &target,int &position)
{
	position = 0;
	while(position < current->count && target > current->data[position])
		position++;
	if(position < current->count && target == current->data[position])
		return success;
	else
		return not_present;
}

template<class Type,int order>
Error_code recursive_search_tree(B_node<Type,order> *current,Type &target)
{
	Error_code result = not_present;
	int position;
	if(current != NULL)
	{
		result = search_node(current,target,position);
		if(result == not_present)
			result = recursive_search_tree(current->branch[position],target);//递归转到子节点
		else
			target = current->data[position];
	}
	return result;
}

template<class Type,int order>
Error_code B_tree<Type,order>::search_tree(Type &target)
{
	return recursive_search_tree(root,target);
}

template<class Type,int order> //insert if it has extra spaces
void B_tree<Type,order>::push_in(B_node<Type,order> *current,const Type &entry,B_node<Type,order> *right_branch,int position)
{
	//cout<<current->count<<endl;
	for(int i = current->count;i > position;i--)
	{
		current->data[i] = current->data[i-1];
		current->branch[i+1] = current->branch[i];
	}
	current->data[position] = entry;
	current->branch[position+1] = right_branch;
	current->count++;
}

template<class Type,int order>
void B_tree<Type,order>::split_node(B_node<Type,order> *current,const Type &extra_entry,B_node<Type,order> *extra_branch,int position,B_node<Type,order> *&right_half,Type &median)
{
	right_half = new B_node<Type,order>;
	int mid = order / 2;
	if(position <= mid)
	{
		for(int i = mid;i < order-1;i++)
		{
			right_half->data[i-mid] = current->data[i];
			right_half->branch[i+1-mid] = current->branch[i+1];
		}
		current->count = mid;
		right_half->count = order-1-mid;
		push_in(current,extra_entry,extra_branch,position);
	}
	else
	{
		mid++;
		for(int i = mid;i < order-1;i++)
		{
			right_half->data[i-mid] = current->data[i];
			right_half->branch[i+1-mid] = current->branch[i+1];
		}
		current->count = mid;
		right_half->count = order-1-mid;
		push_in(right_half,extra_entry,extra_branch,position-mid);
	}
	median = current->data[current->count-1];//remove median from left half
	right_half->branch[0] = current->branch[current->count];
	current->count--;
}

template<class Type,int order>
Error_code B_tree<Type,order>::push_down(B_node<Type,order> *current,const Type &new_entry,Type &median,B_node<Type,order> *&right_branch)
{
	Error_code result;
	int position;
	if(current == NULL)
	{
		median = new_entry;
		right_branch = NULL;
		result = overflow;
	}
	else
	{
		if(search_node(current,new_entry,position) == success)
		{
			result = duplicate_error;
			cout<<new_entry.get_name()<<" has existed!"<<endl;
			int new_amount = current->data[position].get_amount() + new_entry.get_amount();
			current->data[position].set_amount(new_amount);
			cout<<current->data[position].get_amount()<<endl;
		}
		else
		{
			
			Type extra_entry;
			B_node<Type,order> *extra_branch;
			//cout<<position<<endl;
			result = push_down(current->branch[position],new_entry,extra_entry,extra_branch);
			if(result == overflow)
			{
				if(current->count < order-1)
				{
					result = success;
					push_in(current,extra_entry,extra_branch,position);
					//cout<<position<<endl;
				}
				else 
				{			
					split_node(current,extra_entry,extra_branch,position,right_branch,median);		
					//cout<<position<<endl;		
				}
			}

		}
	}
	return result;
}


template<class Type,int order>
Error_code B_tree<Type,order>::insert(const Type &new_entry)
{
	Type median;
	B_node<Type,order> *right_branch,*new_root;
	Error_code result = push_down(root,new_entry,median,right_branch);
	if(result == overflow)
	{
		new_root = new B_node<Type,order>;
		new_root->count = 1;
		new_root->data[0] = median;
		new_root->branch[0] = root;
		new_root->branch[1] = right_branch;
		root = new_root;