求人帮我将一个java程序 改为 C语言的~

时间:2021-07-19 12:37:09

求人帮我将一个java程序 改为 C语言的~/* BPlusTree.h*/

 


#define ORDER_V 2    /* 为简单起见,把v固定为2,实际的B+树v值应该是可配的 */
#define MAXNUM_KEY (ORDER_V * 2)    /* 内部结点中最多键个数,为2v */
#define MAXNUM_POINTER (MAXNUM_KEY + 1)    /* 内部结点中最多指向子树的指针个数,为2v */
#define MAXNUM_DATA (ORDER_V * 2)    /* 叶子结点中最多数据个数,为2v */

//#define ORDER_V 2    /* 为简单起见,把v固定为2,实际的B+树v值应该是可配的 */
//#define MAXNUM_KEY (3)    /* 内部结点中最多键个数,为2v */
//#define MAXNUM_POINTER (3)    /* 内部结点中最多指向子树的指针个数,为2v */
//#define MAXNUM_DATA (3)    /* 叶子结点中最多数据个数,为2v */

/* 键值的类型*/
typedef int KEY_TYPE;    /* 为简单起见,定义为int类型,实际的B+树键值类型应该是可配的 */
/*备注: 为简单起见,叶子结点的数据也只存储键值*/
/* 结点类型 */
enum NODE_TYPE
{
NODE_TYPE_ROOT     = 1,    // 根结点
NODE_TYPE_INTERNAL = 2,    // 内部结点
NODE_TYPE_LEAF     = 3,    // 叶子结点
};
#define NULL 0
#define INVALID 0
#define FLAG_LEFT 1
#define FLAG_RIGHT 2
/* 结点数据结构,为内部结点和叶子结点的父类 */
class CNode
{
public:
    CNode();
    virtual ~CNode();
   
    //获取和设置结点类型
    NODE_TYPE GetType() { return m_Type; }
    void SetType(NODE_TYPE type) {m_Type = type;}
    // 获取和设置有效数据个数
    int GetCount() { return m_Count;}
    void SetCount(int i) { m_Count = i; }
    // 获取和设置某个元素,对中间结点指键,对叶子结点指数据
    virtual KEY_TYPE GetElement(int i) {return 0;}
    virtual void SetElement(int i, KEY_TYPE value) { }
   
    // 获取和设置某个指针,对中间结点指指针,对叶子结点无意义
    virtual CNode* GetPointer(int i) {return NULL;}
    virtual void SetPointer(int i, CNode* pointer) { }
    // 获取和设置父结点
    CNode* GetFather() { return m_pFather;}
    void SetFather(CNode* father) { m_pFather = father; }
    // 获取一个最近的兄弟结点
    CNode* GetBrother(int& flag);
    // 删除结点
    void DeleteChildren();
protected:
   
    NODE_TYPE m_Type;    // 结点类型,取值为NODE_TYPE类型
    int m_Count;    // 有效数据个数,对中间结点指键个数,对叶子结点指数据个数
    CNode* m_pFather;     // 指向父结点的指针,标准B+树中并没有该指针,加上是为了更快地实现结点分裂和旋转等操作
};
/* 内部结点数据结构 */
class CInternalNode : public CNode
{
public:
    CInternalNode();
    virtual ~CInternalNode();
    // 获取和设置键值,对用户来说,数字从1开始
    KEY_TYPE GetElement(int i)
    {
        if ((i > 0 ) && (i <= MAXNUM_KEY))
        {
            return m_Keys[i - 1];
        }
        else
        {
            return INVALID;
        }
    }
    void SetElement(int i, KEY_TYPE key)
    {
        if ((i > 0 ) && (i <= MAXNUM_KEY))
        {
            m_Keys[i - 1] = key;
        }
    }
    // 获取和设置指针,对用户来说,数字从1开始
    CNode* GetPointer(int i)
    {
        if ((i > 0 ) && (i <= MAXNUM_POINTER))
        {
            return m_Pointers[i - 1];
        }
        else
        {
            return NULL;
        }
    }
    void SetPointer(int i, CNode* pointer)
    {
        if ((i > 0 ) && (i <= MAXNUM_POINTER))
        {
            m_Pointers[i - 1] = pointer;
        }
    }
    // 插入键
    bool Insert(KEY_TYPE value, CNode* pNode);
    // 删除键
    bool Delete(KEY_TYPE value);
    // 分裂结点
    KEY_TYPE Split(CInternalNode* pNode, KEY_TYPE key);
    // 结合结点
    bool Combine(CNode* pNode);
    // 从另一结点移一个元素到本结点
    bool MoveOneElement(CNode* pNode);
protected:
    KEY_TYPE m_Keys[MAXNUM_KEY];           // 键数组
    CNode* m_Pointers[MAXNUM_POINTER];     // 指针数组
};
/* 叶子结点数据结构 */
class CLeafNode : public CNode
{
public:
    CLeafNode();
    virtual ~CLeafNode();
    // 获取和设置数据
    KEY_TYPE GetElement(int i)
    {
        if ((i > 0 ) && (i <= MAXNUM_DATA))
        {
            return m_Datas[i - 1];
        }
        else
        {
            return INVALID;
        }
    }
    void SetElement(int i, KEY_TYPE data)
    {
        if ((i > 0 ) && (i <= MAXNUM_DATA))
        {
            m_Datas[i - 1] = data;
        }
    }
    // 获取和设置指针,对叶子结点无意义,只是实行父类的虚函数
    CNode* GetPointer(int i)
    {
        return NULL;
    }
   
    // 插入数据
    bool Insert(KEY_TYPE value);
    // 删除数据
    bool Delete(KEY_TYPE value);
    // 分裂结点
    KEY_TYPE Split(CNode* pNode);
    // 结合结点
    bool Combine(CNode* pNode);
public:
    // 以下两个变量用于实现双向链表
    CLeafNode* m_pPrevNode;                 // 前一个结点
    CLeafNode* m_pNextNode;                 // 后一个结点
   
protected:
    KEY_TYPE m_Datas[MAXNUM_DATA];    // 数据数组
};
/* B+树数据结构 */
class BPlusTree
{
public:
  
    BPlusTree();
    virtual ~BPlusTree();
    // 查找指定的数据
    bool Search(KEY_TYPE data, char* sPath);
    // 插入指定的数据
    bool Insert(KEY_TYPE data);
    // 删除指定的数据
    bool Delete(KEY_TYPE data);
    // 清除树
    void ClearTree();
    // 打印树
    void PrintTree();
    // 旋转树
    BPlusTree* RotateTree();
    // 检查树是否满足B+树的定义
    bool CheckTree();
    void PrintNode(CNode* pNode);
    // 递归检查结点及其子树是否满足B+树的定义
    bool CheckNode(CNode* pNode);
    // 获取和设置根结点
    CNode* GetRoot()
    {
        return m_Root;
    }
    void SetRoot(CNode* root)
    {
        m_Root = root;
    }
    // 获取和设置深度
    int GetDepth()
    {
        return m_Depth;
    }
    void SetDepth(int depth)
    {
        m_Depth = depth;
    }
   
    // 深度加一
    void IncDepth()
    {
        m_Depth = m_Depth + 1;
    }
    // 深度减一
    void DecDepth()
    {
        if (m_Depth > 0)
        {
            m_Depth = m_Depth - 1;
        }
    }
public:
    // 以下两个变量用于实现双向链表
    CLeafNode* m_pLeafHead;                 // 头结点
    CLeafNode* m_pLeafTail;                   // 尾结点
protected:
    // 为插入而查找叶子结点
    CLeafNode* SearchLeafNode(KEY_TYPE data);
    //插入键到中间结点
    bool InsertInternalNode(CInternalNode* pNode, KEY_TYPE key, CNode* pRightSon);
    // 在中间结点中删除键
    bool DeleteInternalNode(CInternalNode* pNode, KEY_TYPE key);
   
    CNode* m_Root;    // 根结点
    int m_Depth;      // 树的深度
};
/* end of BPlusTree.h */

 

 

 

 

/*BPlusTree.cpp*/

 

#include "BPlusTree.h"
#include "stdio.h"
#include "stdlib.h"
CNode::CNode()
{
    m_Type = NODE_TYPE_LEAF;
    m_Count = 0;
    m_pFather = NULL;
}
CNode::~CNode()
{
    DeleteChildren();
}
// 获取一个最近的兄弟结点
CNode* CNode::GetBrother(int& flag)
{
    CNode* pFather = GetFather();
    if (NULL == pFather)
    {
        return NULL;
    }
    CNode* pBrother = NULL;
    for (int i = 1; i <= pFather->GetCount() + 1; i++)
    {
        // 找到本结点的位置
        if (pFather->GetPointer(i) == this)
        {
            if (i == (pFather->GetCount() + 1))
            {
                pBrother = pFather->GetPointer(i - 1);    // 本身是最后一个指针,只能找前一个指针
                flag = FLAG_LEFT;
            }
            else
            {
                pBrother = pFather->GetPointer(i + 1);    // 优先找后一个指针
                flag = FLAG_RIGHT;
            }
        }
    }
    return pBrother;
}
// 递归删除子结点
void CNode::DeleteChildren()
{
    for (int i = 1; i <= GetCount(); i++)
    {
        CNode * pNode = GetPointer(i);
        if (NULL != pNode)    // 叶子结点没有指针
        {
            pNode->DeleteChildren();
        }
        delete pNode;
    }
}
CInternalNode::CInternalNode()
{
    m_Type = NODE_TYPE_INTERNAL;
    int i = 0;
    for (i = 0; i < MAXNUM_KEY; i++)
    {
        m_Keys[i] = INVALID;
    }
    for (i = 0; i < MAXNUM_POINTER; i++)
    {
        m_Pointers[i] = NULL;
    }
}
CInternalNode::~CInternalNode()
{
    for (int i = 0; i < MAXNUM_POINTER; i++)
    {
        m_Pointers[i] = NULL;
    }
}
// 在中间结点中插入键
bool CInternalNode::Insert(KEY_TYPE value, CNode* pNode)
{
    // 如果中间结点已满,直接返回失败
    if (GetCount() >= MAXNUM_KEY)
    {
        return false;
    }
    int j = 0;
    // 找到要插入键的位置
    for (int i = 0; (value > m_Keys[i]) && ( i < m_Count); i++)
    {
    }
    // 当前位置及其后面的键依次后移,空出当前位置
    for (j = m_Count; j > i; j--)
    {
        m_Keys[j] = m_Keys[j - 1];
    }
    // 当前位置及其后面的指针依次后移
    for (j = m_Count + 1; j > i + 1; j--)
    {
        m_Pointers[j] = m_Pointers[j - 1];
    }
   
    // 把键和指针存入当前位置
    m_Keys[i] = value;
    m_Pointers[i + 1] = pNode;    // 注意是第i+1个指针而不是第i个指针
    pNode->SetFather(this);      // 非常重要
    m_Count++;
    // 返回成功
    return true;
}
// 在中间结点中删除键,以及该键后的指针
bool CInternalNode::Delete(KEY_TYPE key)
{
    for (int i = 0; (key >= m_Keys[i]) && (i < m_Count); i++)
    {
    }
    for (int j = i - 1; j < m_Count - 1; j++)
    {
        m_Keys[j] = m_Keys[j + 1];
    }
    m_Keys[j] = INVALID;
    for (int k = i; k < m_Count; k++)
    {
        m_Pointers[k] = m_Pointers[k + 1];
    }
    m_Pointers[k] = NULL;
    m_Count--;
    return true;
}
/* 分裂中间结点
分裂中间结点和分裂叶子结点完全不同,因为中间结点不仅有2V键,还有2V+1指针,如果单纯地一分为2,指针将无法分配。
因此根据http://www.seanster.com/BplusTree/BplusTree.html,分裂中间结点的算法是:
根据要插入的键key判断:
(1)如果key小于第V个键,则把第V个键提出来,其左右的键分别分到两个结点中
(2)如果key大于第V+1个键,则把第V+1个键提出来,其左右的键分别分到两个结点中
(3)如果key介于第V和V+1个键之间,则把key作为要提出的键,原来的键各分一半到两个结点中
提出来的RetKey作用是便于后续插入到祖先结点
*/
KEY_TYPE CInternalNode::Split(CInternalNode* pNode, KEY_TYPE key)
{
    int i = 0, j = 0;
   
    // 如果要插入的键值在第V和V+1个键值中间,需要翻转一下,因此先处理此情况
    if ((key > this->GetElement(ORDER_V)) && (key < this->GetElement(ORDER_V + 1)))
    {
        // 把第V+1 -- 2V个键移到指定的结点中
        for (i = ORDER_V + 1; i <= MAXNUM_KEY; i++)
        {
            j++;
            pNode->SetElement(j, this->GetElement(i));
            this->SetElement(i, INVALID);
        }
        // 把第V+2 -- 2V+1个指针移到指定的结点中
        j = 0;
        for (i = ORDER_V + 2; i <= MAXNUM_POINTER; i++)
        {
            j++;
            this->GetPointer(i)->SetFather(pNode);    // 重新设置子结点的父亲
            pNode->SetPointer(j, this->GetPointer(i));
            this->SetPointer(i, INVALID);
        }
        // 设置好Count个数
        this->SetCount(ORDER_V);
        pNode->SetCount(ORDER_V);
        // 把原键值返回
        return key;
    }
    // 以下处理key小于第V个键值或key大于第V+1个键值的情况
    // 判断是提取第V还是V+1个键
    int position = 0;
    if (key < this->GetElement(ORDER_V))
    {
        position = ORDER_V;
    }
    else
    {
        position = ORDER_V + 1;
    }
    // 把第position个键提出来,作为新的键值返回
    KEY_TYPE RetKey = this->GetElement(position);
    // 把第position+1 -- 2V个键移到指定的结点中
    j = 0;
    for (i = position + 1; i <= MAXNUM_KEY; i++)
    {
        j++;
        pNode->SetElement(j, this->GetElement(i));
        this->SetElement(i, INVALID);
    }
    // 把第position+1 -- 2V+1个指针移到指定的结点中(注意指针比键多一个)
    j = 0;
    for (i = position + 1; i <= MAXNUM_POINTER; i++)
    {
        j++;
        this->GetPointer(i)->SetFather(pNode);    // 重新设置子结点的父亲
        pNode->SetPointer(j, this->GetPointer(i));
        this->SetPointer(i, INVALID);
    }
    // 清除提取出的位置
    this->SetElement(position, INVALID);
    // 设置好Count个数
    this->SetCount(position - 1);
    pNode->SetCount(MAXNUM_KEY - position);
    return RetKey;
}
// 结合结点,把指定中间结点的数据全部剪切到本中间结点
bool CInternalNode::Combine(CNode* pNode)
{
    // 参数检查
    if (this->GetCount() + pNode->GetCount() + 1> MAXNUM_DATA)    // 预留一个新键的位置
    {
        return false;
    }
   
    // 取待合并结点的第一个孩子的第一个元素作为新键值
    KEY_TYPE NewKey = pNode->GetPointer(1)->GetElement(1);
   
    m_Keys[m_Count] = NewKey;
    m_Count++;
    m_Pointers[m_Count] = pNode->GetPointer(1);
    for (int i = 1; i <= pNode->GetCount(); i++)
    {
        m_Keys[m_Count] = pNode->GetElement(i);
        m_Count++;
        m_Pointers[m_Count] = pNode->GetPointer(i+1);
    }
    return true;
}
// 从另一结点移一个元素到本结点
bool CInternalNode::MoveOneElement(CNode* pNode)
{
    // 参数检查
    if (this->GetCount() >= MAXNUM_DATA)
    {
        return false;
    }
    int i,j;

    // 兄弟结点在本结点左边
    if (pNode->GetElement(1) < this->GetElement(1))
    {
        // 先腾出位置
        for (i = m_Count; i > 0; i--)
        {
            m_Keys[i] = m_Keys[i -1];
        }
        for (j = m_Count + 1; j > 0; j--)
        {
            m_Pointers[j] = m_Pointers[j -1];
        }
        // 赋值
        // 第一个键值不是兄弟结点的最后一个键值,而是本结点第一个子结点的第一个元素的值
        m_Keys[0] = GetPointer(1)->GetElement(1);
        // 第一个子结点为兄弟结点的最后一个子结点
        m_Pointers[0] = pNode->GetPointer(pNode->GetCount() + 1);
       
        // 修改兄弟结点
        pNode->SetElement(pNode->GetCount(), INVALID);
        pNode->SetPointer(pNode->GetCount() + 1, INVALID);
    }
    else    // 兄弟结点在本结点右边
    {
        // 赋值
        // 最后一个键值不是兄弟结点的第一个键值,而是兄弟结点第一个子结点的第一个元素的值
        m_Keys[m_Count] = pNode->GetPointer(1)->GetElement(1);
        // 最后一个子结点为兄弟结点的第一个子结点
        m_Pointers[m_Count + 1] = pNode->GetPointer(1);
       
        // 修改兄弟结点
        for (i = 1; i < pNode->GetCount() - 1; i++)
        {
            pNode->SetElement(i, pNode->GetElement(i + 1));
        }
        for (j = 1; j < pNode->GetCount(); j++)
        {
            pNode->SetPointer(j, pNode->GetPointer(j + 1));
        }
    }
    // 设置数目
    this->SetCount(this->GetCount() + 1);
    pNode->SetCount(pNode->GetCount() - 1);
    return true;
}
// 清除叶子结点中的数据
CLeafNode::CLeafNode()
{
    m_Type = NODE_TYPE_LEAF;
    for (int i = 0; i < MAXNUM_DATA; i++)
    {
        m_Datas[i] = INVALID;
    }
    m_pPrevNode = NULL;
    m_pNextNode = NULL;
}
CLeafNode::~CLeafNode()
{
}
// 在叶子结点中插入数据
bool CLeafNode::Insert(KEY_TYPE value)
{
    // 如果叶子结点已满,直接返回失败
    if (GetCount() >= MAXNUM_DATA)
    {
        return false;
    }
    // 找到要插入数据的位置
    for (int i = 0; (value > m_Datas[i]) && ( i < m_Count); i++)
    {
    }
    // 当前位置及其后面的数据依次后移,空出当前位置
    for (int j = m_Count; j > i; j--)
    {
        m_Datas[j] = m_Datas[j - 1];
    }
    // 把数据存入当前位置
    m_Datas[i] = value;
    m_Count++;
    // 返回成功
    return true;
}
bool CLeafNode::Delete(KEY_TYPE value)
{
    bool found = false;
    for (int i = 0; i < m_Count; i++)
    {
        if (value == m_Datas[i])
        {
            found = true;
            break;
        }
    }
    // 如果没有找到,返回失败
    if (false == found)
    {
        return false;
    }
    // 后面的数据依次前移
    for (int j = i; j < m_Count - 1; j++)
    {
        m_Datas[j] = m_Datas[j + 1];
    }
    m_Datas[j] = INVALID;
    m_Count--;
    // 返回成功
    return true;
}
// 分裂叶子结点,把本叶子结点的后一半数据剪切到指定的叶子结点中
KEY_TYPE CLeafNode::Split(CNode* pNode)
{
    // 把本叶子结点的后一半数据移到指定的结点中
    int j = 0;
    for (int i = ORDER_V + 1; i <= MAXNUM_DATA; i++)
    {
        j++;
        pNode->SetElement(j, this->GetElement(i));
        this->SetElement(i, INVALID);
    }
    // 设置好Count个数
    this->SetCount(this->GetCount() - j);
    pNode->SetCount(pNode->GetCount() + j);
    // 返回新结点的第一个元素作为键
    return pNode->GetElement(1);
}
// 结合结点,把指定叶子结点的数据全部剪切到本叶子结点
bool CLeafNode::Combine(CNode* pNode)
{
    // 参数检查
    if (this->GetCount() + pNode->GetCount() > MAXNUM_DATA)
    {
        return false;
    }
   
    for (int i = 1; i <= pNode->GetCount(); i++)
    {
        this->Insert(pNode->GetElement(i));
    }
    return true;
}
BPlusTree::BPlusTree()
{
    m_Depth = 0;
    m_Root = NULL;
    m_pLeafHead = NULL;
    m_pLeafTail = NULL;
}
BPlusTree::~BPlusTree()
{
    ClearTree();
}
// 在树中查找数据
bool BPlusTree::Search(KEY_TYPE data, char* sPath)
{
    int i = 0;
    int offset = 0;
    if (NULL != sPath)
    {
        (void)sprintf(sPath+offset, "The serach path is:");
        offset+=19;
    }
    CNode * pNode = GetRoot();
    // 循环查找对应的叶子结点
    while (NULL != pNode)
    {        
        // 结点为叶子结点,循环结束
        if (NODE_TYPE_LEAF == pNode->GetType())
        {
            break;
        }
        // 找到第一个键值大于等于key的位置
        for (i = 1; (data >= pNode->GetElement(i) )&& (i <= pNode->GetCount()); i++)
        {
        }
        if (NULL != sPath)
        {
            (void)sprintf(sPath+offset, " %3d -->", pNode->GetElement(1));
            offset+=8;
        }
        pNode = pNode->GetPointer(i);
    }
    // 没找到
    if (NULL == pNode)
    {
        return false;
    }
    if (NULL != sPath)
    {
        (void)sprintf(sPath+offset, "%3d", pNode->GetElement(1));
        offset+=3;
    }
    // 在叶子结点中继续找
    bool found = false;
    for (i = 1; (i <= pNode->GetCount()); i++)
    {
        if (data == pNode->GetElement(i))
        {
            found = true;
        }
    }
    if (NULL != sPath)
    {
        if (true == found)
        {
            (void)sprintf(sPath+offset, " ,successed.");
        }
        else
        {
            (void)sprintf(sPath+offset, " ,failed.");
        }
    }
    return found;
}
/* 在B+树中插入数据
插入数据首先要找到理论上要插入的叶子结点,然后分三种情况:
(1) 叶子结点未满。直接在该结点中插入即可;
(2) 叶子结点已满,且无父结点(即根结点是叶子结点),需要首先把叶子结点分裂,然后选择插入原结点或新结点,然后新生成根节点;
(3) 叶子结点已满,但其父结点未满。需要首先把叶子结点分裂,然后选择插入原结点或新结点,再修改父结点的指针;
(4) 叶子结点已满,且其父结点已满。需要首先把叶子结点分裂,然后选择插入原结点或新结点,接着把父结点分裂,再修改祖父结点的指针。
    因为祖父结点也可能满,所以可能需要一直递归到未满的祖先结点为止。
*/
bool BPlusTree::Insert(KEY_TYPE data)
{
    // 检查是否重复插入
    bool found = Search(data, NULL);
    if (true == found)
    {
        return false;
    }
    // for debug
    //if (289 == data)
    //{
    //    printf("/n%d,check failed!",data);
    //}
    // 查找理想的叶子结点
    CLeafNode* pOldNode = SearchLeafNode(data);
    // 如果没有找到,说明整个树是空的,生成根结点
    if (NULL == pOldNode)
    {
        pOldNode = new CLeafNode;
     m_pLeafHead = pOldNode;   
        m_pLeafTail = pOldNode;
        SetRoot(pOldNode);
    }
    // 叶子结点未满,对应情况1,直接插入
    if (pOldNode->GetCount() < MAXNUM_DATA)
    {
        return pOldNode->Insert(data);
    }
    // 原叶子结点已满,新建叶子结点,并把原结点后一半数据剪切到新结点
    CLeafNode* pNewNode = new CLeafNode;
    KEY_TYPE key = INVALID;
    key = pOldNode->Split(pNewNode);
    // 在双向链表中插入结点
    CLeafNode* pOldNext = pOldNode->m_pNextNode;
    pOldNode->m_pNextNode = pNewNode;
    pNewNode->m_pNextNode = pOldNext;
    pNewNode->m_pPrevNode = pOldNode;
    if (NULL == pOldNext)
    {
        m_pLeafTail = pNewNode;
    }
    else
    {
        pOldNext->m_pPrevNode = pNewNode;
    }

    // 判断是插入到原结点还是新结点中,确保是按数据值排序的
    if (data < key)
    {
        pOldNode->Insert(data);    // 插入原结点
    }
    else
    {
        pNewNode->Insert(data);    // 插入新结点
    }
    // 父结点
    CInternalNode* pFather = (CInternalNode*)(pOldNode->GetFather());
    // 如果原结点是根节点,对应情况2
    if (NULL == pFather)
    {
        CNode* pNode1 = new CInternalNode;
        pNode1->SetPointer(1, pOldNode);                           // 指针1指向原结点
        pNode1->SetElement(1, key);                                // 设置键
        pNode1->SetPointer(2, pNewNode);                           // 指针2指向新结点
        pOldNode->SetFather(pNode1);                               // 指定父结点
        pNewNode->SetFather(pNode1);                               // 指定父结点
        pNode1->SetCount(1);
        SetRoot(pNode1);                                           // 指定新的根结点
        return true;
    }
    // 情况3和情况4在这里实现
    bool ret = InsertInternalNode(pFather, key, pNewNode);
    return ret;
}
/* 删除某数据
删除数据的算法如下:
(1) 如果删除后叶子结点填充度仍>=50%,只需要修改叶子结点,如果删除的是父结点的键,父结点也要相应修改;
(2) 如果删除后叶子结点填充度<50%,需要先找到一个最近的兄弟结点(左右均可),然后分两种情况:
    A. 如果该兄弟结点填充度>50%,把该兄弟结点的最近一个数据剪切到本结点,父结点的键值也要相应修改。
    B. 如果该兄弟结点的填充度=50%,则把两个结点合并,父结点键也相应合并。(如果合并后父结点的填充度<50%,则需要递归)
*/
bool BPlusTree::Delete(KEY_TYPE data)
{
    // 查找理想的叶子结点
    CLeafNode* pOldNode = SearchLeafNode(data);
    // 如果没有找到,返回失败
    if (NULL == pOldNode)
    {
        return false;
    }
    // 删除数据,如果失败一定是没有找到,直接返回失败
    bool success = pOldNode->Delete(data);
    if (false == success)
    {
        return false;
    }
    // 获取父结点
    CInternalNode* pFather = (CInternalNode*)(pOldNode->GetFather());
    if (NULL == pFather)
    {
        // 如果一个数据都没有了,删除根结点(只有根节点可能出现此情况)
        if (0 == pOldNode->GetCount())
        {
            delete pOldNode;
            m_pLeafHead = NULL;
            m_pLeafTail = NULL;
            SetRoot(NULL);
        }
        return true;
    }
   
    // 删除后叶子结点填充度仍>=50%,对应情况1
    if (pOldNode->GetCount() >= ORDER_V)
    {
        for (int i = 1; (data >= pFather->GetElement(i)) && (i <= pFather->GetCount()); i++)
        {
            // 如果删除的是父结点的键值,需要更改该键
            if (pFather->GetElement(i) == data)
            {
                pFather->SetElement(i, pOldNode->GetElement(1));    // 更改为叶子结点新的第一个元素
            }
        }
        return true;
    }
    // 找到一个最近的兄弟结点(根据B+树的定义,除了叶子结点,总是能找到的)
    int flag = FLAG_LEFT;
    CLeafNode* pBrother = (CLeafNode*)(pOldNode->GetBrother(flag));
    // 兄弟结点填充度>50%,对应情况2A
    KEY_TYPE NewData = INVALID;
    if (pBrother->GetCount() > ORDER_V)
    {
        if (FLAG_LEFT == flag)    // 兄弟在左边,移最后一个数据过来
        {
            NewData = pBrother->GetElement(pBrother->GetCount());
        }
        else    // 兄弟在右边,移第一个数据过来
        {
            NewData = pBrother->GetElement(1);
        }
        pOldNode->Insert(NewData);
        pBrother->Delete(NewData);
        // 修改父结点的键值
        if (FLAG_LEFT == flag)
        {
            for (int i = 1; i <= pFather->GetCount() + 1; i++)
            {
                if (pFather->GetPointer(i) == pOldNode && i > 1)
                {
                    pFather->SetElement(i - 1 , pOldNode->GetElement(1));    // 更改本结点对应的键
                }
            }
        }
        else
        {
            for (int i = 1; i <= pFather->GetCount() + 1; i++)
            {
                if (pFather->GetPointer(i) == pOldNode && i > 1)
                {
                    pFather->SetElement(i - 1, pOldNode->GetElement(1));    // 更改本结点对应的键
                }
                if (pFather->GetPointer(i) == pBrother && i > 1)
                {
                    pFather->SetElement(i - 1 , pBrother->GetElement(1));    // 更改兄弟结点对应的键
                }
            }
        }

        return true;
    }
    // 情况2B
   
    // 父结点中要删除的键
    KEY_TYPE NewKey = NULL;
    // 把本结点与兄弟结点合并,无论如何合并到数据较小的结点,这样父结点就无需修改指针
   
    if (FLAG_LEFT == flag)
    {
        (void)pBrother->Combine(pOldNode);
        NewKey = pOldNode->GetElement(1);
        CLeafNode* pOldNext = pOldNode->m_pNextNode;
        pBrother->m_pNextNode = pOldNext;
        // 在双向链表中删除结点
        if (NULL == pOldNext)
        {
            m_pLeafTail = pBrother;
        }
        else
        {
            pOldNext->m_pPrevNode = pBrother;
        }
        // 删除本结点
        delete pOldNode;
    }
    else
    {
        (void)pOldNode->Combine(pBrother);
        NewKey = pBrother->GetElement(1);
        CLeafNode* pOldNext = pBrother->m_pNextNode;
        pOldNode->m_pNextNode = pOldNext;
        // 在双向链表中删除结点
        if (NULL == pOldNext)
        {
           m_pLeafTail = pOldNode;
        }
        else
        {
            pOldNext->m_pPrevNode = pOldNode;
        }
         // 删除本结点
        delete pBrother;
    }
    return DeleteInternalNode(pFather, NewKey);
}
// 清除整个树,删除所有结点
void BPlusTree::ClearTree()
{
    CNode* pNode = GetRoot();
    if (NULL != pNode)
    {
        pNode->DeleteChildren();
   
        delete pNode;
    }
    m_pLeafHead = NULL;
    m_pLeafTail = NULL;
    SetRoot(NULL);
}
// 旋转以重新平衡,实际上是把整个树重构一下,结果不理想,待重新考虑
BPlusTree* BPlusTree::RotateTree()
{
    BPlusTree* pNewTree = new BPlusTree;
    int i = 0;
    CLeafNode * pNode = m_pLeafHead;
    while (NULL != pNode)
    {
        for (int i = 1; i <= pNode->GetCount(); i ++)
        {
            (void)pNewTree->Insert(pNode->GetElement(i));
        }
        pNode = pNode->m_pNextNode;
    }
    return pNewTree;
   
}
// 检查树是否满足B+树的定义
bool BPlusTree::CheckTree()
{
    CLeafNode * pThisNode = m_pLeafHead;
    CLeafNode * pNextNode = NULL;
    while (NULL != pThisNode)
    {
        pNextNode = pThisNode->m_pNextNode;
        if (NULL != pNextNode)
        {
           if (pThisNode->GetElement(pThisNode->GetCount()) > pNextNode->GetElement(1))
           {
               return false;
           }
        }
        pThisNode = pNextNode;
    }
       
    return CheckNode(GetRoot());
}
// 递归检查结点及其子树是否满足B+树的定义
bool BPlusTree::CheckNode(CNode* pNode)
{
    if (NULL == pNode)
    {
        return true;
    }
   
    int i = 0;
    bool ret = false;
   
    // 检查是否满足50%的填充度
    if ((pNode->GetCount() < ORDER_V) && (pNode != GetRoot()))
   {
        return false;
    }
    // 检查键或数据是否按大小排序
    for (i = 1; i < pNode->GetCount(); i++)
    {
        if (pNode->GetElement(i) > pNode->GetElement(i + 1))
        {
            return false;
        }
    }
    if (NODE_TYPE_LEAF == pNode->GetType())
    {
        return true;
    }
    // 对中间结点,递归检查子树
    for (i = 1; i <= pNode->GetCount() + 1; i++)
    {
        ret = CheckNode(pNode->GetPointer(i));
     // 只要有一个不合法就返回不合法
        if (false == ret)
        {
            return false;
        }
    }
    return true;
}
// 打印整个树
void BPlusTree::PrintTree()
{
    CNode* pRoot = GetRoot();
    if (NULL == pRoot) return;
    CNode* p1, *p2, *p3;
    int i, j, k;
    int total = 0;
    printf("/n第一层/n | ");
    PrintNode(pRoot);
    total = 0;
    printf("/n第二层/n | ");
    for (i = 1; i <= MAXNUM_POINTER; i++)
    {
        p1 = pRoot->GetPointer(i);
        if (NULL == p1) continue;
        PrintNode(p1);
        total++;
        if (total%4 == 0) printf("/n | ");
    }
    total = 0;
    printf("/n第三层/n | ");
    for (i = 1; i <= MAXNUM_POINTER; i++)
    {
        p1 = pRoot->GetPointer(i);
        if (NULL == p1) continue;
        for (j = 1; j <= MAXNUM_POINTER; j++)
        {
            p2 = p1->GetPointer(j);
            if (NULL == p2) continue;
            PrintNode(p2);
            total++;
            if (total%4 == 0) printf("/n | ");
        }
    }
    total = 0;
    printf("/n第四层/n | ");
    for (i = 1; i <= MAXNUM_POINTER; i++)
    {
        p1 = pRoot->GetPointer(i);
        if (NULL == p1) continue;
        for (j = 1; j <= MAXNUM_POINTER; j++)
        {
            p2 = p1->GetPointer(j);
            if (NULL == p2) continue;
            for (k = 1; k <= MAXNUM_POINTER; k++)
            {
                p3 = p2->GetPointer(k);
                if (NULL == p3) continue;
                PrintNode(p3);
                total++;
                if (total%4 == 0) printf("/n | ");
            }
        }
    }
}
// 打印某结点
void BPlusTree::PrintNode(CNode* pNode)
{
    if (NULL == pNode)
    {
        return;
    }
   
    for (int i = 1; i <= MAXNUM_KEY; i++)
    {
        printf("%3d ", pNode->GetElement(i));
        if (i >= MAXNUM_KEY)
        {
            printf(" | ");
        }
    }
}
// 查找对应的叶子结点
CLeafNode* BPlusTree::SearchLeafNode(KEY_TYPE data)
{
    int i = 0;
    CNode * pNode = GetRoot();
    // 循环查找对应的叶子结点
    while (NULL != pNode)
    {        
        // 结点为叶子结点,循环结束
        if (NODE_TYPE_LEAF == pNode->GetType())
        {
            break;
        }
        // 找到第一个键值大于等于key的位置
        for (i = 1; i <= pNode->GetCount(); i++)
        {
            if (data < pNode->GetElement(i))
            {
                break;
            }
        }
        pNode = pNode->GetPointer(i);
    }
    return (CLeafNode*)pNode;
}
//递归函数:插入键到中间结点
bool BPlusTree::InsertInternalNode(CInternalNode* pNode, KEY_TYPE key, CNode* pRightSon)
{
    if (NULL == pNode || NODE_TYPE_LEAF ==pNode->GetType())
    {
        return false;
    }

    // 结点未满,直接插入
    if (pNode->GetCount() < MAXNUM_KEY)
    {
        return pNode->Insert(key, pRightSon);
    }
    CInternalNode* pBrother = new CInternalNode;
    KEY_TYPE NewKey = INVALID;
    // 分裂本结点
    NewKey = pNode->Split(pBrother, key);
    if (pNode->GetCount() < pBrother->GetCount())
    {
        pNode->Insert(key, pRightSon);
    }
    else if (pNode->GetCount() > pBrother->GetCount())
    {
         pBrother->Insert(key, pRightSon);
    }
    else    // 两者相等,即键值在第V和V+1个键值中间的情况,把字节点挂到新结点的第一个指针上
    {
        pBrother->SetPointer(1,pRightSon);
        pRightSon->SetFather(pBrother);
    }
    CInternalNode* pFather = (CInternalNode*)(pNode->GetFather());
    // 直到根结点都满了,新生成根结点
    if (NULL == pFather)
    {
        pFather = new CInternalNode;
        pFather->SetPointer(1, pNode);                           // 指针1指向原结点
        pFather->SetElement(1, NewKey);                          // 设置键
        pFather->SetPointer(2, pBrother);                        // 指针2指向新结点
        pNode->SetFather(pFather);                               // 指定父结点
        pBrother->SetFather(pFather);                            // 指定父结点
        pFather->SetCount(1);
        SetRoot(pFather);                                        // 指定新的根结点
        return true;
    }
    // 递归
    return InsertInternalNode(pFather, NewKey, pBrother);
}
// 递归函数:在中间结点中删除键
bool BPlusTree::DeleteInternalNode(CInternalNode* pNode, KEY_TYPE key)
{
    // 删除键,如果失败一定是没有找到,直接返回失败
    bool success = pNode->Delete(key);
    if (false == success)
    {
        return false;
    }
    // 获取父结点
    CInternalNode* pFather = (CInternalNode*)(pNode->GetFather());
    if (NULL == pFather)
    {
        // 如果一个数据都没有了,把根结点的第一个结点作为根结点
        if (0 == pNode->GetCount())
        {
            SetRoot(pNode->GetPointer(1));
            delete pNode;
        }
        return true;
    }
   
    // 删除后结点填充度仍>=50%
    if (pNode->GetCount() >= ORDER_V)
    {
        for (int i = 1; (key >= pFather->GetElement(i)) && (i <= pFather->GetCount()); i++)
        {
            // 如果删除的是父结点的键值,需要更改该键
            if (pFather->GetElement(i) == key)
            {
                pFather->SetElement(i, pNode->GetElement(1));    // 更改为叶子结点新的第一个元素
            }
        }
        return true;
    }
    // 找到一个最近的兄弟结点(根据B+树的定义,除了根结点,总是能找到的)
    int flag = FLAG_LEFT;
    CInternalNode* pBrother = (CInternalNode*)(pNode->GetBrother(flag));
    // 兄弟结点填充度>50%
    KEY_TYPE NewData = INVALID;
    if (pBrother->GetCount() > ORDER_V)
    {
        pNode->MoveOneElement(pBrother);
        // 修改父结点的键值
        if (FLAG_LEFT == flag)
        {
            for (int i = 1; i <= pFather->GetCount() + 1; i++)
            {
                if (pFather->GetPointer(i) == pNode && i > 1)
                {
                    pFather->SetElement(i - 1 , pNode->GetElement(1));    // 更改本结点对应的键
                }
            }
        }
        else
        {
            for (int i = 1; i <= pFather->GetCount() + 1; i++)
            {
                if (pFather->GetPointer(i) == pNode && i > 1)
                {
                    pFather->SetElement(i - 1, pNode->GetElement(1));    // 更改本结点对应的键
                }
                if (pFather->GetPointer(i) == pBrother && i > 1)
                {
                    pFather->SetElement(i - 1 , pBrother->GetElement(1));    // 更改兄弟结点对应的键
                }
            }
        }
        return true;
    }
   
    // 父结点中要删除的键
    KEY_TYPE NewKey = NULL;
    // 把本结点与兄弟结点合并,无论如何合并到数据较小的结点,这样父结点就无需修改指针
    if (FLAG_LEFT == flag)
    {
        (void)pBrother->Combine(pNode);
        NewKey = pNode->GetElement(1);
        delete pNode;
    }
    else
    {
        (void)pNode->Combine(pBrother);
        NewKey = pBrother->GetElement(1);
        delete pBrother;
    }
    // 递归
    return DeleteInternalNode(pFather, NewKey);
}

 

 

/*end of   BPlusTree.cpp*/

 

 

/*main*/

 

 

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "BPlusTree.h"

// 随机建立一棵树
void Test1(BPlusTree* pTree, int count)
{
    pTree->ClearTree();
    //and( (unsigned)time( NULL ) );//这是一个种子,如果不要随机功能,请把此句话注释掉
    for (int i = 0; i < count; i++)
    {
        int x = rand()%999 + 1;
        (void)pTree->Insert(x);
    }
    printf("successed!/n");
}
// 在树中查找某数据
void Test2(BPlusTree* pTree, int data)
{
    char sPath[255] = {0, };
    (void)pTree->Search(data, sPath);
    printf("/n%s", sPath);
}
// 在树中插入某数据
void Test3(BPlusTree* pTree, int data)
{
    bool success = pTree->Insert(data);
    if (true == success)
    {
        printf("/nsuccessed!/n");
    }
    else
    {
        printf("/nfailed!/n");
    }
}
// 在树中删除某数据
void Test4(BPlusTree* pTree, int data)
{
    bool success = pTree->Delete(data);
    if (true == success)
    {
        printf("/nsuccessed!/n");
    }
    else
    {
        printf("/nfailed!/n");
    }
}
// 对树进行旋转
BPlusTree* Test5(BPlusTree* pTree)
{
    BPlusTree* pNewTree = pTree->RotateTree();
    delete pTree;
    printf("/nsuccessed!/n");
    return pNewTree;
}
// 打印
void Test6(BPlusTree* pTree)
{
    pTree->PrintTree();
}
// 对树进行检查
void Test7(BPlusTree* pTree)
{
    bool success = pTree->CheckTree();
    if (true == success)
    {
        printf("/nsuccessed!/n");
    }
    else
    {
        printf("/nfailed!/n");
    }
}

int main(int argc, char* argv[])
{
    BPlusTree* pTree = new BPlusTree;
    int x = 1;
    int y = 0;
    while (0 != x)
    {
        printf("/n/n");
        printf("    *******************************************************************/n");
        printf("    *           欢迎进入B+树演示程序,请选择相应功能。                */n");
        printf("    *           1。随机建立一棵B+树;                                 */n");
        printf("    *           2。在B+树中查找一个数;                               */n");
        printf("    *           3。在B+树中插入一个数;                               */n");
        printf("    *           4。在B+树中删除一个数;                               */n");
        printf("    *           5。对B+树旋转,进行重新平衡;                         */n");
        printf("    *           6。显示整个B+树;                                     */n");
        printf("    *           7。检查整个B+树;                                     */n");
        printf("    *           0。退出程序;                                         */n");
        printf("    *******************************************************************/n");
        printf("/n    您的选择是:");
      
        scanf("%d", &x);
        switch (x)
        {
        case 1:
            printf("请输入数据个数(10-150):");
            scanf("%d", &y);
            Test1(pTree, y);
            break;
       
        case 2:
            printf("请输入要查找的数值:");
            scanf("%d", &y);
            Test2(pTree, y);
            break;
        case 3:
            printf("请输入要插入的数值:");
            scanf("%d", &y);
            Test3(pTree, y);
            break;
        case 4:
            printf("请输入要删除的数值:");
            scanf("%d", &y);
            Test4(pTree, y);
            break;
        case 5:
            pTree = Test5(pTree);
            break;
        case 6:
            Test6(pTree);
            break;
        case 7:
            Test7(pTree);
            break;
        case 0:
         delete pTree;
            return 0;
            break;
        default:
            break;
        }
    }
    delete pTree;
    return 0;
}

 

 

/*end of main*/