西文图书管理系统.doc
《西文图书管理系统.doc》由会员分享，可在线阅读，更多相关《西文图书管理系统.doc（23页珍藏版）》请在冰点文库上搜索。
9．西文图书管理系统
图书管理基本业务活动包括：
对一本书的采编入库、清除库存、借阅和归还等等。
试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。
要求：
（1）每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。
（2）作为演示系统，不必使用文件，全部数据可以都在内存存放。
要用B-树（4阶树）对书号建立索引，以获得高效率。
（3）系统应有以下功能：
采编入库、清除库存、借阅、归还、显示（以凹入表的形式显示）等。
1．需求分析
设计一个西文图书管理系统,将图书管理基本业务活动如对一本书的采编入库、清除库存、借阅和归还等等借助于计算机系统完成，该图书管理系统应有以下功能：
采编入库、清除库存、借阅、归还、显示等。
要求用B-树（4阶树）对书号建立索引，以获得高效率，输出以凹入表的形式显示。
2．设计
2.1设计思想
（1）数据结构设计
逻辑结构设计：
树形结构（B-树）
存储结构设计：
链式存储结构
选择B-树这种数据结构的原因：
与二叉树相比，B-树是一种平衡多叉排序树。
平衡是指所有叶结点都在同一层上，从而可避免出现二叉排序树那样的分支退化现象；多叉是指多于二叉，多于二叉的排序树将降低二叉树高度，从而减少查找数据元素时的比较次数。
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为：
其中，M为设定的非叶子结点最多子树个数，N为关键字总数； 所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；因此，B-树是一种动态查找效率较二叉排序树更高的树形结构。
（2）算法设计
算法设计的总体设计思路为：
首先创建一颗4阶B-树，然后在此基础上设计添加图书、查找图书、借阅图书、归还图书、显示图书状态、删除图书记录、退出七个模块，最后主函数再用一个switch选择语句来调用各个模块。
各个模块要完成的主要功能分别为：
添加图书：
可以添加图书记录，按提示依次输入书号、书名、作者、现存量、总量，会提示是否继续添加。
查找图书：
可根据输入的书号进行查询，成功找到后会提示是否想借这本书，输入1为借书，输入0为退出。
借阅图书：
可根据提示输入相应的书号进行借书。
归还图书：
可根据提示输入相应的书号归还图书。
显示图书状态：
可显示图书管理系统里的所有图书状态。
删除图书记录：
可根据提示输入相应的书号删除图书记录。
主程序的流程图如下：
输入i
判断i
显示图书状态
删除图书记录
查找图书
借阅图书
读取文件
退出
归还图书
添加图书
作者
总量
现存量
书号
书名
开始
关闭
InsertBTree
Insert
Split
NewRoot
SearchBTree
addbook
findbook
Lend
book
Return
book
Book
count
exit
menu
delbook
DeleteBTree
RecDelete
SearchNode
Successor
Remove
Restore
MoveLeft
Combine
MoveRight
2.2设计表示
（1）函数调用关系图
（2）函数接口规格说明
intSearch（BTNode*p,KeyTypek）
ResultSearchBTree（BTNode*&t,KeyTypek）
voidInsert（BTNode*&q,inti,KeyTypex,BTNode*&ap）
voidSplit（BTNode*&q,BTNode*&ap）
voidNewRoot（BTNode*&t,BTNode*p,KeyTypex,BTNode*ap）
voidInsertBTree（BTNode*&t,KeyTypek,BTNode*&q,inti）
voidRemove（BTNode*p,inti）
voidSuccessor（BTNode*p,inti）
voidMoveLeft（BTNode*p,inti）
voidMoveRight（BTNode*p,inti）
voidCombine（BTNode*p,inti）
voidRestore（BTNode*p,inti）
intSearchNode（KeyTypek,BTNode*p,int&i）
intRecDelete（KeyTypek,BTNode*p）
voidDeleteBTree（KeyTypek,BTNode*root）
voidaddbook（）//添加书
voidlendbook（intbooknumber）//借书
voidfindbook（）//查找书
voidreturnbook（）//还书
voiddelbook（）//删除
voidbookcount（）//显示书的状况
voidmenu（）//主界面
intmain（）//主函数
2.3详细设计
各个功能模块主要算法的伪代码实现
Ø添加图书模块
printf（请输入书号）
scanf（书号）
IfSearchBTree（书号）=true
printf（此书已存在!
）
else
{
printf（请输入书名）
scanf（书名）
printf（请输入作者）
scanf（作者）
printf（请输入现存量）
scanf（现存量）
printf（请输入总量）
scanf（总量）
}
InsertBTree（书号，书名,作者,现存量,总量）
printf（输入1继续添加,0返回主界面）
scanf（1or0）
return
Ø查找图书模块
printf（请输入书号）
scanf（书号）
ifSearchBTree（书号）=true
printf（成功找到!
）
printf（书号,书名,作者,现存量,总量）
if总量大于零
printf（你想借这本书吗?
输入1借,0退出）
scanf（1or0）
if
（1）总量减一
else
printf（此书不存）
return
Ø借阅图书模块
printf（请输入书号）
scanf（书号）
ifSearchBTree（书号）=trueand总量大于零
{
printf（"操作成功!
"）
总量减一
}
else
printf（操作失败!
书已经被借出或不存在这本书）
return
Ø归还图书模块
printf（请输入书号）
scanf（书号）
ifSearchBTree（书号）=true
printf（操作成功!
）
总量加一
else
printf（"操作失败!
\n"）;
return
Ø删除图书记录模块
printf（请输入书号）
scanf（书号）
ifSearchBTree（书号）=true
printf（书的具体信息:
书号,书名,作者,现存量,总量）
printf（输入1删除这本书）
scanf（）
if
（1）
{
书号=0
printf（删除成功!
）
}
elseprintf（操作失败!
不存在这本书）
return
Ø显示图书状态模块
inti;
for（i=1;i<1000;i++）
if（总量!
=0）
printf（书号,书名,作者,现存量,总量）
3．调试分析
（1）本程序最大的问题就是B-树的基本算法的实现，此处难点在于B_树的结点的分裂，当插入结点时，判断结点中关键字的个数是否大于规定的个数，如果大于则要对此结点进行分裂，在分裂时，要改变孩子结点的parent指针，并且把分裂出的关键字放到该关键字的parent结点中，然后继续判断是否要分裂，一直到符合要求。
在进行检测时，出现了分裂时的错误，就是没有考虑到在分裂结点时，该结点的孩子结点的parent指针的改变，我参考了课本和老师的课件，并与和其他同学讨论后终于通过调试和改正，测试正确。
另外，在老师您在验收我的程序时，指出了我的程序的两个不足之处，一是没有按要求以凹入表的形式显示，二是在删除图书记录后图书记录并没有消失，而仅仅是图书号变成了—1，因此您只给我的这个程序打了个B，我当时心里真的很伤心。
这两个不足之处我在您验收之后很快就改过来了，因为原因很简单：
第一个不足之处产生的原因是我没注意到题目有这个要求，其实只要在输出语句中的书名前面加\n\t就行了；第二个不足之处产生的原因是在删除图书记录时应将要删除的图书号置为0，而我却将它置为了—1.本来我当时是想找老师您再验收一次把成绩改高一点的，但由于当时验收的人太多了，就没再去麻烦您。
（2）算法的时间空间复杂度分析
由于B-树查找的时间复杂度为O（Log2N），而程序中多次用到了一重循环，其时间复杂度为O（n）,因此程序的时间复杂度为O（n），空间复杂度也为O（n）.
（3）可改进内容：
1、利用MFC做一个界面，使界面更加美观；2、可尝试用B+树代替B_树，更容易应用于文件系统3、删除图书记录的时候必须先收回所有的书，即要保证现存量和总量相等后方可删除；4、采用文件的形式，可以保存图书状态。
4．用户手册
本程序在VC++6.0环境下运行，按照菜单提示的要求输入即可。
5．测试数据及测试结果
测试用例1：
测试输入：
见截屏1、2
测试目的：
是否能按要求以凹入表的形式显示
正确输出：
见截屏1
实际输出：
见截屏2
错误原因：
没有注意审题，因此未在输出语句中的书号前加\n\t
当前状态：
已改正
测试用例2：
测试输入：
见截屏3、4
测试目的：
是否能按要求以凹入表的形式显示
正确输出：
见截屏3
实际输出：
见截屏4
错误原因：
编程时粗心，错误的将应删除的书号置为了—1.
当前状态：
已改正
截屏1
截屏2
截屏3
截屏4
6．源程序清单
#include
#include
#include
#include
#include
#defineMAXM10/*定义B-树的最大的阶数*/
typedefintKeyType;/*KeyType为关键字类型*/
structBookInfo//书结构体
{
intnumber;
charname[30];
charauthor[30];
intextant;
inttotal;
};
typedefstructnode//B-树结点定义
{
intkeynum;/*结点当前拥有的关键字的个数*/
KeyTypekey[MAXM];/*key[1..keynum]存放关键字,key[0]不用*/
structnode*parent;/*双亲结点指针*/
structnode*ptr[MAXM];/*孩子结点指针数组ptr[0..keynum]*/
}BTNode;
BTNode*bookp=NULL;
typedefstruct/*B-树的查找结果类型*/
{
BTNode*pt;/*指向找到的结点*/
inti;/*1..m,在结点中的关键字序号*/
inttag;/*1:
查找成功,O:
查找失败*/
}Result;
intm;/*m阶B-树,为全局变量*/
intMax;/*m阶B-树中每个结点的至多关键字个数,Max=m-1*/
intMin;/*m阶B-树中非叶子结点的至少关键字个数,Min=（m-1）/2*/
Results;
intSearch（BTNode*p,KeyTypek）
{//在p->key[1..keynum]中查找关键字序号i,使得p->key[i]<=kkey[i+1]
inti;
for（i=0;ikeynum&&p->key[i+1]<=k;i++）;
returni;
}
ResultSearchBTree（BTNode*&t,KeyTypek）//在m阶t树t上查找关键字k,返回查找结果（pt,i,tag）。
若查找成功
{//则tag=1,指针pt所指结点中第i个关键字等于k；否则tag=0,等于k的
//关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间
BTNode*p=t,*q=NULL;/*初始化,t为待查树,p指向待查结点,q指向p的双亲*/
intfound=0,i=0;//found为标志位
Resultr;//创建查找结果类型结构体r
while（p!
=NULL&&found==0）
{
i=Search（p,k）;/*在p->key[1..keynum]中查找i,使得p->key[i]<=kkey[i+1]*/
if（i>0&&p->key[i]==k）/*找到待查关键字*/
found=1;
else
{
q=p;//双亲结点q指向p
p=p->ptr[i];//p变成它原来的孩子结点
}
}
r.i=i;//关键字序号i
if（found==1）/*查找成功*/
{
r.pt=p;r.tag=1;//pt指向找到的结点p,tag置为1
}
else/*查找不成功,返回K的插入位置信息*/
{
r.pt=q;r.tag=0;//pt指向q,tag置为0
}
returnr;/*返回k的位置（或插入位置）*/
}
voidInsert（BTNode*&q,inti,KeyTypex,BTNode*&ap）
{//若有位置,将x插入到q->key[i+1],ap插到q->ptr[i+1]中
intj;
for（j=q->keynum;j>i;j--）/*空出一个位置*/
{
q->key[j+1]=q->key[j];
q->ptr[j+1]=q->ptr[j];
}
q->key[i+1]=x;
q->ptr[i+1]=ap;
if（ap!
=NULL）ap->parent=q;
q->keynum++;
}
voidSplit（BTNode*&q,BTNode*&ap）
{//无空位置则分裂.将结点q分裂成两个结点,前一半保留,后一半移入新生结点ap
inti,s=（m+1）/2;//分裂的位置
ap=（BTNode*）malloc（sizeof（BTNode））;/*生成新结点*ap*/
ap->ptr[0]=q->ptr[s];/*后一半移入ap*/
for（i=s+1;i<=m;i++）
{
ap->key[i-s]=q->key[i];
ap->ptr[i-s]=q->ptr[i];
if（ap->ptr[i-s]!
=NULL）
ap->ptr[i-s]->parent=ap;
}
ap->keynum=q->keynum-s;
ap->parent=q->parent;
for（i=0;i<=q->keynum-s;i++）/*修改指向双亲结点的指针*/
if（ap->ptr[i]!
=NULL）ap->ptr[i]->parent=ap;
q->keynum=s-1;/*q的前一半保留,修改keynum*/
}
voidNewRoot（BTNode*&t,BTNode*p,KeyTypex,BTNode*ap）//生成含信息（T,x,ap）的新的根结点*t,
//原t和ap为子树指针
{
t=（BTNode*）malloc（sizeof（BTNode））;
t->keynum=1;
t->ptr[0]=p;
t->ptr[1]=ap;
t->key[1]=x;
if（p!
=NULL）p->parent=t;
if（ap!
=NULL）ap->parent=t;
t->parent=NULL;
}
voidInsertBTree（BTNode*&t,KeyTypek,BTNode*&q,inti）
{/*最终的插入函数.在m阶t树t上结点*q的key[i]与key[i+1]之间插入关键字k。
若引起
结点过大,则沿双亲链进行必要的结点分裂调整,使t仍是m阶t树。
*/
BTNode*ap;
intfinished,needNewRoot,s;
KeyTypex;
if（q==NULL）/*t是空树（参数q初值为NULL）*/
NewRoot（t,NULL,k,NULL）;//生成仅含关键字k的根结点*t
else
{
x=k;ap=NULL;finished=needNewRoot=0;
while（needNewRoot==0&&finished==0）
{
Insert（q,i,x,ap）;/*将x和ap分别插入到q->key[i+1]和q->ptr[i+1]*/
if（q->keynum<=Max）finished=1;/*无须分裂,插入完成*/
else
{/*分裂结点*q,将q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新结点*ap*/
s=（m+1）/2;
Split（q,ap）;
x=q->key[s];
if（q->parent）/*在双亲结点*q中查找x的插入位置*/
{
q=q->parent;
i=Search（q,x）;
}
elseneedNewRoot=1;
}
}
if（needNewRoot==1）/*根结点已分裂为结点*q和*ap*/
NewRoot（t,q,x,ap）;/*生成新根结点*t,q和ap为子树指针*/
}
}
voidRemove（BTNode*p,inti）
/*从*p结点删除key[i]和它的孩子指针ptr[i]*/
{
intj;
for（j=i+1;j<=p->keynum;j++）/*前移删除key[i]和ptr[i]*/
{
p->key[j-1]=p->key[j];
p->ptr[j-1]=p->ptr[j];
}
p->keynum--;
}
voidSuccessor（BTNode*p,inti）
/*查找被删关键字p->key[i]（在非叶子结点中）的替代叶子结点*/
{
BTNode*q;
for（q=p->ptr[i];q->ptr[0]!
=NULL;q=q->ptr[0]）;
p->key[i]=q->key[1];/*复制关键字值*/
}
voidMoveRight（BTNode*p,inti）
/*把一个关键字移动到右兄弟中*/
{
intc;
BTNode*t=p->ptr[i];
for（c=t->keynum;c>0;c--）/*将右兄弟中所有关键字左移一位*/
{
t->key[c+1]=t->key[c];
t->ptr[c+1]=t->ptr[c];
}
t->ptr[1]=t->ptr[0];/*从双亲结点移动关键字到右兄弟中*/
t->keynum++;
t->key[1]=p->key[i];
t=p->ptr[i-1];/*将左兄弟中最后一个关键字移动到双亲结点中*/
p->key[i]=t->key[t->keynum];
p->ptr[i]->ptr[0]=t->ptr[t->keynum];
t->keynum--;
}
voidMoveLeft（BTNode*p,inti）
/*把一个关键字移动到左兄弟中*/
{
intc;
BTNode*t;
t=p->ptr[i-1];/*把双亲结点中的关键字移动到左兄弟中*/
t->keynum++;
t->key[t->keynum]=p->key[i];
t->ptr[t->keynum]=p->ptr[i]->ptr[0];
t=p->ptr[i];/*把右兄弟中的关键字移动到双亲兄弟中*/
p->key[i]=t->key[1];
p->ptr[0]=t->ptr[1];
t->keynum--;
for（c=1;c<=t->keynum;c++）/*将右兄弟中所有关键字移动一位*/
{
t->key[c]=t->key[c+1];
t->ptr[c]=t->ptr[c+1];
}
}
voidCombine（BTNode*p,inti）
/*将三个结点合并到一个结点中*/
{
intc;
BTNode*q=p->ptr[i];/*指向右结点,它将被置空和删除*/
BTNode*l=p->ptr[i-1];
l->keynum++;
升级会员 