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

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

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

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

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

6、e int n;關(guān)鍵字的計(jì)量 sKeywords keywordsMAX_KEYWORDS; 關(guān)鍵字的最大容量 bool leaf; /判斷是否為葉子 sBTree* childrenMAX_KIDSNUM; / 孩子 ; sBTree *root=NULL; / 根結(jié)點(diǎn) int deep=0; / 深度 void CreateBTree(); / 構(gòu)建 B 樹(shù)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 樹(shù)的插入 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-樹(shù)操作定義 void CreateBTree() /構(gòu)建B-樹(shù) sBTree* newNode=(sBTree*)malloc(sizeof(sBTree); 分配存儲(chǔ)空間 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樹(shù)已滿，則分配新的結(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) 圖書(shū)管理存儲(chǔ)定義 (4) 圖書(shū)管理函數(shù)定義 sKeywords MakeNewBook() / 輸入新書(shū)的信息 void prin tBTree(sBTree* T); B樹(shù)的形式顯示當(dāng)前所有的圖書(shū)號(hào) void prin tTab(); void In sertBook(sBTree *T,sKeywords keywords); sKeywords MakeNewBook(); / 輸入新書(shū)的信息 void ren t(i nt coun t); / 借書(shū) vo

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

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

21、rt(keywords); void rent(int count) /借書(shū)，書(shū)庫(kù)中有書(shū)號(hào)為count的書(shū)，借閱成功，否則 查 找 /失敗 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); /還書(shū)，如果書(shū)庫(kù)中有書(shū)號(hào)為count的書(shū)，則可歸還/若無(wú)，則輸出查無(wú)此書(shū) 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(查無(wú)此書(shū)! n); void printBTree(sBTree* T) /B樹(shù)的形式顯示當(dāng)前所有的圖書(shū)號(hào) 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() /按制表位輸出書(shū)號(hào) for(i nt i=0;ideep;i+) prin tf(t); (5) 主函數(shù) void mai n() sKeywords keywords; int count; / 書(shū)號(hào)專業(yè).專注 char choice; CreateBTree(); / 構(gòu)建 B 樹(shù) prin tf( nn); printf( AAAAAAAAAAAAAAAAAAAAA

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

25、ook(root,keywords); printf( 圖書(shū)管理系統(tǒng)主菜單 n); printf( case 1: 專業(yè).專注 break; case 2: /清除庫(kù)存 printf(要?jiǎng)h除的書(shū)編號(hào)為:); sca nf(%d,&count); BTreeDeleteKeywords(root,co un t); break; case 3: / 借書(shū) printf(要借出的書(shū)編號(hào)為:); sca nf(%d,&count); ren t(co un t); break; case 4: / 還書(shū) printf(歸還的樹(shù)編號(hào)為:); 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)用過(guò)程如下圖所示 構(gòu) 采 造 編 函 入 數(shù) 庫(kù) 清 除 庫(kù) 存 錄 入 信 息 插 入 結(jié) 占 八、 、 專業(yè).專注 4. 調(diào)試分析 調(diào)試過(guò)程中遇到的問(wèn)題以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析 ： 對(duì)于本次設(shè)計(jì)個(gè)人感覺(jué)難度很大，因?yàn)閳D書(shū)管理系統(tǒng)涉及到的功能比較 多，采編入庫(kù)、清除庫(kù)存、借閱和和歸還，其中最難的部分是B樹(shù)定義和操作 以及B樹(shù)相關(guān)操作的調(diào)用，書(shū)上對(duì)于B樹(shù)這一塊的內(nèi)容比較少，網(wǎng)上B樹(shù)的基

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

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

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