广工数据结构课程设计--图书管理系统.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，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〈Ki+1（i=1，2,……n-1）;Ai（i=0,……n）为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1，2，……n），An所指子树中所有结点的关键字均大于Kn，n（m/2（取上限）—1〈=n〈=m-1）为关键字的个数
基本操作：
CreateBTree(BTree ＊T)
操作结果:构建B—树
BTreeSearch（sBTree ＊T，int k,sBTree＊ ＆x，int ＆index）
初始条件:树T存在，k为和关键字类型相同的给定值。
操作结果：若B树T中存在关键字等k的数据元素，则返回该元素的值或在表中的位置，否则返回“空”.
BTreeInsert(k)
初始条件：B树T存在，k为待插入的数据元素。
操作结果：若T中不存在关键字等于k的数据元素，则插入k到T中。
BTreeDeleteKeywords（sBTree＊ T,k)；
初始条件：B树T存在，k为和关键字相同的给定值。
操作结果:若T中存在其关键字等于k的数据元素，则删除之。
BTreeTraverse（BTree T，Visit）
初始条件:B树T存在,Visit是对T结点的函数
操作结果:遍历B树T，对每个结点调用Visit函数
PrintBTree（sBTree＊ T);
初始条件：书库T存在。
操作结果：以凹入表形式显示B树T。
｝ADT BTree
(2)。图书管理类型定义：
ADT Book｛
数据对象:D=｛ai ｜ ai∈BookType，i=1，2，3，……n，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(）
显示菜单信息；
接受命令；
处理命令;
输出结果；
}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；i<MAX_KIDSNUM;i++)
root—〉children［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 ＆& keywords〈x—>keywords[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；index<x->n；index++）{
if（count〈x—〉keywords［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；i<T—>n；i++）{
printTab(）；
printf（"％d\n"，T—>keywords［i］。count)；
｝
｝
else ｛
for（int i=0；i<T—〉n；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〈deep；i++)
printf（"\t”）;
｝
（5） 主函数
void main（）
｛
sKeywords keywords;
int count; //书号
char choice；
CreateBTree()； //构建B树
printf（” \n\n”）；
printf(” 图书管理系统主菜单\n”）;
printf(” ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n"）；
printf(” ☆ 1-—--采编入库 ☆\n\n”)；
printf（" ☆ 2---—清除库存 ☆\n\n”）;
printf（” ☆ 3-——-借阅 ☆\n\n");
printf（” ☆ 4—--—归还 ☆\n\n"）；
printf（” ☆ 5-———显示 ☆\n\n”);
printf(" ☆ 6—--—退出 ☆\n\n"）;
printf（” ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n”)；
printf(" 请选择相应编码：")；
do{
scanf("％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树的插入和删除算法上花了很多时间,后来通过网上查找资料跟同学讨论得出。此外,因为涉及的算法和代码比较多，很容易出各种各样的错,在编译方面也花了不少时间.
⑵算法的时空分析：
这个图书管理系统的存储时建立在内存上的，故程序退出数据得不到保存，每个功能感觉比较独立，相互间联系不算多，想要提高基本操作和算法的效率只能通过在算法的设计以及存储结构上下功夫.
⑶经验和体会：
《数据结构》这门课程考验的不仅仅是人的思维，更多的是考验人的耐心和洞察力，想要学好这一门课程，掌握基本要领，以及编写出执行能力各方面都强的程序需要花更多的时间去钻研；在编写过程中，会出现各种各样细节上的问题,大到一条算法，小到一个“="与“=="或者是“;”与“；”都可能成为你的障碍,细心和牢固的基础知识很重要。
5。 用户使用说明
1. 本程序运行环境为VC 6。0,执行文件为:图书管理系统。exe；
2. 程序界面与菜单信息
选择1:采编入库 ，新书购入,将书号、书名、著者、册数、出版时间添加入图书账目中去，如果这种书在帐中已有，则只将总库存量增加，每新增一个书号则以凹入表的形式显示B树现状。
选择2:清除库存,实现某本书的全部信息删除操作 ，没清除一个书号则已以凹入表的形式显示B树现状。
选择3:图书借阅，如果书的库存量大于零时则执行出借，登记借阅者的图书证号和姓名，系统自动抓取当前借阅时间和计算归还时间.
选择4：图书归还,注销借阅者信息，并改变该书的现存量.
选择5：显示输出。
选择6：安全退出.
6. 测试结果
测试数据：
入库书号：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树形式显示：
（3)分别删除书号45、90、50、22、42
（4） 删除后以B树形式显示剩下所有的书号
（5） 当只向系统中录入书号为35的书时，以下为借书号为12和书号为35、还书号为12和还书号为35的运行情况（成功和失败的测试结果）
7。 附录
提交源程序软盘
程序文件名清单：