^.
数据结构课程设计报告
题目：图书管理系统
学 院 计算机学院
专 业
年级班别
学 号
学生姓名
指导教师
成 绩 ____________________
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,42
2. 概要设计
（1）.抽象数据类型B树定义：
ADT BTree{
数据对象：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字。
数据关系：数据元素同属于一个集合并且：
一棵m阶的B树，或为空，或为满足下列特性的m叉树：
树中每个结点至多有m棵子树；
若根结点不是叶子结点，则至少有两棵子树；
除根之外的所有非终端结点至少有m/2（取上限）棵子树；
所有的非终端结点包含下列信息数据：
(n,A0,K1,A1,K2,A2,K3,……,Kn,An)
其中：Ki（i=1，2，……n）为关键字，且Ki
=0，其中
每个数据元素ai含有类型相同，可惟一标识数据元素的关键字}
数据关系：数据元素同属一个集合
基本操作：
InsertBook(sBTree *T,sKeywords keywords)
初始条件：B树T已存在。
操作结果：如果所要插入的书中已存在T树中，则只将该书的库存量增加，否则插入到T树中。
Rent(k)
初始条件：书库不为空。
操作结果：如果书库中有书号为k的书，则借书成功，否则返回查找失败。Get(k)
初始条件：书库不为空。
操作结果：如果书库中有书号为k的书，则还书成功，否则返回查无此书。
}ADT Book
（3）主程序
int main()
{ 初始化
系统界面；
do
{ switch()
显示菜单信息；
接受命令；
处理命令；
输出结果；
}while
}
3. 详细设计
（1）抽象数据类型 B- 树存储定义:
struct sBTree{
int n;//关键字的计量
sKeywords keywords[MAX_KEYWORDS];//关键字的最大容量
bool leaf; //判断是否为叶子
sBTree* children[MAX_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;ichildren[i]=NULL;
}
bool BTreeSearch(sBTree *T,int count,sBTree* &x,int &index)
{//查找操作
int i=0;
while( i<(T->n) && count>(T->keywords[i].count) )
i++;
if( i<(T->n) && count==(T->keywords[i].count) ){
x=T;
index=i;
return true;
}
if(T->leaf)
return false;
else
return BTreeSearch(T->children[i],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->children[0]=r;
BTreeSplitChild(newNode,0);
BTreeInsertNonfull(newNode,keywords);
}
else
BTreeInsertNonfull(r,keywords);
}
void BTreeInsertNonfull(sBTree* x,sKeywords keywords)
{
int i=(x->n);
while( i>0 && keywordskeywords[i-1] )
i--;
if(x->leaf)
AddKeywordsToLine(x,i,keywords,NULL,true);
else{
if( x->children[i]->n==MAX_KEYWORDS ){
BTreeSplitChild(x,i);
if( keywords>x->keywords[i] )
i++;
}
BTreeInsertNonfull(x->children[i],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->children[index]->n) > MIN_KEYWORDS ){
keywords=MaxKeywords(x->children[index]);
x->keywords[index]=keywords;
BTreeDeleteKeywords(x->children[index],keywords.count);
}
else if( (x->children[index+1]->n) > MIN_KEYWORDS ){
keywords=MinKeywords(x->children[index+1]);
x->keywords[index]=keywords;
BTreeDeleteKeywords(x->children[index+1],keywords.count);
}
else{
newNode=RemoveKeywordsFromLine(x,index,keywords,false);
BTreeCombine(x->children[index],keywords,newNode);
BTreeDeleteKeywords(x->children[index],count);
}
}
else{
for(index=0;indexn;index++){
if(countkeywords[index].count)
break;
}
if(x->children[index]->n==MIN_KEYWORDS){
if( index>0 && (x->children[index-1]->n)>MIN_KEYWORDS ){
newNode=RemoveKeywordsFromLine(x->children[index-1],x->children[index-1]->n-1,keywords,false);
AddKeywordsToLine(x->children[index],0,x->keywords[index-1],newNode,false);
x->keywords[index-1]=keywords;
BTreeDeleteKeywords(x->children[index],count);
}
else if( index<(x->n) && (x->children[index+1]->n>MIN_KEYWORDS) )
{
newNode=RemoveKeywordsFromLine(x->children[index+1],0,keywords,true);
AddKeywordsToLine(x->children[index],x->children[index]->n,x->keywords[index],newNode,true);
x->keywords[index]=keywords;
BTreeDeleteKeywords(x->children[index],count);
}
else{
if(index==0){
newNode=RemoveKeywordsFromLine(x,index,keywords,false);
BTreeCombine(x->children[index],keywords,newNode);
BTreeDeleteKeywords(x->children[index],count);
}
else{
newNode=RemoveKeywordsFromLine(x,index-1,keywords,false);
BTreeCombine(x->children[index-1],keywords,newNode);
BTreeDeleteKeywords(x->children[index-1],count);
}
}
}
else{
BTreeDeleteKeywords(x->children[index],count);
}
}
newNode=root;
while(root->n==0){
newNode=root->children[0];
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",keywords.name);
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->keywords[index].allReserves+=keywords.allReserves;//库存增加
x->keywords[index].reserves+=keywords.reserves;//现有量增加
}
else{
BTreeInsert(keywords);
}
}
void rent(int count) //借书，书库中有书号为count的书，借阅成功，否则“查 找
//失败
{
sBTree* x;
int index;
if( BTreeSearch(root,count,x,index) && (x->keywords[index].reserves>0) )
x->keywords[index].reserves--;
else
printf("查找失败！\n");
}
void get(int count) //还书，如果书库中有书号为count的书，则可归还
{ //若无，则输出“查无此书”。
sBTree* x;
int index;
if( BTreeSearch(root,count,x,index) )
x->keywords[index].reserves++;
else
printf("查无此书！\n");
}
void printBTree(sBTree* T) //B树的形式显示当前所有的图书号
{
if(T==NULL)
return;
if(T->leaf){
for(int i=0;in;i++){
printTab();
printf("%d\n",T->keywords[i].count);
}
}
else {
for(int i=0;in;i++){
deep++;
printBTree(T->children[i]);
deep--;
printTab();
printf("%d\n",T->keywords[i].count);
}
deep++;
printBTree(T->children[T->n]);
deep--;
}
}
void printTab() //按制表位输出书号
{
for(int i=0;i
展开阅读全文
相关搜索