skyrainreg.cpp

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

*                         /                                                 *
*                        /                                                  *
*            PrevNode-->■B───●b0───●b1                                      *
*                      /                                                    *
*                     /                                                     *
*              c0●───■C                                                     *
*                     \                                                     *
*                      \                                                    *
*                       ■D                                                  *
*           插入结点F：                                                     *
*                Root --->■A                                                *
*                         /                                                 *
*                        /                                                  *
*           PrevNode-->■B───●b0───●b1                                       *
*                      / \                                                  *
*                     /   \                                                 *
*              c0●───■C    ■F───●f0───●f1                                   *
*                     \                                                     *
*                      \                                                    *
*                       ■D                                                  *
*                                                                           *
*           到此整个二叉树链表创建完毕。                                    *
*                                                                           *
*   参数说明：hFile 已打开的数据文件句柄                                    *
*                                                                           *
*   返 回 值：若成功创建返回TRUE，否则返回FALSE                             *
*                                                                           *
*   日    期：2003.08.09 -- 2006.03.02                                      *
*                                                                           *
****************************************************************************/
bool CSkyRainReg::PreOrderCreateBiTree(HANDLE hFile)
{   
    if (Root == NULL) 
    {
        CreateRoot();
    }

    PREGKEY KeyNode;
    PREGKEY PrevNode = Root;         // 前驱指针
    
    // 从文件中读取数据并创建主键结点，若读取数据期间发送读数错误
    // 或读到文件结尾，退出循环。  
    //ShowMsg("开始循环读取数据创建");
    while (ReadCreateKeyNode(KeyNode, hFile))
    {
        // 如果前驱结点信息中记录为结点为子结点，则新建的结点为前
        // 驱结点的孩子结点，根结点肯定有子结点。
        if (PrevNode->Info->cFlag == hsnHAVE) 
        {
            PrevNode->SubKey = KeyNode;
        }

        // 否则新建的结点为前驱结点的兄弟结点
        else
        {
            // 第04步回溯PrevNode指针条件
            while (!(!PrevNode->SibKey && PrevNode->Info->sFlag==hsnHAVE))
            {
                 PrevNode = PrevNode->Parent;
            }
            
            PrevNode->SibKey = KeyNode;
        }

        KeyNode->Parent = PrevNode;
        PrevNode = KeyNode;
    } 

    return TRUE;                    
}
//---------------------------------------------------------------------------

CLoadFileActive CSkyRainReg::LoadFromFile(PSTRTYPE AFileName)
{   // 从文件中加载数据
    
    // 文件不存在
    if (INVALID_FILE_ATTRIBUTES == GetFileAttributes(AFileName)) 
    {
        return lfaFileNotExist;
    }

    HANDLE hFile = CreateFile(AFileName,                    // 打开的文件的名字
                              GENERIC_READ|GENERIC_WRITE,   // 允许对文件进行读写访问
                              0,                            // 不共享
                              NULL, // 指向一个SECURITY_ATTRIBUTES结构的指针，定义了文件的安全特性
                              OPEN_EXISTING,                // 文件必须已经存在
                              FILE_ATTRIBUTE_ARCHIVE,       // 标记归档属性
                              NULL);// 如果不为零，则指定一个文件句柄。新文件将从这个文件中复制扩展属性
    
    // 打开文件错误
    if (hFile == INVALID_HANDLE_VALUE)
    {
        return lfaFileVoid;
    }

    // 返回文件的长度
    DWORD nFileLength = 0;
    nFileLength = GetFileSize(hFile, &nFileLength); 
    if (nFileLength == INVALID_FILE_SIZE)
    {
        CloseHandle(hFile);
        return lfaFileVoid;
    }

    // 所指定的文件为空
    if (nFileLength < sizeof(REGINFO))
    {
        CloseHandle(hFile);
        return lfaFileVoid;      
    }

    SetFilePointer(hFile, 0, 0, FILE_BEGIN);

    // 先序创建二叉树链表
    PreOrderCreateBiTree(hFile);
    CloseHandle(hFile);
    return lfaSuccess;
}
//---------------------------------------------------------------------------

void CSkyRainReg::Save(void)
{   // 保存数据
    SaveToFile(FileName);
}
//---------------------------------------------------------------------------

bool CSkyRainReg::SaveToFile(PSTRTYPE AFileName)
{   // 把数据写入文件中 2006.03.03
    
    DeleteFile(AFileName);
   
    HANDLE hFile = CreateFile(AFileName,                    // 打开的文件的名字
                              GENERIC_READ|GENERIC_WRITE,   // 允许对文件进行读写访问
                              0,                            // 不共享
                              NULL, // 指向一个SECURITY_ATTRIBUTES结构的指针，定义了文件的安全特性
                              OPEN_ALWAYS,                   // 如文件不存在则创建它
                              FILE_ATTRIBUTE_ARCHIVE,       // 标记归档属性
                              NULL);// 如果不为零，则指定一个文件句柄。新文件将从这个文件中复制扩展属性
    
    
    // 创建文件错误
    if (hFile == INVALID_HANDLE_VALUE)
    {
        return FALSE;
    }

    // 如果没有数据项不需要保存操作。先序遍历二叉树算法，往文件中写入数据。
    if (Root && Root->SubKey) 
    { 
        // 根结点"天雨注册表"不存入文件中
        PreOrderWrite(hFile, Root->SubKey);
    }
    CloseHandle(hFile);
    return TRUE;
}
//---------------------------------------------------------------------------

void CSkyRainReg::PreOrderWrite(HANDLE hFile, PREGKEY pNode)
{   // 先序遍历二叉树递归算法,把以pNode为根结点的二叉树中所有的结点的数据保存到文件中
    // 2006.03.03

    if (!pNode || hFile==INVALID_HANDLE_VALUE) 
    {
        return;
    }

    // 1.先写主键结点的数据
    WriteKey(hFile, pNode);
    
    // 2.写pNode的键值结点的数据
    WriteValue(hFile, pNode);

    // 3.遍历pNode的子树结点
    PreOrderWrite(hFile, pNode->SubKey);

    // 4.遍历pNode的兄弟结点
    PreOrderWrite(hFile, pNode->SibKey);
}
//---------------------------------------------------------------------------

void CSkyRainReg::WriteKey(HANDLE hFile, PREGKEY pNode)
{   // 把主键结点pNode的数据写入文件中
    // 2006.03.03
    if (pNode==NULL || hFile==INVALID_HANDLE_VALUE) 
    {
        return;
    }

    pNode->Info->sFlag      = (pNode->SibKey) ? hsnHAVE : hsnNO;
    pNode->Info->cFlag      = (pNode->SubKey) ? hsnHAVE : hsnNO;
    pNode->Info->vFlag      = (pNode->Value ) ? hsnHAVE : hsnNO;
    pNode->Info->StringSize = StrLen(pNode->Name);
    
    // 关于主键目前暂不存放任何数据，以后再升级时，可以考虑保存数据
    pNode->Info->DTByteSize = 0; // 主键没有数据记录
    DWORD nWriteCount = 0;

    // 1.先写主键结点的信息数据
    WriteFile(hFile,pNode->Info,sizeof(REGINFO),&nWriteCount,NULL);

    // 2.再写主键结点的名称
    WriteFile(hFile,pNode->Name,sizeof(STRTYPE)*StrLen(pNode->Name),&nWriteCount,NULL);
}
//---------------------------------------------------------------------------

void  CSkyRainReg::WriteValue(HANDLE hFile, PREGKEY pNode)
{   // 把主键结点pNode所拥有的所有键值结点数据写入文件
    // 2006.03.03
    if (pNode==NULL || hFile==INVALID_HANDLE_VALUE) 
    {
        return;
    }

    DWORD nWriteCount = 0;
    PREGVALUE pValue  = pNode->Value;
    while(pValue)
    {
        // 该键值结点是否有下一个兄弟结点
        pValue->Info->sFlag = (pValue->Next) ? hsnHAVE : hsnNO;
        pValue->Info->cFlag = hsnNO;
        pValue->Info->vFlag = hsnNO;
        pValue->Info->StringSize = StrLen(pValue->Name);

        // 1.写键值结点信息
        WriteFile(hFile,pValue->Info,sizeof(REGINFO),&nWriteCount,NULL);

        // 2.写键值结点的名称
        WriteFile(hFile,pValue->Name,sizeof(STRTYPE)*StrLen(pValue->Name),&nWriteCount,NULL);
    
        // 3.写键值结点记录的数据
        WriteFile(hFile,pValue->Data,pValue->Info->DTByteSize*pValue->Info->DTByteLen,&nWriteCount,NULL);

        pValue = pValue->Next;
    }
}
//---------------------------------------------------------------------------

/****************************************************************************
*                                                                            
*   函数名称：Insert(重载)                                                   
*                                                                            
*   实现功能：在当前主键结点pNode中插入一个孩子结点或兄弟结点，Name参数指    
*            定要创建的结点名,并使CuurenCKeyNode指向创建的结点, 并返回新    
*            创建并加入的主键结点。                                         
*                                                                            
*   参数说明：                                                               
*                                                                            
*   返 回 值：无                                                             
*                                                                            
*   日    期：2003.12.16 -- 2006.02.19                                       
*                                                                            
****************************************************************************/
SkyRain::CKeyNode *CSkyRainReg::Insert(PREGKEY pNode, PSTRTYPE Name)
{
    SkyRain::CKeyNode  *NewKey;
    SkyRain::CNodeInfo *InfoNode;

    // 创建一个信息结点
    InfoNode = CreateInfoNode(Name);

    // 创建一个主键结点
    NewKey = CreateKeyNode(InfoNode, Name);
    NewKey->Parent = pNode;

    // 在当前打开的主键OpenKeyPtr中的第一层子主键中，
    // 在pNode指示的位置中，完成新建结点NewKey的插入。
    Insert(OpenKeyPtr, pNode, NewKey);

    return NewKey;
}
//---------------------------------------------------------------------------

/****************************************************************************
*                                                                            
*   函数名称：Insert(重载)                                                   
*                                                                            
*   实现功能：在主键pParentKey中的第一层子主键中的结点位置pInsertPos后插     
*             入子主键pSubKey。                                              
*                                                                            
*   参数说明：pParentKey 当前父主键                                         
*             pSubKey    要插入的子主键                                      
*             pInsertPos 插入结点的位置，可能指示pParentKey结点，也可能     
*                        指示pParentKey的子主键中的某一个结点                
*                                                                            
*   返 回 值：无                                                             
*                                                                            
*   日    期：2003.12.29 --2006.02.19