Удаление дубликатов из 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

Использование встроенного Remove функция DoublyLinkedList и передать его итератор. Код delete - это вариант C++ с голыми костями, который не касается удаления узлов и правильной перегруппировки списка. Вызов delete удаляет только то, что находится в узле, а не сам узел!

Remove(m_itr); 

Вместо

delete m_itr.Item(); 

Кроме того, я думаю, что место вашего удаления может быть выключен (вы всегда будете удалить последний элемент, кажется). Возможно, вы хотите сделать что-то вроде ниже. Не уверен, что делает статистика(), но, надеюсь, вы получите эту идею. В основном вам нужно убрать элемент для удаления, переместить обычный итератор, а затем удалить тот, который вы убрали. В качестве альтернативы, полностью прекратите итерацию после завершения удаления. Это необходимо, потому что, когда итератор удаляется, его нельзя использовать для дальнейшей итерации.

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

Answer 2

Я ничего о библиотеке, которую вы используете, не знаю, но в стандартной библиотеке, удаление, как вы идете идет что-то вроде этого:

for (auto i = begin(list); i != end(list);) { 
    if (dont_want(*i)) { 
     i = list.erase(i); 
    } else { 
     ++i; 
    } 
} 

Основная идея заключается в том, что внутри цикл, либо вы удаляете текущий узел, и до list.erase(…), чтобы сообщить вам, какой узел продолжить итерацию после того, как он удалил текущий узел, или вы держите узел, и в этом случае вы проходите мимо него просто увеличивая итератор.

В своем коде, эквивалент ++i является m_itr.Forth() и list.erase(…) является Remove(…). Однако, поскольку Remove() не возвращает никакой информации о том, как продвигаться по списку, вы застреваете; вы не можете позвонить m_itr.Forth(), потому что узел, на который указывает, больше не существует.

Я не знаю, что могу помочь вам гораздо дальше, так как я изо всех сил пытаюсь понять, как работает ваш код. Выражение m_itr.Item().getFirstName() подразумевает, что m_itr.Item() является ссылкой на объект, тогда как delete m_itr.Item() означает, что он должен быть указателем, а не ссылкой.

Обратите внимание, что приведенный выше код соответствует C++ 11. C++ 03 эквивалент:

for (std::list<Datatype>::iterator i = list.begin(); i != list.end();) { … } 

Answer 3

внутренний цикл ничего не делает для вас: Это просто продолжает итерацию начатую внешнего цикла.

Здесь много проблем, я предполагаю, что вы учитесь, и я приветствую ваши усилия: Хорошо для вас, чтобы связаться.

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)) 
      { 
        if ((m_itr.Item().getFirstName() == searchByFirstName)&& 
         (m_itr.Item().getSecondName() == searchBySecondName)) 
          { 
           m_itr.Item() = Stats(); 
          } 
       } 
     } 
    delete m_itr.Item(); 
} 

Присвоение элемента к статистике также, вероятно, не то, что вы хотите: Вы хотите удалить элемент, а затем удалить эту запись из списка. Я должен были бы увидеть API для итератора и дважды связанного списка, но вам нужно как удалить элемент, и удалить его из списка, вероятно, с участием что-то вроде этого:

   m_itr.Item().m_prev.m_next = m_itr.Item().m_next; 
       if (m_itr.Item().m_next != null) 
       m_itr.Item().m_next.m_prev = m_itr.Item().m_prev; 
       // now that the item is spliced out of the list, delete it. 

Надеется, что это помогает.