📄 tushuguanguanli.txt
字号:
#include<dos.h>
#include<stdio.h>
#include<conio.h>
#define m 3 /* 定义为3阶B-树 */
#define FALSE 0
#define TRUE 1
typedef struct Booknode
{
int key; /* 图书的书号 */
char bname[20]; /* 书名 */
char writter[20]; /* 著者 */
int left; /* 现存量 */
int total; /* 总存量 */
}Book; /* 定义图书的结点 */
typedef struct BTNode
{
int keynum; /* 定义结点的个数，即结点的大小 */
struct BTNode *parent; /* 指向双亲结点 */
Book key[m+1]; /* 图书向量，0号单元未用 */
struct BTNode *ptr[m+1]; /* 子树指针向量 */
}BTNode; /* 定义B-树的结点 */
typedef struct Borrower
{
char number[20]; /* 借阅者的图书证号 */
int year;
int month;
int day; /* 借阅日期 */
int deadline;
Book key; /* 所借图书内容 */
struct Borrower *next; /* 下个借阅者 */
}Borrower; /* 定义借阅者的结点 */
typedef BTNode *BTree;
typedef struct seenode
{
BTNode *pt; /* 定义找到的结点 */
int i; /* 1...m,在结点中的关键字序号 */
int tag; /* 1：查找成功；0：查找失败 */
}Result; /* 定义查找结果的结点 */
int Search(BTree p,int k) /* 在结点p中寻找关键字为k，并返回k所在的位置 */
{
int i;
for(i=1;i<=p->keynum;i++)
if(p->key.key>k)break;
i--;
return(i);
}
Result *SearchBTree(BTree T,int k) /* 在B-树T中寻找关键字为k,并返回查找结果 */
{
int i,found;
BTree p,q;
Result *x;
p=(BTree)malloc(sizeof(BTNode));
p=T; /* 先令p等于树根 */
q=(BTree)malloc(sizeof(BTNode));
q=NULL;
found=FALSE; /*为找之前，令found的值为假 */
i=0;
while(p->keynum!=0&&found==FALSE)
{
i=Search(p,k); /* 在p中查找关键字为k的位置 */
if(i>0&&p->key.key==k)found=TRUE; /* 如果找到，令found的值为真 */
else
{
q=p;
p=p->ptr; /* 如果还没找到，就p的子树找 */
}
}
x=(Result*)malloc(sizeof(Result));
if(found==TRUE){x->pt=p;x->i=i;x->tag=1;} /* 找到所找的结点 */
else {x->pt=q;x->i=i;x->tag=0;} /* 没找到 */
return(x);
}
BTree Newroot(BTree T,Book x,BTree ap) /* 重新创建新的根结点 */
{
BTree Root;
int i;
Root=(BTree)malloc(sizeof(BTNode));
Root->keynum=T->keynum;
Root->parent=T->parent;
Root->ptr[0]=T->ptr[0];
Root->ptr[0]->parent=Root;
for(i=1;i<=Root->keynum;i++)
{
Root->key=T->key;
Root->ptr=T->ptr;
Root->ptr->parent=Root;
} /* 获取原来树的内容 */
free(T);
T=(BTree)malloc(sizeof(BTNode)); /* 重新创建新的根结点 */
T->keynum=1;
T->key[1]=x;
T->parent=NULL;
T->ptr[0]=Root; /* 原来根结点作为新的根结点的子树 */
T->ptr[0]->parent=T;
T->ptr[1]=ap;
T->ptr[1]->parent=T;
return(T);
}
BTree Insert(BTree q,int i,Book x,BTree ap) /* 在q中插入关键字为x的图书 */
{
int j;
q->keynum++;
for(j=q->keynum;j>i+1;j--)
{
q->key[j]=q->key[j-1];
q->ptr[j]=q->ptr[j-1];
q->ptr[j]->parent=q;
}
q->key[i+1]=x;
q->ptr[i+1]=ap;
q->ptr[i+1]->parent=q;
return(q);
}
BTree split(BTree q,BTree ap) /*将结点q分裂为q和ap */
{
int i,s;
s=(m+1)/2;
ap=(BTree)malloc(sizeof(BTNode));
ap->parent=NULL;
ap->keynum=m-s;
for(i=s+1;i<=m;i++)
ap->key[i-s]=q->key;
for(i=s;i<=m;i++)
{
ap->ptr[i-s]=q->ptr;
ap->ptr[i-s]->parent=ap;
} /* 分裂得到ap的内容 */
for(i=s;i<=m;i++)
{
/*q->key=NULL;*/
q->ptr=NULL;
}
q->keynum=s-1; /* 分裂得到q的内容 */
return(ap);
}
BTree InsertBTree(BTree T,Book k) /* 在树中插入关键字为k的图书 */
{
int i,finished,s;
BTree q,ap;
Result *out;
Book x;
/*out=(Result*)malloc(sizeof(Result));*/
out=SearchBTree(T,k.key); /*在树中查找书号为k->key的图书 */
if(out->tag==1){cprintf("\nThis book is exist!\n");getch();return(T);} /* 如果该书存在打印出“这本书已经存在” */
else{ /* 否则进行插入 */
x=k;
ap=(BTree)malloc(sizeof(BTNode));
ap->parent=NULL;
ap->keynum=0;
finished=FALSE; /* 还未插入前finished的值为假 */
q=(BTree)malloc(sizeof(BTNode));
q=out->pt; /* q为要插入的结点 */
i=out->i;
while(q->keynum!=0&&finished==FALSE) /* 只要没完成插入，就继续插入 */
{
q=Insert(q,i,x,ap); /* q为插入后的结点 */
if(q->keynum<m)finished=TRUE; /* 插入完成 */
else /* 分裂结点q */
{
s=(m+1)/2;
x=q->key[s];
ap=split(q,ap);
q=q->parent; /* 插入双亲结点 */
if(q->keynum!=0)i=Search(q,x.key); /*在双亲结点q中查找x的插入位置 */
}
}
if(finished==FALSE)T=Newroot(T,x,ap); /*T是空树，或根结点已分裂为结点q和ap */
return(T);
}
}
int display(int x,int y,BTree s,int length) /* 将B-树已凹入表形式显示出来 */
{
BTree p;
int i,j;
if(s->keynum!=0)
{
for(i=1;i<=s->keynum;i++)
{
gotoxy(x,y);
cprintf("%3d",s->key.key);
y+=1;
for(j=1;j<=length;j++)
putch(223);
if(y==16){gotoxy(x,y);cprintf("ress any key to continue...");getch();y=1;clrscr();}
}
for(i=0;i<=s->keynum;i++)
{
p=s->ptr;
y=display(x,y,p,length/2);
}
}
return y;
}
BTree Unite(BTree T,BTree p,BTree y) /* 结点合并 */
{
BTree t,l,ap,last;
int u,v,w,j,a,finish,s,i;
Book x;
t=p->parent;
u=1+p->keynum;
if(t->keynum==0){T=y;T->parent->keynum=0;} /* 如果父亲结点为空，则将合并后的结点改为根结点 */
else
{
if(p->keynum!=0)v=Search(t,p->key[p->keynum].key);
else v=Search(t,y->key[y->keynum].key);
if(v!=0)
{
l=t->ptr[v-1];
w=l->keynum;
l->key[l->keynum+1]=t->key[v];
l->keynum+=1;
for(j=l->keynum+1;j<=l->keynum+p->keynum;j++)
l->key[j]=p->key[j-l->keynum];
l->keynum=l->keynum+p->keynum;
for(j=w+1;j<=w+u;j++)
{
l->ptr[j]=y;
y->parent=l;
l->ptr[j]->parent=l;
}
for(j=v;j<t->keynum;j++)
{
t->key[j]=t->key[j+1];
t->ptr[j]=t->ptr[j+1];
t->ptr[j]->parent=t;
}
t->keynum-=1;
if(l->keynum>=m)
{
finish=FALSE;
ap=(BTree)malloc(sizeof(BTNode));
ap->parent=NULL;
ap->keynum=0;
while(l->keynum!=0&&finish==FALSE)
{
s=(m+1)/2;
x=l->key[s];
ap=split(l,ap);
last=l;
l=l->parent;
if(l->keynum!=0){i=Search(l,x.key);l=Insert(l,i,x,ap);}
if(l->keynum<m&&l->keynum!=0){finish=TRUE;l=last;}
}
if(finish==FALSE){T=Newroot(last,x,ap);l=T;}
}
if(t->keynum==0)T=Unite(T,t,l);
}
else
{
l=t->ptr[1];
for(j=l->keynum+1+p->keynum;j>1+p->keynum;j--)
{
l->key[j]=l->key[j-1-p->keynum];
l->ptr[j]=l->ptr[j-1-p->keynum];
l->ptr[j]->parent=l;
}
l->ptr[1+p->keynum]=l->ptr[0];
l->ptr[1+p->keynum]->parent=l;
for(j=1;j<=p->keynum;j++)
l->key[j]=p->key[j];
l->key[1+p->keynum]=t->key[1];
for(j=0;j<1+p->keynum;j++)
{
l->ptr[j]=y;
y->parent=l;
l->ptr[j]->parent=l;
}
l->keynum=l->keynum+1+p->keynum;
for(j=1;j<t->keynum;j++)
{
t->key[j]=t->key[j+1];
t->ptr[j]=t->ptr[j+1];
t->ptr[j]->parent=t;
}
t->keynum-=1;
if(l->keynum>=m)
{
finish=FALSE;
ap=(BTree)malloc(sizeof(BTNode));
ap->parent=NULL;
ap->keynum=0;
while(l->keynum!=0&&finish==FALSE)
{
s=(m+1)/2;
x=l->key[s];
ap=split(l,ap);
last=l;
l=l->parent;
if(l->keynum!=0){i=Search(l,x.key);l=Insert(l,i,x,ap);}
if(l->keynum<m&&l->keynum!=0){finish=TRUE;l=last;}
}
if(finish==FALSE){T=Newroot(last,x,ap);l=T;}
}
if(t->keynum==0)T=Unite(T,t,l);
else
{
t->ptr[0]=l;
t->ptr[0]->parent=t;
}
}
}
return(T);
}
BTree DeleteBTree(BTree T,int k) /* 注销无价值的图书，其书号为k */
{
Result *out;
BTree q,small,p,y;
int i,j,o;
Book x;
if(T->keynum==0){cprintf("\nNo imformation on the tree!\n");getch();return(T);} /* 树中没有任何内容 */
else
{
out=SearchBTree(T,k); /* 在树中查找书号为k的位置 */
if(out->tag==0) /* 找不到要找的书 */
{
cprintf("\nThis book is not existant!\n");
getch();
return(T);
}
else
{
q=(BTree)malloc(sizeof(BTNode));
q=out->pt; /* q为要找的图书所在的结点 */
i=out->i;
if(q->ptr->keynum!=0) /* q为非终端结点时，删除比所删书号大的最小关键字 */
{
small=q->ptr;
while(small->ptr[0]->keynum!=0)
small=small->ptr[0];
x=small->key[1];
T=DeleteBTree(T,small->key[1].key);
out=SearchBTree(T,k);
q=out->pt;
i=out->i;
q->key=x;
return(T);
}
else
{
if(q->keynum>=(m+1)/2) /* 被删关键字所在结点的关键字数目不小于 (m+1)/2的情形 */
{
for(j=i;j<q->keynum;j++)
{
q->key[j]=q->key[j+1];
q->ptr[j]=q->ptr[j+1];
} /* 删除关键字及相邻指针 */
q->ptr[q->keynum]=NULL;
/* q->key[q->keynum]=NULL;*/
q->keynum--; /* 将所在结点数目减一 */
return(T);
}
else
{
p=q->parent;
o=Search(p,q->key.key);
if(p->keynum==0&&q->ptr[o]->keynum==0) /* 只有树结点的情形 */
{
for(j=i;j<q->keynum;j++)
{
q->key[j]=q->key[j+1];
q->ptr[j]=q->ptr[j+1];
q->ptr[j]->parent=q;
}
q->ptr[q->keynum]->keynum=0; /* 删除关键字及相邻指针 */
q->keynum--; /* 将所在结点数目减一 */
return(T);
}
else{
if(o<p->keynum&&p->ptr[o+1]->keynum>(m-1)/2) /* 有右兄弟并且右兄弟关键字数目大于(m-1)/2 */
{
q->key=p->key[o+1];
p->key[o+1]=p->ptr[o+1]->key[1];
p->ptr[o+1]->ptr[0]=p->ptr[o+1]->ptr[1]; /* 将双亲结点的紧靠的关键字下移至被删结点 */
for(j=1;j<p->ptr[o+1]->keynum;j++)
{
p->ptr[o+1]->key[j]=p->ptr[o+1]->key[j+1];
p->ptr[o+1]->ptr[j]=p->ptr[o+1]->ptr[j+1];
}
p->ptr[o+1]->ptr[p->ptr[o+1]->keynum]=NULL;
/*p->ptr[o+1]->key[p->ptr[o+1]->keynum]=NULL;*/ /* 将右兄弟中最小关键字上移至双亲结点 */
p->ptr[o+1]->keynum--;
return(T);
}
else if(o!=0&&p->ptr[o-1]->keynum>(m-1)/2) /* 有左兄弟并且左兄弟关键字数目大于(m-1)/2 */
{
q->key=p->key[o];
p->key[o]=p->ptr[o-1]->key[p->ptr[o-1]->keynum]; /* 将双亲结点的紧靠的关键字下移至被删结点 */
p->ptr[o-1]->ptr[p->ptr[o-1]->keynum]=NULL;
/*p->ptr[o-1]->key[p->ptr[o-1]->keynum]=0; */ /* 将左兄弟中最小关键字上移至双亲结点 */
p->ptr[o-1]->keynum--;
return(T);
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -