广工数据结构课程设计--图书管理系统.doc

数据结构课程设计报告 题目：图书管理系统 学 院 计算机学院 专 业 年级班别 学 号 学生姓名 指导教师 成 绩 _ 2012年6月 1. 需求分析 图书管理系统中图书管理模块包括图书类型定义：书号、现存量、总存量为整型，书名、著者名为字符型，B树（2-3树）类型定义：关键字个数和关键字数组为整型、另外还有指向双亲的指针、指向子树的指针、记录单元指针；B树查找结果类型定义： 节点指针、关键字序号和查找标志变量为整型。 输出的形式； 该演示系统，没有使用文件，全部数据放在内存存放。四项基本业务都以书号为关键字进行的，采用了B树（2-3树）对书号建立索引，以B树的形式进行输出，形象且可以提高效率。 程序所能达到的功能； 采编入库：新书购入，将书号、书名、著者、册数、出版时间添加入图书账目中去，如果这种书在帐中已有，则只将总库存量增加，每新增一个书号则以凹入表的形式显示B树现状。 清除库存： 实现某本书的全部信息删除操作 ，每清除一个书号则已以凹入表的形式显示B树现状。 图书借阅： 如果书的库存量大于零时则执行出借，登记借阅者的图书证号和姓名，系统自动抓取当前借阅时间和计算归还时间。 图书归还：注销借阅者信息，并改变该书的现存量。 显示：以凹入表的形式显示 B树。这个操作是为了调试和维护的目的而设置的。 测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。入库书号：35,16,18,70,5,50,22,60,13,17,12,45,25,42,15,90,30,7清除书号：45,90,50,22,422. 概要设计（1）.抽象数据类型B树定义：ADTBTree数据对象：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字。数据关系：数据元素同属于一个集合并且：一棵m阶的B树，或为空，或为满足下列特性的m叉树：树中每个结点至多有m棵子树；若根结点不是叶子结点，则至少有两棵子树；除根之外的所有非终端结点至少有m/2（取上限）棵子树；所有的非终端结点包含下列信息数据：(n,A0,K1,A1,K2,A2,K3,Kn,An)其中：Ki（i=1，2，n）为关键字，且KiKi+1（i=1，2，n-1）；Ai（i=0，n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki（i=1，2，n），An所指子树中所有结点的关键字均大于Kn，n（m/2(取上限)-1=n=0，其中每个数据元素ai含有类型相同，可惟一标识数据元素的关键字数据关系：数据元素同属一个集合基本操作：InsertBook(sBTree *T,sKeywords keywords) 初始条件：B树T已存在。操作结果：如果所要插入的书中已存在T树中，则只将该书的库存量增加，否则插入到T树中。Rent(k) 初始条件：书库不为空。操作结果：如果书库中有书号为k的书，则借书成功，否则返回查找失败。Get(k)初始条件：书库不为空。操作结果：如果书库中有书号为k的书，则还书成功，否则返回查无此书。ADT Book（3）主程序int main() 初始化 系统界面； do switch() 显示菜单信息； 接受命令； 处理命令； 输出结果； while3. 详细设计（1）抽象数据类型 B- 树存储定义:struct sBTreeint n;/关键字的计量sKeywords keywordsMAX_KEYWORDS;/关键字的最大容量bool leaf; /判断是否为叶子sBTree* childrenMAX_KIDSNUM; /孩子;sBTree *root=NULL; /根结点int deep=0; /深度 void CreateBTree(); /构建B树bool BTreeSearch(sBTree *T,int count，sBTree* &x,int &index);/查找关键字void BTreeInsert(sKeywords keywords);/插入void BTreeInsertNonfull(sBTree* x,sKeywords keywords); /非满B树的插入void BTreeDeleteKeywords(sBTree* x,int count);/删除结点void BTreeSplitChild(sBTree *parent,int i); /分裂孩子结点sBTree* BTreeSplit(sBTree *x,sKeywords &keywords); /分裂结点void BTreeCombine(sBTree *x,sKeywords keywords,sBTree *newNode)/结点合并（2） B- 树操作定义void CreateBTree()/构建B-树 sBTree* newNode=(sBTree*)malloc(sizeof(sBTree);/分配存储空间 newNode-leaf=true; newNode-n=0; root=newNode; for(int i=0;ichildreni=NULL;bool BTreeSearch(sBTree *T,int count,sBTree* &x,int &index)/查找操作 int i=0; while( in) & count(T-keywordsi.count) ) i+; if( in) & count=(T-keywordsi.count) ) x=T; index=i; return true; if(T-leaf) return false; else return BTreeSearch(T-childreni,count,x,index);void BTreeInsert(sKeywords keywords) / /插入操作 sBTree* r=root; if(r-n=MAX_KEYWORDS) /如果结点B树已满，则分配新的结点 sBTree* newNode=(sBTree*)malloc(sizeof(sBTree); root=newNode; newNode-leaf=false; newNode-n=0; newNode-children0=r; BTreeSplitChild(newNode,0); BTreeInsertNonfull(newNode,keywords); else BTreeInsertNonfull(r,keywords);void BTreeInsertNonfull(sBTree* x,sKeywords keywords) int i=(x-n); while( i0 & keywordskeywordsi-1 ) i-; if(x-leaf) AddKeywordsToLine(x,i,keywords,NULL,true); else if( x-childreni-n=MAX_KEYWORDS ) BTreeSplitChild(x,i); if( keywordsx-keywordsi ) i+; BTreeInsertNonfull(x-childreni,keywords); void BTreeDeleteKeywords(sBTree* x,int count) /删除结点 sKeywords keywords; sBTree* newNode; int index=-1; if(x-leaf) BTreeDeleteLeafData(x,count); else if( DataInNode(x,count,index) ) if( (x-childrenindex-n) MIN_KEYWORDS ) keywords=MaxKeywords(x-childrenindex); x-keywordsindex=keywords; BTreeDeleteKeywords(x-childrenindex,keywords.count); else if( (x-childrenindex+1-n) MIN_KEYWORDS ) keywords=MinKeywords(x-childrenindex+1); x-keywordsindex=keywords; BTreeDeleteKeywords(x-childrenindex+1,keywords.count); else newNode=RemoveKeywordsFromLine(x,index,keywords,false); BTreeCombine(x-childrenindex,keywords,newNode); BTreeDeleteKeywords(x-childrenindex,count); else for(index=0;indexn;index+) if(countkeywordsindex.count) break; if(x-childrenindex-n=MIN_KEYWORDS) if( index0 & (x-childrenindex-1-n)MIN_KEYWORDS ) newNode=RemoveKeywordsFromLine(x-childrenindex-1,x-childrenindex-1-n-1,keywords,false); AddKeywordsToLine(x-childrenindex,0,x-keywordsindex-1,newNode,false); x-keywordsindex-1=keywords; BTreeDeleteKeywords(x-childrenindex,count); else if( indexn) & (x-childrenindex+1-nMIN_KEYWORDS) ) newNode=RemoveKeywordsFromLine(x-childrenindex+1,0,keywords,true); AddKeywordsToLine(x-childrenindex,x-childrenindex-n,x-keywordsindex,newNode,true); x-keywordsindex=keywords; BTreeDeleteKeywords(x-childrenindex,count); else if(index=0) newNode=RemoveKeywordsFromLine(x,index,keywords,false); BTreeCombine(x-childrenindex,keywords,newNode); BTreeDeleteKeywords(x-childrenindex,count); else newNode=RemoveKeywordsFromLine(x,index-1,keywords,false); BTreeCombine(x-childrenindex-1,keywords,newNode); BTreeDeleteKeywords(x-childrenindex-1,count); else BTreeDeleteKeywords(x-childrenindex,count); newNode=root; while(root-n=0) newNode=root-children0; free(root); root=newNode; （3） 图书管理存储定义void printBTree(sBTree* T); /B树的形式显示当前所有的图书号void printTab();void InsertBook(sBTree *T,sKeywords keywords); /插入新书sKeywords MakeNewBook(); /输入新书的信息void rent(int count); /借书void get(int count); /还书（4）图书管理函数定义sKeywords MakeNewBook() /输入新书的信息 sKeywords keywords; printf(请输入新书编号：n); scanf(%d,&(keywords.count); printf(请输入新书名称：n); scanf(%s,); printf(请输入新书作者：n); scanf(%s,keywords.author); printf(请输入新书数量：n); scanf(%d,&(keywords.allReserves); keywords.reserves=keywords.allReserves;/现有数量等于库存量 return keywords;void InsertBook(sBTree *T,sKeywords keywords) /插入新书 int index; sBTree* x; bool exist=BTreeSearch(T,keywords.count,x,index); if(exist) x-keywordsindex.allReserves+=keywords.allReserves;/库存增加 x-keywordsindex.reserves+=keywords.reserves;/现有量增加 else BTreeInsert(keywords); void rent(int count) /借书，书库中有书号为count的书，借阅成功，否则“查 找 /失败 sBTree* x; int index; if( BTreeSearch(root,count,x,index) & (x-keywordsindex.reserves0) ) x-keywordsindex.reserves-; else printf(查找失败！n);void get(int count) /还书，如果书库中有书号为count的书，则可归还 /若无，则输出“查无此书”。 sBTree* x; int index; if( BTreeSearch(root,count,x,index) ) x-keywordsindex.reserves+; else printf(查无此书！n); void printBTree(sBTree* T) /B树的形式显示当前所有的图书号 if(T=NULL) return; if(T-leaf) for(int i=0;in;i+) printTab(); printf(%dn,T-keywordsi.count); else for(int i=0;in;i+) deep+; printBTree(T-childreni); deep-; printTab(); printf(%dn,T-keywordsi.count); deep+; printBTree(T-childrenT-n); deep-; void printTab() /按制表位输出书号 for(int i=0;ideep;i+) printf(t);（5） 主函数void main() sKeywords keywords;int count; /书号char choice;CreateBTree(); /构建B树printf( nn);printf( 图书管理系统主菜单n);printf( n);printf( 1-采编入库 nn);printf( 2-清除库存 nn);printf( 3-借阅 nn);printf( 4-归还 nn);printf( 5-显示 nn);printf( 6-退出 nn);printf( n);printf( 请选择相应编码:); doscanf(%c,&choice); switch(choice) case 1: /采编入库 keywords=MakeNewBook(); InsertBook(root,keywords); break; case 2: /清除库存 printf(要删除的书编号为：); scanf(%d,&count); BTreeDeleteKeywords(root,count); break; case 3: /借书 printf(要借出的书编号为：); scanf(%d,&count); rent(count); break; case 4: /还书 printf(归还的树编号为： ); scanf(%d,&count); get(count); break; case 5: /退出 printBTree(root); default: break; while(choice!=6);函数调用过程如下图所示：主函数还书借书采编入库清除库存退出构造函数录入信息插入结点 4. 调试分析 调试过程中遇到的问题以及对设计与实现的回顾讨论和分析： 对于本次设计个人感觉难度很大，因为图书管理系统涉及到的功能比较多，采编入库、清除库存、借阅和和归还，其中最难的部分是B树定义和操作以及B树相关操作的调用，书上对于B树这一块的内容比较少，网上B树的基本操作和算法很少，因此在B树的插入和删除算法上花了很多时间，后来通过网上查找资料跟同学讨论得出。此外，因为涉及的算法和代码比较多，很容易出各种各样的错，在编译方面也花了不少时间。 算法的时空分析：这个图书管理系统的存储时建立在内存上的，故程序退出数据得不到保存，每个功能感觉比较独立，相互间联系不算多，想要提高基