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

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

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

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

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

8、ntf(此書已存在!)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(你想借這本

9、書嗎?輸入 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&quo

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

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

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

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

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

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

16、g; /*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<=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上查找關鍵字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的雙親*/int found=0,i=0;/found為標志位Result r;/創建查找結果類型結構體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) /*找到待查關鍵字*/ 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置

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) /無空位置則分裂.將結點q分裂成兩個結點,前一半保留,后一半移入新生結點apint i,s=(m+1)/2;/分裂的位置ap=(BTNode *)malloc(sizeof(BTNode); /*生成新結點*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+) /*修改指向雙親結點的指針*/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

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) /*最終的插入函數.在m階t樹t上結點*q的keyi與keyi+1之間插入關鍵字k。若引起 結點過大,則沿雙親鏈進行必

23、要的結點分裂調整,使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->keynum&

24、lt;=Max) finished=1; /*無須分裂,插入完成*/ else /*分裂結點*q,將q->keys+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); /*生成新根結

25、點*t,q和ap為子樹指針*/void Remove(BTNode *p,int i)/*從*p結點刪除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)/*查找被刪關鍵字p->keyi(在非葉子結點中)的替代葉子結點*/BTNode *q;for (q=p->ptri;q->ptr0!=NU

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

27、i;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=

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

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

30、gt;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->keynum>Min) MoveLeft(p,1); else Combine(p,1);else if (i=p->keynum) /*為最右邊關鍵字的情況*/ 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)/*在結點p中找關鍵字為k的位置i,成功時返回1,否則返回0*/if (k<p->key1) /*k小于*p結

32、點的最小關鍵字時返回0*/ i=0; return 0;else /*在*p結點中查找*/ i=p->keynum; while (k<p->keyi && i>1) 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) /*若為非葉子結點*/ Succ

33、essor(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->keynum<Min) /*刪除后關鍵字個數小于MIN*/ Restore(p,i); return found;void DeleteBTree(KeyType

34、k,BTNode *root)/*從B-樹root中刪除關鍵字k,若在一個結點中刪除指定的關鍵字,不再有其他關鍵字,則刪除該結點*/BTNode *p; /*用于釋放一個空的root*/if (RecDelete(k,root)=0) printf(" 關鍵字%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現存量:");scanf("%d"

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

37、quot;,&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

38、(s.tag)printf("成功找到!.n");printf("書號:%d,nt書名:%s,作者:%s,現存量:%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;