数据结构-图书管理系统实验报告.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 // 图书结点