skyrainreg.cpp

《数据结构》中二叉树的常用算法的练习。包括排序、兄弟－孩子链表的建立

*                                                                            
****************************************************************************/
void CSkyRainReg::Insert(PREGKEY pParentKey, PREGKEY pInsertPos, PREGKEY pSubKey)
{
    // 如果插入位置是父结点的位置，也即是pSubKey是pParentKey的第一个孩子结点，
    // 需要把原来的结点后移。
    if (pParentKey == pInsertPos) 
    {                             
        pSubKey->SibKey    = pParentKey->SubKey;
        pParentKey->SubKey = pSubKey;
        pSubKey->Parent    = pParentKey;
    }

    // 此时pSubKey是pParentKey->SubKey的兄弟结点
    else                        
    {
        pSubKey->SibKey    = pInsertPos->SibKey;
        pInsertPos->SibKey = pSubKey;
        pSubKey->Parent    = pInsertPos;
    }

    if (pSubKey->SibKey) 
    {
        pSubKey->SibKey->Parent = pSubKey;
    }
}
//---------------------------------------------------------------------------

/****************************************************************************
*                                                                            
*   函数名称：Insert(重载)                                                   
*                                                                            
*   实现功能：在当前主键结点pKey的键值列表中插入一个新结点pNode                 
*                                                                            
*   参数说明：pKey  当前主键结点                                             
*            pPrev 当前主键键值列表中要插入结点位置的前驱                   
*            pNode 要插入的键键结点                                         
*                                                                           
*   返 回 值：无                                                             
*                                                                            
*   日    期：2003.12.25 -- 2006.02.19                                       
*                                                                          
****************************************************************************/
void CSkyRainReg::Insert(PREGKEY pKey, PREGVALUE pPrev, PREGVALUE pNode)
{
    if (!pKey || !pNode)
    {
        return;
    }

    /**************************************************************************
    * ①如果主键pKey的键值链表为空，要插入的pNode即为主键pKey的第一个键值结点。
    * pKey■-->●pNode
    **************************************************************************/
    if (pKey->Value == NULL)   
    {
        pKey->Value = pNode;
    }
    
    /**************************************************************************
    * ②如果待插入位置的前驱结点为主键pKey的第一个键值结点，并且该结点的名称大于
    * pNode的名称，此时需要把pNode插入为pKey的第一个键值结点。
    *       pPrev
    *         ↓
    * pKey■-->●B   ●A<--pNode
    *
    * 插入●A<--pNode后：
    *            pPrev
    *              ↓
    * pKey■-->●A-->●B 
    *         ↑
    *       pNode
    **************************************************************************/
    else if(pKey->Value==pPrev && CompareName(pPrev, pNode)>0)
    {
        pNode->Next = pPrev;
        pKey->Value = pNode;
    }
    
    /**************************************************************************
    * ③其它情况直接插入到待插入位置的前驱结点pPrev之后。 
    **************************************************************************/
    else
    {
        pNode->Next = pPrev->Next;
        pPrev->Next = pNode;
    }
}
//---------------------------------------------------------------------------

PREGKEY CSkyRainReg::CreateKey(PSTRTYPE Name)
{   // 在当前打开的主键中增加一个名称为Name的主键，如果要创建的
    // 主键已经存在，该函数什么也不干。
    // 2006.03.03
    PREGKEY KeyNode;
   
    // 首先在当前打开的主键的第一层子主键中查找是否有同名的结点
    // 如果有同样名称的主键结点，则不进行插入新建操作。
    if (Search(OpenKeyPtr->SubKey, Name, KeyNode) == saSuccess)
    {
        return NULL;
    }
    return Insert(KeyNode, Name);
}
//---------------------------------------------------------------------------

WORD CSkyRainReg::CreateValue(PREGVALUE &pValue, PSTRTYPE Name)
{   // 在当前主键中创建名为的Name键值，如果该键值名已经存在，则该函数什么
    // 也不干。其实际是在二叉树中主键结点的键值列表中按顺序插入一个新结点。
    // 2003.02.13 -- 2006.02.23

    // 在当前打开的主键的键值链表中查找同名的键值结点是否已经存在
    // 若查找到该键值，则用pVale返回指向该键值的指针,
    if (Search(OpenKeyPtr->Value, Name, pValue) == saSuccess)
    {
        // 已经存在相同的结点不需要再创建
        return caExistNoCreate;
    }

    // 没有查找到，则创建一个新的键值结点，并返回该键值结点
    PREGVALUE NewValue = CreateValueNode(CreateInfoNode(Name), Name);

    // 在pValue之后，完成新建结点的插入
    Insert(OpenKeyPtr, pValue, NewValue);

    // 移动pValue指针到新的键值结点
    pValue = NewValue;
    
    // 已创建一个新的结点
    return caCreated; 
}
//---------------------------------------------------------------------------

PSTRTYPE CSkyRainReg::GetSubKey(PSTRTYPE &Key)
{   // 对例如Key为“AA\BB\CC”这样的主键字符串进行处理
    // 返回子键Key中第一个'\'字符前的字符串“AA”，并对Key重新赋值
    // Key取第一个'\'字符后余下的子字符串“BB\CC”。
    // 2006.02.19
    
    // 返回Key中第一个'\\'字符出现的位置
    int nPos = AnsiPos(Key, '\\');
    if (nPos<0) 
    {
        PSTRTYPE temp = NULL;
        StrCopy(temp,Key);
        Key[0] = '\0'; 
        Key[0] = '\0';
        return temp;
    }

    PSTRTYPE SubKey = new STRTYPE[nPos+1];
    SubKey[nPos] = '\0';

    // 从Key的第一个字符开始拷贝nPos个字符到SubKey中
    StrNCopy(SubKey, Key, nPos);

    // 从nPos+1开始，一直到Key的结尾，让Key取第一个'\\'字符后的子字符串
    StrStartEndCopy(Key, Key, nPos+1, StrLen(Key)); 
    return SubKey;
}
//---------------------------------------------------------------------------

bool CSkyRainReg::OpenKey(PSTRTYPE Key, bool CanCreate)
{   // 若CanCreate为TRUE时当Key在链表中不存在时则创建子主键,否则不创建
    // 此函数的实际作用是定位指针OpenKeyPtr。
    // 例如：Key = "A\B\C"，表示B是A的子主键，C又是B的子主键。先在Root
    // 中查找主键A，如果A存在，再在主键A中查找B，如果B也存在，则继续在
    // B中查找C，最后如果A、B、C三个主键都存在，OpenKeyPtr指针最后就指
    // 向主键C。但如果三个中有一个不存在，例如如果C不存在，并且CanCreate
    // =TRUE，则在主键B中创建主键C，并让指针OpenKeyPtr指向C；如果CanCreate
    // =FALSE，则返回，此时OpenKeyPtr指向主键B。
    // 2006.02.20

    // Key值不合法
    if (StrLen(Key) == 0) 
    {
        return FALSE;
    }

    // Key开头不能有'\'
    if (Key[0] == '\\')
    {
        StrStartEndCopy(Key, Key, 1, StrLen(Key));
    }

    // Key结尾不能有'\'
    if (Key[StrLen(Key)-1] == '\\')
    {
        StrNCopy(Key, Key, StrLen(Key)-1);
    }

    PSTRTYPE SubKey;
    PREGKEY  ptemp;

    OpenKeyPtr = Root;
    while (StrLen(Key) != 0)
    {
        // 从Key的前端开始取出子主键，并把余下的子主键让Key记录
        SubKey = GetSubKey(Key);

        // 如果在当前主键中没有查找到于SubKey相匹配的主键，则根据
        // CanCreate的情况确定是否继续进行。
        // 此时查找结束后ptemp是OpenKeyPtr的子主键
		if (Search(OpenKeyPtr->SubKey, SubKey, ptemp) != saSuccess)
        {
            // 在OpenKeyPtr中ptemp后创建名称为SubKey的新结点，并
            // 插入到ptemp后，然后让OpenKeyPtr指向新建的结点。
            if (CanCreate) 
            {
                OpenKeyPtr = Insert(ptemp, SubKey);
            }
             
            else 
            {
                return FALSE;
            }
        }

        // 如果查找成功，则移动OpenKeyPtr指向匹配的结点
        else 
        {
            OpenKeyPtr = ptemp;
        }
    }// while Key
    return TRUE;
}
//---------------------------------------------------------------------------

CSearchActive CSkyRainReg::Search(PREGKEY pNode, PSTRTYPE Name, PREGKEY &ptr)
{   // 从pNode开始在其兄弟结点中查找名称为Name的主键结点，若找到则返回TRUE，
    // 并使ptr指向该结点；否则返回FALSE；并使ptr指向最后查找结点的前驱结点。
    // 2003.08.17 -- 2006.02.20

    int Option;          // 记录两个字符串比较的结果
    ptr = OpenKeyPtr;    // ptr首先指向当前打开结点的指针
    while (pNode)
    {
        // 把字符串名称全部转换为大写后进行比较
        Option = CompareStr(pNode->Name, Name);

        // 如果当前结点pNode->Name比Name小，则沿pNode->SibKey(兄弟结点)
        // 指针走，继续进行查找。
        if (Option < 0) 
        { 
            ptr   = pNode; 
            pNode = pNode->SibKey; 
        }

        // 查找到所需的结点，查找成功，中断查找返回saSuccess
        else if(Option == 0) 
        { 
            ptr = pNode; 
            return saSuccess; 
        }

        // 当前结点pNode->Name比Name大，因为同一层中的主键结点是按升序排列，
        // 不需要再继续查找，则返回saPrevBig，此时ptr指向pNode的前驱。
        else 
        {
            return saPrevBig;
        }
    }

    // 如果查找到最后，也没有查找到与Name匹配的结点则返回saUnsuccess，
    // 此时ptr指向OpenKeyPtr打开的第一层主键的最后一个结点。
    return saUnsuccess;
}
//---------------------------------------------------------------------------

WORD CSkyRainReg::Search(PREGVALUE pValue, PSTRTYPE Name, PREGVALUE &ptr)
{   // 从pValue开始,在其所有兄弟键值结点链表中查找名称为Name的键值结点，若
    // 找到则返回TRUE，并使ptr指向该结点；否则返回FALSE，并使ptr指向最后查
    // 找结点的前驱结点。
    // 2003.08.17 -- 2006.02.20
    
    int Option;
    ptr = pValue;

    while (pValue)
    {
        // 全部转换为大写进行比较
        Option = CompareStr(pValue->Name, Name);

        // 当前结点pNode->Name比Name小则沿单链表继续查找