西文图书管理系统.docx

《西文图书管理系统.docx》由会员分享，可在线阅读，更多相关《西文图书管理系统.docx（84页珍藏版）》请在三一文库上搜索。

1、西文图书管理系统9西文图书管理系统图书管理基本业务活动包括：对一本书的采 编入库、清除库存、借阅和归还等等。试设计一 个图书管理系统，将上述业务活动借助于计算机 系统完成。要求：（1） 每种书的登记内容至少包括书号、书 名、著者、现存量和总库存量等五项。（2） 作为演示系统，不必使用文件，全部 数据可以都在内存存放。要用 B-树（4 阶树）对 书号建立索引，以获得高效率。（3） 系统应有以下功能：采编入库、清除库存、借阅、归还、显示（以 凹入表的形式显示）等。1需求分析设计一个西文图书管理系统 , 将图书管理 基本业务活动如对一本书的采编入库、清除库 存、借阅和归还等等借助于计算机系统完成，该

2、 图书管理系统应有以下功能：采编入库、清除库 存、借阅、归还、显示等。要求用 B-树（4 阶树） 对书号建立索引，以获得高效率，输出以凹入表的形式显示。 2设计2.1 设计思想（1）数据结构设计逻辑结构设计：树形结构（ B-树）存储结构设计：链式存储结构选择 B-树这种数据结构的原因：与二叉树相比，B-树是一种平衡多叉排序 树。平衡是指所有叶结点都在同一层上，从而可 避免出现二叉排序树那样的分支退化现象；多叉 是指多于二叉，多于二叉的排序树将降低二叉树 高度，从而减少查找数据元素时的比较次数。由 于限制了除根结点以外的非叶子结点，至少含有 M/2 个儿子，确保了结点的至少利用率，其最底 搜索性

3、能为：其中，M 为设定的非叶子结点最多子树个数，N 为关键字总数；所以 B-树的性能总是等价于二分查找（与 M 值无关），也就没有 B 树平衡 的问题；因此，B-树是一种动态查找效率较二叉 排序树更高的树形结构。（2）算法设计算法设计的总体设计思路为：首先创建一颗 4 阶 B-树，然后在此基础上设计添加图书、查找 图书、借阅图书、归还图书、显示图书状态、删 除图书记录、退出七个模块，最后主函数再用一 个 switch 选择语句来调用各个模块。各个模块 要完成的主要功能分别为：添加图书：可以添加图书记录，按提示依次输入书号、书名、作者、现存量、总量，会提示是否继续添加。查找图书：可根据输入的书号

4、进行查询，成功找 到后会提示是否想借这本书，输入 1 为借书，输入 0 为退出。借阅图书：可根据提示输入相应的书号进行借 书。归还图书：可根据提示输入相应的书号归还图 书。显示图书状态：可显示图书管理系统里的所有图 书状态。删除图书记录：可根据提示输入相应的书号删除 图书记录。主程序的流程图如下：开输 入判2.2 设计表示（1）函数调用关系图addInsefindSeaLendRet Bo delburn okDeletexrch RemoInRecDRestSpSearcNewRMoveCombinMoveSucc（2）函数接口规格说明int Search(BTNode *p,KeyType

5、 k)Result SearchBTree(BTNode *&t,KeyType k)void Insert(BTNode *&q,int i,KeyTypex,BTNode *&ap)void Split(BTNode *&q,BTNode *&ap)void NewRoot(BTNode *&t,BTNode *p,KeyTypex,BTNode *ap)void InsertBTree(BTNode *&t, KeyType k, BTNode *&q, int i)void Remove(BTNode *p,int i)void Successor(BTNode *p,int i)vo

6、id 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 findboo

7、k()/ 查找书void returnbook()/ 还书void delbook()/ 删除void bookcount()/ 显示书的状况 void menu()/ 主界面int main()/ 主函数2.3 详细设计各个功能模块主要算法的伪代码实现 添加图书模块printf( 请输入书号)scanf （书号 ）If SearchBTree( 书号)=trueprintf( 此书已存在!)elseprintf( 请输入书名 )scanf( 书名)printf( 请输入作者 )scanf( 作者)printf( 请输入现存量)scanf( 现存量)printf( 请输入总量 )scanf(

8、总量)InsertBTree( 书号，书名, 作者, 现存量, 总量)printf( 输入 1 继续添加, 0 返回主界面)scanf(1 or 0)return查找图书模块printf( 请输入书号 )scanf （书号 ）if SearchBTree( 书号)=trueprintf( 成功找到 !)printf( 书号 ,书名,作者,现存量,总量)if 总量大于零printf( 你想借这本书吗?输入 1 借, 0 退出) scanf(1 or 0)if(1) 总量减一elseprintf( 此书不存 )return借阅图书模块printf( 请输入书号 )scanf( 书号)if Sear

9、chBTree( 书号)=true and 总量大于零printf( 操作成功!)总量减一elseprintf( 操作失败 !书已经被借出或不存在这本书) return归还图书模块printf( 请输入书号 )scanf( 书号)if SearchBTree( 书号)=trueprintf( 操作成功!)总量加一elseprintf( 操作失败!n);return删除图书记录模块printf( 请输入书号 )scanf( 书号)if SearchBTree( 书号)=trueprintf( 书的具体信息:书号,书名,作者,现存量,总量 ) printf( 输入 1 删除这本书 )scanf()

10、if(1)书号=0printf( 删除成功!)else printf( 操作失败 !不存在这本书 ) return显示图书状态模块 int i;for(i=1;i1000;i+)if( 总量!=0)printf( 书号,书名, 作者,现存量,总量)3调试分析（1）本程序最大的问题就是 B-树的基本算 法的实现，此处难点在于 B_树的结点的分裂， 当插入结点时，判断结点中关键字的个数是否大 于规定的个数，如果大于则要对此结点进行分 裂，在分裂时，要改变孩子结点的 parent 指针， 并且把分裂出的关键字放到该关键字的 parent 结点中，然后继续判断是否要分裂，一直到符合 要求。在进行检测时

11、，出现了分裂时的错误，就 是没有考虑到在分裂结点时，该结点的孩子结点 的 parent 指针的改变，我参考了课本和老师的 课件，并与和其他同学讨论后终于通过调试和改 正，测试正确。另外，在老师您在验收我的程序 时，指出了我的程序的两个不足之处，一是没有按要求以凹入表的形式显示，二是在删除图书记 录后图书记录并没有消失，而仅仅是图书号变成 了1，因此您只给我的这个程序打了个 B，我 当时心里真的很伤心。这两个不足之处我在您验 收之后很快就改过来了，因为原因很简单：第一 个不足之处产生的原因是我没注意到题目有这 个要求，其实只要在输出语句中的书名前面加 nt 就行了；第二个不足之处产生的原因是在

12、删除图书记录时应将要删除的图书号置为 0，而 我却将它置为了 1.本来我当时是想找老师您 再验收一次把成绩改高一点的，但由于当时验收 的人太多了，就没再去麻烦您。（2）算法的时间空间复杂度分析由于 B-树查找的时间复杂度为 O（Log2N ）， 而程序中多次用到了一重循环，其时间复杂度为 O（n）,因此程序的时间复杂度为 O（n），空间 复杂度也为 O（n）.（3）可改进内容：1、利用 MFC 做一个界面，使 界面更加美观；2、可尝试用 B+树代替 B_树，更 容易应用于文件系统 3、删除图书记录的时候必 须先收回所有的书，即要保证现存量和总量相等后方可删除；4、采用文件的形式，可以保存图 书

13、状态。4用户手册本程序在 VC+6.0 环境下运行，按照菜单提示的 要求输入即可。5测试数据及测试结果测试用例 1：测试输入：见截屏 1、2测试目的：是否能按要求以凹入表的形式显示 正确输出：见截屏 1实际输出：见截屏 2错误原因：没有注意审题，因此未在输出语句中 的书号前加nt当前状态： 已改正测试用例 2：测试输入：见截屏 3、4测试目的：是否能按要求以凹入表的形式显示 正确输出：见截屏 3实际输出：见截屏 4错误原因：编程时粗心，错误的将应删除的书号 置为了1.当前状态： 已改正截屏 1截屏 2截屏 3截屏 46源程序清单#include #include#include #includ

14、e#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; /* 双亲结点指针

15、*/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=

16、(m-1)/2*/Result s;int Search(BTNode *p,KeyType k) /在 p-key1.keynum 中查找关键字序号 i, 使得 p-keyi=kkeyi+1int i;for(i=0;ikeynum &p-keyi+1key1.keynum 中查找 i,使得 p-keyi=kkeyi+1*/if (i0 & p-keyi=k) /*找到待查关键 字*/found=1;elseq=p;/ 双亲结点 q 指向 p p=p-ptri;/p 变成它原来的孩子结点r.i=i;/ 关键字序号 iif (found=1) /* 查找成功*/r.pt=p;r.tag=1;/

17、pt 指向找到的结点 p,tag 置为 1else /* 查找不成功,返回 K 的插入位置 信息*/r.pt=q;r.tag=0;/pt 指向 q,tag 置为 0 return r; /* 返回 k 的位置(或插入位 置)*/void Insert(BTNode *&q,int i,KeyTypex,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;i

18、f (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-

19、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=

20、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)

21、 /*t 是空树(参数 q 初值为 NULL)*/NewRoot(t,NULL,k,NULL); / 生成仅含 关键字 k 的根结点*telsex=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)

22、/* 在双亲结点*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-k

23、eynum-;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

24、-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-

25、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-ke

26、yi;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) /*

27、为最左边关键字的情况 */ if (p-ptr1-keynumMin)MoveLeft(p,1);elseCombine(p,1);else if (i=p-keynum) /* 为最右边关键 字的情况*/if (p-ptri-1-keynumMin)MoveRight(p,i);elseCombine(p,i);else if (p-ptri-1-keynumMin) /*为其他 情况*/MoveRight(p,i);else if (p-ptri+1-keynumMin)MoveLeft(p,i+1);elseCombine(p,i);int SearchNode(KeyType k,BT

28、Node *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;elseif (found=SearchNode(k,p,i)=1) /* 查找关键字

29、 k*/if (p-ptri-1!=NULL) /* 若为非叶 子结点*/Successor(p,i); /* 由其后继代替 它*/RecDelete(p-keyi,p-ptri); /*p-keyi 在叶子结点中*/elseRemove(p,i); /* 从*p 结点中位置 i 处删除关键字*/elsefound=RecDelete(k,p-ptri); /* 沿 孩子结点递归查找并删除关键字 k*/if (p-ptri!=NULL)if (p-ptri-keynumkeynum=0)p=root;root=root-ptr0;free(p);struct BookInfo book1000

30、;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,&booknu

31、m.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);bookbooknum

32、ber.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)print

33、f( 你想借这本书吗 ?输入 1 借, 0 退出.n);scanf(%d,&select);if(select)lendbook(num);elsereturn;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 confir

34、m;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(

35、)/ 显示书的状况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