西文图书管理系统.doc

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显示图书状态删除图书记录查找图书借阅图书读取文件退出归还图书添加图书作者总量现存量书号书名开始关闭 InsertBTreeInsertSplitNewRootSearchBTreeaddbookfindbookLendbookReturnbookBookcountexit menudelbookDeleteBTreeRecDeleteSearchNodeSuccessorRemoveRestoreMoveLeftCombineMoveRight2.2 设计表示（1）函数调用关系图（2）函数接口规格说明int Search(BTNode *p,KeyType k)Result SearchBTree(BTNode *&t,KeyType k)void Insert(BTNode *&q,int i,KeyType x,BTNode *&ap)void Split(BTNode *&q,BTNode *&ap)void NewRoot(BTNode *&t,BTNode *p,KeyType x,BTNode *ap)void InsertBTree(BTNode *&t, KeyType k, BTNode *&q, int i)void Remove(BTNode *p,int i)void Successor(BTNode *p,int i)void MoveLeft(BTNode *p,int i)void MoveRight(BTNode *p,int i)void Combine(BTNode *p,int i)void Restore(BTNode *p,int i)int SearchNode(KeyType k,BTNode *p,int &i)int RecDelete(KeyType k,BTNode *p)void DeleteBTree(KeyType k,BTNode *root)void addbook()/添加书void lendbook(int booknumber)/借书void findbook()/查找书void returnbook()/还书void delbook()/删除void bookcount()/显示书的状况void menu()/主界面int main()/主函数2.3 详细设计各个功能模块主要算法的伪代码实现 添加图书模块 printf(请输入书号)scanf（书号 ） If SearchBTree(书号)=true printf(此书已存在!)elseprintf(请输入书名)scanf(书名)printf(请输入作者)scanf(作者)printf(请输入现存量)scanf(现存量)printf(请输入总量)scanf(总量)InsertBTree(书号，书名, 作者, 现存量, 总量)printf(输入 1 继续添加, 0 返回主界面)scanf(1 or 0) return 查找图书模块printf(请输入书号)scanf（书号 ）if SearchBTree(书号)=true printf(成功找到!)printf(书号,书名,作者,现存量,总量) if 总量大于零 printf(你想借这本书吗?输入 1 借, 0 退出)scanf(1 or 0)if(1) 总量减一elseprintf(此书不存)return 借阅图书模块printf(请输入书号)scanf(书号)if SearchBTree(书号)=true and 总量大于零printf(操作成功!)总量减一elseprintf(操作失败!书已经被借出或不存在这本书) return 归还图书模块printf(请输入书号)scanf(书号)if SearchBTree(书号)=true printf(操作成功!) 总量加一else printf(操作失败!n);return 删除图书记录模块printf(请输入书号)scanf(书号)if SearchBTree(书号)=trueprintf(书的具体信息:书号,书名,作者,现存量,总量) printf(输入 1 删除这本书) scanf() if(1) 书号=0 printf(删除成功!) else printf(操作失败!不存在这本书)return 显示图书状态模块int i;for(i=1;i1000;i+)if(总量!=0)printf(书号, 书名, 作者, 现存量, 总量)3调试分析（1）本程序最大的问题就是B-树的基本算法的实现，此处难点在于B_树的结点的分裂，当插入结点时，判断结点中关键字的个数是否大于规定的个数，如果大于则要对此结点进行分裂，在分裂时，要改变孩子结点的parent指针，并且把分裂出的关键字放到该关键字的parent结点中，然后继续判断是否要分裂，一直到符合要求。在进行检测时，出现了分裂时的错误，就是没有考虑到在分裂结点时，该结点的孩子结点的parent指针的改变，我参考了课本和老师的课件，并与和其他同学讨论后终于通过调试和改正，测试正确。另外，在老师您在验收我的程序时，指出了我的程序的两个不足之处，一是没有按要求以凹入表的形式显示，二是在删除图书记录后图书记录并没有消失，而仅仅是图书号变成了1，因此您只给我的这个程序打了个B，我当时心里真的很伤心。这两个不足之处我在您验收之后很快就改过来了，因为原因很简单：第一个不足之处产生的原因是我没注意到题目有这个要求，其实只要在输出语句中的书名前面加nt就行了；第二个不足之处产生的原因是在删除图书记录时应将要删除的图书号置为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错误原因：没有注意审题，因此未在输出语句中的书号前加nt当前状态： 已改正测试用例2：测试输入：见截屏3、4测试目的：是否能按要求以凹入表的形式显示正确输出：见截屏3实际输出：见截屏4错误原因：编程时粗心，错误的将应删除的书号置为了1.当前状态： 已改正截屏1截屏2截屏3 截屏4 6源程序清单#include #include#include #include#include #define MAXM 10 /*定义B-树的最大的阶数*/typedef int KeyType; /*KeyType为关键字类型*/struct BookInfo /书结构体int number;char name30;char author30;int extant;int total;typedef struct node /B-树结点定义 int keynum; /*结点当前拥有的关键字的个数*/ KeyType keyMAXM; /*key1.keynum存放关键字,key0不用*/ struct node *parent; /*双亲结点指针*/ struct node *ptrMAXM; /*孩子结点指针数组ptr0.keynum*/ BTNode;BTNode *bookp=NULL;typedef struct /*B-树的查找结果类型*/BTNode *pt; /*指向找到的结点*/ int i; /*1.m,在结点中的关键字序号*/ int tag; /*1:查找成功,O:查找失败*/ Result;int m; /*m阶B-树,为全局变量*/int Max; /*m阶B-树中每个结点的至多关键字个数,Max=m-1*/int Min; /*m阶B-树中非叶子结点的至少关键字个数,Min=(m-1)/2*/Result s;int Search(BTNode *p,KeyType k) /在p-key1.keynum中查找关键字序号i,使得p-keyi=kkeyi+1 int i; for(i=0;ikeynum & p-keyi+1key1.keynum中查找i,使得p-keyi=kkeyi+1*/ if (i0 & p-keyi=k) /*找到待查关键字*/ found=1; else q=p;/双亲结点q指向p p=p-ptri;/p变成它原来的孩子结点 r.i=i;/关键字序号iif (found=1) /*查找成功*/ r.pt=p;r.tag=1;/pt指向找到的结点p,tag置为1else /*查找不成功,返回K的插入位置信息*/ r.pt=q;r.tag=0;/pt指向q,tag置为0return r; /*返回k的位置(或插入位置)*/void Insert(BTNode *&q,int i,KeyType x,BTNode *&ap) /若有位置,将x插入到q-keyi+1,ap插到q-ptri+1中int j;for(j=q-keynum;ji;j-) /*空出一个位置*/ q-keyj+1=q-keyj; q-ptrj+1=q-ptrj;q-keyi+1=x;q-ptri+1=ap;if (ap!=NULL) ap-parent=q; q-keynum+;void Split(BTNode *&q,BTNode *&ap) /无空位置则分裂.将结点q分裂成两个结点,前一半保留,后一半移入新生结点apint i,s=(m+1)/2;/分裂的位置ap=(BTNode *)malloc(sizeof(BTNode); /*生成新结点*ap*/ap-ptr0=q-ptrs; /*后一半移入ap*/for (i=s+1;ikeyi-s=q-keyi; ap-ptri-s=q-ptri; if (ap-ptri-s!=NULL) ap-ptri-s-parent=ap; ap-keynum=q-keynum-s; ap-parent=q-parent; for (i=0;ikeynum-s;i+) /*修改指向双亲结点的指针*/if (ap-ptri!=NULL) ap-ptri-parent = ap;q-keynum=s-1; /*q的前一半保留,修改keynum*/void NewRoot(BTNode *&t,BTNode *p,KeyType x,BTNode *ap)/生成含信息(T,x,ap)的新的根结点*t, / 原t和ap为子树指针t=(BTNode *)malloc(sizeof(BTNode);t-keynum=1;t-ptr0=p;t-ptr1=ap;t-key1=x;if (p!=NULL) p-parent=t; if (ap!=NULL) ap-parent=t;t-parent=NULL;void InsertBTree(BTNode *&t, KeyType k, BTNode *&q, int i) /*最终的插入函数.在m阶t树t上结点*q的keyi与keyi+1之间插入关键字k。若引起 结点过大,则沿双亲链进行必要的结点分裂调整,使t仍是m阶t树。*/BTNode *ap;int finished,needNewRoot,s;KeyType x;if (q=NULL) /*t是空树(参数q初值为NULL)*/ NewRoot(t,NULL,k,NULL); /生成仅含关键字k的根结点*telse x=k;ap=NULL;finished=needNewRoot=0; while (needNewRoot=0 & finished=0) Insert(q,i,x,ap); /*将x和ap分别插入到q-keyi+1和q-ptri+1*/ if (q-keynumkeys+1.m,q-ptrs.m和q-recptrs+1.m移入新结点*ap*/ s=(m+1)/2; Split(q,ap); x=q-keys; if (q-parent) /*在双亲结点*q中查找x的插入位置*/ q=q-parent; i=Search(q, x); else needNewRoot=1; if (needNewRoot=1) /*根结点已分裂为结点*q和*ap*/ NewRoot(t,q,x,ap); /*生成新根结点*t,q和ap为子树指针*/void Remove(BTNode *p,int i)/*从*p结点删除keyi和它的孩子指针ptri*/int j;for (j=i+1;jkeynum;j+) /*前移删除keyi和ptri*/ p-keyj-1=p-keyj; p-ptrj-1=p-ptrj;p-keynum-;void Successor(BTNode *p,int i)/*查找被删关键字p-keyi(在非叶子结点中)的替代叶子结点*/BTNode *q;for (q=p-ptri;q-ptr0!=NULL;q=q-ptr0);p-keyi=q-key1; /*复制关键字值*/void MoveRight(BTNode *p,int i)/*把一个关键字移动到右兄弟中*/int c;BTNode *t=p-ptri;for (c=t-keynum;c0;c-) /*将右兄弟中所有关键字左移一位*/ t-keyc+1=t-keyc; t-ptrc+1=t-ptrc;t-ptr1=t-ptr0; /*从双亲结点移动关键字到右兄弟中*/t-keynum+;t-key1=p-keyi;t=p-ptri-1; /*将左兄弟中最后一个关键字移动到双亲结点中*/p-keyi=t-keyt-keynum;p-ptri-ptr0=t-ptrt-keynum;t-keynum-;void MoveLeft(BTNode *p,int i)/*把一个关键字移动到左兄弟中*/int c;BTNode *t;t=p-ptri-1; /*把双亲结点中的关键字移动到左兄弟中*/t-keynum+;t-keyt-keynum=p-keyi;t-ptrt-keynum=p-ptri-ptr0;t=p-ptri; /*把右兄弟中的关键字移动到双亲兄弟中*/p-keyi=t-key1;p-ptr0=t-ptr1;t-keynum-;for (c=1;ckeynum;c+) /*将右兄弟中所有关键字移动一位*/ t-keyc=t-keyc+1; t-ptrc=t-ptrc+1;void Combine(BTNode *p,int i)/*将三个结点合并到一个结点中*/int c;BTNode *q=p-ptri; /*指向右结点,它将被置空和删除*/BTNode *l=p-ptri-1;l-keynum+; /*l指向左结点*/l-keyl-keynum=p-keyi;l-ptrl-keynum=q-ptr0;for (c=1;ckeynum;c+) /*插入右结点中的所有关键字*/ l-keynum+; l-keyl-keynum=q-keyc; l-ptrl-keynum=q-ptrc;for (c=i;ckeynum;c+) /*删除父结点所有的关键字*/ p-keyc=p-keyc+1; p-ptrc=p-ptrc+1;p-keynum-;free(q); /*释放空右结点的空间*/void Restore(BTNode *p,int i)/*关键字删除后,调整B-树,找到一个关键字将其插入到p-ptri中*/if (i=0) /*为最左边关键字的情况*/ if (p-ptr1-keynumMin) MoveLeft(p,1); else Combine(p,1);else if (i=p-keynum) /*为最右边关键字的情况*/ if (p-ptri-1-keynumMin) MoveRight(p,i); else Combine(p,i);else if (p-ptri-1-keynumMin) /*为其他情况*/ MoveRight(p,i);else if (p-ptri+1-keynumMin) MoveLeft(p,i+1);else Combine(p,i);int SearchNode(KeyType k,BTNode *p,int &i)/*在结点p中找关键字为k的位置i,成功时返回1,否则返回0*/if (kkey1) /*k小于*p结点的最小关键字时返回0*/ i=0; return 0;else /*在*p结点中查找*/ i=p-keynum; while (kkeyi & i1) i-; return(k=p-keyi);int RecDelete(KeyType k,BTNode *p)/*查找并删除关键字k*/int i;int found;if (p=NULL) return 0;else if (found=SearchNode(k,p,i)=1) /*查找关键字k*/ if (p-ptri-1!=NULL) /*若为非叶子结点*/ Successor(p,i); /*由其后继代替它*/ RecDelete(p-keyi,p-ptri); /*p-keyi在叶子结点中*/ else Remove(p,i); /*从*p结点中位置i处删除关键字*/ else found=RecDelete(k,p-ptri); /*沿孩子结点递归查找并删除关键字k*/ if (p-ptri!=NULL) if (p-ptri-keynumkeynum=0) p=root; root=root-ptr0; free(p);struct BookInfo book1000;void addbook()/添加书int n=1,num;while(n)printf(书号:);scanf(%d,&num); s=SearchBTree(bookp,num);if(s.tag=1)printf(此书已存在!);elsebooknum.number=num;printf(n书名:);scanf(%s,&booknum.name);printf(n作者:);scanf(%s,&booknum.author);printf(n现存量:);scanf(%d,&booknum.extant);printf(n总量:);scanf(%d,&booknum.total);InsertBTree(bookp,booknum.number,s.pt,s.i);printf(n输入 1 继续添加, 0 返回主界面);scanf(%d,&n);void lendbook(int booknumber)/借书int num;if(booknumber=-1)printf(请输入书号:);scanf(%d,&num);if(booknum.extant)printf(操作成功!);booknum.extant-;elseprintf(操作失败!书已经被借出或不存在这本书.);elseprintf(操作成功!n);bookbooknumber.extant-;return;void findbook()/查找书int num,select;printf(请输入书号:);scanf(%d,&num);s=SearchBTree(bookp,num);if(s.tag)printf(成功找到!.n);printf(书号:%d,nt书名:%s,作者:%s,现存量:%d,总量:%dn,booknum.number,booknum.name,booknum.author,booknum.extant,booknum.total);elseprintf(此书不存在.);if(booknum.extant)printf(你想借这本书吗?输入 1 借, 0 退出.n);scanf(%d,&select);if(select)lendbook(num);else return;elsereturn;void returnbook()/还书int num;printf(请输入书号:);scanf(%d,&num);if(booknum.number!=-1&booknum.extantbooknum.total)booknum.extant+;printf(操作成功!n);else printf(操作失败!n);return;void delbook()/删除int num;int confirm;printf(请输入书号:);scanf(%d,&num);printf(书的具体信息:n书号:%d,nt书名:%s,作者%s,现存量%d,总量%dn,booknum.number,booknum.name,booknum.author,booknum.extant,booknum.total);printf(输入 1 删除这本书:);scanf(%d,&confirm);if(confirm=1)DeleteBTree(booknum.number,bookp);booknum.number=0;printf(删除成功!);return;void bookcount()/显示书的状况int i;for(i=1;i1000;i+)if(booki.number!=0)printf(书号:%3d, nt书名:%7s, 作者:%7s, 现存量:%5d, 总量:%5dn,booki.number,booki.name,booki.author,booki.extant,booki.total);void menu()/主界面printf(ntt操作选单n); printf(t1 新添书籍nt2 查找图书n); printf(t3 借阅图书n); printf(t4 归还图书nt5 图书状态n); printf(t6 删除图书记录n); printf(t7 退出n); switch(getch() case 1 : addbook() ;break; case 2 : findbook() ;break; case 3 : lendbook(-1) ;break; case 4 : returnbook();break; case 5 : bookcount() ;break; case 6 : delbook() ;break; case 7 : exit(0) ; int main()/主函数int j,n=20;m=4; Max=m-1;Min=(m-1)/2;for (j=0;j1000;j+) /*创建一棵4阶B-树t*/ s=SearchBTree(bookp,bookj.number); if (s.tag=0&bookj.number!=-1)InsertBTree(bookp,bookj.number,s.pt,s.i); while(1)menu();return 0;