📄 skyrainreg.cpp
字号:
****************************************************************************/
int CSkyRainReg::GetValueCount(PREGKEY pKey)
{
int i=0;
// 获得当前打开的主键的键指链表
PREGVALUE pNode = pKey->Value;
while (pNode)
{
i++;
pNode = pNode->Next;
}
return i;
}
//---------------------------------------------------------------------------
/****************************************************************************
* *
* 函数名称：CutDownNode *
* *
* 隶属对象：CSkyRainReg : private *
* *
* 用 法：void CutDownNode(SkyRain::CKeyNode *pMainKey, *
* SkyRain::CKeyNode *&pSubKey) *
* *
* 实现功能：在当前主键pMainKey中断开子主键pSubKey *
* *
* 参数说明：pMainKey 指向已打开主键的结点的指针 *
* pSubKey 将要与二叉链表断开的结点指针 *
* *
* 返 回 值：无 *
* *
* 日 期：2003.12.16 *
* *
* 修改日期：2006.01.27 -- 2006.02.15 *
* *
****************************************************************************/
void CSkyRainReg::CutDownNode(
PREGKEY pMainKey,
PREGKEY &pSubKey)
{
// 若pSubKey是主键pMainKey的第一个孩子结点，则使pSubKey的兄弟结点成为
// pMainKey的第一个孩子结点，并使pSubKey的所有子结点和pSubKey一起脱离
// 链表结构。
/***********************************************************************\
* ■A <----pMainKey
* /
* /
* pSubKey ----> ■B───●b0───●b1
* / \
* / \
* c0●───■C ■F───●f0───●f1
* \ /
* \ /
* ■D ■G───●g0
*
* 把子主键pSubKey断开之后的链表结构如下：
* ■A <----pMainKey
* /
* /
* ■F───●f0───●f1
* /
* /
* ■G───●g0
\************************************************************************/
if (pSubKey->Parent == pMainKey)
{
pMainKey->SubKey = pSubKey->SibKey;
}
// 若pSubKey是主键pMainKey的第一个孩子结点的兄弟结点 (并不一定是第一个兄
// 弟结点，只要与pSubKey是同一层的兄弟结点，算法与此相同)，则使pSubKey的
// 兄弟接点成为pMainKey的第一个孩子结点的兄弟结点，并使pSubKey的所有子结
// 点与pSubKey一起脱离链表结构。
/************************************************************************
* ■A <----pMainKey
* /
* /
* ■B───●b0───●b1
* / \
* / \
* c0●───■C ■F <----pSubKey
* \ /\
* \ / \
* ■D ■G ■M───●m0
*
* 把子主键pSubKey断开之后的链表结构如下：
* ■A <----pMainKey
* /
* /
* ■B───●b0───●b1
* / \
* / \
* c0●───■C ■M───●m0
* \
* \
* ■D
*************************************************************************/
else pSubKey->Parent->SibKey = pSubKey->SibKey;
// 若pSubKey有兄弟结点，则使其兄弟结点的Parent指针指向pSubKey的父亲结点
if (pSubKey->SibKey)
{
pSubKey->SibKey->Parent = pSubKey->Parent;
}
// 使pSubKey结点与双亲结点和兄弟结点断开
pSubKey->Parent = NULL;
pSubKey->SibKey = NULL;
}
//---------------------------------------------------------------------------
/****************************************************************************
* *
* 函数名称：SortSiblingTree *
* *
* 隶属对象：CSkyRainReg : public *
* *
* 用 法：void SortSiblingTree(SkyRain::CKeyNode *pParent, *
* SkyRain::CKeyNode *pSubKey) *
* *
* 实现功能：在主键pParent的第一层所有子主键中以排列规则进行排序。 *
* 排列规则：以主键名从小到大，没有或只有一个子主键不排序。 *
* 实现方法：在主键pParent的第一层所有子主键中查找适当位置， 并 *
* 移动pSubKey子主键，使pParent的第一层中所有子主键按排序规则有 *
* 序排列。并保持原子主键结点为根结点的子树的原来状态。(pSubKey *
* 结点也是其中的子主键,但pSubKey在其兄弟结点中可能无序)。 *
* pParent的子主键除pSubKey之外其它结点均有序排好,只需把pSubKey *
* 移动的适当位置,使pParent的子主键有序排列。 *
* 实际操作：沿pParent->SubKey 向右走到底进行判定比较查找适当位 *
* 置就地排序。 *
* *
* 参数说明：pParent 打开的主键指针，为pSubKey的父结点 *
* pSubKey 将要插入排序的值主键指针 *
* *
* 返 回 值：无 *
* *
* 日 期：2003.12.16 *
* *
* 修改日期：2006.01.27 -- 2006.02.17 *
* *
****************************************************************************/
void CSkyRainReg::SortSiblingTree(PREGKEY pParent, PREGKEY pSubKey)
{
// 有下列4种情况之一, 均不需要进行排序
if (!pParent // 1.pParent为空结点
||
!pSubKey // 2.pSubKey为空结点
||
!pParent->SubKey // 3.pParent没有子结点
||
!pParent->SubKey->SibKey) // 4.pParent只有一个子结点
{
return;
}
// 首先断开结点pSubKey
CutDownNode(pParent, pSubKey);
// 在pParent的第一层子结点中查找pSubKey结点需要移动到的位置p
// 查找条件：以排序规则对名称，在p的兄弟结点中进行比较查找
PREGKEY p = pParent->SubKey;
while (p->SibKey && CompareName(p, pSubKey)<0)
{
p = p->SibKey;
}
// 比较完之后，如果p的主键名仍然小于pSubKey的主键名，则在p之后插入pSubKey,
// 此时实际p已经指向最后一个兄弟结点。
if (CompareName(p, pSubKey) < 0)
{
pSubKey->SibKey = NULL;
p->SibKey = pSubKey;
pSubKey->Parent = p;
}
// 在p之前插入pSubKey
else
{
// p是主键pParent的第一个孩子结点
if (p == pParent->SubKey)
{
pParent->SubKey = pSubKey;
}
// p是主键pParent的第一个孩子结点的兄弟结点列表中的某一个结点
else
{
p->Parent->SibKey = pSubKey;
}
pSubKey->Parent = p->Parent;
pSubKey->SibKey = p;
p->Parent = pSubKey;
}
}
//---------------------------------------------------------------------------
/****************************************************************************
*
* 函数名称：SortValueList
*
* 实现功能：对主键结点pKey的键值链表结点进行排序。pValue是其中一个键值
* 结点但在链表中可能是无序的, 移动结点pValue使整个链表有序。
* 没有结点或只有一个结点不排序。
*
* 参数说明：pKey 打开的主键指针
* pValue 将要插入排序的键值指针
*
* 返 回 值：无
*
* 日 期：2003.12.16 -- 2006.02.16 -- 2006.03.08
*
****************************************************************************/
void CSkyRainReg::SortValueList(PREGKEY pKey, PREGVALUE pValue)
{
// 以下3种情况不进行排序
if (!pKey // 1.主键为空
||
!pKey->Value // 2.主键没有键值结点
||
!pKey->Value->Next) // 3.只有一个结点
{
return;
}
PREGVALUE prevIn; // 指示插入位置的前驱结点
PREGVALUE p;
// 首先断开pValue结点
if (pKey->Value == pValue)
{
pKey->Value = pValue->Next;
}
else
{
p = pKey->Value;
while (p && p->Next && p->Next!=pValue)
{
p = p->Next;
}
p->Next = pValue->Next;
}
pValue->Next = NULL;
// 查找插入位置
p = pKey->Value;
prevIn = NULL;
while (p && !(CompareName(p, pValue)>0))
{
prevIn = p;
p = p->Next;
}
if (!prevIn)
{
pValue->Next = pKey->Value;
pKey->Value = pValue;
}
else
{
pValue->Next = prevIn->Next;
prevIn->Next = pValue;
}
}
//---------------------------------------------------------------------------
/****************************************************************************
* *
* 函数名称：SetUnvisited *
* *
* 隶属对象：CSkyRainReg : public *
* *
* 用 法：void ReSetVisited(SkyRain::CKeyNode *pRoot) *
* *
* 实现功能：设置以pRoot为根结点的二叉树中所有结点的访问标志为vtUNVISITED *
* *
* 参数说明：pRoot 二叉树根结点,先序遍历递归算法 *
* *
* 返 回 值：无 *
* *
* 日 期：2003.12.16 *
* *
****************************************************************************/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -