4 向链表

• 下载源代码 - 18.7 KB

引言

本文描述了如何构建一个多向增长的链表，以及如何在不产生内存泄漏的情况下操作它。

背景

我读过很多解释如何管理单向和双向链表的文章。但是，当我需要一个多于两个方向增长的链表时，我找不到任何相关的资料。如果您了解链表的基础知识，就可以继续阅读本文。

使用代码

我创建了一个名为CMultiLinkedList的链表，它将用于模拟树形控件的结构。因此，链表将用作数据存储，而树形控件将用于可视化列表。我已经添加了代码来在列表中插入和删除节点。删除列表的方式可以确保没有内存泄漏。要创建一个链表并在树形控件中显示它，只需在文本文件中指定层次结构，使用%作为分隔符，一旦文件被导入，您将拥有链表和树形控件。

/***************************************************************************
/DESCRIPTION:
/-----------
/            To delete all the linked nodes of a given node.
/            Given a node this function loop through using next pointer till the end
/            of the branch and delete all the linked nodes
/
/PARAM
/------
/        pNode[IN]    -    Node whose all the linked nodes to be deleted
/
/RESULT:
/-------
/        void
*/
void CMultiLinkedList::DeleteLinkedNodes(Node* pNode)
{
    for( ; pNode != NULL;  )
    {
        Node* delNode =  pNode;
        pNode      =  pNode->m_pNext;

        //If branch found i.e, if pNode has children delete all of them
        if( delNode->m_pRight )
            DeleteChildren(delNode->m_pRight );

        //If the node is start node in a branch,then move the next node of the pNode
        //as the start node of the branch
        if( delNode->m_pLeft )
        {
            //If the node is a start node in a branch and it has a sibling
            if( delNode->m_pNext )
            {
                delNode->m_pLeft->m_pRight = delNode->m_pNext;
                delNode->m_pNext->m_pLeft  = delNode->m_pLeft;
            
                if( delNode->m_pPrev )
                    delNode->m_pNext->m_pPrev = delNode->m_pPrev;
                else
                    delNode->m_pNext->m_pPrev = NULL;
            }
            else
                delNode->m_pLeft->m_pRight = NULL;
            
        }
        delete delNode;
        delNode = NULL;

                    
    }    
}
/***************************************************************************
/DESCRIPTION:
/-----------
/            To delete all the associated children of a given node
/
/PARAM
/------
/        pNode[IN]    -    Node whose children to be deleted
/
/RESULT:
/-------
/        void
*/
void CMultiLinkedList::DeleteChildren( Node* pNode,bool flag  )
{
    //If branch found i.e, if pNode has children delete all of them
    if( pNode->m_pRight )
    {
        DeleteChildren(pNode->m_pRight);     
    }

    //If the node is start node in a branch,then move the next node of the pNode
    //as the start node of the branch
    if( pNode->m_pLeft )
    {
        if( pNode->m_pNext )
        {
            pNode->m_pLeft->m_pRight = pNode->m_pNext;
            pNode->m_pNext->m_pLeft  = pNode->m_pLeft;
            
            if( pNode->m_pPrev )
            {
                pNode->m_pNext->m_pPrev  = pNode->m_pPrev;
                pNode->m_pPrev ->m_pNext = pNode->m_pNext;
            }
            else
                pNode->m_pNext->m_pPrev = NULL;
            
        }
        else
            pNode->m_pLeft->m_pRight = NULL;
    }
    if( pNode->m_pRight )
    {
        DeleteChildren(pNode->m_pRight);     
    }

    //Delete all the linked nodes of the pNode
    DeleteLinkedNodes( pNode );

}

关注点

创建这个四向增长的链表非常有趣，而且删除列表的方式也非常好。

历史

这是代码的第一个版本，可能存在错误和问题。根据用户的反馈，我将修复它们并更新代码。