在從雙向鏈表中刪除重複項時附加指針

Question

我正在實現一個從未排序的雙向鏈表中刪除重複項的函數。我刪除了其他函數以使代碼更簡短更清晰。請假設像InsertFront這樣的其他功能可以正常工作。

我在刪除重複項時附加從Node類的prev指針時遇到問題。我不確定是否正確連接了prev指針。我目前正在發生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成爲空當鏈表的最後一個元素一個被刪除。所以下一行runner->next->prev會崩潰，因爲它相當於'NULL->next'。 所以你必須在第二行和第三行之間添加if (runner->next != NULL)。這就是你說的「連接下一個以前只在旁邊有（僅當不是最後一個項目）

2）瞭解調試工具。

Answer 2

讓我們通過代碼的相關部分，非常非常緩慢：

dup = runner->next; 

這就是你以後會delete。這是重複的節點，好的。

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

如果將上面的行更改爲「runner-> next = dup-> next;」，它有助於提高可讀性。它清楚地表明你正在重新連接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;