c++ - 从 DoublyLinkedList 中删除重复项

Question

我正在尝试删除 C++ 中的重复项目。我已经设法通过使用对象默认构造函数将对象设置为 = null。但我无法将其从列表中完全删除。此代码还删除了两个对象，而不仅仅是一个。这是另一个问题的重新发布。我的代码和部分帖子已更改。 How to remove duplicates from a doubly linked list by full name .谁能帮我这个？这是我的 removeDuplicates 函数:

***Remove Duplicates***
    void RemoveDuplicates(DoublyLinkedListIterator<Datatype> m_itr, string searchByFirstName, string searchBySecondName)
    {
        for (m_itr.Start(); m_itr.Valid(); m_itr.Forth())
            {
                if ((m_itr.Item().getFirstName() == searchByFirstName )
                          && (m_itr.Item().getSecondName() == searchBySecondName))
                {
                    for (m_itr.Item(); m_itr.Valid(); m_itr.Forth())
                    {
                        if ((m_itr.Item().getFirstName() == searchByFirstName )&&
                            (m_itr.Item().getSecondName() == searchBySecondName))
                                {
                                    m_itr.Item() = Stats();
                                }
                    }
                }
            }
        delete m_itr.Item();
    }
***Remove***
    void Remove(DoublyLinkedListIterator<Datatype> m_itr)
        {
            query.clock1();
            DoublyLinkedListNode<Datatype>* node = m_head;
            //Check to see if the iterator belongs to this list, if not return nothing.
            if (m_itr.m_list != this)
                return;
            //Check to see if the node is valid, if not return nothing.
            if (m_itr.m_node == 0)
                return;
            //If the iterator is pointing to the head...
            if (m_itr.m_node == m_head)
            {
                //Move the iterator forward.
                m_itr.Forth();
                //Delete the head.
                RemoveHead();
                //Decrement the size.
                m_count--;
            }
            //If the iterator is not pointing to the head...
            else
            {
                //Search forward through the list until you find
                //the node prior to the node you want to remove.
                while (node->m_next != m_itr.m_node)
                node = node->m_next;
                // move the iterator forward.
                m_itr.Forth();
                //If the node being are deleted is the tail...
                //Then update the tail node.
                if (node->m_next == m_tail)
                {
                    //Tail is now equal to node.  Which means we can now delete the node.
                    m_tail = node;
                }
                //Delete the node.
                delete node -> m_next;
                //Relink the list.
                node -> m_next = m_itr.m_node;
                //Decrement the count because a node was removed.
                m_count--;
                query.clock2();
                cout << "\nTime Taken : " << query.time2 - query.time1 << "\n";
            }
        }

***Class Declarations***
template <class Datatype>
class DoublyLinkedList
{   
public:
//-------------------------------------------------------------------------------------------
//  Member Vairables.
//-------------------------------------------------------------------------------------------
DoublyLinkedListNode<Datatype>* m_head;
DoublyLinkedListNode<Datatype>* m_tail;
int m_count;

template<class Datatype>
class DoublyLinkedListNode
{
public:
//-------------------------------------------------------------------------------------------
//  Member Vairables.
//-------------------------------------------------------------------------------------------
    DoublyLinkedListNode<Datatype>* m_next; //The next node.
    DoublyLinkedListNode<Datatype>* m_prev; //The previous node.
    Datatype m_data;                        //The data in the node.

template <class Datatype>
class DoublyLinkedListIterator
{
public:
//-------------------------------------------------------------------------------------------
//  Member Vairables.
//-------------------------------------------------------------------------------------------
    DoublyLinkedListNode<Datatype>* m_node; //A node for the Iterator to pointn to.
    DoublyLinkedList<Datatype>* m_list;     //A list for the Iteraotor to go through.
//-------------------------------------------------------------------------------------------
//  Name:           Constructor.
//  Description:    Constructs the DoublyLinkedListIterator.
//-------------------------------------------------------------------------------------------
    DoublyLinkedListIterator(DoublyLinkedList<Datatype>* p_list= 0, DoublyLinkedListNode<Datatype>* p_node= 0)
    {
        m_list= p_list;
        m_node= p_node;
    }

// ------------------------------------------------------------------
//  Name:           Start
//  Description:    Resets the iterator to the beginning of the list.
//  Arguments:      None.
//  Return Value:   None.
// ------------------------------------------------------------------
    void Start()
    {
        if(m_list!= 0)
        m_node= m_list -> m_head;
    }

// ----------------------------------------------------------------
//  Name:           End
//  Description:    Resets the iterator to the end of the list.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void End()
    {
        if(m_list!= 0)
        m_node = m_list->m_tail;
    }

// ----------------------------------------------------------------
//  Name:           Forth
//  Description:    Moves the iterator forward by one position.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Forth()
    {
        if(m_node != 0)
        {
        m_node = m_node ->m_next;
        }
    }

// ----------------------------------------------------------------
//  Name:           Back
//  Description:    Moves the iterator back by one position.
//  Arguments:      None.
//  Return Value:   None.
// ----------------------------------------------------------------
    void Back()
    {
        if(m_node!= 0)
        m_node = m_node->m_prev;
    }


// ----------------------------------------------------------------
//  Name:           Item
//  Description:    Gets the item that the iterator is pointing to.
//  Arguments:      None.
//  Return Value:   Reference to the data in the node.
// ----------------------------------------------------------------
    Datatype& Item()
    {
        return m_node->m_data;
    }
//-----------------------------------------------------------------
//  Name:           Valid
//  Description:    Determines if the node is valid.
//  Arguments:      None.
//  Return Value:   true if valid.
// ----------------------------------------------------------------
    bool Valid()
    {
        return (m_node!= 0);
    }
};

Answer 1

使用 DoublyLinkedList 的内置 Remove 函数并将其传递给迭代器。 delete 调用是基本的 C++ 变体，它不处理节点删除和正确重新链接列表。调用 delete 只会删除节点中的内容，而不是节点本身!

Remove(m_itr);

代替

delete m_itr.Item();

另外，我觉得你删除的地方可能是关闭的(你似乎总是删除最后一项，似乎)。也许你想做如下的事情。不确定 Stats() 的作用，但希望您能明白。基本上你需要收起要删除的项目，向前推进常规迭代器，然后删除你收起的那个。或者，一旦删除完成就完全停止迭代。这是必需的，因为当迭代器被移除时，它不能用于进一步的迭代。

    if ((m_itr.Item().getFirstName() == searchByFirstName ) &&
        (m_itr.Item().getSecondName() == searchBySecondName))
    {
      DoublyLinkedListIterator<Datatype> toDelete = m_itr; 
      m_itr.Forth(); 
      Remove(toDelete);
    }