数据结构图书管理系统实验报告.doc

数据结构课程设计报告

课程名称_____ ____
题目名称
学生学院
专业班级
学 号
学生姓名
指导教师

2010 年 7 月 8 日

一、 需求分析
1. 图书管理系统中图书管理模块包括图书类型定义：书号、现存量、总存量，出版时间为整型，定价为浮点型，书名、著者名为字符型，借阅指针、预约指针为读者类型；读者类型定义：证号为整型、姓名为字符型，另外借阅类型和预约类型组合成其中的共用体类型。
B树（2-3树）类型定义：关键字个数和关键字数组为整型、另外还有指向双亲的指针、指向子树的指针、记录单元指针；B树查找结果类型定义： 节点指针、关键字序号和查找标志变量为整型。
2. 演示程序以用户和计算机的对话方式进行,在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在后面。该演示系统，没有使用文件，全部数据放在内存存放。四项基本业务都以书号为关键字进行的，采用了B树（2-3树）对书号建立索引，以提高效率。
3. 图书管理系统实现功能：
①采编入库：新书购入，将书号、书名、著者、册数、出版时间添加入图书账目中去，如果这种书在帐中已有，则只将总库存量增加，每新增一个书号则以凹入表的形式显示B树现状。
②清除库存： 实现某本书的全部信息删除操作 ，每清除一个书号则已以凹入表的形式显示B树现状。
③图书借阅： 如果书的库存量大于零时则执行出借，登记借阅者的图书证号和姓名，系统自动抓取当前借阅时间和计算归还时间。
④图书预约：如果某书库存为零，则记录预约者姓名和证号，系统自动抓取当前预约时间和取书时间。
⑤图书归还：注销借阅者信息，并改变该书的现存量。
⑥作者专区：输入作者名字，系统将查找相应作者全部著作并显示出来。
⑦图书信息：可以根据书号查阅此书基本信息、借阅信息和预约信息，亦可以查找全部图书基本信息。
二、 概要设计
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）为关键字的个数
基本操作：
SearchBTree(T ,key);
初始条件：B树T存在，key为和关键字类型相同的给定值。
操作结果：若T中存在关键字等于key的数据元素，则返回该元素的值或在表中的位置，否则返回“空”。
Insert(T, i, k, P, recptr)
初始条件：B树q和p存在，i、k是指定变量，recptr指针有效
操作结果：将k和ap分别插入到q->key[i+1]和q->ptr[i+1],并插入关键字为k的记录recptr
InsertBTree(&T ,e);
初始条件：B树T存在，e为待插入的数据元素。
操作结果：若T中步存在关键字等于e.key的数据元素，则插入e到T中。
DeleteBTree(&T ,key);
初始条件：B树T存在，key为和关键字类型相同的给定值。
操作结果：若T中存在其关键字等于key的数据元素，则删除之
BTreeTraverse(BTree T,Visit)
初始条件：B树T存在，Visit是对T结点的函数
操作结果：遍历B树T，对每个结点调用Visit函数
ShowBTree( T );
初始条件：B树T存在。
操作结果：以凹入表形式显示B树T。
}ADT BTree

2 .系统时间类型定义：
ADT Time{
数据对象：D={TM 是各种整型类型的系统时间格式定义}
数据关系：数据元素同属一个集合
基本操作：
GetDate(tm &tim)
初始条件：系统时间运行
操作结果：获取系统时间，赋予tm变量tim
AddDate(tm &date2,tm date1, int day)
初始条件：系统时间date2、date1、day存在
操作结果：把date1的日期加day天后赋给date2
Earlier(tm date1,tm date2)
初始条件：系统时间date2、date1存在
操作结果：比较data1与date2日期的迟与早，如果date1早于或等于date2则返回TRUE，否则返回FALSE。
}ADT Time

3. 图书管理类型定义：
ADT BTree{
数据对象：D={ai | ai∈BookType，i=1，2，3，……n，n>=0，其中
每个数据元素ai含有类型相同，可惟一标识数据元素的关键字}
数据关系：数据元素同属一个集合
基本操作：
InitLibrary(&L );
操作结果：初始化书库L为空书库。
InsertBook(&L ,B ,result);
初始条件：书库L和B已存在，result包含B书在书库中的位置或应该插入的位置。
操作结果：如果书库中已存在B书，则只将B书的库存量增加，否则插入B书到书库L中。
DeleteBook(&L ,&B);
初始条件：书库L和B存在。
操作结果：如果书库中存在B书，则从书库中删除B书的信息，并返回OK，否则返回ERROR
BorrowBook(L ,&B ,R);
初始条件：书库L存在，B书是书库中的书并且可被读者R借阅。
操作结果：借出一本B书，记录信息。
ReturnBook(L ,&B ,R);
初始条件：书库L存在。
操作结果：若书库L中有读者R借阅B书的记录，则注销该记录，改变B书现存量，并返回OK，书不存在或无该读者记录则返回ERROR。
BespeakBook(L ,&B ,R);
初始条件：书库L存在，B书是书库中的书，R为借阅者。
操作结果：为读者R预约B书。
ListAuthor(L ,author);
初始条件：书库L存在，author为指定作者姓名
操作结果：显示author的所有著作。
ShowBookinfo(L ,B );
初始条件：书L存在。
操作结果：若书库L中存在书B，则显示B书基本信息并返回OK，否则返回ERROR。
PrintAllBooks(L );
初始条件：书库L存在。
操作结果：显示所有图书基本信息。
}ADT BTree
3. 主程序
int main()
{
系统界面；
初始化；
for( ; ; )
{
显示菜单信息；
接受命令；
处理命令；
输出结果；
}
}|
4. 本程序有四个调用模块
主程序模块
↓
图书管理模块
↓ ↓
B树单元模块 系统时间模块
三、 详细设计
《抽象数据类型B树算法详解》
/**************************抽象数据类型 B- 树存储定义*************************/
typedef BookNode Record; //记录指针为图书结点类型
typedef struct BTNode{
int keynum; //结点关键字个数
struct BTNode *parent; //指向双亲指针
int key[m+1]; //关键字数组，0号单元未用
struct BTNode *ptr[m+1]; //指向子树指针
Record *recptr[m+1]; //记录指针，0号单元未用
}BTNode, *BTree; // B树节点类型和B树类型

typedef struct{
BTNode *pt; //指向找到的结点或应该插入的结点
int i; //1...m，在结点中关键字序号
int tag; // 1表示查找成功，0表示查找失败
}Result; // B树查找结果类型
/****************************************************************************/
/**************************B- 树操作定义************************************/
int Search(BTree p, int k)
/* 在B树p中查找关键字k的位置i,使得p->node[i].key≤K＜p->node[i+1].key*/
{
int i;
for(i=0;i<p->keynum && p->key[i+1]<=k;i++);
return i;
}
Result SearchBTree(BTree T, int k)
// 在m阶B树T上查找关键字K，返回结果(pt,i,tag)。若查找成功，则特征值
// tag=1，指针pt所指结点中第i个关键字等于K；否则特征值tag=0，等于K的
// 关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间。
{
Result r;
int i=1;
BTree p=T,q=NULL; // 初始化，p指向待查结点，q指向p的双亲
int found=FALSE;
while(p && !found){
i=Search( p, k); //在p->key[1...keynum]中查找
if(i && p->key[i]==k) found=TRUE; //找到待查关键字
else
{
q=p;
p=p->ptr[i];
}
}
if(found)
{
r.pt=p;
r.i=i;
r.tag=1;
}
else
{
r.pt=q;
r.i=i;
r.tag=0;
}
return r;
}
void Insert(BTree &q, int i, int k, BTree ap, Record *recptr)
// 将k和ap分别插入到q->key[i+1]和q->ptr[i+1],并插入关键字为k的记录recprt
{
for(int j=q->keynum;j>i;--j)
{ // 记录、关键字、子树指针后移
q->key[j+1]=q->key[j];
q->ptr[j+1]=q->ptr[j];
q->recptr[j+1]=q->recptr[j];
}
q->key[i+1]=k; //插入记录、关键字、子树指针，关键字个数加1
q->ptr[i+1]=ap;
q->recptr[i+1]=recptr;
q->keynum++;
if(ap) ap->parent = q; //子树ap的父亲指针
}

void Split(BTree &q, int n, BTree &ap)
// 以n为分界将结点q分裂为两个结点，前一半保留，后一半移入新生结点ap
{
int i;
ap = (BTree)malloc(sizeof(BTNode)); // 申请新结点ap
ap->ptr[0]=q->ptr[n];
for(i = n+1;i <= m; i++) // n后的关键字、子树指针、记录转移到ap
{
ap->key[i-n] = q->key[i];
ap->ptr[i-n] = q->ptr[i];
ap->recptr[i-n] = q->recptr[i];
}
ap->keynum = q->keynum - n; // 计算ap的关键字个数
q->keynum = n-1; // q的关键字个数减少
ap->parent = q->parent;
for (i=0; i<=m-n; i++)
if(ap->ptr[i]) ap->ptr[i]->parent = ap; // ap的子树的父亲指针
}
void NewRoot(BTree &T, BTree p, int k, BTree ap,Record *recptr)
// 当插入B树时T为空或根结点分裂为p和ap两个节点，需建立一个根节点空间
// 本函数为T申请一块空间，插入p,k,ap和记录rec
{
T = (BTree)malloc(sizeof(BTNode));
T->keynum = 1;
T->ptr[0] = p; // 插入
T->ptr[1] = ap;
T->key[1] = k;
T->recptr[1] = recptr;
if (p) p->parent= T; // T的子树ap的父亲指针
if (ap) ap->parent = T;
T->parent = NULL; // 根节点双亲为NULL
}
int InsertBTree(BTree &T, int k, BTree q, int i,Record *recptr)
// 在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K和记录rec。
// 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树。
{
BTree ap = NULL;
int finished = FALSE; // T是空树，生成仅含关键字K的根结点*T
if (!q) NewRoot(T, NULL, k, NULL,recptr);
else{
while (!finished)
{
Insert(q, i, k, ap,recptr); /将k和ap插入到q->key[i+1]和q->ptr[i+1]
if (q->keynum < m) finished = TRUE; // 插入完成
else{
Split(q, (m+1)/2, ap); // 分裂结点q
k = q->key[(m+1)/2];
recptr = q->recptr[(m+1)/2];
if (q->parent)
{ // 在双亲结点*q中查找k的插入位置
q = q->parent;
i = Search(q, k);
}
else finished = OVERFLOW; // 根节点已分裂为*q和*ap两个结点
}
}
if (finished == OVERFLOW) // 根结点已分裂为结点*q和*ap
NewRoot(T, q, k, ap,recptr); // 需生成新根结点*T,q和ap为子树指针
}
return OK;
}
void TakePlace(BTree &q, int &i)
// *q结点的第i个关键字为k，用q的后继关键字替代q，且令q指向后继所在结点
{
BTree p = q;
q = q->ptr[i];
while(q->ptr[0]) q = q->ptr[0]; // 查找p的后继
p->key[i] = q->key[1]; // 关键字代替
p->recptr[i] = q->recptr[1]; // 记录代替
i = 1; // 代替后应该删除q所指结点的第1个关键字
}
void Del(BTree q, int i)
// 删除q所指结点第i个关键字及其记录
{
for(;i < q->keynum ;i++) // 关键字和记录指针前移
{
q->key[i] = q->key[i+1];
q->recptr[i] = q->recptr[i+1];
}
q->keynum --; // 关键字数目减1
}

int Borrow(BTree q)
// 若q的兄弟结点关键字大于(m-1)/2,则从兄弟结点上移最小（或最大）的关键字到双亲结点，
// 而将双亲结点中小于(或大于）且紧靠该关键字的关键字下移至q中,并返回OK，否则返回EREOR。
{
int i;
BTree p = q->parent, b; // p指向q的双亲结点
for(i = 0 ; p->ptr[i] != q;i++) ; // 查找q在双亲p的子树位置
if(i >= 0 && i+1 <= p->keynum && p->ptr[i+1]->keynum > (m-1)/2)
{ // 若q的右兄弟关键字个数大于(m-1)/2
b = p->ptr[i+1]; // b指向右兄弟结点
q->ptr[1] = b->ptr[0]; // 子树指针也要同步移动
q->key[1] = p->key[i+1]; // 从父节点借第i+1个关键字
q->recptr[1] = p->recptr[i+1];
p->key[i+1] = b->key[1]; // b第一个关键字上移到父节点
p->recptr[i+1] = b->recptr[1];
for(i =1 ;i <= b->keynum;i++) // b第一个关键字上移，需把剩余记录前移一位
{
b->key[i] = b->key[i+1];
b->recptr[i] = b->recptr[i+1];
b->ptr[i-1] = b->ptr[i];
}
}
else if(i > 0 && p->ptr[i-1]->keynum > (m-1)/2)
{ // 若q的左兄弟关键字个数大约(m-1)/2
b = p->ptr[i-1]; // b指向左兄弟结点
q->ptr[1] = q->ptr[0];
q->ptr[0] = b->ptr[b->keynum];
q->key[1] = p->key[i]; // 从父节点借第i个关键字
q->recptr[1] = p->recptr[i];
p->key[i] = b->key[b->keynum]; // 将b最后一个关键字上移到父节点
p->recptr[i] = b->recptr[b->keynum];
}
else return ERROR; // 无关键字大于(m-1)/2的兄弟
q->keynum ++;
b->keynum --;
for(i = 0 ;i <=q->keynum; i++)
if(q->ptr[i]) q->ptr[i]->parent = q; // 刷新q的子结点的双亲指针
return OK;
}
void Combine(BTree &q)
// 将q剩余部分和q的父结点的相关关键字合并到q兄弟中,然后释放q，令q指向修改的兄弟
{
int i, j ;
BTree p = q->parent, b; // p指向q的父亲
for(i = 0; p->ptr[i] != q; i++) ; // 插好q在父亲p中的子树位置
if(i == 0) // 如为0，则需合并为兄弟的第一个关键字
{
b = p->ptr[i+1];
for(j = b->keynum ; j >= 0 ;j--) // 将b的关键字和记录后移一位
{
b->key[j+1] = b->key[j];
b->recptr[j+1] = b->recptr[j];
b->ptr[j+1] = b->ptr[j];
}
b->ptr[0] = q->ptr[0]; // 合并
b->key[1] = p->key[1];
b->recptr[1] = p->recptr[1];
}
else if(i > 0) // 若q在父亲的子树位置大约0
{ // 需合并为兄弟b的最后一个关键字
b = p->ptr[i-1];
b->key[b->keynum+1] = p->key[i]; // 合并
b->recptr[b->keynum+1] = p->recptr[i];
b->ptr[b->keynum+1] = q->ptr[0];
}
if(i == 0 || i == 1) // 若i为0或1，需将父节点p关键字前移一位
for( ; i < p->keynum; i++)
{
p->key[i] = p->key[i+1];
p->ptr[i] = p->ptr[i+1];
p->recptr[i] = p->recptr[i+1];
}
p->keynum --;
b->keynum ++;
free(q);
q = b; // q指向修改的兄弟结点
for(i = 0;i <= b->keynum; i++)
if(b->ptr[i]) b->ptr[i]->parent = b; // 刷新b的子结点的双亲指针
}

int DeleteBTree(BTree &T,int k)
// 在m阶B树T上删除关键字k及其对应记录，并返回OK。
// 如T上不存在关键字k，则返回ERROR。
{
int x=k;
BTree q,b = NULL;
int finished = FALSE,i = 1;
Result res = SearchBTree(T,k); // 在T中查找关键字k
if(res.tag == 0 ) return ERROR; // 未搜索到
else
{
q = res.pt; // q指向待删结点
i = res.i;
if(q->ptr[0]) TakePlace(q, i); // 若q的子树不空，(非底层结点)
// 则以其后继代之，且令q指向后继所在结点
Del(q,i); // 删除q所指向结点中第i个关键字及记录
if(q->keynum>=(m-1)/2||!q->parent)// 若删除后关键字个数不小于(m-1)/2或q是根
{
finished = TRUE; // 删除完成
if(q->keynum == 0 ) T = NULL; // 若q的关键字个数为0 ，则为空树
}
while(!finished)
{
if(Borrow(q)) finished = TRUE; // 若q的相邻兄弟结点关键字大于(m-1)/2,则
//从该兄弟结点上移一个最大（或最小）关键字到
// 父节点，从父节点借一关键字到q
else{ // 若q相邻兄弟关键字个数均等于┌m /2┑-1
Combine(q); // 将q中的剩余部分和双亲中的相关关键字合并至q的一个兄弟中
q = q->parent; // 检查双亲
if(q == T && T->keynum ==0 ) // 若被删结点的父节点是根T且T的关键字个数为0
{
T = T->ptr[0]; // 新根
T->parent = NULL;
free(q); // 删除原双亲结点
finished = TRUE;
}
else if(q->keynum >= m/2) finished = TRUE;
} // 合并后双亲关键字个数不少于(m-1)/2，完成
}
}
return OK ;
}
void BTreeTraverse(BTree T,void ( *Visit)(BTree p))
// 遍历B树T，对每个结点调用Visit函数
{
if(!T) return;
Visit(T);
for(int i=0;i<=T->keynum;++i)
if(T->ptr[i])BTreeTraverse(T->ptr[i],Visit);
}

void ShowBTree(BTree T,short x = 8)
// 递归以凹入表形式显示B树T,每层的缩进量为x，初始缩进量为8
{
if(!T) return ;
int i;
printf("\n");
for(i = 0;i<=x;i++) putchar(' '); // 缩进x
for(i = 1 ;i <= T->keynum;i++)
printf("%d,",T->key[i]);
for(i = 0 ;i <= T->keynum;i++) // 递归显示子树结点关键字
ShowBTree(T->ptr[i],x+7);
}
/*****************************************************************************/

/******************************系统时间函数定义*******************************/
void GetDate(tm &tim)
// 获取系统时间，赋予tm结构体变量tim
{
time_t curtime=time(0);
tim = *localtime(&curtime);
tim.tm_year += 1900; // tm 年份少1900年
tim.tm_mon ++; // tm month 从0-11，故加1
}
void AddDate(tm &date2,tm date1, int day)
// 把date1的日期加day天后赋给date2
{
date2.tm_year = date1.tm_year + (day/30 + date1.tm_mon) / 12;
date2.tm_mon = (date1.tm_mon + (day / 30)) % 12;
date2.tm_mday = (date1.tm_mday + day) % 30;
}
int Earlier(tm date1,tm date2)
// 比较data1与date2日期的迟与早，如果date1早于或等于date2则返回TRUE，否则返回FALSE。
{
if(date1.tm_year < date2.tm_year) return TRUE;
if(date1.tm_year > date2.tm_year) return ERROR;
if(date1.tm_mon < date2.tm_mon) return TRUE;
if(date1.tm_mon > date2.tm_mon) return ERROR;
if(date1.tm_mday <date2.tm_mday) return TRUE;
return ERROR;
}
/****************************************************************************/

/****************************图书管理存储定义*******************************/
char *books[MAX_BOOKS]; // 某作者作品数组
char author[MAX_NAME_LEN]; // 某作者姓名
int books_counter; // 某作者作品计数
typedef struct ReaderNode // 借阅者/预约者结点
{
int cardnum; // 证号
char rname[MAX_NAME_LEN]; // 姓名
union{
struct{
tm bordate; // 借书日期
tm retdate; // 还书日期
struct ReaderNode *nextr; // 下一个借阅者指针
};
struct{
tm bespeakdate; // 预约日期
struct ReaderNode *nextb; // 下一个预约者指针
};
};
}ReaderNode,*ReaderType; // 读者类型

typedef struct BookNode // 图书结点
{
int booknum; // 书号
char bookname[MAX_BKNAME_LEN]; // 书名
char writer[MAX_NAME_LEN]; // 作者名
int current; // 现存量
int total; // 总库存
int publishyear; // 出版时间
float price; // 定价
ReaderType reader; // 借阅者链表指针
ReaderType bespeaker; // 预约者链表指针
} BookNode,*BookType; // 图书类型
/*****************************************************************************/

/*****************************图书管理函数定义********************************/
void InitLibrary(BTree &L )
// 初始化书库L为空书库。
{
L = NULL;
}
void InsertBook(BTree &L ,BookType B , Result res)
// 书库L已存在，res包含B书在书库L中的位置或应该插入的位置
// 如果书库中已存在B书，则只将B书的库存量增加，否则插入B书到书库L中。
{
if(res.tag==0) InsertBTree(L, B->booknum, res.pt, res.i, B); // 书库中不存在该书，则插入
else
{
BookType b=res.pt->recptr[res.i];
b->current=b->current+B->total; //现存量增加
b->total=b->total+B->total