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

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

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

3、能為：其中，m 為設定的非葉子結點最多子樹個數，n 為關鍵字總數；所以 b-樹的性能總是等價于二分查找（與 m 值無關），也就沒有 b 樹平衡 的問題；因此，b-樹是一種動態(tài)查找效率較二叉 排序樹更高的樹形結構。（2）算法設計算法設計的總體設計思路為：首先創(chuàng)建一顆 4 階 b-樹，然后在此基礎上設計添加圖書、查找 圖書、借閱圖書、歸還圖書、顯示圖書狀態(tài)、刪 除圖書記錄、退出七個模塊，最后主函數再用一 個 switch 選擇語句來調用各個模塊。各個模塊 要完成的主要功能分別為：添加圖書：可以添加圖書記錄，按提示依次輸入書號、書名、作者、現存量、總量，會提示是否繼續(xù)添加。查找圖書：可根據輸入的書號

4、進行查詢，成功找 到后會提示是否想借這本書，輸入 1 為借書，輸入 0 為退出。借閱圖書：可根據提示輸入相應的書號進行借 書。歸還圖書：可根據提示輸入相應的書號歸還圖 書。顯示圖書狀態(tài)：可顯示圖書管理系統(tǒng)里的所有圖 書狀態(tài)。刪除圖書記錄：可根據提示輸入相應的書號刪除 圖書記錄。主程序的流程圖如下：開輸 入判2.2 設計表示（1）函數調用關系圖addinsefindsealendret bo delburn okdeletexrch remoinrecdrestspsearcnewrmovecombinmovesucc（2）函數接口規(guī)格說明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 繼續(xù)添加, 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顯示圖書狀態(tài)模塊 int i;for(i=1;i1000;i+)if( 總量!=0)printf( 書號,書名, 作者,現存量,總量)3調試分析（1）本程序最大的問題就是 b-樹的基本算 法的實現，此處難點在于 b_樹的結點的分裂， 當插入結點時，判斷結點中關鍵字的個數是否大 于規(guī)定的個數，如果大于則要對此結點進行分 裂，在分裂時，要改變孩子結點的 parent 指針， 并且把分裂出的關鍵字放到該關鍵字的 parent 結點中，然后繼續(xù)判斷是否要分裂，一直到符合 要求。在進行檢測時

11、，出現了分裂時的錯誤，就 是沒有考慮到在分裂結點時，該結點的孩子結點 的 parent 指針的改變，我參考了課本和老師的 課件，并與和其他同學討論后終于通過調試和改 正，測試正確。另外，在老師您在驗收我的程序 時，指出了我的程序的兩個不足之處，一是沒有按要求以凹入表的形式顯示，二是在刪除圖書記 錄后圖書記錄并沒有消失，而僅僅是圖書號變成 了1，因此您只給我的這個程序打了個 b，我 當時心里真的很傷心。這兩個不足之處我在您驗 收之后很快就改過來了，因為原因很簡單：第一 個不足之處產生的原因是我沒注意到題目有這 個要求，其實只要在輸出語句中的書名前面加 nt 就行了；第二個不足之處產生的原因是在

12、刪除圖書記錄時應將要刪除的圖書號置為 0，而 我卻將它置為了 1.本來我當時是想找老師您 再驗收一次把成績改高一點的，但由于當時驗收 的人太多了，就沒再去麻煩您。（2）算法的時間空間復雜度分析由于 b-樹查找的時間復雜度為 o（log2n ）， 而程序中多次用到了一重循環(huán)，其時間復雜度為 o（n）,因此程序的時間復雜度為 o（n），空間 復雜度也為 o（n）.（3）可改進內容：1、利用 mfc 做一個界面，使 界面更加美觀；2、可嘗試用 b+樹代替 b_樹，更 容易應用于文件系統(tǒng) 3、刪除圖書記錄的時候必 須先收回所有的書，即要保證現存量和總量相等后方可刪除；4、采用文件的形式，可以保存圖 書

13、狀態(tài)。4用戶手冊本程序在 vc+6.0 環(huán)境下運行，按照菜單提示的 要求輸入即可。5測試數據及測試結果測試用例 1：測試輸入：見截屏 1、2測試目的：是否能按要求以凹入表的形式顯示 正確輸出：見截屏 1實際輸出：見截屏 2錯誤原因：沒有注意審題，因此未在輸出語句中 的書號前加nt當前狀態(tài)： 已改正測試用例 2：測試輸入：見截屏 3、4測試目的：是否能按要求以凹入表的形式顯示 正確輸出：見截屏 3實際輸出：見截屏 4錯誤原因：編程時粗心，錯誤的將應刪除的書號 置為了1.當前狀態(tài)： 已改正截屏 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,&); 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 繼續(xù)添加, 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.author,booknum.extant,booknum.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(