西文圖書管理系統(tǒng)

1、9西文圖書管理系統(tǒng)圖書管理基本業(yè)務(wù)活動包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計一個圖書管理系統(tǒng)，將上述業(yè)務(wù)活動借助于計算機(jī)系統(tǒng)完成。要求：（1）每種書的登記內(nèi)容至少包括書號、書名、著者、現(xiàn)存量和總庫存量等五項(xiàng)。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。要用B-樹（4階樹）對書號建立索引，以獲得高效率。（3）系統(tǒng)應(yīng)有以下功能：采編入庫、清除庫存、借閱、歸還、顯示（以凹入表的形式顯示）等。1需求分析設(shè)計一個西文圖書管理系統(tǒng), 將圖書管理基本業(yè)務(wù)活動如對一本書的采編入庫、清除庫存、借閱和歸還等等借助于計算機(jī)系統(tǒng)完成，該圖書管理系統(tǒng)應(yīng)有以下功能：采編入庫、清除庫存、

2、借閱、歸還、顯示等。要求用B-樹（4階樹）對書號建立索引，以獲得高效率，輸出以凹入表的形式顯示。2設(shè)計2.1 設(shè)計思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計邏輯結(jié)構(gòu)設(shè)計：樹形結(jié)構(gòu)（B-樹）存儲結(jié)構(gòu)設(shè)計：鏈?zhǔn)酱鎯Y(jié)構(gòu)選擇B-樹這種數(shù)據(jù)結(jié)構(gòu)的原因：與二叉樹相比，B-樹是一種平衡多叉排序樹。平衡是指所有葉結(jié)點(diǎn)都在同一層上，從而可避免出現(xiàn)二叉排序樹那樣的分支退化現(xiàn)象；多叉是指多于二叉，多于二叉的排序樹將降低二叉樹高度，從而減少查找數(shù)據(jù)元素時的比較次數(shù)。由于限制了除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)，至少含有M/2個兒子，確保了結(jié)點(diǎn)的至少利用率，其最底搜索性能為：其中，M為設(shè)定的非葉子結(jié)點(diǎn)最多子樹個數(shù)，N為關(guān)鍵字總數(shù)； &#

3、160;所以B-樹的性能總是等價于二分查找（與M值無關(guān)），也就沒有B樹平衡的問題；因此，B-樹是一種動態(tài)查找效率較二叉排序樹更高的樹形結(jié)構(gòu)。（2）算法設(shè)計算法設(shè)計的總體設(shè)計思路為：首先創(chuàng)建一顆4階B-樹，然后在此基礎(chǔ)上設(shè)計添加圖書、查找圖書、借閱圖書、歸還圖書、顯示圖書狀態(tài)、刪除圖書記錄、退出七個模塊，最后主函數(shù)再用一個switch選擇語句來調(diào)用各個模塊。各個模塊要完成的主要功能分別為：添加圖書：可以添加圖書記錄，按提示依次輸入書號、書名、作者、現(xiàn)存量、總量，會提示是否繼續(xù)添加。查找圖書：可根據(jù)輸入的書號進(jìn)行查詢，成功找到后會提示是否想借這本書，輸入1為借書，輸入0為退出。借閱圖書：可根據(jù)提示

4、輸入相應(yīng)的書號進(jìn)行借書。歸還圖書：可根據(jù)提示輸入相應(yīng)的書號歸還圖書。顯示圖書狀態(tài)：可顯示圖書管理系統(tǒng)里的所有圖書狀態(tài)。刪除圖書記錄：可根據(jù)提示輸入相應(yīng)的書號刪除圖書記錄。主程序的流程圖如下：輸入i判斷i顯示圖書狀態(tài)刪除圖書記錄查找圖書借閱圖書讀取文件退出歸還圖書添加圖書作者總量現(xiàn)存量書號書名開始關(guān)閉 InsertBTreeInsertSplitNewRootSearchBTreeaddbookfindbookLendbookReturnbookBookcountexit menudelbookDeleteBTreeRecDeleteSearchNodeSuccessorRemoveRestor

5、eMoveLeftCombineMoveRight2.2 設(shè)計表示（1）函數(shù)調(diào)用關(guān)系圖（2）函數(shù)接口規(guī)格說明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 Insert

6、BTree(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

7、 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()/主函數(shù)2.3 詳細(xì)設(shè)計各個功能模塊主要算法的偽代碼實(shí)現(xiàn)Ø 添加圖書模塊 printf(請輸入書號)scanf（書號 ） If SearchBTree(書號)=true pri

8、ntf(此書已存在!)elseprintf(請輸入書名)scanf(書名)printf(請輸入作者)scanf(作者)printf(請輸入現(xiàn)存量)scanf(現(xiàn)存量)printf(請輸入總量)scanf(總量)InsertBTree(書號，書名, 作者, 現(xiàn)存量, 總量)printf(輸入 1 繼續(xù)添加, 0 返回主界面)scanf(1 or 0) returnØ 查找圖書模塊printf(請輸入書號)scanf（書號 ）if SearchBTree(書號)=true printf(成功找到!)printf(書號,書名,作者,現(xiàn)存量,總量) if 總量大于零 printf(你想借這本

9、書嗎?輸入 1 借, 0 退出)scanf(1 or 0)if(1) 總量減一elseprintf(此書不存)returnØ 借閱圖書模塊printf(請輸入書號)scanf(書號)if SearchBTree(書號)=true and 總量大于零printf("操作成功!")總量減一elseprintf(操作失敗!書已經(jīng)被借出或不存在這本書) returnØ 歸還圖書模塊printf(請輸入書號)scanf(書號)if SearchBTree(書號)=true printf(操作成功!) 總量加一else printf("操作失敗!n&quo

10、t;);returnØ 刪除圖書記錄模塊printf(請輸入書號)scanf(書號)if SearchBTree(書號)=trueprintf(書的具體信息:書號,書名,作者,現(xiàn)存量,總量) printf(輸入 1 刪除這本書) scanf() if(1) 書號=0 printf(刪除成功!) else printf(操作失敗!不存在這本書)returnØ 顯示圖書狀態(tài)模塊int i;for(i=1;i<1000;i+)if(總量!=0)printf(書號, 書名, 作者, 現(xiàn)存量, 總量)3調(diào)試分析（1）本程序最大的問題就是B-樹的基本算法的實(shí)現(xiàn)，此處難點(diǎn)在于B_樹

11、的結(jié)點(diǎn)的分裂，當(dāng)插入結(jié)點(diǎn)時，判斷結(jié)點(diǎn)中關(guān)鍵字的個數(shù)是否大于規(guī)定的個數(shù)，如果大于則要對此結(jié)點(diǎn)進(jìn)行分裂，在分裂時，要改變孩子結(jié)點(diǎn)的parent指針，并且把分裂出的關(guān)鍵字放到該關(guān)鍵字的parent結(jié)點(diǎn)中，然后繼續(xù)判斷是否要分裂，一直到符合要求。在進(jìn)行檢測時，出現(xiàn)了分裂時的錯誤，就是沒有考慮到在分裂結(jié)點(diǎn)時，該結(jié)點(diǎn)的孩子結(jié)點(diǎn)的parent指針的改變，我參考了課本和老師的課件，并與和其他同學(xué)討論后終于通過調(diào)試和改正，測試正確。另外，在老師您在驗(yàn)收我的程序時，指出了我的程序的兩個不足之處，一是沒有按要求以凹入表的形式顯示，二是在刪除圖書記錄后圖書記錄并沒有消失，而僅僅是圖書號變成了1，因此您只給我的這個程序

12、打了個B，我當(dāng)時心里真的很傷心。這兩個不足之處我在您驗(yàn)收之后很快就改過來了，因?yàn)樵蚝芎唵危旱谝粋€不足之處產(chǎn)生的原因是我沒注意到題目有這個要求，其實(shí)只要在輸出語句中的書名前面加nt就行了；第二個不足之處產(chǎn)生的原因是在刪除圖書記錄時應(yīng)將要刪除的圖書號置為0，而我卻將它置為了1.本來我當(dāng)時是想找老師您再驗(yàn)收一次把成績改高一點(diǎn)的，但由于當(dāng)時驗(yàn)收的人太多了，就沒再去麻煩您。（2）算法的時間空間復(fù)雜度分析 由于B-樹查找的時間復(fù)雜度為O（Log2N），而程序中多次用到了一重循環(huán)，其時間復(fù)雜度為O（n）,因此程序的時間復(fù)雜度為O（n），空間復(fù)雜度也為O（n）.（3）可改進(jìn)內(nèi)容：1、利用MFC做一個界面，使

13、界面更加美觀；2、可嘗試用B+樹代替B_樹，更容易應(yīng)用于文件系統(tǒng)3、刪除圖書記錄的時候必須先收回所有的書，即要保證現(xiàn)存量和總量相等后方可刪除；4、采用文件的形式，可以保存圖書狀態(tài)。4用戶手冊本程序在VC+6.0環(huán)境下運(yùn)行，按照菜單提示的要求輸入即可。5測試數(shù)據(jù)及測試結(jié)果測試用例1：測試輸入：見截屏1、2測試目的：是否能按要求以凹入表的形式顯示正確輸出：見截屏1實(shí)際輸出：見截屏2錯誤原因：沒有注意審題，因此未在輸出語句中的書號前加nt當(dāng)前狀態(tài)： 已改正測試用例2：測試輸入：見截屏3、4測試目的：是否能按要求以凹入表的形式顯示正確輸出：見截屏3實(shí)際輸出：見截屏4錯誤原因：編程時粗心，錯誤的將應(yīng)刪除

14、的書號置為了1.當(dāng)前狀態(tài)： 已改正截屏1截屏2截屏3 截屏4 6源程序清單#include <stdio.h>#include<windows.h>#include <malloc.h>#include<string.h>#include<conio.h> #define MAXM 10 /*定義B-樹的最大的階數(shù)*/typedef int KeyType; /*KeyType為關(guān)鍵字類型*/struct BookInfo /書結(jié)構(gòu)體int number;char name30;char author30;int extant;int

15、 total;typedef struct node /B-樹結(jié)點(diǎn)定義 int keynum; /*結(jié)點(diǎn)當(dāng)前擁有的關(guān)鍵字的個數(shù)*/ KeyType keyMAXM; /*key1.keynum存放關(guān)鍵字,key0不用*/ struct node *parent; /*雙親結(jié)點(diǎn)指針*/ struct node *ptrMAXM; /*孩子結(jié)點(diǎn)指針數(shù)組ptr0.keynum*/ BTNode;BTNode *bookp=NULL;typedef struct /*B-樹的查找結(jié)果類型*/BTNode *pt; /*指向找到的結(jié)點(diǎn)*/ int i; /*1.m,在結(jié)點(diǎn)中的關(guān)鍵字序號*/ int ta

16、g; /*1:查找成功,O:查找失敗*/ Result;int m; /*m階B-樹,為全局變量*/int Max; /*m階B-樹中每個結(jié)點(diǎn)的至多關(guān)鍵字個數(shù),Max=m-1*/int Min; /*m階B-樹中非葉子結(jié)點(diǎn)的至少關(guān)鍵字個數(shù),Min=(m-1)/2*/Result s;int Search(BTNode *p,KeyType k) /在p->key1.keynum中查找關(guān)鍵字序號i,使得p->keyi<=k<p->keyi+1 int i; for(i=0;i<p->keynum && p->keyi+1<=k

17、;i+) ; return i;Result SearchBTree(BTNode *&t,KeyType k)/在m階t樹t上查找關(guān)鍵字k,返回查找結(jié)果(pt,i,tag)。若查找成功 /則tag=1,指針pt所指結(jié)點(diǎn)中第i個關(guān)鍵字等于k；否則tag=0,等于k的 /關(guān)鍵字應(yīng)插入在指針Pt所指結(jié)點(diǎn)中第i和第i+1個關(guān)鍵字之間BTNode *p=t,*q=NULL; /*初始化,t為待查樹,p指向待查結(jié)點(diǎn),q指向p的雙親*/int found=0,i=0;/found為標(biāo)志位Result r;/創(chuàng)建查找結(jié)果類型結(jié)構(gòu)體rwhile (p!=NULL && found=0)

18、 i=Search(p,k); /*在p->key1.keynum中查找i,使得p->keyi<=k<p->keyi+1*/ if (i>0 && p->keyi=k) /*找到待查關(guān)鍵字*/ found=1; else q=p;/雙親結(jié)點(diǎn)q指向p p=p->ptri;/p變成它原來的孩子結(jié)點(diǎn) r.i=i;/關(guān)鍵字序號iif (found=1) /*查找成功*/ r.pt=p;r.tag=1;/pt指向找到的結(jié)點(diǎn)p,tag置為1else /*查找不成功,返回K的插入位置信息*/ r.pt=q;r.tag=0;/pt指向q,tag置

19、為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;j>i;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

20、+;void Split(BTNode *&q,BTNode *&ap) /無空位置則分裂.將結(jié)點(diǎn)q分裂成兩個結(jié)點(diǎn),前一半保留,后一半移入新生結(jié)點(diǎn)apint i,s=(m+1)/2;/分裂的位置ap=(BTNode *)malloc(sizeof(BTNode); /*生成新結(jié)點(diǎn)*ap*/ap->ptr0=q->ptrs; /*后一半移入ap*/for (i=s+1;i<=m;i+) ap->keyi-s=q->keyi; ap->ptri-s=q->ptri; if (ap->ptri-s!=NULL) ap->ptri-

21、s->parent=ap; ap->keynum=q->keynum-s; ap->parent=q->parent; for (i=0;i<=q->keynum-s;i+) /*修改指向雙親結(jié)點(diǎn)的指針*/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)的新的根結(jié)點(diǎn)*t, / 原t

22、和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) /*最終的插入函數(shù).在m階t樹t上結(jié)點(diǎn)*q的keyi與keyi+1之間插入關(guān)鍵字k。若引起 結(jié)點(diǎn)過大,則沿雙親鏈進(jìn)行必

23、要的結(jié)點(diǎn)分裂調(diào)整,使t仍是m階t樹。*/BTNode *ap;int finished,needNewRoot,s;KeyType x;if (q=NULL) /*t是空樹(參數(shù)q初值為NULL)*/ NewRoot(t,NULL,k,NULL); /生成僅含關(guān)鍵字k的根結(jié)點(diǎn)*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->keynum&

24、lt;=Max) finished=1; /*無須分裂,插入完成*/ else /*分裂結(jié)點(diǎn)*q,將q->keys+1.m,q->ptrs.m和q->recptrs+1.m移入新結(jié)點(diǎn)*ap*/ s=(m+1)/2; Split(q,ap); x=q->keys; if (q->parent) /*在雙親結(jié)點(diǎn)*q中查找x的插入位置*/ q=q->parent; i=Search(q, x); else needNewRoot=1; if (needNewRoot=1) /*根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)*q和*ap*/ NewRoot(t,q,x,ap); /*生成新根結(jié)

25、點(diǎn)*t,q和ap為子樹指針*/void Remove(BTNode *p,int i)/*從*p結(jié)點(diǎn)刪除keyi和它的孩子指針ptri*/int j;for (j=i+1;j<=p->keynum;j+) /*前移刪除keyi和ptri*/ p->keyj-1=p->keyj; p->ptrj-1=p->ptrj;p->keynum-;void Successor(BTNode *p,int i)/*查找被刪關(guān)鍵字p->keyi(在非葉子結(jié)點(diǎn)中)的替代葉子結(jié)點(diǎn)*/BTNode *q;for (q=p->ptri;q->ptr0!=NU

26、LL;q=q->ptr0);p->keyi=q->key1; /*復(fù)制關(guān)鍵字值*/void MoveRight(BTNode *p,int i)/*把一個關(guān)鍵字移動到右兄弟中*/int c;BTNode *t=p->ptri;for (c=t->keynum;c>0;c-) /*將右兄弟中所有關(guān)鍵字左移一位*/ t->keyc+1=t->keyc; t->ptrc+1=t->ptrc;t->ptr1=t->ptr0; /*從雙親結(jié)點(diǎn)移動關(guān)鍵字到右兄弟中*/t->keynum+;t->key1=p->key

27、i;t=p->ptri-1; /*將左兄弟中最后一個關(guān)鍵字移動到雙親結(jié)點(diǎn)中*/p->keyi=t->keyt->keynum;p->ptri->ptr0=t->ptrt->keynum;t->keynum-;void MoveLeft(BTNode *p,int i)/*把一個關(guān)鍵字移動到左兄弟中*/int c;BTNode *t;t=p->ptri-1; /*把雙親結(jié)點(diǎn)中的關(guān)鍵字移動到左兄弟中*/t->keynum+;t->keyt->keynum=p->keyi;t->ptrt->keynum=

28、p->ptri->ptr0;t=p->ptri; /*把右兄弟中的關(guān)鍵字移動到雙親兄弟中*/p->keyi=t->key1;p->ptr0=t->ptr1;t->keynum-;for (c=1;c<=t->keynum;c+) /*將右兄弟中所有關(guān)鍵字移動一位*/ t->keyc=t->keyc+1; t->ptrc=t->ptrc+1;void Combine(BTNode *p,int i)/*將三個結(jié)點(diǎn)合并到一個結(jié)點(diǎn)中*/int c;BTNode *q=p->ptri; /*指向右結(jié)點(diǎn),它將被置空

29、和刪除*/BTNode *l=p->ptri-1;l->keynum+; /*l指向左結(jié)點(diǎn)*/l->keyl->keynum=p->keyi;l->ptrl->keynum=q->ptr0;for (c=1;c<=q->keynum;c+) /*插入右結(jié)點(diǎn)中的所有關(guān)鍵字*/ l->keynum+; l->keyl->keynum=q->keyc; l->ptrl->keynum=q->ptrc;for (c=i;c<p->keynum;c+) /*刪除父結(jié)點(diǎn)所有的關(guān)鍵字*/ p-&

30、gt;keyc=p->keyc+1; p->ptrc=p->ptrc+1;p->keynum-;free(q); /*釋放空右結(jié)點(diǎn)的空間*/void Restore(BTNode *p,int i)/*關(guān)鍵字刪除后,調(diào)整B-樹,找到一個關(guān)鍵字將其插入到p->ptri中*/if (i=0) /*為最左邊關(guān)鍵字的情況*/ if (p->ptr1->keynum>Min) MoveLeft(p,1); else Combine(p,1);else if (i=p->keynum) /*為最右邊關(guān)鍵字的情況*/ if (p->ptri-1-&

31、gt;keynum>Min) MoveRight(p,i); else Combine(p,i);else if (p->ptri-1->keynum>Min) /*為其他情況*/ MoveRight(p,i);else if (p->ptri+1->keynum>Min) MoveLeft(p,i+1);else Combine(p,i);int SearchNode(KeyType k,BTNode *p,int &i)/*在結(jié)點(diǎn)p中找關(guān)鍵字為k的位置i,成功時返回1,否則返回0*/if (k<p->key1) /*k小于*p結(jié)

32、點(diǎn)的最小關(guān)鍵字時返回0*/ i=0; return 0;else /*在*p結(jié)點(diǎn)中查找*/ i=p->keynum; while (k<p->keyi && i>1) i-; return(k=p->keyi);int RecDelete(KeyType k,BTNode *p)/*查找并刪除關(guān)鍵字k*/int i;int found;if (p=NULL) return 0;else if (found=SearchNode(k,p,i)=1) /*查找關(guān)鍵字k*/ if (p->ptri-1!=NULL) /*若為非葉子結(jié)點(diǎn)*/ Succ

33、essor(p,i); /*由其后繼代替它*/ RecDelete(p->keyi,p->ptri); /*p->keyi在葉子結(jié)點(diǎn)中*/ else Remove(p,i); /*從*p結(jié)點(diǎn)中位置i處刪除關(guān)鍵字*/ else found=RecDelete(k,p->ptri); /*沿孩子結(jié)點(diǎn)遞歸查找并刪除關(guān)鍵字k*/ if (p->ptri!=NULL) if (p->ptri->keynum<Min) /*刪除后關(guān)鍵字個數(shù)小于MIN*/ Restore(p,i); return found;void DeleteBTree(KeyType

34、k,BTNode *root)/*從B-樹root中刪除關(guān)鍵字k,若在一個結(jié)點(diǎn)中刪除指定的關(guān)鍵字,不再有其他關(guān)鍵字,則刪除該結(jié)點(diǎn)*/BTNode *p; /*用于釋放一個空的root*/if (RecDelete(k,root)=0) printf(" 關(guān)鍵字%d不在B-樹中n",k);else if (root->keynum=0) p=root; root=root->ptr0; free(p);struct BookInfo book1000;void addbook()/添加書int n=1,num;while(n)printf("書號:&qu

35、ot;);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現(xiàn)存量:");scanf("%d"

36、;,&booknum.extant);printf("n總量:");scanf("%d",&booknum.total);InsertBTree(bookp,booknum.number,s.pt,s.i);printf("n輸入 1 繼續(xù)添加, 0 返回主界面");scanf("%d",&n);void lendbook(int booknumber)/借書int num;if(booknumber=-1)printf("請輸入書號:");scanf("%d&

37、quot;,&num);if(booknum.extant)printf("操作成功!");booknum.extant-;elseprintf("操作失敗!書已經(jīng)被借出或不存在這本書.");elseprintf("操作成功!n");bookbooknumber.extant-;return;void findbook()/查找書int num,select;printf("請輸入書號:");scanf("%d",&num);s=SearchBTree(bookp,num);if

38、(s.tag)printf("成功找到!.n");printf("書號:%d,nt書名:%s,作者:%s,現(xiàn)存量:%d,總量:%dn",booknum.number,,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.extant<booknum.total)booknum.extant+;printf("操作成功!n");else printf("操作失敗!n");return;