数据结构课程设计——B树图书管理

这是数据结构最后的课程设计，我选择的是用B树为存储结构制作一个图书管理系统，里面还包括实验报告和用到的资源文件

#include “Library.h“

/********************************B树接口实现****************************/

int Search（BTree p int k） {
	//在B树p中查找关键字k的位置i，使得p->node[i].key<=Knode[i+1].key
	int i;
	for （i = 0; i < p->keynum&&p->key[i + 1] <= k; i++）;
	return i;
}

result	SearchBTree（BTree T KeyType k）
// 在m阶B树上查找关键字k，返回结果（pt，i，tag）。若查找成功，则特征值tag=1，指针pt
// 所指结点中第i个关键字等于k；否则返回特征值tag=0，等于k的关键字应插入在pt所指结点
// 中第i和第i+1个关键字之间。
{
	int		i = 1;
	BTree	p = T q = NULL;						// 初始化，p指向待查结点，q指向p的双亲
	int		found = FALSE;
	while （p && !found）
	{
		i = Search（p k）;							// 查找k的位置使p->key[i]<=kkey[i+1]
		if （i> 0 && k == p->key[i]）	found = TRUE;
		else {										// 未找到，则查找下一层
			q = p;
			p = p->ptr[i];
		}
	}
	if （found） { result	r = { p i 1 };	return r; }	// 查找成功
	else { result	r = { q i 0 };	return r; }	// 查找不成功，返回k的插入位置信息
}

void split（BTree &q int s BTree &ap） {
	//将q结点分裂成两个结点，前一半保留，后一半移入新结点ap
	int i n = q->keynum;
	ap = （BTNode*）malloc（sizeof（BTNode））;//生成新结点ap
	ap->ptr[0] = q->ptr[s];
	for （i = s + 1; i <= M; i++） {//后一半移入ap结点
		ap->key[i-s] = q->key[i];
		ap->ptr[i-s] = q->ptr[i];
		ap->recptr[i - s] = q->recptr[i];
	}
	ap->keynum = n - s;//计算ap的关键字个数
	ap->parent = q->parent;
	for （i = 0; i <= M - s; i++） {
		if （ap->ptr[i]）
			ap->ptr[i]->parent = ap;//将ap所有孩子结点指向ap
	}
	q->keynum = s - 1;//q结点的前一半保留，修改keynum
}

void newroot（BTree &T BTree p int k BTree apRecord *recptr） {//生成新的根结点
	T = （BTNode*）malloc（sizeof（BTNode））;
	T->keynum = 1;
	T->ptr[0] = p;
	T->ptr[1] = ap;
	T->key[1] = k;
	T->recptr[1] = recptr;  //T的子树ap的父亲指针
	if （p != NULL） p->parent = T;
	if （ap != NULL） ap->parent = T;
	T->parent = NULL;//新根的双亲是空指针
}

void Insert（BTree &q int i int k BTree apRecord *recptr） {//k和ap分别插到q->key[i+1]和q->ptr[i+1]
															//并插入关键字为k的记录recprt
	int j n = q->keynum;
	for （j = n; j > i; j--） {
		q->key[j + 1] = q->key[j];//关键字指针向后移一位
		q->ptr[j + 1] = q->ptr[j];//孩子结点指针向后移一位
		q->recptr[j + 1] = q->recptr[j];
	}
	q->key[i+1] = k;//赋值
	q->ptr[i+1] = ap;
	q->recptr[i + 1] = recptr;
	if （ap != NULL） ap->parent = q;
	q->keynum++;//关键字数+1
}

Status InsertBTree（BTree &T KeyType k BTree q int i Record *rec）
//  在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K和记录rec。
//  若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树。
{
	BTree ap = NULL;
	int finished = FALSE;
	if （!q）    newroot（T NULL k NULL rec）;	// T是空树，生成仅含关键字K的根结点*T
	else {
		while （!finished）
		{
			Insert（q i k ap rec）;			// 将k和ap分别插入到q->key[i+1]和q->ptr[i+1]
			if （q->keynum < M） finished = TRUE; // 插入完成
			else {
				split（q （M + 1） / 2 ap）;			// 分裂结点Q
				k = q->key[（M + 1） / 2];
				rec = q->recptr[（M + 1） / 2];
				if （q->parent）
				{							// 在双亲结点*q中查找k的插入位置
					q = q->parent;
					i = Search（q k）;
				}
				else finished = OVERFLOW;		// 根节点已分裂为*q和*ap两个结点
			}
		}
		if （finished == OVERFLOW）				// 根结点已分裂为结点*q和*ap
			newroot（T q k ap rec）;			// 需生成新根结点*Tq和ap为子树指针
	}
	return OK;
} //  InsertBTree

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-12-17 12:55  杨宇杰_3115005372_实验四\
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\.vs\
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\.vs\BTree_Library\
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\.vs\BTree_Library\v14\
     文件       38400  2016-12-17 10:45  杨宇杰_3115005372_实验四\BTree_Library\.vs\BTree_Library\v14\.suo
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\
     文件        6022  2016-12-17 12:09  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\BTree_Library.vcxproj
     文件        1502  2016-12-17 12:09  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\BTree_Library.vcxproj.filters
     文件         165  2016-12-17 11:08  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\BTree_Library.vcxproj.user
     文件       11425  2016-12-17 11:36  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\BTree_Operation.cpp
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\
     文件         205  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.log
     目录           0  2016-12-17 12:13  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\
     文件         202  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\BTree_Library.lastbuildstate
     文件        1822  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\CL.command.1.tlog
     文件       66276  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\CL.read.1.tlog
     文件        4700  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\CL.write.1.tlog
     文件        1546  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\link.command.1.tlog
     文件        3104  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\link.read.1.tlog
     文件         790  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Library.tlog\link.write.1.tlog
     文件       52957  2016-12-17 11:36  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\BTree_Operation.obj
     文件       52278  2016-12-17 12:09  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\Library.obj
     文件       45685  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\main.obj
     文件      707584  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\vc140.idb
     文件      176128  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Debug\vc140.pdb
     文件        7626  2016-12-17 12:09  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Library.cpp
     文件        3713  2016-12-17 11:36  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\Library.h
     文件         714  2016-12-17 10:26  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\bookinfo.dat
     文件       32000  2009-06-14 01:55  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\borrower.dat
     文件        4291  2016-12-17 12:11  杨宇杰_3115005372_实验四\BTree_Library\BTree_Library\main.cpp
............此处省略15个文件信息