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

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

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

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

4、進(jìn)行查詢，成功找 到后會(huì)提示是否想借這本書，輸入 1 為借書，輸入 0 為退出。借閱圖書：可根據(jù)提示輸入相應(yīng)的書號(hào)進(jìn)行借 書。歸還圖書：可根據(jù)提示輸入相應(yīng)的書號(hào)歸還圖 書。顯示圖書狀態(tài)：可顯示圖書管理系統(tǒng)里的所有圖 書狀態(tài)。刪除圖書記錄：可根據(jù)提示輸入相應(yīng)的書號(hào)刪除 圖書記錄。主程序的流程圖如下：開輸 入判2.2 設(shè)計(jì)表示（1）函數(shù)調(diào)用關(guān)系圖addinsefindsealendret bo delburn okdeletexrch remoinrecdrestspsearcnewrmovecombinmovesucc（2）函數(shù)接口規(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()/ 主函數(shù)2.3 詳細(xì)設(shè)計(jì)各個(gè)功能模塊主要算法的偽代碼實(shí)現(xiàn) 添加圖書模塊printf( 請(qǐng)輸入書號(hào))scanf （書號(hào) ）if searchbtree( 書號(hào))=trueprintf( 此書已存在!)elseprintf( 請(qǐng)輸入書名 )scanf( 書名)printf( 請(qǐng)輸入作者 )scanf( 作者)printf( 請(qǐng)輸入現(xiàn)存量)scanf( 現(xiàn)存量)printf( 請(qǐng)輸入總量 )scanf(

8、總量)insertbtree( 書號(hào)，書名, 作者, 現(xiàn)存量, 總量)printf( 輸入 1 繼續(xù)添加, 0 返回主界面)scanf(1 or 0)return查找圖書模塊printf( 請(qǐng)輸入書號(hào) )scanf （書號(hào) ）if searchbtree( 書號(hào))=trueprintf( 成功找到 !)printf( 書號(hào) ,書名,作者,現(xiàn)存量,總量)if 總量大于零printf( 你想借這本書嗎?輸入 1 借, 0 退出) scanf(1 or 0)if(1) 總量減一elseprintf( 此書不存 )return借閱圖書模塊printf( 請(qǐng)輸入書號(hào) )scanf( 書號(hào))if sear

9、chbtree( 書號(hào))=true and 總量大于零printf( 操作成功!)總量減一elseprintf( 操作失敗 !書已經(jīng)被借出或不存在這本書) return歸還圖書模塊printf( 請(qǐng)輸入書號(hào) )scanf( 書號(hào))if searchbtree( 書號(hào))=trueprintf( 操作成功!)總量加一elseprintf( 操作失敗!n);return刪除圖書記錄模塊printf( 請(qǐng)輸入書號(hào) )scanf( 書號(hào))if searchbtree( 書號(hào))=trueprintf( 書的具體信息:書號(hào),書名,作者,現(xiàn)存量,總量 ) printf( 輸入 1 刪除這本書 )scanf()

10、if(1)書號(hào)=0printf( 刪除成功!)else printf( 操作失敗 !不存在這本書 ) return顯示圖書狀態(tài)模塊 int i;for(i=1;i1000;i+)if( 總量!=0)printf( 書號(hào),書名, 作者,現(xiàn)存量,總量)3調(diào)試分析（1）本程序最大的問題就是 b-樹的基本算 法的實(shí)現(xiàn)，此處難點(diǎn)在于 b_樹的結(jié)點(diǎn)的分裂， 當(dāng)插入結(jié)點(diǎn)時(shí)，判斷結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)是否大 于規(guī)定的個(gè)數(shù)，如果大于則要對(duì)此結(jié)點(diǎn)進(jìn)行分 裂，在分裂時(shí)，要改變孩子結(jié)點(diǎn)的 parent 指針， 并且把分裂出的關(guān)鍵字放到該關(guān)鍵字的 parent 結(jié)點(diǎn)中，然后繼續(xù)判斷是否要分裂，一直到符合 要求。在進(jìn)行檢測(cè)時(shí)

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

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

13、狀態(tài)。4用戶手冊(cè)本程序在 vc+6.0 環(huán)境下運(yùn)行，按照菜單提示的 要求輸入即可。5測(cè)試數(shù)據(jù)及測(cè)試結(jié)果測(cè)試用例 1：測(cè)試輸入：見截屏 1、2測(cè)試目的：是否能按要求以凹入表的形式顯示 正確輸出：見截屏 1實(shí)際輸出：見截屏 2錯(cuò)誤原因：沒有注意審題，因此未在輸出語句中 的書號(hào)前加nt當(dāng)前狀態(tài)： 已改正測(cè)試用例 2：測(cè)試輸入：見截屏 3、4測(cè)試目的：是否能按要求以凹入表的形式顯示 正確輸出：見截屏 3實(shí)際輸出：見截屏 4錯(cuò)誤原因：編程時(shí)粗心，錯(cuò)誤的將應(yīng)刪除的書號(hào) 置為了1.當(dāng)前狀態(tài)： 已改正截屏 1截屏 2截屏 3截屏 46源程序清單#include #include#include #includ

14、e#include#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 total;typedef struct node /b- 樹結(jié)點(diǎn)定義int keynum; /* 結(jié)點(diǎn)當(dāng) 前擁有的關(guān)鍵字的個(gè)數(shù) */keytype keymaxm;/*key1.keynum 存放關(guān)鍵字,key0 不用*/ struct node *parent; /* 雙親結(jié)點(diǎn)指針

15、*/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)鍵字序號(hào)*/int tag; /*1: 查找成功,o:查找失 敗*/ result;int m; /*m 階 b-樹,為全局變量*/ int max; /*m 階 b-樹中每個(gè)結(jié)點(diǎn)的至多 關(guān)鍵字個(gè)數(shù),max=m-1*/int min; /*m 階 b-樹中非葉子結(jié)點(diǎn)的至 少關(guān)鍵字個(gè)數(shù),min=

16、(m-1)/2*/result s;int search(btnode *p,keytype k) /在 p-key1.keynum 中查找關(guān)鍵字序號(hào) i, 使得 p-keyi=kkeyi+1int i;for(i=0;ikeynum &p-keyi+1key1.keynum 中查找 i,使得 p-keyi=kkeyi+1*/if (i0 & p-keyi=k) /*找到待查關(guān)鍵 字*/found=1;elseq=p;/ 雙親結(jié)點(diǎn) q 指向 p p=p-ptri;/p 變成它原來的孩子結(jié)點(diǎn)r.i=i;/ 關(guān)鍵字序號(hào) iif (found=1) /* 查找成功*/r.pt=p;r.tag=1;/

17、pt 指向找到的結(jié)點(diǎn) 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-) /* 空出一個(gè)位置*/ 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) /無空位置則分裂.將結(jié)點(diǎn) q 分裂成兩個(gè)結(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;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+) /* 修改指向雙 親結(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 和 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) /*最終的插入函數(shù).在 m 階 t 樹 t 上結(jié)點(diǎn)*q 的 keyi 與 keyi+1 之間插入關(guān)鍵字 k。若引起結(jié)點(diǎn)過大,則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂 調(diào)整,使 t 仍是 m 階 t 樹。*/btnode *ap;int finished,neednewroot,s;keytype x;if (q=null)

21、 /*t 是空樹(參數(shù) q 初值為 null)*/newroot(t,null,k,null); / 生成僅含 關(guān)鍵字 k 的根結(jié)點(diǎn)*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 移入新結(jié)點(diǎn)*ap*/s=(m+1)/2;split(q,ap);x=q-keys;if (q-parent)

22、/* 在雙親結(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é)點(diǎn) *t,q 和 ap 為子樹指針*/void remove(btnode *p,int i)/*從*p 結(jié)點(diǎn)刪除 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)/*查找被刪關(guān)鍵字 p-keyi( 在非葉子結(jié)點(diǎn)中) 的替代葉子結(jié)點(diǎn)*/btnode *q;for(q=p-ptri;q-ptr0!=null;q=q-ptr0);p-keyi=q-key1; /* 復(fù)制關(guān)鍵字值*/void moveright(btnode *p,int i)/*把一個(gè)關(guān)鍵字移動(dòng)到右兄弟中 */int c;btnode *t=p-ptri;for (c=t-keynum;c0;c-) /*將右兄弟中所有 關(guān)鍵字左移一位*/t-keyc+1=t-keyc;t-ptrc+1=t-ptrc;t-ptr1=t

24、-ptr0; /* 從雙親結(jié)點(diǎn)移動(dòng)關(guān) 鍵字到右兄弟中*/t-keynum+;t-key1=p-keyi;t=p-ptri-1; /* 將左兄弟中最后一個(gè)關(guān) 鍵字移動(dòng)到雙親結(jié)點(diǎn)中 */ p-keyi=t-keyt-keynum;p-ptri-ptr0=t-ptrt-keynum;t-keynum-;void moveleft(btnode *p,int i)/*把一個(gè)關(guān)鍵字移動(dòng)到左兄弟中 */int c;btnode *t;t=p-ptri-1; /* 把雙親結(jié)點(diǎn)中的關(guān)鍵字 移動(dòng)到左兄弟中*/t-keynum+;t-keyt-keynum=p-keyi;t-ptrt-keynum=p-ptri-

25、ptr0;t=p-ptri; /* 把右兄弟中的關(guān)鍵字移動(dòng) 到雙親兄弟中*/p-keyi=t-key1;p-ptr0=t-ptr1;t-keynum-;for (c=1;ckeynum;c+) /* 將右兄弟中所 有關(guān)鍵字移動(dòng)一位 */t-keyc=t-keyc+1;t-ptrc=t-ptrc+1;void combine(btnode *p,int i)/*將三個(gè)結(jié)點(diǎn)合并到一個(gè)結(jié)點(diǎn)中 */int c;btnode *q=p-ptri; /* 指向右結(jié)點(diǎn),它將 被置空和刪除*/btnode *l=p-ptri-1;l-keynum+; /*l 指向左結(jié)點(diǎn)*/l-keyl-keynum=p-ke

26、yi;l-ptrl-keynum=q-ptr0;for (c=1;ckeynum;c+) /* 插入右結(jié)點(diǎn) 中的所有關(guān)鍵字*/l-keynum+;l-keyl-keynum=q-keyc;l-ptrl-keynum=q-ptrc;for (c=i;ckeynum;c+) /* 刪除父結(jié)點(diǎn) 所有的關(guān)鍵字*/p-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-樹,找到一個(gè)關(guān)鍵字將 其插入到 p-ptri 中*/if (i=0) /*

27、為最左邊關(guān)鍵字的情況 */ if (p-ptr1-keynummin)moveleft(p,1);elsecombine(p,1);else if (i=p-keynum) /* 為最右邊關(guān)鍵 字的情況*/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)/*在結(jié)點(diǎn) p 中找關(guān)鍵字為 k 的位置 i,成功時(shí)返 回 1,否則返回 0*/if (kkey1) /*k 小于*p 結(jié)點(diǎn)的最小關(guān)鍵 字時(shí)返回 0*/i=0;return 0;else /* 在*p 結(jié)點(diǎn)中查找*/i=p-keynum;while (kkeyi & i1)i-;return(k=p-keyi);int recdelete(keytype k,btnode *p) /*查找并刪除關(guān)鍵字 k*/int i;int found;if (p=null)return 0;elseif (found=searchnode(k,p,i)=1) /* 查找關(guān)鍵字

29、 k*/if (p-ptri-1!=null) /* 若為非葉 子結(jié)點(diǎn)*/successor(p,i); /* 由其后繼代替 它*/recdelete(p-keyi,p-ptri); /*p-keyi 在葉子結(jié)點(diǎn)中*/elseremove(p,i); /* 從*p 結(jié)點(diǎn)中位置 i 處刪除關(guān)鍵字*/elsefound=recdelete(k,p-ptri); /* 沿 孩子結(jié)點(diǎn)遞歸查找并刪除關(guān)鍵字 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( 書號(hào):); 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,&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( 請(qǐng)輸入書號(hào):); scanf(%d,&num);if(booknum.extant)printf( 操作成功!); booknum.extant-;elseprintf( 操作失敗!書已經(jīng)被借出或不存 在這本書.);elseprintf( 操作成功!n);bookbooknum

32、ber.extant-;return;void findbook()/ 查找書 int num,select;printf( 請(qǐng)輸入書號(hào):); scanf(%d,&num);s=searchbtree(bookp,num);if(s.tag) printf( 成功找到!.n);printf( 書號(hào):%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);elsereturn;elsereturn;void returnbook()/ 還書int num;printf( 請(qǐng)輸入書號(hào):); scanf(%d,&num);if(booknum.number!=-1&booknum.extantbooknum.total) booknum.extant+;printf(