廣工數(shù)據(jù)結(jié)構(gòu)課程設(shè)計__圖書管理系統(tǒng)方案

1、專業(yè).專注 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 題目：圖書管理系統(tǒng) 學(xué) 院 計算機(jī)學(xué)院 _ 專 業(yè) _ 年級班別 _ 學(xué) 號 _ 學(xué)生姓名 _ 指導(dǎo)教師 _ 成 績 _ 20122012 年 6 6 月 專業(yè).專注 1.需求分析 圖書管理系統(tǒng)中圖書管理模塊包括圖書類型定義 ：書號、現(xiàn)存量、總存量 為整型，書名、著者名為字符型，B樹（2-3樹）類型定義：關(guān)鍵字個數(shù)和關(guān)鍵 字?jǐn)?shù)組為整型、 另外還有指向雙親的指針、 指向子樹的指針、 記錄單元指針；B 樹查找結(jié)果類型定義：節(jié)點(diǎn)指針、關(guān)鍵字序號和查找標(biāo)志變量為整型。 輸出的形式； 該演示系統(tǒng)，沒有使用文件，全部數(shù)據(jù)放在內(nèi)存存放。四項基本業(yè)務(wù)都以書 號為關(guān)鍵字進(jìn)行的，

2、采用了 B樹（2-3樹）對書號建立索引，以B樹的形式進(jìn)行 輸出，形象且可以提高效率。 程序所能達(dá)到的功能； 采編入庫：新書購入，將書號、書名、著者、冊數(shù)、出版時間添加入圖 書賬目中去，如果這種書在帳中已有，則只將總庫存量增加，每新增一個書號 則以凹入表的形式顯示B樹現(xiàn)狀。 清除庫存：實現(xiàn)某本書的全部信息刪除操作 ，每清除一個書號則已以 凹入表的形式顯示B樹現(xiàn)狀。 圖書借閱：如果書的庫存量大于零時則執(zhí)行出借，登記借閱者的圖書證 號和姓名，系統(tǒng)自動抓取當(dāng)前借閱時間和計算歸還時間 圖書歸還：注銷借閱者信息，并改變該書的現(xiàn)存量。 顯示：以凹入表的形式顯示 B樹。這個操作是為了調(diào)試和維護(hù)的目的而 設(shè)置的

3、。 專業(yè).專注 測試數(shù)據(jù)，包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果 。 入庫書號:35,16,18,70,5,50,22,60,13,17,12,45,25,42,15,90,30,7 清除書號:45,90,50,22,42 2概要設(shè)計 （1）.抽象數(shù)據(jù)類型B樹定義： ADT BTree 數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。各個數(shù)據(jù)元素均含有類型相 同，可惟一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系：數(shù)據(jù)元素同屬于一個集合并且： 一棵m階的B樹，或為空，或為滿足下列特性的m叉樹： 樹中每個結(jié)點(diǎn)至多有m棵子樹； 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹； 除根之外的所有非終端結(jié)點(diǎn)至少

4、有 m/2 （取上限）棵子樹； 所有的非終端結(jié)點(diǎn)包含下列信息數(shù)據(jù)： （n ,A0,K1,A1,K2,A2,K3, ,Kn,An） 其中：Ki （i=1，2，n）為關(guān)鍵字，且 KiKi+1 （i=1，2，n-1 ）； Ai （i=0，n）為指向子樹根結(jié)點(diǎn)的指針，且指針Ai-1所指子樹中所有結(jié)點(diǎn)的 關(guān)鍵字均小于Ki (i=1 , 2, n) , An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于 Kn, n (m/2(取上限)-1=0 ,其中 每個數(shù)據(jù)元素ai含有類型相同，可惟一標(biāo)識數(shù)據(jù)元素的關(guān)鍵字 數(shù)據(jù)關(guān)系：數(shù)據(jù)元素同屬一個集合 基本操作： In sertBook(sBTree *T,sKeywords ke

5、ywords) 初始條件：B樹T已存在。 操作結(jié)果：如果所要插入的書中已存在T樹中，則只將該書的庫存量增加， 否則插入到T樹中。 Ren t(k) 初始條件：書庫不為空。 操作結(jié)果： 如果書庫中有書號為k的書，則借書成功，否則返回查找失敗。 Get(k) 初始條件： 書庫不為空。 操作結(jié)果： 如果書庫中有書號為k的書，則還書成功，否則返回查無此書。 ADT Book (3)主程序 int main() 初始化 專業(yè).專注 系統(tǒng)界面； do switch() 顯示菜單信息； 接受命令; 處理命令; 輸出結(jié)果； while 3.詳細(xì)設(shè)計 (1)抽象數(shù)據(jù)類型B-樹存儲定義： struct sBTre

6、e int n;關(guān)鍵字的計量 sKeywords keywordsMAX_KEYWORDS; 關(guān)鍵字的最大容量 bool leaf; /判斷是否為葉子 sBTree* childrenMAX_KIDSNUM; / 孩子 ; sBTree *root=NULL; / 根結(jié)點(diǎn) int deep=0; / 深度 void CreateBTree(); / 構(gòu)建 B 樹bool BTreeSearch(sBTree *T,i nt coun t,sBTree* &x,i nt &in dex) 專業(yè).專注 bool BTreeSearch(sBTree *T,int count , s

7、BTree* &x,int &index); 查找關(guān)鍵字 void BTreel nsert(sKeywords keywords);/ 插入 void BTreeInsertNonfull(sBTree* x,sKeywords keywords); / 非滿 B 樹的插入 void BTreeDeleteKeywords(sBTree* x,i nt cou nt);/ 刪除結(jié)點(diǎn) void BTreeSplitChild(sBTree *parent,int i); / 分裂孩子結(jié)點(diǎn) sBTree* BTreeSplit(sBTree *x,sKeywords &k

8、eywords); / 分裂結(jié)點(diǎn) void BTreeComb in e(sBTree *x,sKeywords keywords,sBTree *n ewNode)/ 結(jié)點(diǎn)合 并 (2) B-樹操作定義 void CreateBTree() /構(gòu)建B-樹 sBTree* newNode=(sBTree*)malloc(sizeof(sBTree); 分配存儲空間 n ewNode-leaf=true; n ewNode-n=0; root=n ewNode; for(int i=0;ichildre n i=NULL; 專業(yè).專注 /查找操作 int i=0; while( in) &

9、; coun t(T-keywordsi.co un t) i+； if( in) & coun t=(T-keywordsi.co un t) ) x=T; in dex=i; return true; if(T-leaf) return false; else return BTreeSearch(T-childre ni,co un t,x,i ndex); void BTreeI nsert(sKeywords keywords) / /插入操作 sBTree* r=root; if(r-n=MAX_KEYWORDS) /如果結(jié)點(diǎn)B樹已滿，則分配新的結(jié)點(diǎn) sBTree* n e

10、wNode=(sBTree*)malloc(sizeof(sBTree); root=n ewNode; n ewNode-leaf=false; n ewNode-n=0;BTreeI nsertN on full(x-childre ni,keywords); 專業(yè).專注 n ewNode-childre n 0=r; BTreeSplitChild( newNode,0); BTreel nsertN on full( newNode,keywords); else BTreeI nsertN on full(r,keywords); void BTree In sertN on ful

11、l(sBTree* x,sKeywords keywords) int i=(x- n); while( i0 & keywordskeywordsi-1) i-; if(x-leaf) AddKeywordsToLi ne(x,i,keywords,NULL,true); else if( x-childre n i- n=MAX_KEYWORDS ) BTreeSplitChild(x,i); if( keywordsx-keywordsi) i+; void BTreeDeleteKeywords(sBTree* x,i nt count) BTreeDeleteKeywords

12、(x-childre nin dex+1,keywords.co unt); 專業(yè).專注 /刪除結(jié)點(diǎn) sKeywords keywords; sBTree* n ewNode; int in dex=-1; if(x-leaf) BTreeDeleteLeafData(x,co un t); else if( DataI nN ode(x,co un t,i ndex) ) if( (x-childrenindex-n) MIN_KEYWORDS ) keywords=MaxKeywords(x-childre nin dex); x-keywordsi ndex=keywords; BTre

13、eDeleteKeywords(x-childre nin dex,keywords.co un t); else if( (x-childre ni ndex+1- n) MIN_KEYWORDS ) keywords=Mi nKeywords(x-childre nin dex+1); x-keywordsi ndex=keywords;BTreeDeleteKeywords(x-childre nin dex,co un t); 專業(yè).專注 else n ewNode=RemoveKeywordsFromLi ne(x,i ndex,keywords,false); BTreeCombi

14、 ne(x-childre nin dex,keywords, newNode); BTreeDeleteKeywords(x-childre nin dex,co un t); else for(i ndex=0;i ndexvx-n ;i ndex+) if(co un tkeywordsi ndex.co unt) break; if(x-childre nin dex- n=MIN_KEYWORDS) if( in dex0 & (x-childre ni ndex-1- n)MIN_KEYWORDS ) n ewNode=RemoveKeywordsFromLi ne(x-c

15、hildre nin dex-1,x-childre ninde x-1- n-1,keywords,false); AddKeywordsToLi ne(x-childre nin dex,0,x-keywordsi ndex-1, newNode,fal se); x-keywordsi ndex-1=keywords; else if( in dex n) & (x-childre ni ndex+1- n MIN_KEYWORDS) n ewNode=RemoveKeywordsFromLi ne(x-childre nin dex+1,0,keywords,true) BTr

16、eeDeleteKeywords(x-childre nin dex-1,co un t); 專業(yè).專注 J AddKeywordsToLi ne(x-childre nin dex,x-childre nin dex-n ,x-keywordsi n dex, newNode,true); x-keywordsi ndex=keywords; BTreeDeleteKeywords(x-childre nin dex,co un t); else if(i ndex=0) n ewNode=RemoveKeywordsFromLi ne(x,i ndex,keywords,false); B

17、TreeCombi ne(x-childre nin dex,keywords, newNode); BTreeDeleteKeywords(x-childre nin dex,co un t); else n ewNode=RemoveKeywordsFromLi ne(x,i ndex-1,keywords,false); BTreeCombi ne(x-childre nin dex-1,keywords, newNode);專業(yè).專注 else BTreeDeleteKeywords(x-childre nin dex,co unt); n ewNode=root; while(roo

18、t- n=0) n ewNode=root-childre n 0; free(root); root=n ewNode; (3) 圖書管理存儲定義 (4) 圖書管理函數(shù)定義 sKeywords MakeNewBook() / 輸入新書的信息 void prin tBTree(sBTree* T); B樹的形式顯示當(dāng)前所有的圖書號 void prin tTab(); void In sertBook(sBTree *T,sKeywords keywords); sKeywords MakeNewBook(); / 輸入新書的信息 void ren t(i nt coun t); / 借書 vo

19、id get(i nt coun t); / 還書 /插入新書 bool exist=BTreeSearch(T,keywords.co un t,x,i ndex); 專業(yè).專注 sKeywords keywords; printf(請輸入新書編號:n); sca nf(%d,&(keywords.cou nt); printf(請輸入新書名稱:n); sca nf(%s,keywords .n ame); printf(請輸入新書作者:n); sca nf(%s,keywords.author); printf(請輸入新書數(shù)量:n); sca nf(%d,&(keyword

20、s.allReserves); keywords.reserves=keywords.allReserves; 現(xiàn)有數(shù)量等于庫存量 return keywords; void In sertBook(sBTree *T,sKeywords keywords) int in dex; sBTree* x; if(exist) x-keywordsi ndex.allReserves+=keywords.allReserves; 庫存增加 x-keywordsi ndex.reserves+=keywords.reserves; 現(xiàn)有量增力口 /插入新書 專業(yè).專注 else BTreel nse

21、rt(keywords); void rent(int count) /借書，書庫中有書號為count的書，借閱成功，否則 查 找 /失敗 sBTree* x; int in dex; if( BTreeSearch(root,co un t,x,i ndex) & (x-keywordsi ndex.reserves0) x-keywordsi ndex.reserves-; else printf(查找失敗! n); /還書，如果書庫中有書號為count的書，則可歸還/若無，則輸出查無此書 sBTree* x; int in dex; if( BTreeSearch(root,co

22、 un t,x,i ndex) void get(i nt count) 專業(yè).專注 x-keywordsi ndex.reserves+; else printf(查無此書! n); void printBTree(sBTree* T) /B樹的形式顯示當(dāng)前所有的圖書號 if(T=NULL) return; if(T-leaf) for(i nt i=0;in ;i+) prin tTab(); prin tf(%dn,T-keywordsi.cou nt); else for(i nt i=0;in ;i+) deep+; prin tBTree(T-childre ni); deep-;

23、 prin tTab(); prin tf(%dn,T-keywordsi.cou nt); 專業(yè).專注 deep+; prin tBTree(T-childre nT- n); deep-; void printTab() /按制表位輸出書號 for(i nt i=0;ideep;i+) prin tf(t); (5) 主函數(shù) void mai n() sKeywords keywords; int count; / 書號專業(yè).專注 char choice; CreateBTree(); / 構(gòu)建 B 樹 prin tf( nn); printf( AAAAAAAAAAAAAAAAAAAAA

24、AAAAAAAAAAAAAAAAAAAAAAAA門門) printf( 1- -米編入庫 nn); printf( 2- -清除庫存 nn); printf( 3- -借閱 nn); printf( 4 -歸還 nn); printf( 5- -顯示 nn); prin tf( 6- -退出 nn); printf( AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA門門) 請選擇相應(yīng)編碼:); do sea nf(%c,&choice); switch(choice) /米編入庫 keywords=MakeNewBook(); In sertB

25、ook(root,keywords); printf( 圖書管理系統(tǒng)主菜單 n); printf( case 1: 專業(yè).專注 break; case 2: /清除庫存 printf(要刪除的書編號為:); sca nf(%d,&count); BTreeDeleteKeywords(root,co un t); break; case 3: / 借書 printf(要借出的書編號為:); sca nf(%d,&count); ren t(co un t); break; case 4: / 還書 printf(歸還的樹編號為:); sca nf(%d,&count);

26、 get(co un t); break; case 5: / 退出 prin tBTree(root); default: break; 專業(yè).專注 while(choice!=6);專業(yè).專注 函數(shù)調(diào)用過程如下圖所示 構(gòu) 采 造 編 函 入 數(shù) 庫 清 除 庫 存 錄 入 信 息 插 入 結(jié) 占 八、 、 專業(yè).專注 4. 調(diào)試分析 調(diào)試過程中遇到的問題以及對設(shè)計與實現(xiàn)的回顧討論和分析 ： 對于本次設(shè)計個人感覺難度很大，因為圖書管理系統(tǒng)涉及到的功能比較 多，采編入庫、清除庫存、借閱和和歸還，其中最難的部分是B樹定義和操作 以及B樹相關(guān)操作的調(diào)用，書上對于B樹這一塊的內(nèi)容比較少，網(wǎng)上B樹的基

27、 本操作和算法很少，因此在B樹的插入和刪除算法上花了很多時間，后來通過 網(wǎng)上查找資料跟同學(xué)討論得出。此外，因為涉及的算法和代碼比較多，很容易 出各種各樣的錯，在編譯方面也花了不少時間。 算法的時空分析： 這個圖書管理系統(tǒng)的存儲時建立在內(nèi)存上的 ，故程序退出數(shù)據(jù)得不到保 存，每個功能感覺比較獨(dú)立，相互間聯(lián)系不算多，想要提高基本操作和算法的 效率只能通過在算法的設(shè)計以及存儲結(jié)構(gòu)上下功夫 。 經(jīng)驗和體會： 數(shù)據(jù)結(jié)構(gòu)這門課程考驗的不僅僅是人的思維，更多的是考驗人的耐心和 洞察力，想要學(xué)好這一門課程，掌握基本要領(lǐng)，以及編寫出執(zhí)行能力各方面都 強(qiáng)的程序需要花更多的時間去鉆研；在編寫過程中，會出現(xiàn)各種各樣細(xì)

28、節(jié)上的 問題，大到一條算法，小到一個=”與=”或者是“；與都可能成為你的障 礙，細(xì)心和牢固的基礎(chǔ)知識很重要。 5. 用戶使用說明 1.本程序運(yùn)行環(huán)境為 V 6.0，執(zhí)行文件為：圖書管理系統(tǒng).exe； 2.程序界面與菜單信息 專業(yè).專注 選擇1 :采編入庫，新書購入，將書號、書名、著者、冊數(shù)、出版時間添 加入圖書賬目中去，如果這種書在帳中已有，則只將總庫存量增加，每新增一 個書號則以凹入表的形式顯示 B樹現(xiàn)狀。 選擇2:清除庫存，實現(xiàn)某本書的全部信息刪除操作 ，沒清除一個書號則 已以凹入表的形式顯示B樹現(xiàn)狀。 選擇3：圖書借閱，如果書的庫存量大于零時則執(zhí)行出借，登記借閱者的圖 書證號和姓名，系統(tǒng)

29、自動抓取當(dāng)前借閱時間和計算歸還時間。 選擇4:圖書歸還，注銷借閱者信息，并改變該書的現(xiàn)存量。 選擇5:顯示輸出。 選擇6:安全退出專業(yè).專注 6. 測試結(jié)果 測試數(shù)據(jù)： 入庫書號:35,16,18,70,5,50,22,60,13,17,12,45,25,42,15,90,30,7 分別刪除書號：45、90、50、22、42 (1)新書入庫界面如下： (2)所有的書號錄入完畢后以B樹形式顯示：飛譯程設(shè)計譚糧設(shè)計耀書奇f鑿職D上bug煨書管涯蠱統(tǒng)心擴(kuò) 1 請輸入新書編號: 耕書名稱. 書作者, 戰(zhàn)新書數(shù)置 稱者量 請選擇相應(yīng)編碼皿 回S3 專業(yè).專注 (3)分別刪除書號45、90、50、22、42 (4)刪除后以B樹形式顯示剩下所有的書號 專業(yè).專注 (5)當(dāng)只向系統(tǒng)中錄入書號為 35的書時，以下為借書號為12和書號為 35、還書號為12和還書號為35的運(yùn)行情況(成功和失敗的測試結(jié)果) 7. 附錄 提交