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

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

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

3、不可恥。阿卜日法拉茲=Olog 2(Ff- 0 x log 尋(岸訂)= Onog2(f)xOlog(|)= C*log2()xaog 尋 N _1”=opog 2 AT-log2(妁= tDog2Ar-oc= O2N其中，M為設定的非葉子結(jié)點最多子樹個數(shù)，N為關(guān)鍵字總數(shù)；所以B擁的性能總是等價于二分查找(與 M值無關(guān))，也就沒有 B樹平衡的問題；因此，B揺是一種動態(tài)查找 效率較二叉排序樹更高的樹形結(jié)構(gòu)。(2 )算法設計算法設計的總體設計思路為：首先創(chuàng)建一顆4階B揺，然后在此基礎上設計添加圖書、查找圖書、借閱圖書、歸還圖書、顯示圖書狀態(tài)、刪除圖書記錄、退出七個模塊，最后主函數(shù)再用一個switc

4、h選擇語句來調(diào)用各個模塊。各個模塊要完成的主要功能分別為：添加圖書：可以添加圖書記錄，按提示依次輸入書號、書名、作者、現(xiàn)存量、總量，會提示是否繼續(xù)添加。查找圖書：可根據(jù)輸入的書號進行查詢， 成功找到后會提示是否想借這本書， 輸入1為借書,輸入0為退出。借閱圖書：可根據(jù)提示輸入相應的書號進行借書。歸還圖書：可根據(jù)提示輸入相應的書號歸還圖書。顯示圖書狀態(tài)：可顯示圖書管理系統(tǒng)里的所有圖書狀態(tài)。刪除圖書記錄：可根據(jù)提示輸入相應的書號刪除圖書記錄。主程序的流程圖如下：書名判斷(2) 函數(shù)接口規(guī)格說明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（）/ 主函數(shù)2.3 詳細設計 各個功能模塊主要算法的偽代碼實現(xiàn)添加圖書模塊printf（ 請輸入書號 ） scanf （書號 ） If SearchBTree（ 書號 ）=true printf（ 此書已存在 !）elseprintf（ 請輸入書名 ） scanf（ 書名 ）printf（ 請輸入作者 ） scanf（ 作者 ） printf（ 請輸入現(xiàn)存量 ） scanf（ 現(xiàn)存量 ） printf（ 請輸入總量 ） scanf

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

9、f（ 請輸入書號 ）閱讀使人充實，會談使人敏捷，寫作使人精確。培根scanf（ 書號 ）if SearchBTree（ 書號 ）=true and 總量大于零printf（ 操作成功 !）總量減一elseprintf（ 操作失敗 ! 書已經(jīng)被借出或不存在這本書 ）return歸還圖書模塊printf（ 請輸入書號 ）scanf（ 書號 ）if SearchBTree（ 書號 ）=trueprintf（ 操作成功 !）總量加一elseprintf（ 操作失敗 !n）;return刪除圖書記錄模塊printf（ 請輸入書號 ）scanf（ 書號 ）if SearchBTree（ 書號 ）=true

10、printf（ 書的具體信息 :書號,書名 ,作者,現(xiàn)存量 ,總量）printf（ 輸入 1 刪除這本書 ）scanf（）if（1）書號=0printf（ 刪除成功 !）else printf（ 操作失敗 ! 不存在這本書 ）return顯示圖書狀態(tài)模塊int i;for（i=1;i4 54 54 5量量存存現(xiàn)現(xiàn)3 43 43 413單選作 書圖圖圖狀圖，驀閱還書12 3 4 5 6 7 丿1 21 21 2 號號單選 錄 記 書圖圖圖狀圖 綢閱還書逼ri&i-OTT詵一作 舊WW書 書圖圖圖狀圖 養(yǎng)閱還書掘12 3 4 5 6 7555666777總量: 總量: 總量:444,555,666

11、,333,現(xiàn)存量:444,現(xiàn)存量:555,現(xiàn)存量: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,現(xiàn)存量:444,現(xiàn)存量:555,現(xiàn)存量:單選 作.書圖圖圖狀圖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書書書單選作書圖圖圖狀圖發(fā)閱還書燼12 3 4 5 6 7閱讀使人充實，會談使人敏捷，寫作使人精確。培根學冋是異常珍貴的東西，從任何源泉吸收都不可恥。阿卜日法拉茲6源程序清單#include #include#include #include #include #define MAXM

13、 10/*typedef int KeyType;定義 B- 樹的最大的階數(shù) */*KeyType 為關(guān)鍵字類型 */struct BookInfo /int number; char name30; char author30;int extant;int total;書結(jié)構(gòu)體typedef struct node /B-int keynum;KeyType keyMAXM; struct node *parent; /* struct node *ptrMAXM;typedef struct /*B-樹的查找結(jié)果類型 */樹結(jié)點定義/* 結(jié)點當前擁有的關(guān)鍵字的個數(shù) */*key1.keyn

14、um存放關(guān)鍵字 ,key0 不用 */雙親結(jié)點指針 */* 孩子結(jié)點指針數(shù)組 ptr0.keynum*/ BTNode;BTNode *bookp=NULL;BTNode *pt; /* int i;/*1.m,int tag; /*1: Result;指向找到的結(jié)點 */ 在結(jié)點中的關(guān)鍵字序號 */ 查找成功 ,O: 查找失敗 */int m; /*m階 B- 樹 , 為全局變量 */int Max; /*mint Min; /*m階 B- 樹中每個結(jié)點的至多關(guān)鍵字個數(shù) ,Max=m-1*/階 B- 樹中非葉子結(jié)點的至少關(guān)鍵字個數(shù) ,Min=(m-1)/2*/Result s;int Sea

15、rch(BTNode *p,KeyType k) / 在 p-key1.keynum 中查找關(guān)鍵字序號 i, 使得 p-keyi=kkeyi+1int i;for(i=0;ikeynum & p-keyi+1key1.keynum中查找 i, 使得p-keyi=kkeyi+1*/找到待查關(guān)鍵字 */if (i0 & p-keyi=k) /*found=1; elseq 指向 p變成它原來的孩子結(jié)點i查找成功 */q=p;/ 雙親結(jié)點 p=p-ptri;/pr.i=i;/ 關(guān)鍵字序號 if (found=1) /*r.pt=p;r.tag=1;/pt指向找到的結(jié)點 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) / 無空位置則分裂 . 將結(jié)點 q 分裂成兩個結(jié)點 , 前一半保留 , 后一 int i,s=(m+1)/2;/ 分裂的位置ap=(BTNode *)malloc(sizeof(BTNode); /* 生成新結(jié)點 *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+) /* 修改指向雙親結(jié)點的指針 */ if (ap-ptri!=NULL) ap-ptri-parent = ap;q-keynum=s-1; /*q 的前一半保留 , 修改 keynum*/void NewRoot(BTNode *&t,BTNode *p,KeyType x,BTNode *ap)/ 的根結(jié)點 *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)半移入新生結(jié)點 ap生成含信息 (T,x,ap) 的新 原 t 和 ap 為子樹指針之間插入關(guān)鍵字k。若引 /* 最終的插入函數(shù) . 在 m 階 t 樹 t 上結(jié)點 *q 的 keyi 與 keyi+1 起結(jié)點過大，則沿雙親鏈進行必要的結(jié)點分裂調(diào)整，使t仍是m階t樹。*/BTNode *ap;int finished，needNewRoot，s;KeyType x;if (q=NULL) /*t是空樹 (參數(shù) q 初

20、值為 NULL)*/NewRoot(t，NULL，k，NULL); /生成僅含關(guān)鍵字 k 的根結(jié)點 *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移入新結(jié)點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); /*在雙親結(jié)點 *q 中查找 x 的插入位置 */根結(jié)點已分裂為結(jié)點*q和*ap*/ 生成新根結(jié)點 *t，q 和 ap 為子樹指針 */void Remove(BTNode *p，int i)/* 從 *p 結(jié)點刪除 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)/* 查找被刪關(guān)鍵字 p-keyi( 在非葉子結(jié)點中 ) 的替代葉子結(jié)點 */BTNode *q;for (q=p-ptri;q-ptr0!=NULL;q=q-ptr0); p-keyi=q-key1; /* 復制關(guān)鍵字值 */void MoveRight(BTNode *p,int i)/* 把一個關(guān)鍵字移動到右兄弟中 */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-ptr0; /*

23、 從雙親結(jié)點移動關(guān)鍵字到右兄弟中 */ t-keynum+;t-key1=p-keyi;t=p-ptri-1; /* 將左兄弟中最后一個關(guān)鍵字移動到雙親結(jié)點中 */ 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é)點中的關(guān)鍵字移動到左兄弟中 */ t-keynum+;t-keyt-keynum=p-keyi; t-ptrt-keynum=p-ptri-ptr0;t

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

25、eyi;l-ptrl-keynum=q-ptr0;for (c=1;ckeynum;c+) /* 插入右結(jié)點中的所有關(guān)鍵字 */ l-keynum+;l-keyl-keynum=q-keyc; l-ptrl-keynum=q-ptrc;for (c=i;ckeynum;c+) /* 刪除父結(jié)點所有的關(guān)鍵字 */p-keyc=p-keyc+1; p-ptrc=p-ptrc+1;p-keynum-;free(q); /* 釋放空右結(jié)點的空間 */void Restore(BTNode *p,int i)中*/*關(guān)鍵字刪除后,調(diào)整B-樹,找到一個關(guān)鍵字將其插入到p-ptriif (i=0)/*為最左

26、邊關(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,BTNode

27、*p,int &i)/*在結(jié)點p中找關(guān)鍵字為k的位置i,成功時返回1,否則返回0*/if (kkey1) /*k 小于 *p 結(jié)點的最小關(guān)鍵字時返回 0*/i=0;return 0;else /* 在*p結(jié)點中查找*/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)鍵字 k*/if (p-ptri-

28、1!=NULL)/*若為非葉子結(jié)點 */Successor(p,i); /*由其后繼代替它 */RecDelete(p-keyi,p-ptri); /*p-keyi在葉子結(jié)點中 */elseRemove(p,i); /*從*p結(jié)點中位置i處刪除關(guān)鍵字*/elsek*/found=RecDelete(k,p-ptri); /*沿孩子結(jié)點遞歸查找并刪除關(guān)鍵字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現(xiàn)存量 :);scanf(%d,&booknum.extant);printf(n總量 :);scanf(%d,&booknum.total);InsertBTree(bookp,boo

30、knum.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-; else printf( 操作失敗 ! 書已經(jīng)被借出或不存在這本書 .);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, 現(xiàn)存量 :%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