西文图书管理系统.docx
《西文图书管理系统.docx》由会员分享,可在线阅读,更多相关《西文图书管理系统.docx(18页珍藏版)》请在冰点文库上搜索。
西文图书管理系统
LGGROUPsystemofficeroom【LGA16H-LGYY-LGUA8Q8-LGA162】
西文图书管理系统
9.西文图书管理系统
图书管理基本业务活动包括:
对一本书的采编入库、清除库存、借阅和归还等等。
试设计一个图书管理系统,将上述业务活动借助于计算机系统完成。
要求:
(1)每种书的登记内容至少包括书号、书名、着者、现存量和总库存量等五项。
(2)作为演示系统,不必使用文件,全部数据可以都在内存存放。
要用B-树(4阶树)对书号建立索引,以获得高效率。
(3)系统应有以下功能:
采编入库、清除库存、借阅、归还、显示(以凹入表的形式显示)等。
1.需求分析
设计一个西文图书管理系统,将图书管理基本业务活动如对一本书的采编入库、清除库存、借阅和归还等等借助于计算机系统完成,该图书管理系统应有以下功能:
采编入库、清除库存、借阅、归还、显示等。
要求用B-树(4阶树)对书号建立索引,以获得高效率,输出以凹入表的形式显示。
2.设计
设计思想
(1)数据结构设计
逻辑结构设计:
树形结构(B-树)
存储结构设计:
链式存储结构
选择B-树这种数据结构的原因:
与二叉树相比,B-树是一种平衡多叉排序树。
平衡是指所有叶结点都在同一层上,从而可避免出现二叉排序树那样的分支退化现象;多叉是指多于二叉,多于二叉的排序树将降低二叉树高度,从而减少查找数据元素时的比较次数。
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:
其中,M为设定的非叶子结点最多子树个数,N为关键字总数;所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;因此,B-树是一种动态查找效率较二叉排序树更高的树形结构。
(2)算法设计
算法设计的总体设计思路为:
首先创建一颗4阶B-树,然后在此基础上设计添加图书、查找图书、借阅图书、归还图书、显示图书状态、删除图书记录、退出七个模块,最后主函数再用一个switch选择语句来调用各个模块。
各个模块要完成的主要功能分别为:
添加图书:
可以添加图书记录,按提示依次输入书号、书名、作者、现存量、总量,会提示是否继续添加。
查找图书:
可根据输入的书号进行查询,成功找到后会提示是否想借这本书,输入1为借书,输入0为退出。
借阅图书:
可根据提示输入相应的书号进行借书。
归还图书:
可根据提示输入相应的书号归还图书。
显示图书状态:
可显示图书管理系统里的所有图书状态。
删除图书记录:
可根据提示输入相应的书号删除图书记录。
主程序的流程图如下:
设计表示
(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()和来我当时是想找老师您再验收一次把成绩改高一点的,但由于当时验收的人太多了,就没再去麻烦您。
(2)算法的时间空间复杂度分析
由于B-树查找的时间复杂度为O(Log2N),而程序中多次用到了一重循环,其时间复杂度为O(n),因此程序的时间复杂度为O(n),空间复杂度也为O(n).
(3)可改进内容:
1、利用MFC做一个界面,使界面更加美观;2、可尝试用B+树代替B_树,更容易应用于文件系统3、删除图书记录的时候必须先收回所有的书,即要保证现存量和总量相等后方可删除;4、采用文件的形式,可以保存图书状态。
4.用户手册
本程序在VC++环境下运行,按照菜单提示的要求输入即可。
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为关键字类型*/
structBookInfokeynum]存放关键字,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)
{keynum]中查找关键字序号i,使得p->key[i]<=kkey[i+1]
inti;
for(i=0;ikeynum&&p->key[i+1]<=k;i++);
returni;
}
ResultSearchBTree(BTNode*&t,KeyTypek)keynum]中查找i,使得p->key[i]<=kkey[i+1]*/
if(i>0&&p->key[i]==k)/*找到待查关键字*/
found=1;
else
{
q=p;Split结点q分裂成两个结点,前一半保留,后一半移入新生结点ap
inti,s=(m+1)/2;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);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++;/*l指向左结点*/
l->key[l->keynum]=p->key[i];
l->ptr[l->keynum]=q->ptr[0];
for(c=1;c<=q->keynum;c++)/*插入右结点中的所有关键字*/
{
l->keynum++;
l->key[l->keynum]=q->key[c];
l->ptr[l->keynum]=q->ptr[c];
}
for(c=i;ckeynum;c++)/*删除父结点所有的关键字*/
{
p->key[c]=p->key[c+1];
p->ptr[c]=p->ptr[c+1];
}
p->keynum--;
free(q);/*释放空右结点的空间*/
}
voidRestore(BTNode*p,inti)
/*关键字删除后,调整B-树,找到一个关键字将其插入到p->ptr[i]中*/
{
if(i==0)/*为最左边关键字的情况*/
if(p->ptr[1]->keynum>Min)
MoveLeft(p,1);
else
Combine(p,1);
elseif(i==p->keynum)/*为最右边关键字的情况*/
if(p->ptr[i-1]->keynum>Min)
MoveRight(p,i);
else
Combine(p,i);
elseif(p->ptr[i-1]->keynum>Min)/*为其他情况*/
MoveRight(p,i);
elseif(p->ptr[i+1]->keynum>Min)
MoveLeft(p,i+1);
else
Combine(p,i);
}
intSearchNode(KeyTypek,BTNode*p,int&i)
/*在结点p中找关键字为k的位置i,成功时返回1,否则返回0*/
{
if(kkey[1])/*k小于*p结点的最小关键字时返回0*/
{
i=0;
return0;
}
else/*在*p结点中查找*/
{
i=p->keynum;
while(kkey[i]&&i>1)
i--;
return(k==p->key[i]);
}
}
intRecDelete(KeyTypek,BTNode*p)
/*查找并删除关键字k*/
{
inti;
intfound;
if(p==NULL)
return0;
else
{
if((found=SearchNode(k,p,i))==1)/*查找关键字k*/
{
if(p->ptr[i-1]!
=NULL)/*若为非叶子结点*/
{
Successor(p,i);/*由其后继代替它*/
RecDelete(p->key[i],p->ptr[i]);/*p->key[i]在叶子结点中*/
}
else
Remove(p,i);/*从*p结点中位置i处删除关键字*/
}
else
found=RecDelete(k,p->ptr[i]);/*沿孩子结点递归查找并删除关键字k*/
if(p->ptr[i]!
=NULL)
if(p->ptr[i]->keynumRestore(p,i);
returnfound;
}
}
voidDeleteBTree(KeyTypek,BTNode*root)
/*从B-树root中删除关键字k,若在一个结点中删除指定的关键字,不再有其他关键字,则删除该结点*/
{
BTNode*p;/*用于释放一个空的root*/
if(RecDelete(k,root)==0)
printf("关键字%d不在B-树中\n",k);
elseif(root->keynum==0)
{
p=root;
root=root->ptr[0];
free(p);
}
}
structBookInfobook[1000];
voidaddbook()umber=num;
printf("\n书名:
");
scanf("%s",&book[num].name);
printf("\n作者:
");
scanf("%s",&book[num].author);
printf("\n现存量:
");
scanf("%d",&book[num].extant);
printf("\n总量:
");
scanf("%d",&book[num].total);
}
InsertBTree(bookp,book[num].number,,;
printf("\n输入1继续添加,0返回主界面");
scanf("%d",&n);
}
}
voidlendbook(intbooknumber)xtant)
{
printf("操作成功!
");
book[num].extant--;
}
else
printf("操作失败!
书已经被借出或不存在这本书.");
}
else
{
printf("操作成功!
\n");
book[booknumber].extant--;
}
return;
}
voidfindbook()n");
printf("书号:
%d,\n\t书名:
%s,作者:
%s,现存量:
%d,总量:
%d\n",book[num].number,book[num].name,book[num].author,book[num].extant,book[num].total);
}
else
printf("此书不存在.");
if(book[num].extant)
{
printf("你想借这本书吗?
输入1借,0退出.\n");
scanf("%d",&select);
if(select)
lendbook(num);
else
return;
}
else
{
return;
}
}
voidreturnbook()umber!
=-1&&book[num].extant{book[num].extant++;
printf("操作成功!
\n");
}
elseprintf("操作失败!
\n");
return;
}
voiddelbook()umber,book[num].name,book[num].author,book[num].extant,book[num].total);
printf("输入1删除这本书:
");
scanf("%d",&confirm);
if(confirm==1)
{
DeleteBTree(book[num].number,bookp);
book[num].number=0;
printf("删除成功!
");
}
return;
}
voidbookcount()umber!
=0)
printf("书号:
%3d,\n\t书名:
%7s,作者:
%7s,现存量:
%5d,总量:
%5d\n",book[i].number,book[i].name,book[i].author,book[i].extant,book[i].total);
}
voidmenu()umber);
if==0&&book[j].number!
=-1)
InsertBTree(bookp,book[j].number,,;
}
while
(1)
menu();
return0;
}