西文图书管理系统

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显示图书状态删除图书记录查找图书借阅图书读取文件退出归还图书添加图书作者总量现存量书号书名开始关闭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()//删除InsertBTreeInsertSplitNewRootSearchBTreeaddbookfindbookLendbookReturnbookBookcountexitmenudelbookDeleteBTreeRecDeleteSearchNodeSuccessorRemoveRestoreMoveLeftCombineMoveRightvoidbookcount()//显示书的状况voidmenu()//主界面intmain()//主函数2.3详细设计各个功能模块主要算法的伪代码实现添加图书模块printf(请输入书号)scanf（书号）IfSearchBTree(书号)=trueprintf(此书已存在!)else{printf(请输入书名)scanf(书名)printf(请输入作者)scanf(作者)printf(请输入现存量)scanf(现存量)printf(请输入总量)scanf(总量)}InsertBTree(书号，书名,作者,现存量,总量)printf(输入1继续添加,0返回主界面)scanf(1or0)return查找图书模块printf(请输入书号)scanf（书号）ifSearchBTree(书号)=trueprintf(成功找到!)printf(书号,书名,作者,现存量,总量)if总量大于零printf(你想借这本书吗?输入1借,0退出)scanf(1or0)if(1)总量减一elseprintf(此书不存)return借阅图书模块printf(请输入书号)scanf(书号)ifSearchBTree(书号)=trueand总量大于零{printf(操作成功!)总量减一}elseprintf(操作失败!书已经被借出或不存在这本书)return归还图书模块printf(请输入书号)scanf(书号)ifSearchBTree(书号)=trueprintf(操作成功!)总量加一elseprintf(操作失败!\n);return删除图书记录模块printf(请输入书号)scanf(书号)ifSearchBTree(书号)=trueprintf(书的具体信息:书号,书名,作者,现存量,总量)printf(输入1删除这本书)scanf()if(1){书号=0printf(删除成功!)}elseprintf(操作失败!不存在这本书)return显示图书状态模块inti;for(i=1;i1000;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截屏46．源程序清单#includestdio.h#includewindows.h#includemalloc.h#includestring.h#includeconio.h#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]=kp-key[i+1]inti;for(i=0;ip-keynum&&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;//创建查找结果类型结构体rwhile(p!=NULL&&found==0){i=Search(p,k);/*在p-key[1..keynum]中查找i,使得p-key[i]=kp-key[i+1]*/if(i0&&p-key[i]==k)/*找到待查关键字*/found=1;else{q=p;//双亲结点q指向pp=p-ptr[i];//p变成它原来的孩子结点}}r.i=i;//关键字序号iif(found==1)/*查找成功*/{r.pt=p;r.tag=1;//pt指向找到的结