Прикрепление указателей при удалении дубликатов из дважды связанного списка

Question

Я реализую функцию, которая удаляет дубликаты из несортированного дважды связанного списка. Я удалил другие функции, чтобы код был коротким и понятным. Предположим, что другие функции, такие как InsertFront, работают правильно.

У меня возникли проблемы с прикреплением указателя prev из моего класса Node, когда я удаляю дубликат. Я не уверен, правильно ли подключаю предыдущий указатель. В настоящее время я получаю ошибку seg. Спасибо.

Вот мой заголовочный файл. dlinkedlist.h

#ifndef _DLINKEDLIST_H_ 
#define _DLINKEDLIST_H_ 

#include <cstdlib> 
#include <stdexcept> 
#include <string> 
#include <iostream> 

using namespace std; 

template <class T> 
class Node 
{ 
public: 
    T data; 
    //string data; 
    Node<T>* prev; 
    Node<T>* next; 

    // default constructor 
    Node(T value) 
    { 
     data = value; 
     prev = NULL; 
     next = NULL; 
    } 
}; 

// DLinkedList class definition 
template <class T> 
class DLinkedList 
{ 
private: 
    // DLinkedList private members 
    int size; // number of items stored in list 
    Node<T>* front; // references to the front 
    Node<T>* back; // and back of the list 


DLinkedList(); 
DLinkedList(const DLinkedList& ll); 
~DLinkedList(); 

    void RemoveDuplicates(); 
} 

Вот моя реализация dlinkedlist.cpp

#ifdef _DLINKEDLIST_H_ 

#include <cstdlib> 
#include <stdexcept> 
#include "dlinkedlist.h" 
#include <string> 
#include <iostream> 
using namespace std; 


template <class T> 
void DLinkedList<T>::RemoveDuplicates() { 
    Node<T> *current, *runner, *dup; 
    current = front; 

    cout << "Removing the duplicates..." << endl; 

    while (current != NULL && current->next != NULL) { 

     runner = current; 

     while (runner->next != NULL) { 
      if(current->data == runner->next->data) { 
       dup = runner->next; 
       runner->next = runner->next->next; 
       runner->next->prev = runner->next->prev->prev; //trying to connect to previous node. Works without this line. 
       delete dup; 
      } 
      else { 
       runner = runner->next; 
      } 
     } 
     current = current->next; 
    } 

} 

Вот мой тестовый файл. test.cpp

#include <cstdlib> 
#include <iostream> 
#include <string> 
#include "ccqueue.h" 
#include "dlinkedlist.h" 
#include "ticket.h" 

using namespace std; 

void LLTest(); 

int main() 
{ 
    cout << "\nEntering DLinkedList test function..." << endl; 
    LLTest(); 
    cout << "...DLinkedList test function complete!\n" << endl; 
    return 0; 
} 

void LLTest() 
{ 
    // default constructor, InsertFront, InsertBack, ElementAt 
    DLinkedList<int> lla; 
    lla.InsertFront(2); 
    cout << "-------------------------------------------------\n"; 
    lla.InsertBack(5); 
    lla.InsertBack(10); 
    lla.InsertBack(2); 
    cout << "-------------------------------------------------\n"; 
    lla.RemoveDuplicates(); 
} 

Благодарим за ваше время.

Answer 1

dup = runner->next; 
runner->next = runner->next->next; 
runner->next->prev = runner->next->prev->prev; 

1) После второй строки в фрагменте кода я указываю, то runner->next становится NULL, когда последний элемент связанного списка тот, который нужно удалить. Таким образом, следующая строка runner->next->prev выйдет из строя, поскольку она эквивалентна 'NULL->next'. Итак, вы должны добавить if (runner->next != NULL) между 2-й и 3-й строками. То есть вы говорите, "Соедините рядом с предыдущей только тогда, когда рядом есть (только тогда, когда не последний пункт)

2) Научитесь отладочные инструменты.

Answer 2

Давайте пройдемся по соответствующему разделу кода, очень медленно:

dup = runner->next; 

Это то, что вы будете позже delete. Это дублированный узел, нормально.

runner->next = runner->next->next; 

Это помогает, для удобства чтения, если вы измените эту строку на "runner-> следующий = dup-> следующей;". Это дает понять, что вы перематываете предшественника dup «вокруг него», чтобы указать его на следующий узел после dup.

runner->next->prev = runner->next->prev->prev; //trying to connect to previous node. Works without this line. 

Хорошо, runner->next теперь узел, который был первоначально после того, как dup. Теперь, просто остановитесь на мгновение, выпить чашечку кофе, и задать себе следующий вопрос:

В двусвязном списке, предполагая, что узел ptr не последний узел в списке, что должно:

ptr->next->prev 

всегда быть ????

Ну, ptr является узлом в списке. ptr -> следующий следующий узел. Что вы ожидаете найти в качестве значения prev следующего узла?

Если вы сделаете шаг вперед, а затем шаг назад, где вы заканчиваете? Ну, в этой вселенной вы закроете то, где вы начали (игнорируя эффекты относительности). Поэтому в классическом двусвязном списке ptr->next->prev будет ptr, считая, что ptr не является последним узлом в списке (обратите внимание на эту часть, это станет важным).

Итак, я собираюсь сделать дикий, с верхней части моей головы догадаться, что то, что ваш код должен делать, вместо:

runner->next->prev = runner; // Relink to the previous node 

Но это не правильный ответ либо. Помните, что мы сделали предположение, что runner не является последним узлом в двусвязном списке.Если это так, то runner->next, очевидно, будет NULL, так как runner по определению является последним узлом в списке (вы удалили последний узел в списке, поэтому runner - это новый последний узел в списке), поэтому нулевой указатель здесь происходит разыменование.

Итак, что, по вашему мнению, должно произойти здесь, если runner, действительно, последний узел в списке? Если вы не сказали «ничего», то был правильный ответ:

if (runner->next) 
    runner->next->prev = runner; 

Answer 3

dup = runner->next; 
runner->next = dup->next; 
if (dup->next != NULL) 
    dup->next->prev = runner; 
else 
    back = runner; /* since we are deleting last element */ 
delete dup; 

Это может быть более четкое выполнение, что заменяет:

dup = runner->next; 
runner->next = runner->next->next; 
runner->next->prev = runner->next->prev->prev; //trying to connect to previous node. Works without this line. 
delete dup;