能力值：
( LV2，RANK：10 )
|
-
-
2 楼
//状态宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#include "iostream.h"
#include "Define.h"
#define M 3
typedef class BNode //B-树节点结构体
{
public:
int Ext; //节点中包含有效关键字的数目，初始化的时候为0，取值1或2
int Elem[M-1]; //关键字数组，2个关键字
BNode *Ptr[M]; //下一级指针，3个指针
BNode *Parent; //指向双亲的指针
int ParentPosition; //指向该节点的指针在双亲节点下级指针数组中的位置
BNode(); //构造函数
}BNode,*BTree;
BNode::BNode()
{
Ext=0; //初始化元素个数为0
int i=0;
for(i=0;i<M;i++) //初始化所有指向下级的指针为空
Ptr[i]=NULL;
Parent=NULL; //初始化指向双亲指针为空
ParentPosition=-1; //初始化指向该节点的指针在双亲节点下级指针数组中的位置为-1
}
class ElemInfo //需要加入的节点的信息结构体
{
public:
int Elem; //需要加入的关键字
BNode *EL; //该关键字对应的左边的指向下级的指针
BNode *ER; //该关键字对应的右边的指向下级的指针
ElemInfo(int x=0){Elem=x;EL=ER=NULL;};//构造函数以x初始化关键字，左右指向下级的指针初始化为空
};
#include "Queue.h"//包含队列头文件
BNode *FindPosition(int Elem,BTree T) //该函数返回关键字Elem在B-树中应该插入的位置，前提，Elem不在树中
{
if(!T) return NULL;
else
{
int i=0;
while(i<T->Ext&&T->Elem[i]<Elem)
i++;
BNode *p=FindPosition(Elem,T->Ptr[i]);
if(p==NULL) return T;
else return p;
}
}
BNode *InsertElem(ElemInfo EI,BNode * &p) //该函数完成将节点信息结构体EI插入到p指向的节点当中，用递归完成了分裂和上升
{
if(!p||p->Ext==0)//插入到空的p中或者p不存在,主要用于处理树的分裂时需要申请新节点和删除时节点的移位
{
if(!p) p=new BNode;
p->Elem[0]=EI.Elem;
if(EI.ER!=NULL&&EI.EL!=NULL)//插入的同时调整了下级的Parent指针和ParentPosition
{
p->Ptr[0]=EI.EL;
p->Ptr[0]->ParentPosition=0;
p->Ptr[0]->Parent=p;
p->Ptr[1]=EI.ER;
p->Ptr[1]->ParentPosition=1;
p->Ptr[1]->Parent=p;
}
p->Ext++;
return p;
}
else if(p->Ext<M-1)//p中有一个元素
{
if(EI.Elem>p->Elem[0])//要插入的关键字大于存在的关键字,插入的同时调整了下级的Parent指针和ParentPosition
{
if(EI.ER)
{
p->Ptr[2]=EI.ER;
p->Ptr[2]->ParentPosition=2;
p->Ptr[2]->Parent=p;
p->Ptr[1]=EI.EL;
p->Ptr[1]->ParentPosition=1;
p->Ptr[1]->Parent=p;
}
p->Elem[1]=EI.Elem;
p->Ext++;
return p;
}
else//要插入的关键字小于存在的关键字,插入的同时调整了下级的Parent指针和ParentPosition
{
p->Elem[1]=p->Elem[0];
if(p->Ptr[1])
{
p->Ptr[2]=p->Ptr[1];
p->Ptr[2]->ParentPosition=2;
p->Ptr[1]=EI.ER;
p->Ptr[1]->ParentPosition=1;
p->Ptr[1]->Parent=p;
p->Ptr[0]=EI.EL;
p->Ptr[0]->ParentPosition=0;
p->Ptr[0]->Parent=p;
}
p->Elem[0]=EI.Elem;
p->Ext++;
return p;
}
}
//以下是待插入的节点已经存在两个关键字的情况
else if(EI.Elem>p->Elem[1])//待插入关键字大于已存在的两个关键字
{
BNode *newp=new BNode;//分裂
if(EI.ER)//将待插入的关键字及其信息放入新节点
{
newp->Ptr[1]=EI.ER;
newp->Ptr[1]->ParentPosition=1;
newp->Ptr[0]=EI.EL;
}
newp->Elem[0]=EI.Elem;
newp->Ext++;
p->Ptr[2]=NULL;
p->Ext--;
EI.Elem=p->Elem[1];//将已存在的两个关键字中大的一个封装成下一步的待插入节点
EI.EL=p;
EI.ER=newp;
newp->Parent=InsertElem(EI,p->Parent);//将新的待插入节点插入到现有节点的父亲中,及上升
if(p->Parent==NULL)
{
p->Parent=newp->Parent;
}
else if(p->Parent->Ptr[p->ParentPosition]==NULL)
{
p->Parent=newp->Parent;
p->ParentPosition=newp->ParentPosition-1;
}
return newp;//调用前的新节点的父亲是这里的新节点
}
else if(EI.Elem>p->Elem[0])//待插入的关键字位于已存在的两个关键字中间
{
BNode *newp=new BNode;
if(p->Ptr[2])//将已存在关键字较大的一个放入新生成的节点
{
newp->Ptr[1]=p->Ptr[2];
newp->Ptr[1]->ParentPosition=1;
newp->Ptr[1]->Parent=newp;
newp->Ptr[0]=EI.ER;
newp->Ptr[0]->ParentPosition=0;
}
newp->Elem[0]=p->Elem[1];
newp->Ext++;
p->Ptr[2]=NULL;
if(EI.EL)
{
p->Ptr[1]=EI.EL;
p->Ptr[1]->ParentPosition=1;
p->Ptr[1]->Parent=p;
}
p->Ext--;
EI.EL=p;//更新待插入节点的指针信息
EI.ER=newp;
newp->Parent=InsertElem(EI,p->Parent);//将待插入节点插入到父亲节点中
if(p->Parent==NULL)//顶层分裂,产生了新的树根
{
p->Parent=newp->Parent;
}
else if(p->Parent->Ptr[p->ParentPosition]==NULL)//校正p的ParentPosition信息
{
p->Parent=newp->Parent;
p->ParentPosition=newp->ParentPosition-1;
}
return newp;//调用前的新节点的父亲是这里的新节点
}
else//待插入的关键字比与存在的两个关键字都要小
{
BNode *newp=new BNode;
if(p->Ptr[2])//将最大的一个放入新的节点,同时调整其子节点的父亲指针和位置标记
{
newp->Ptr[1]=p->Ptr[2];
newp->Ptr[1]->ParentPosition=1;
newp->Ptr[1]->Parent=newp;
newp->Ptr[0]=p->Ptr[1];
newp->Ptr[0]->ParentPosition=0;
newp->Ptr[0]->Parent=newp;
}
newp->Elem[0]=p->Elem[1];
newp->Ext++;
newp->Elem[1]=p->Elem[0];//利用新节点后一个关键字的空间暂存中间的关键字
if(EI.EL)
{
p->Ptr[0]=EI.EL;
p->Ptr[0]->ParentPosition=0;
p->Ptr[0]->Parent=p;
p->Ptr[1]=EI.ER;
p->Ptr[1]->ParentPosition=1;
}
p->Elem[0]=EI.Elem;//将待插入的节点放入0号位置
p->Ext--;
EI.Elem=newp->Elem[1];//将中间节点及其信息封装成新的待插入节点
EI.EL=p;
EI.ER=newp;
newp->Parent=InsertElem(EI,p->Parent);//将型的待插入节点插入其父亲节点
if(p->Parent==NULL)//顶层分裂,产生了新的树根
{
p->Parent=newp->Parent;
}
else if(p->Parent->Ptr[p->ParentPosition]==NULL)//校正p的ParentPosition信息
{
p->Parent=newp->Parent;
p->ParentPosition=newp->ParentPosition-1;
}
return p;//调用前的新节点的父亲是这里的旧节点
}
}
Status Search(int x,BTree T) //该函数在B-树中查找关键字x，若存在返回TRUE，不存在返回FALSE
{
if(!T) return FALSE;
int i=0;
while(i<T->Ext&&T->Elem[i]<x)
i++;
if(i<T->Ext&&T->Elem[i]==x)
return TRUE;
if(Search(x,T->Ptr[i]))
return TRUE;
else return FALSE;
}
Status Insert(int Elem,BTree &T) //该函数完成将关键字Elem插入到B-树T中
{
if(Search(Elem,T)) //若关键字已经存在，则插入失败
{
cout<<"该关键字已经存在！插入失败！"<<endl;
return ERROR;
}
ElemInfo temp(Elem); //构造带插入节点结构体
BNode *p=FindPosition(Elem,T); //找到带插入的位置
if(p) InsertElem(temp,p); //若找到，则调用函数插入
else InsertElem(temp,T); //若树为空，插入到根节点
while(T->Parent) T=T->Parent; //重新定位根节点位置
return OK;
}
BNode *FindDePosition(int x,BTree T)//该函数在B-树中查找关键字x所在的节点，若x不在树中，返回NULL
{
if(!T) return NULL;
int i=0;
while(i<T->Ext&&T->Elem[i]<x)
i++;
if(i<T->Ext&&T->Elem[i]==x)
return T;
else
return FindDePosition(x,T->Ptr[i]);
}
void DeleteElem(BNode *p,int Elem,BTree &T)//在B-树T中删除p指向的节点中的关键字Elem，通过递归完成对B-树的调整l
{
if(p->Ext==2)//待删除关键字所在节点中有两个关键字的情况
{
if(p->Elem[0]==Elem)
{
p->Elem[0]=p->Elem[1];
if(p->Ptr[2]!=NULL)
{
p->Ptr[0]=p->Ptr[1];
p->Ptr[0]->ParentPosition=0;
p->Ptr[1]=p->Ptr[2];
p->Ptr[1]->ParentPosition=1;
}
}
p->Ptr[2]=NULL;
p->Ext--;
return;
}
else//p->Ext==1 待删除关键字所在节点只有一个关键字的情况
{
BNode *pPare=p->Parent;
BNode *pLeftInfo=NULL;
ElemInfo EI;
if((pLeftInfo=p->Ptr[0])!=NULL||(pLeftInfo=p->Ptr[1])!=NULL)//一下七行将p的剩余信息存到pLfetInfo
;
if(pLeftInfo==NULL&&pPare==NULL)//删除根节点并且只剩下根节点的情况
{
delete p;
T=NULL;
return ;
}
if(pPare==NULL)//删除根节点的情况
{
delete p;
T=pLeftInfo;
T->Parent=NULL;
T->ParentPosition=-1;
return;
}
if(pPare->Ext==2)
{
if(p->ParentPosition==0)
{
if(pPare->Ptr[1]->Ext==1)
{
if(pPare->Ptr[2]->Ext==1)//case 1
{
delete p;
EI.EL=pLeftInfo;
EI.ER=pPare->Ptr[1]->Ptr[0];
EI.Elem=pPare->Elem[0];
DeleteElem(pPare,pPare->Elem[0],T);
InsertElem(EI,pPare->Ptr[0]);
return;
}
else//pPare->Ptr[2]->Ext==2 case 3
{
EI.EL=pPare->Ptr[1]->Ptr[1];
EI.Elem=pPare->Elem[1];
EI.ER=pPare->Ptr[2]->Ptr[0];
InsertElem(EI,pPare->Ptr[1]);
pPare->Elem[1]=pPare->Ptr[2]->Elem[0];
DeleteElem(pPare->Ptr[2],pPare->Ptr[2]->Elem[0],T);
DeleteElem(p,p->Elem[0],T);
return;
}
}
else//pPare->Ptr[1]->Ext==2 case 2
{
p->Ext--;
EI.EL=pLeftInfo;
EI.ER=pPare->Ptr[1]->Ptr[0];
EI.Elem=pPare->Elem[0];
InsertElem(EI,p);
pPare->Elem[0]=pPare->Ptr[1]->Elem[0];
DeleteElem(pPare->Ptr[1],pPare->Ptr[1]->Elem[0],T);
return ;
}
}
else if(p->ParentPosition==1)
{
if(pPare->Ptr[2]->Ext==1)
{
if(pPare->Ptr[0]->Ext==1)//case 6
{
delete p;
EI.EL=pLeftInfo;
EI.ER=pPare->Ptr[2]->Ptr[0];
EI.Elem=pPare->Elem[1];
pPare->Ptr[1]=pPare->Ptr[2];
pPare->Ptr[1]->ParentPosition=1;
InsertElem(EI,pPare->Ptr[1]);
DeleteElem(pPare,pPare->Elem[1],T);
return ;
}
else//pPare->Ptr[0]->Ext==2 case 5
{
p->Ext--;
EI.EL=pPare->Ptr[0]->Ptr[2];
EI.ER=pLeftInfo;
EI.Elem=pPare->Elem[0];
InsertElem(EI,p);
pPare->Elem[0]=pPare->Ptr[0]->Elem[1];
DeleteElem(pPare->Ptr[0],pPare->Ptr[0]->Elem[1],T);
return ;
}
}
else//pPare->Ptr[2]->Ext==2 case 4
{
p->Ext--;
EI.EL=pLeftInfo;
EI.ER=pPare->Ptr[2]->Ptr[0];
EI.Elem=pPare->Elem[1];
InsertElem(EI,p);
pPare->Elem[1]=pPare->Ptr[2]->Elem[0];
DeleteElem(pPare->Ptr[2],pPare->Ptr[2]->Elem[0],T);
return ;
}
}
else//p->ParentPosition==2
{
if(pPare->Ptr[1]->Ext==2)//case 7
{
p->Ext--;
EI.EL=pPare->Ptr[1]->Ptr[2];
EI.ER=pLeftInfo;
EI.Elem=pPare->Elem[1];
InsertElem(EI,p);
pPare->Elem[1]=pPare->Ptr[1]->Elem[1];
DeleteElem(pPare->Ptr[1],pPare->Ptr[1]->Elem[1],T);
return ;
}
else//pPare->Ptr[1]->Ext==1
{
if(pPare->Ptr[0]->Ext==1)//case 9
{
delete p;
EI.EL=pPare->Ptr[1]->Ptr[1];
EI.ER=pLeftInfo;
EI.Elem=pPare->Elem[1];
InsertElem(EI,pPare->Ptr[1]);
DeleteElem(pPare,pPare->Elem[1],T);
return;
}
else//pPare->Ptr[0]->Ext==2 case 8
{
EI.EL=pPare->Ptr[0]->Ptr[2];
EI.Elem=pPare->Elem[0];
EI.ER=pPare->Ptr[1]->Ptr[0];
InsertElem(EI,pPare->Ptr[1]);
pPare->Elem[0]=pPare->Ptr[0]->Elem[1];
DeleteElem(pPare->Ptr[0],pPare->Ptr[0]->Elem[1],T);
DeleteElem(p,p->Elem[0],T);
return;
}
}
}
}
else//pPare->Ext==1
{
if(p->ParentPosition==0)
{
if(pPare->Ptr[1]->Ext==1)//case 11
{
delete p;
EI.EL=pLeftInfo;
EI.ER=pPare->Ptr[1]->Ptr[0];
EI.Elem=pPare->Elem[0];
InsertElem(EI,pPare->Ptr[1]);
pPare->Ptr[0]=NULL;
DeleteElem(pPare,pPare->Elem[0],T);
return ;
}
else//pPare->Ptr[1]->Ext==2 case 10
{
p->Ext--;
EI.EL=pLeftInfo;
EI.ER=pPare->Ptr[1]->Ptr[0];
EI.Elem=pPare->Elem[0];
InsertElem(EI,p);
pPare->Elem[0]=pPare->Ptr[1]->Elem[0];
DeleteElem(pPare->Ptr[1],pPare->Ptr[1]->Elem[0],T);
return ;
}
}
else//p->ParentPosition==1
{
if(pPare->Ptr[0]->Ext==1)//case 13
{
delete p;
EI.EL=pPare->Ptr[0]->Ptr[1];
EI.ER=pLeftInfo;
EI.Elem=pPare->Elem[0];
InsertElem(EI,pPare->Ptr[0]);
pPare->Ptr[1]=NULL;
DeleteElem(pPare,pPare->Elem[0],T);
return ;
}
else//pPare->Ptr[0]==2 case 12
{
p->Ext--;
EI.EL=pPare->Ptr[0]->Ptr[2];
EI.ER=pLeftInfo;
EI.Elem=pPare->Elem[0];
InsertElem(EI,p);
pPare->Elem[0]=pPare->Ptr[0]->Elem[1];
DeleteElem(pPare->Ptr[0],pPare->Ptr[0]->Elem[1],T);
return ;
}
}
}
}
}
Status Delete(int Elem,BTree &T)//该函数完成在B-树中删除关键字Elem
{
BNode *p=FindDePosition(Elem,T);//指向待删除的关键字所在节点的指针
if(p==NULL)
{
cout<<"关键字:"<<Elem<<"不在树中，无法进行删除操作"<<endl;
return FALSE;
}
int ElemPos=(p->Elem[0]==Elem)?0:1;//待删除关键字在其所在节点的位置
if(p->Ptr[0]!=NULL) //若待删除的关键字不在叶子节点中，找到其右边的最左边替换，转换成删除叶子节点
{
BNode *q=p->Ptr[ElemPos+1];
while(q->Ptr[0]!=NULL)
q=q->Ptr[0];
Elem=p->Elem[ElemPos]=q->Elem[0];
p=q;
ElemPos=0;
}
//至此已经将问题转化成删除值为Elem的关键字，该关键字在p所指向的叶子节点中
DeleteElem(p,Elem,T);
return OK;
}
void Print(BTree T) //以层次遍历输出树
{
if(!T)
{
cout<<"空树!"<<endl;
return;
}
LinkQueue a,b; //用到2个队列以完成分层输出
InitQueue(a);
InitQueue(b);
BNode *temp;
int n;
EnQueue(a,T);
while(!QueueEmpty(a)||!QueueEmpty(b))//两个队列都为空时，输出结束
{
if(!QueueEmpty(a))
{
while(!QueueEmpty(a))
{
DeQueue(a,temp);
for(n=0;n<temp->Ext;n++)
{
cout<<temp->Elem[n]<<"+";
if(temp->Ptr[n]) EnQueue(b,temp->Ptr[n]);
}
if(temp->Ptr[n]) EnQueue(b,temp->Ptr[n]);
cout<<"\b ";
}
cout<<endl;
}
else
{
while(!QueueEmpty(b))
{
DeQueue(b,temp);
for(n=0;n<temp->Ext;n++)
{
cout<<temp->Elem[n]<<"+";
if(temp->Ptr[n]) EnQueue(a,temp->Ptr[n]);
}
if(temp->Ptr[n]) EnQueue(a,temp->Ptr[n]);
cout<<"\b ";
}
cout<<endl;
}
}
}
void PrintDetails(BTree T)//用层次遍历输出每一个节点的详细信息,调试用函数
{
if(!T)
{
cout<<"树为空树!"<<endl;
return;
}
LinkQueue a; //以一个队列层次遍历
InitQueue(a);
BNode *temp;
int n,m=1;
EnQueue(a,T);
while(!QueueEmpty(a))
{
DeQueue(a,temp);
cout<<"节点序号:"<<m<<endl;
cout<<"所含关键字个数:"<<temp->Ext<<endl;
cout<<"所含关键字为：";
for(n=0;n<temp->Ext;n++)
{
cout<<temp->Elem[n]<<" ";
}
cout<<endl;
cout<<endl;
for(n=0;n<3;n++)
{
if(temp->Ptr[n])
{
EnQueue(a,temp->Ptr[n]);
cout<<"孩子"<<n<<"的第一个关键字："<<temp->Ptr[n]->Elem[0]<<endl;
}
else
{
cout<<"孩子"<<n<<"不存在"<<endl;
}
}
cout<<endl;
if(temp->Parent)
{
cout<<"父亲的第一个关键字："<<temp->Ptr[n]->Elem[0]<<endl;
cout<<"该节点在父亲中的位置"<<temp->ParentPosition<<endl;
}
else
{
cout<<"父亲不存在"<<endl;
}
system("pause");
system("cls");
m++;
}
cout<<"输出结束!"<<endl;
system("pause");
}
void Destroy(BTree &T)//销毁B-树T,算法思想就是不算的删除根关键字直到树空
{
while(T)
{
Delete(T->Elem[0],T);
}
}
#include "iostream.h"
typedef BTree QElemType;
typedef struct QNode //队列的节点类型
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct //队列类型声明
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q) //初始化队列,申请专用的对头节点
{
Q.front=Q.rear=new QNode;
if(!Q.front) return OVERFLOW;
Q.front->next=NULL;
return OK;
}
Status ClearQueue(LinkQueue &Q) //清空队列,只剩下专用的头节点
{
if(Q.front==Q.rear) return OK;
QNode *p=Q.front->next;
while(p)
{
Q.front->next=p->next;
delete p;
p=Q.front->next;
}
Q.rear=Q.front;
return OK;
}
Status DestroyQueue(LinkQueue &Q) //销毁队列,在清空的基础上删除专用头结点
{
ClearQueue(Q);
delete Q.front;
Q.front=Q.rear=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q) //队列判空,如果是空队列返回TRUE,否则返回FALSE
{
if(Q.rear==Q.front) return TRUE;
else return FALSE;
}
int QueueLength(LinkQueue Q) //求队列长度
{
int cout=0;
QNode *p=Q.front->next;
while(p)
{
cout++;
p=p->next;
}
return cout;
}
Status QueueTraverse(LinkQueue &Q) //遍历队列,输出队列中的元素
{
if(Q.front==Q.rear)
{
cout<<"空队"<<endl;
return OK;
}
QNode *p=Q.front->next;
while(p)
{
cout<<p->data<<endl;
p=p->next;
}
return OK;
}
Status GetHead(LinkQueue Q,QElemType &e) //取头结点,将其数据放到e中
{
if(QueueEmpty(Q))
return ERROR;
else
{
e=Q.front->next->data;
return OK;
}
}
Status EnQueue(LinkQueue &Q,QElemType &e) //将e入队
{
Q.rear->next=new QNode;
if(!Q.rear->next)
return OVERFLOW;
Q.rear=Q.rear->next;
Q.rear->data=e;
Q.rear->next=NULL;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e) //出队,将出对的元素放入e中
{
if(!GetHead(Q,e))
return ERROR;
if(Q.rear==Q.front->next)
Q.rear=Q.front;
QNode *p=Q.front->next;
Q.front->next=p->next;
delete p;
return OK;
}
#include "Testmode.h"
void Frist() //开始界面
{
cout <<"************************************************" <<endl;
cout <<"课程设计：B-Trees 的实现及分析" <<endl;
cout <<"班级：09计算机1班" <<endl;
cout <<"学号：0900303128" <<endl;
cout <<"姓名：胡远璇" <<endl;
cout <<"************************************************" <<endl;
cout <<endl;
cout <<endl;
cout <<"介绍：" <<endl;
cout <<endl;
cout <<"该程序是M=3的的B-树" <<endl;
cout <<endl;
cout <<"该程序包含：" <<endl;
cout <<"1.实现在B-树上的查找" <<endl;
cout <<"2.实现B-树的ADT，包括其上的基本操作：结点的加入和删除" <<endl;
cout <<endl;
cout <<endl;
system("pause");
}
void systemmenu() //顶级的系统菜单
{
char choose=0;
while(1)
{
system("cls");
cout <<"测试模式选择" <<endl;
cout <<"A.指定关键字插入删除测试" <<endl;
cout <<"E.退出系统" <<endl;
choose=getch();
if(toupper(choose)=='A')
{
BTree T=NULL;
InputIDTest(T);
}
if(toupper(choose)=='E') break;
}
}
void End() //结束界面
{
system("cls");
cout <<"************************************************" <<endl;
cout <<"程序结束" <<endl;
cout <<"2011-1-15" <<endl;
cout <<"************************************************" <<endl;
system("pause");
}
void main()
{
Frist();
systemmenu();
End();
}
|
能力值：
( LV3，RANK：20 )
|
-
-
3 楼
试试google的 https://code.google.com/p/cpp-btree/
|
能力值：
( LV2，RANK：10 )
|
-
-
6 楼
学数据结构的话。 还是应该先看书，或者先看图。 算法导论和“数据结构” 这本书里面都有B树的图。 我觉得还算是深入浅出。 红黑树什么的也讲的很好。
|
