📄 bptree.cpp
字号:
#include <stdio.h>
#include <stdlib.h>
void menu(void);
struct PAIR
{
long key;
//char file[60];
char * pp;
} ;
struct bpnode
{
struct PAIR rec[5]; //纪录数组
struct bpnode *pa;
struct bpnode *lbro;
struct bpnode *rbro;
int numrec;
struct bpnode * pt[4];
} ;
typedef struct bpnode * BP;
// struct bpnode * root=NULL;
//struct bpnode * back;
struct biback
{
BP back;
long data;
};
BP back1=NULL;
long data1=-1;
BP nnode=NULL;
struct PAIR x[100];
struct PAIR y[100];
struct bpnode * nroot=NULL;
void paixu(BP roo,long key,char * file)
{
long mem[5];
char * parray[5];
int cc=roo->numrec;
for(int i=0;i<cc-1;i++)
{
mem[i]=roo->rec[i].key;
parray[i]=roo->rec[i].pp;
}
mem[cc-1]=key; parray[cc-1]=file;
for(int j=cc-2;j>=0;j--)
for(int k=0;k<=j;k++)
{if(mem[k]>mem[k+1])
{ long med=mem[k];
char * medp=parray[k];
mem[k]=mem[k+1];
mem[k+1]=med;
parray[k]=parray[k+1];
parray[k+1]=medp;
}
}
for(int kk=0;kk<cc;kk++)
{ roo->rec[kk].key=mem[kk];
roo->rec[kk].pp=parray[kk];
}
} // 对节点内纪录按关键码排序
void crack(BP roo,struct bpnode* neo,struct PAIR record)
{ long mem[6];
char * parray[6];
for(int i=0;i<5;i++)
{ mem[i]=roo->rec[i].key;
parray[i]=roo->rec[i].pp;
}
mem[5]=record.key; parray[5]=record.pp;
for(int j=4;j>=0;j--)
for(int k=0;k<=j;k++)
{if(mem[k]>mem[k+1])
{ long med=mem[k];
char * medp=parray[k];
mem[k]=mem[k+1];
mem[k+1]=med;
parray[k]=parray[k+1];
parray[k+1]=medp;
}
}
for(int kk=0;kk<3;kk++)
{ roo->rec[kk].key=mem[kk];
roo->rec[kk].pp=parray[kk];
}
for(int jj=0;jj<3;jj++)
{ neo->rec[jj].key=mem[jj+3];
neo->rec[jj].pp=parray[jj+3];
}
}// 节点分裂后均分纪录
//struct bpnode *
struct biback insert(BP &root,struct PAIR record, BP & retptr,long &retkey)
{
long myretv=0;
struct bpnode * myretp;
myretp=NULL;
if(root==NULL){
root=(struct bpnode*)malloc(sizeof(struct bpnode));
root->rec[0].key=record.key;
root->numrec=1;
root->pa=NULL;
root->lbro=NULL;
root->rbro=NULL;
root->pt[0]=NULL;
root->pt[1]=NULL;
root->pt[2]=NULL;
root->pt[3]=NULL; //初始化
//for(int count=0;count<60;count++)
//{ root->rec[0].file[count]=record.file[count];}
root->rec[0].pp=record.pp;
}
else{
if(root->pt[0]==NULL)
{//叶子节点
if(root->numrec!=5){//只有一个关键码
root->numrec+=1;
paixu(root,record.key,record.pp);
} //叶子节点纪录数未满,直接插入
else {//关键码满，分裂提升
retptr=(struct bpnode*)malloc(sizeof(struct bpnode));//申请L'节点
retptr->pa=NULL;
retptr->lbro=NULL;
retptr->rbro=NULL;
retptr->pt[0]=NULL;
retptr->pt[1]=NULL;
retptr->pt[2]=NULL;
retptr->pt[3]=NULL;
crack(root,retptr,record);
retkey=retptr->rec[0].key;
root->numrec=3;retptr->numrec=3;//置L和L'关键码数为1
if(root->rbro==NULL)
{
root->rbro=retptr;
retptr->lbro=root;
}
else
{retptr->rbro=root->rbro;
root->rbro->lbro=retptr;
root->rbro=retptr;
retptr->lbro=root;
}
}
}//叶子节点结束
else {//非叶子节点小于左关键码值搜寻左子树*/
if(root->numrec==1)
{
if(record.key<root->rec[0].key) insert(root->pt[0],record, myretp,myretv);
else insert(root->pt[1],record,myretp,myretv);
/*子树为2叉或小于右关键码搜寻中间子树*/
}
else if(root->numrec==2)
{
if(record.key<root->rec[0].key) insert(root->pt[0],record, myretp,myretv);
else if (record.key>=root->rec[0].key&&record.key<root->rec[1].key)
insert(root->pt[1],record,myretp,myretv);
else insert(root->pt[2],record,myretp,myretv);
/*子树为2叉或小于右关键码搜寻中间子树*/
}
else if(root->numrec==3)
{
if(record.key<root->rec[0].key) insert(root->pt[0],record, myretp,myretv);
else if (record.key>=root->rec[0].key&&record.key<root->rec[1].key)
insert(root->pt[1],record,myretp,myretv);
else if (record.key>=root->rec[1].key&&record.key<root->rec[2].key)
insert(root->pt[2],record,myretp,myretv);
else insert(root->pt[3],record,myretp,myretv);
/*子树为2叉或小于右关键码搜寻中间子树*/
}
} //对应非叶子节点else
if(myretp!=NULL){// 有孩子节点分裂而形成提升
if(root->numrec==3&&root->pt[0]!=NULL){//分裂并提升父节点
retptr=(struct bpnode*)malloc(sizeof(struct bpnode));
retptr->pa=NULL;
retptr->lbro=NULL;
retptr->rbro=NULL;
retptr->pt[0]=NULL;
retptr->pt[1]=NULL;
retptr->pt[2]=NULL;
retptr->pt[3]=NULL;
root->numrec=2;retptr->numrec=1;
//************************
if(root->rbro==NULL)
{
root->rbro=retptr;
retptr->lbro=root;
}
else
{retptr->rbro=root->rbro; // 同层节点链接
root->rbro->lbro=retptr;
root->rbro=retptr;
retptr->lbro=root;
}
//****************************
if(myretv<root->rec[0].key)
{//*提升左关键码
retkey=root->rec[1].key;//*返回值
retptr->rec[0].key=root->rec[2].key;
//*root为L
root->rec[1].key=root->rec[0].key;
root->rec[0].key=myretv;
retptr->pt[0]=root->pt[2];
retptr->pt[1]=root->pt[3];
root->pt[2]=root->pt[1];
root->pt[1]=myretp; //指向L'
//*********************
root->pt[0]->pa=root;
root->pt[1]->pa=root;
root->pt[2]->pa=root;
retptr->pt[0]->pa=retptr; //父指针赋值
retptr->pt[1]->pa=retptr;
}
else if(myretv>=root->rec[0].key&&myretv<root->rec[1].key)
{ //提升中间点
retkey=root->rec[1].key;
retptr->rec[0].key=root->rec[2].key;//L'键
root->rec[1].key=myretv;
retptr->pt[0]=root->pt[2];
retptr->pt[1]=root->pt[3];
root->pt[2]=myretp;
root->pt[0]->pa=root;
root->pt[1]->pa=root;
root->pt[2]->pa=root; //父指针赋值
retptr->pt[0]->pa=retptr;
retptr->pt[1]->pa=retptr;
}
else if(myretv>=root->rec[1].key&&myretv<root->rec[2].key)
{ //提升中间点
retkey=myretv;
retptr->rec[0].key=root->rec[2].key;//L'键
retptr->pt[0]=myretp;
retptr->pt[1]=root->pt[3];
root->pt[0]->pa=root;
root->pt[1]->pa=root;
root->pt[2]->pa=root;
retptr->pt[0]->pa=retptr; //父指针赋值
retptr->pt[1]->pa=retptr;
}
else
{ retkey=root->rec[2].key;
retptr->rec[0].key=myretv;//L'键
retptr->pt[0]=root->pt[3];
retptr->pt[1]=myretp;
root->pt[0]->pa=root;
root->pt[1]->pa=root;
root->pt[2]->pa=root;
retptr->pt[0]->pa=retptr; //父指针赋值
retptr->pt[1]->pa=retptr;
}
}//对应提升父节点
else
{//root节点内键未满，可增加一个
root->numrec+=1;
if(root->numrec==2)
{
if(myretv<root->rec[0].key){
root->rec[1].key=root->rec[0].key;
root->rec[0].key=myretv;
root->pt[2]=root->pt[1];
root->pt[1]=myretp;
}
else{
root->rec[1].key=myretv;
root->pt[2]=myretp;
}
}//对应root->numrec=2
if(root->numrec==3)
{
if(myretv<root->rec[0].key){
root->rec[2].key=root->rec[1].key;
root->rec[1].key=root->rec[0].key;
root->rec[0].key=myretv;
root->pt[3]=root->pt[2];
root->pt[2]=root->pt[1];
root->pt[1]=myretp;
}
else if( myretv>=root->rec[0].key&&myretv<root->rec[1].key)
{
root->rec[2].key=root->rec[1].key;
root->rec[1].key=myretv;
root->pt[3]=root->pt[2];
root->pt[2]=myretp;
}
else
{
root->rec[2].key=myretv;
root->pt[3]=myretp;
}
} //对应root->numrec=3
}//对应else root内节点未满
} //对应有孩子节点分裂提升
} //对应root 非空的else
struct biback bi;
bi.back=retptr;
bi.data=retkey;
return bi;
} //插入函数
void menu(void)
{
printf(" 1插入记录 \n"
" 2删除记录 \n"
" 3列表显示 \n"
" 4范围检索 \n"
" 5精确检索 \n"
" 6显示结构 \n"
" 7退出系统 \n"
);
printf("请选择:");
} // 菜单
void display (struct bpnode * root)
{ if(root==NULL)
return;
if(root->pt[0]==NULL)
{ while(root)
{ for(int c1=0; c1<root->numrec;c1++)
printf(" 关键码:%-20ld 文件名:%s\n",root->rec[c1].key,root->rec[c1].pp);
root=root->rbro;
}
}
else
display(root->pt[0]);
}
void delet(BP root,long del)
{
int mark=0;
int u=0;
long end=0;
while(root->pt[0]!=NULL)
{
root=root->pt[0];
}
if(root->pt[0]==NULL)
{
while(root)
{ for(int c1=0; c1<root->numrec;c1++)
{
y[mark+c1].key=root->rec[c1].key;
y[mark+c1].pp=root->rec[c1].pp;
}
mark=mark+(root->numrec);
root=root->rbro;
}
for(int he=0;he<mark;he++)
{ if(y[he].key==del&&he!=(mark-1)){ u=1;he++;}
if(y[he].key==del&&he==(mark-1)){ u=1;continue;}
x[he-u].key=y[he].key;
x[he-u].pp=y[he] .pp;
}
for(int hh=0;hh<mark-u;hh++)
{ data1=-1;
back1=NULL;
struct biback rre=insert(nroot,x[hh],back1,data1);
if(rre.back)
{ nnode=(struct bpnode * )malloc(sizeof(struct bpnode));
nnode->pa=NULL;
nnode->lbro=NULL;
nnode->rbro=NULL;
nnode->pt[0]=NULL;
nnode->pt[1]=NULL;
nnode->pt[2]=NULL;
nnode->pt[3]=NULL;
nnode->numrec=1;
nnode->rec[0].key=rre.data;
nnode->pt[0]=nroot;
nnode->pt[1]=rre.back;
nroot=nnode;
}
}
} return;
}
void find(BP root,long bit,long big)
{
while(root->pt[0]!=NULL){root=root->pt[0];}
printf("检索范围纪录:\n");
if(root->pt[0]==NULL)
{ while(root)
{ for(int c1=0; c1<root->numrec;c1++)
{ if(root->rec[c1].key>=bit&&root->rec[c1].key<=big)
printf(" 关键码:%-20ld 文件名:%s\n",root->rec[c1].key,root->rec[c1].pp);
}
root=root->rbro;
}
}
}
void findkey(BP root,long fkey)
{ int w=0;
while(root->pt[0]!=NULL){root=root->pt[0];}
if(root->pt[0]==NULL)
{ while(root)
{ for(int c1=0; c1<root->numrec;c1++)
{ if(root->rec[c1].key==fkey)
{printf(" 关键码:%-20ld 文件名:%s\n",root->rec[c1].key,root->rec[c1].pp);
w=1;
}
}
root=root->rbro;
}
}
if(w==0)printf("不存在\n");
}
void str(BP root)
{
int dd=0,ll=0;
if(root==NULL)return;
while(root)
{
BP root1=root;
while(root1)
{ if(root1->pt[0]!=NULL)
{
for(int c1=0; c1<root1->numrec;c1++)
printf(" 关键码:%ld**",root1->rec[c1].key);
printf("||");
root1=root1->rbro;
}
else
{ for(int c1=0; c1<root1->numrec;c1++)
printf(" 关键码:%ld 文件名:%s**",root1->rec[c1].key,root1->rec[c1].pp);
printf("||");
root1=root1->rbro;
}
}
printf("\n--------------------------------------------------------------------\n");
root=root->pt[0];
}
}
void main()
{
int choice;
struct bpnode * root=NULL;
struct bpnode * back;
long del;
long small,large,fkey;
long data=-1;
menu();
scanf("%d",&choice);
while(choice!=7)
{ switch(choice)
{
case 1:
data=-1;
back=NULL;
struct PAIR xrec;
xrec.pp=(char * )malloc(sizeof("fjldjlfjdjfldjfkjdkfjdkljfkdjjfkdjfjdjfkdfd"));
printf("\n请输入要插入的关键字:\n");
scanf ("%ld", &xrec.key);
printf("输入相应的文件名:\n");
scanf("%s",xrec.pp);
struct biback re=insert(root,xrec,back,data);
if(re.back)
{ struct bpnode * node=(struct bpnode * )malloc(sizeof(struct bpnode));
node->pa=NULL;
node->lbro=NULL;
node->rbro=NULL;
node->pt[0]=NULL;
node->pt[1]=NULL;
node->pt[2]=NULL;
node->pt[3]=NULL;
node->numrec=1;
node->rec[0].key=re.data;
node->pt[0]=root;
node->pt[1]=re.back;
root=node;
}
break;
case 2:
if(root==NULL)printf("当前树空\n");
else
{
printf("请输入要删除纪录的关键字\n");
scanf( "%ld",&del);
delet(root,del);
root=nroot;
}
break;
case 3:
if(root==NULL)
printf("当前记录为空\n");
else
display(root);
break;
case 4:
if(root==NULL)
printf("当前记录为空\n");
else
{printf("请输入检索范围的下限和上限:\n");
scanf("%ld %ld",&small,&large);
find(root,small,large);
}
break;
case 5:
if(root==NULL)
printf("当前记录为空\n");
else
{printf("请输入精确检索的关键码:\n");
scanf("%ld",&fkey);
findkey(root,fkey);
}
break;
case 6:
if(root==NULL)
printf("当前记录为空\n");
else str(root);
break;
case 7:
break;
default:
printf ("对不起，你的输入有误，请重试.\n\n");
break;
}
menu();
scanf("%d",&choice);
}
printf ("已退出\n");
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -