西文图书管理系统(20210224131127)

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

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

3、不可耻。阿卜日法拉兹=Olog 2(Ff- 0 x log 寻(岸订)= Onog2(f)xOlog(|)= C*log2()xaog 寻 N _1”=opog 2 AT-log2(妁= tDog2Ar-oc= O2N其中，M为设定的非叶子结点最多子树个数，N为关键字总数；所以B拥的性能总是等价于二分查找(与 M值无关)，也就没有 B树平衡的问题；因此，B揺是一种动态查找 效率较二叉排序树更高的树形结构。(2 )算法设计算法设计的总体设计思路为：首先创建一颗4阶B揺，然后在此基础上设计添加图书、查找图书、借阅图书、归还图书、显示图书状态、删除图书记录、退出七个模块，最后主函数再用一个switc

4、h选择语句来调用各个模块。各个模块要完成的主要功能分别为：添加图书：可以添加图书记录，按提示依次输入书号、书名、作者、现存量、总量，会提示是否继续添加。查找图书：可根据输入的书号进行查询， 成功找到后会提示是否想借这本书， 输入1为借书,输入0为退出。借阅图书：可根据提示输入相应的书号进行借书。归还图书：可根据提示输入相应的书号归还图书。显示图书状态：可显示图书管理系统里的所有图书状态。删除图书记录：可根据提示输入相应的书号删除图书记录。主程序的流程图如下：书名判断(2) 函数接口规格说明int Search(BTNode *p,KeyType k)Result SearchBTree(BTN

5、ode *&t,KeyType k)void In sert(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 In sertBTree(BTNode *&t, KeyType k, BTNode *&q, i nt i)void Remove(BTNode *p,i nt i)void Successor(BTNode *p,i nt i)void MoveLeft(BTNod

6、e *p,i nt i)void MoveRight(BTNode *p,i nt i)void Combine(BTNode *p,int i)void Restore(BTNode *p,i nt i)int SearchNode(KeyType k,BTNode *p,i nt &i)int RecDelete(KeyType k,BTNode *p)void DeleteBTree(KeyType k,BTNode *root)void addbook() 添加书void len dbook(i nt book nu mber)/ 借书void findbook()/ 查找书void

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

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） 总量减一else printf（ 此书不存 ） return借阅图书模块print

9、f（ 请输入书号 ）阅读使人充实，会谈使人敏捷，写作使人精确。培根scanf（ 书号 ）if SearchBTree（ 书号 ）=true and 总量大于零printf（ 操作成功 !）总量减一elseprintf（ 操作失败 ! 书已经被借出或不存在这本书 ）return归还图书模块printf（ 请输入书号 ）scanf（ 书号 ）if SearchBTree（ 书号 ）=trueprintf（ 操作成功 !）总量加一elseprintf（ 操作失败 !n）;return删除图书记录模块printf（ 请输入书号 ）scanf（ 书号 ）if SearchBTree（ 书号 ）=true

10、printf（ 书的具体信息 :书号,书名 ,作者,现存量 ,总量）printf（ 输入 1 删除这本书 ）scanf（）if（1）书号=0printf（ 删除成功 !）else printf（ 操作失败 ! 不存在这本书 ）return显示图书状态模块int i;for（i=1;i4 54 54 5量量存存现现3 43 43 413单选作 书图图图状图，驀阅还书12 3 4 5 6 7 丿1 21 21 2 号号单选 录 记 书图图图状图 绸阅还书逼ri&i-OTT诜一作 舊WW书 书图图图状图 养阅还书掘12 3 4 5 6 7555666777总量: 总量: 总量:444,555,666

11、,333,现存量:444,现存量:555,现存量:333书书Mn-4TTT选作心书 书图图图状S 绸阅还书掘 f 息as 书芟人是:2朗号-xs选作 书图图图状图绸阅还书；555777总量:总量:444,6阪1成入除*W,|12 3 4 5 6 7 1 31 31 3 号号y3 -选 录 记 书图图图状图 绸阅还书除岀12 3 4 5 6 7阅读使人充实，会谈使人敏捷，写作使人精确。培根截屏4学冋是异常珍贵的东西，从任何源泉吸收都不可耻。阿卜日法拉兹豐WW书 书图图图状图 绸阅还书矍555666777555666777总量:总量:总量:总量:总量:总量:444,555,666,444,555,

12、666,333,现存量:444,现存量:555,现存量:单选 作.书图图图状图1 2 3 4 5 6 7 P-FP ff12 312 312 3书书书绸阅还书雷22:息口看， 书休22 人具:212 3 4 5 6 7单选作 书图图图状图 绸阅还书陞 uffil12 3 4 5 6 7 Fp1131 一 31 3书书书单选作书图图图状图發阅还书烬12 3 4 5 6 7阅读使人充实，会谈使人敏捷，写作使人精确。培根学冋是异常珍贵的东西，从任何源泉吸收都不可耻。阿卜日法拉兹6源程序清单#include #include#include #include #include #define MAXM

13、 10/*typedef int KeyType;定义 B- 树的最大的阶数 */*KeyType 为关键字类型 */struct BookInfo /int number; char name30; char author30;int extant;int total;书结构体typedef struct node /B-int keynum;KeyType keyMAXM; struct node *parent; /* struct node *ptrMAXM;typedef struct /*B-树的查找结果类型 */树结点定义/* 结点当前拥有的关键字的个数 */*key1.keyn

14、um存放关键字 ,key0 不用 */双亲结点指针 */* 孩子结点指针数组 ptr0.keynum*/ BTNode;BTNode *bookp=NULL;BTNode *pt; /* int i;/*1.m,int tag; /*1: Result;指向找到的结点 */ 在结点中的关键字序号 */ 查找成功 ,O: 查找失败 */int m; /*m阶 B- 树 , 为全局变量 */int Max; /*mint Min; /*m阶 B- 树中每个结点的至多关键字个数 ,Max=m-1*/阶 B- 树中非叶子结点的至少关键字个数 ,Min=(m-1)/2*/Result s;int Sea

15、rch(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变成它原来的孩子结点i查找成功 */q=p;/ 双亲结点 p=p-ptri;/pr.i=i;/ 关键字序号 if (found=1) /*r.pt=p;r.tag=1;/pt指向找到的结点 p,tag 置为 1else

16、/*查找不成功，返回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-ke

17、ynum+;void Split(BTNode *&q,BTNode *&ap) / 无空位置则分裂 . 将结点 q 分裂成两个结点 , 前一半保留 , 后一 int 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=

18、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,/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!=

19、NULL) ap-parent=t;t-parent=NULL;void InsertBTree(BTNode *&t, KeyType k, BTNode *&q, int i)半移入新生结点 ap生成含信息 (T,x,ap) 的新 原 t 和 ap 为子树指针之间插入关键字k。若引 /* 最终的插入函数 . 在 m 阶 t 树 t 上结点 *q 的 keyi 与 keyi+1 起结点过大，则沿双亲链进行必要的结点分裂调整，使t仍是m阶t树。*/BTNode *ap;int finished，needNewRoot，s;KeyType x;if (q=NULL) /*t是空树 (参数 q 初

20、值为 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 *ap*/和 q-recptrs+1.m移入新结点s=(m+1)/2;Split(q，ap);x=q-keys;if (q-parent) /*q=q-parent;i=Se

21、arch(q， x);else needNewRoot=1;if (needNewRoot=1) /*NewRoot(t，q，x，ap); /*在双亲结点 *q 中查找 x 的插入位置 */根结点已分裂为结点*q和*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 Succ

22、essor(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; /*

23、 从双亲结点移动关键字到右兄弟中 */ 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

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

25、eyi;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-ptriif (i=0)/*为最左

26、边关键字的情况 */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,BTNode

27、*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) /*查找关键字 k*/if (p-ptri-

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

29、=1,num;while(n)printf( 书号 :); scanf(%d,&num);s=SearchBTree(bookp,num);if(s.tag=1)printf( 此书已存在 !);elsebooknum.number=num;printf(n书名 :);scanf(%s,&);printf(n作者 :);scanf(%s,&booknum.author);printf(n现存量 :);scanf(%d,&booknum.extant);printf(n总量 :);scanf(%d,&booknum.total);InsertBTree(bookp,boo

30、knum.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-; else printf( 操作失败 ! 书已经被借出或不存在这本书 .);elseprintf( 操作成功 !n); bookbooknumber.extant-;retu

31、rn;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,book nu m. nu mber,book nu m. name,book nu m.author,book nu m.exta nt,book num.total);elseprintf( 此书不存在 .);if(booknum.extant)printf( 你想借这本书吗 ?输入 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;vo