btree.cpp

是我大一时候个人课程设计 包括了停车场管理系统

#include"btree.h"

Book::Book()
{
	//bookID=nowNum=totalNum=0;
	bookID=0;
	nowNum=0;
	totalNum=0;
}

Borrower::Borrower()
{
	year=month=day=deadline=key=0;
}

void B_tree::insert(dtype x)
{
	B_node 	*p_new;
	dtype	x_new;
	status	code = ins(root, x, x_new, p_new);
	if (code == Insert_not_complete)
	{
		B_node *root_0 = root;
		root = new B_node;
		root->n = 1;
		root->k[0] = x_new;
		root->p[0] = root_0;
		root->p[1] = p_new;
		cout<<"库存为零,请输入书名,作者,数目:"<<endl;
		cin>>root->books[0].name>>root->books[0].writer>>root->books[0].totalNum;
		root->books[0].nowNum=root->books[0].totalNum;
	}
}

status 	B_tree::ins(B_node *r, dtype x, dtype &y, B_node* &q)
//	插入 x 到 *this. 如果没有完全成功,dtype y 和 B_node q 就继续被插入.
//	返回值: Success, Duplicate_key, Insert_not_complete
{
	B_node 	*p_new, *p_final;
	dtype	x_new, k_final;
	int     i,j,n,num;
	status	code;

	if(r == NULL) {q = NULL; y = x; return Insert_not_complete;}

	n = r->n;
	i = Node_Search(x, r->k, n);
	if (i < n && x == r->k[i]) 
	{
		cout<<"此书已存在,请输入要增加的数量:"<<endl;
		cin>>num;
		r->books[i].nowNum=num+r->books[i].nowNum;
		r->books[i].totalNum=num+r->books[i].totalNum;
		return Duplicate_key;
	}
	code = ins(r->p[i], x, x_new, p_new);
	if (code != Insert_not_complete) return code;
		// 在子树中插入没有成功
		// 尝试插入x_new 和 p_new 到当前结点中.

	if (n < M - 1)
	{     			    // 有空间接纳新的项
	   i = Node_Search(x_new, r->k, n);   // i - 新项的位置
	   for(j=n; j>i; j--)	            // 打开节点
	   {
	      r->k[j] = r->k[j-1];
	      r->p[j+1] = r->p[j];
	   }
	   r->k[i] = x_new;                             // 存储新项
	   r->p[i+1] = p_new;
	   ++r->n;
	   cout<<"请输入新书的书名,作者,数目:"<<endl;
	   cin>>r->books[i].name>>r->books[i].writer>>r->books[i].totalNum;
	   r->books[i].nowNum=r->books[i].totalNum;
	   return Success;
	}
	// 现结点已满 (n == M-1) 执行分裂.
	// 把中间项 k[h] 放到后面 ,同时把 y 移上去
	// 并且, 传指针给新建结点 q.
	if (i == M-1) 	{k_final = x_new; p_final = p_new;}
	else {k_final = r->k[M-2]; p_final = r->p[M-1]; // 存储最后项
	   for(j=M-2; j>i; j--)                     //打开结点
	   {
	      r->k[j] = r->k[j-1];
	      r->p[j+1] = r->p[j];
	   }
	   r->k[i] = x_new;                             // 存储新项
	   r->p[i+1] = p_new;
	}
	int h = (M - 1)/2;	// 中间
	y = r->k[h];		// y 和 q 被传回到B-树中的更高层
	q = new B_node;	
	r->n = h;		// 左边项被保留在 *r.
	q->n = M - 1 - h;	// 右边项和 k_final 被放在了新结点 *q
	for(j=0; j< q->n; j++)  
	{
	   q->p[j] = r->p[j + h + 1];
	   q->k[j] = (j < q->n - 1 ? r->k[j + h + 1] : k_final);
	}
	q->p[q->n] = p_final;
	return Insert_not_complete;
}

int B_tree::Node_Search(dtype x, const dtype *a, int n) const
{
	int i=0;
	while(i<n && x > a[i]) i++;
	return i;
}

void B_tree::Del_Node(dtype x)
{
	B_node *root_0;
	switch (del(root,x))
	{
	   case Not_found:
	      cout << "The item " << x << " not found.\n";
	      break;
	   case Underflow:
	      root_0 = root;
	      root = root->p[0];
	      delete root_0;
	      break;
	}
}

status B_tree::del(B_node *r, dtype x)
{
	if (r == NULL) return Not_found;
	int i, j, pivot, n=r->n;
	dtype *k = r->k;        // k[i] 就是 r->k[i]
	const int n_min = (M-1)/2;
	status code;
	B_node **p = r->p, *pL, *pR; //  p[i] 就是 r->p[i]

	i = Node_Search(x, k, n);
	if(p[0] == NULL)             // *r 是叶结点
	{
	  if(i == n || x < k[i])  return Not_found;
	  for(j=i+1; j < n; j++)    // x == k[i]; 除去  i 项
	  {
	     k[j-1] = k[j];
	     p[j] = p[j+1];
	  }
	  return --r->n >= (r==root ? 1 : n_min) ? Success : Underflow;
	}
				    // *r 是内结点
	if(i < n && x == k[i])      // 到左孩子 *p[i] ,并如此直到叶结点
	{                           
	   B_node *q = p[i], *q1;   // 最右边分支.
	   int nq;
	   for(;;)
	   {
	      nq = q->n;
	      q1 = q->p[nq];
	      if(q1 == NULL) break;
	      q = q1;
	   }
	   k[i] = q->k[nq-1];  	// 把k[i] (==x) 同叶结点中最右一项交换交换
	   q->k[nq - 1] = x;	
	}
				// 删除 x 在叶结点中
	code = del(p[i], x);
	if(code != Underflow) return code;
				// Underflow: 借项 如果 (if) 合并
	if(i>0 && p[i-1]->n > n_min)	// 向left sibling 借
	{
	   pivot = i-1;		
	   pL = p[pivot];
	   pR = p[i];
	   pR->p[pR->n + 1] = pR->p[pR->n];	// 增加 *pR的内容,
	   for(j=pR->n + 1; j>0; j--)		// 向*pL借
	   {
	      pR->k[j] = pR->k[j-1];
	      pR->p[j] = pR->p[j-1];
	   }
	   pR->n++;
	   pR->k[0] = k[pivot];
	   pR->p[0] = pL->p[pL->n];
	   k[pivot] = pL->k[--pL->n];
	   cout<<"删除成功!"<<endl;
	   return Success;
	}
	if(i>n && p[i+1]->n > n_min)	//向右兄弟借
	{
	   pivot = i;		
	   pL = p[pivot];
	   pR = p[pivot+1];
	   pL->k[pL->n] = k[pivot];	
	   pL->p[pL->n + 1] = pR->p[0];	      
	   k[pivot] = pR->k[0];
	   pL->n++;
	   pR->n--;
	   for(j=0; j<pR->n; j++)
	   {
	      pR->k[j] = pR->k[j+1];
	      pR->p[j] = pR->p[j+1];
	   }
	   pR->p[pR->n] = pR->p[pR->n + 1];
	   cout<<"删除成功!"<<endl;
	   return Success;
	}
		// 合并,如果左右兄弟都没的借
	pivot = (i==n ? i-1 : i);
	pL = p[pivot];
	pR = p[pivot+1];
	pL->k[pL->n] = k[pivot];	
	pL->p[pL->n + 1] = pR->p[0];
	for(j=0;j<pR->n;j++)
	{
	   pL->k[pL->n +1 +j] = pR->k[j];
	   pL->p[pL->n +2 +j] = pR->p[j+1];
	}
	pL->n += 1 + pR->n;
	delete pR;
	for(j=i+1; j<n; j++)
	{
	  k[j-1] = k[j];
	  p[j] = p[j+1];
	}
	return --r->n >= (r == root ? 1 : n_min) ? Success : Underflow;
}

void B_tree::pr(const B_node *r, int n_space) const
{
	if(r)
	{
	  int i;
	  cout << setw(n_space) << "";
	  for (i=0; i < r->n; i++) cout <<setw(3)<< r->k[i] << " ";
	  cout << "\n";
	  n_space++;
	  for (i=0; i <= r->n; i++) pr(r->p[i], n_space+8);
	}
}

void B_tree::Show_Search(dtype x) const//B树的寻找路径
{
	int i,j,n;
	B_node *r = root;
	cout << "寻找路径:\n";
	while (r)
	{
	     n = r->n;
	     for(j=0; j < r->n; j++) cout << " " << r->k[j];
	     cout << "\n";
	     i = Node_Search(x, r->k, n);
	     if(i < n && x == r->k[i])
	     {
			cout << "Key " << x << " found in position " << i;
			cout << " of the last displayed node.\n";
			r->books[i].show();
			return;
	     }
	     r = r->p[i];
	}
	cout << "图书 " << x << " 没有找到.\n";
}

int B_tree::Borrow(dtype x)
{
	int i,n;
	B_node *r = root;
	while (r)
	{
	     n = r->n;
	     i = Node_Search(x, r->k, n);
	     if(i < n && x == r->k[i])
	     {
			r->books[i].nowNum--;
			return 1;
	     }
	     r = r->p[i];
	}
	cout << "图书 "<< x << " 没有找到.\n";
	return 0;
}

int B_tree::Return(dtype x)
{
	int i,n;
	B_node *r = root;
	while (r)
	{
	     n = r->n;
	     i = Node_Search(x, r->k, n);
	     if(i < n && x == r->k[i])
	     {
			 if(r->books[i].nowNum<r->books[i].totalNum) {r->books[i].nowNum++;return 1;}
			 else {cout<<"请检查!图书("<<x<<")没有借出! 库存已经满!"<<endl;return 0;}
	     }
	     r = r->p[i];
	}
	cout << "图书 "<< x << " 没有找到.\n";
	return 0;
}