雙STL鏈接列表push_front錯誤

Question

我正在努力實現STL Double LinkedList。我幾乎是一個使用C++和OOP編程的新手，我幾乎對C語言有很好的瞭解，但所有這些新概念都很難通過數據結構來掌握和實現。我正在嘗試使用迭代器模式和模板在STL樣式之後創建一個良好的通用ADT。 沒有語法錯誤，相反，插入最後一個元素（檢查主函數）的元素插入（pushFront函數）存在很大的邏輯問題，我嘗試調試但仍找不到問題。希望有人能幫助我:-)

這是我的代碼片段

Node類：

//Forward declaration 
template<class T> 
class LinkedList; 


//Node should be structure? 
template<class T> 
class Node 
{ 
    friend class LinkedList<T>; 
public: 

    Node(): pPrev_(nullptr), pNext_(nullptr) {} 
    Node(const T& value): data_(value), pPrev_(nullptr), pNext_(nullptr) {} 

    /* 
    * Implementing double linked list node 
    * data_: node's data of type T 
    * pNext_: pointer to the next node 
    * pPrev_: pointer to the previous node 
    */ 
// if I put Private there some errors with private stuff, I have declared also LInkedList as friend 
    T data_; 
    Node<T>* pPrev_; 
    Node<T>* pNext_; 

}; 

迭代器類：

template<class T> 
class ListIterator 
{ 
    // Declaring LinkedList friend class, now 
    //LinkedList can access to all data in this class 
    friend class LinkedList<T>; 

public: 
    //Constructors 
    ListIterator(); 
    ListIterator(Node<T>* node); 

    //Destructor 
    ~ListIterator(); 

    // Assignement Overload 
    //ListIterator<T> operator=(const) 
    //Deferencing Overload 
    T operator*(); 

    //Prefix Overload 
    ListIterator<T> operator++(); 
    ListIterator<T> operator--(); 

    //Postfix Overload 
    ListIterator<T> operator++(int); 
    ListIterator<T> operator--(int); 

    //Relational Overload 
    bool operator==(const ListIterator<T>& Node); 
    bool operator!=(const ListIterator<T>& Node); 



private: 
    // Actual node holden by iterator 
    Node<T>* curNode_; 

}; 

/* 
LIST_ITERATOR IMPLEMETATION 
*/ 

template <class T> 
ListIterator<T>::ListIterator(): curNode_(nullptr){} 

template <class T> 
ListIterator<T>::ListIterator(Node<T>* node): curNode_(node) {} 

//Destructor 
template <class T> 
ListIterator<T>::~ListIterator() {} 

//Deferencing Overload 
template <class T> 
T ListIterator<T>::operator *() 
{ 
    //Return the VALUE of the current node holden by iterator 
    return this->curNode_->data_; 
} 

//Prefix Overload 
template <class T> 
ListIterator<T> ListIterator<T>::operator ++() 
{ 
    /* 
    * Check if the next node is a valid node, then 
    * the current node will be the next node 
    * Return the value of the current node 
    */ 
    if (this->curNode_->pNext_ != nullptr) 
     this->curNode_ =this->curNode_->pNext_; //Like it++, jump to the next node 

    return *this; 
} 

template <class T> 
ListIterator<T> ListIterator<T>::operator --() 
{ 
    /* 
    * Check if the previous node is a valid node, then 
    * the current node will be the previous node 
    * Return the value of the current node 
    */ 

    if(this->curNode_->pPrev_ != nullptr) 
     this->curNode_ = this->curNode_->pPrev; 

    return *this; //?? why return this 
} 

//Postfix Overload 
template <class T> 
ListIterator<T> ListIterator<T>::operator ++(int) 
{ 
    ListIterator<T> temp= *this; 
    ++(*this); 

    return temp; 
} 

template <class T> 
ListIterator<T> ListIterator<T>::operator --(int) 
{ 
    ListIterator<T> temp= *this; 
    --(*this); 

    return temp; 
} 

// Inequalities Overload 
template <class T> 
bool ListIterator<T>::operator==(const ListIterator<T>& node) 
{ 
    /* 
    * Check if the address of the current node is equal to the address of node param 
    */ 
    return(this->curNode_== node.curNode_); 
} 

template <class T> 
bool ListIterator<T>::operator!=(const ListIterator<T>& node) 
{ 
    return !((*this) == node); 
} 

LinkedList類：

template<class T> 
class LinkedList 
{ 
public: 
    typedef ListIterator<T> iterator; 

    //Constructors 
    LinkedList(); 
    LinkedList(const LinkedList<T>& copyList); 

    //Destructor 
    ~LinkedList(); 

    //List Status Methods 
    bool isEmpty(); 
    unsigned int getSize(); 
    iterator begin(); 
    iterator end(); 
    //Should parameters be constant and passed by reference &? let's check with tester if there are some troubles 
    //Insert Methods 
    void pushFront(const T value); 
    void pushBack(const T value); 
    void insertAt(const T value,iterator& atPos); 
    //Remove Methods 
    void popFront(); 
    void popBack(); 
    void removeAt(iterator& pos); 
    void clear(); 

    /** Addtional methods 
    * 
    * sort 
    * min,max, 
    * clear, 
    * overload << 
    * print 
    */ 


private: 
    /* 
    * Keeping a pointer to head and tail of the list; 
    * Size_: number of list's element 
    */ 
    Node<T>* Head_; 
    Node<T>* Tail_; 
    unsigned int Size_; 


}; 



// LIST IMPLEMENTATION 

// Constructors 
template < class T> 
LinkedList<T>::LinkedList() 
{ 
    /* 
    * Create a new empty node, head and tail are/share the same node at this step. 
    * Assign to head's pointer to next node NULL 
    * Assign to tail's pointer to previous node NULL 
    */ 
    this->Head_=this->Tail_= new Node<T>; 

    this->Head_->pNext_= nullptr; 
    this->Tail_->pPrev_= nullptr; 

    this->Size_=0; 
} 
// WIP TO CHECK 
template <class T> 
LinkedList<T>::LinkedList(const LinkedList<T>& list){ 

    this->Head_=this->Tail_= new Node<T>; 

    this->Head_->pNext_= nullptr; 
    this->Tail_->pPrev_= nullptr; 
    this->Size_=0; 

    // create iterator to loop inside the container 

    for(iterator it= list.begin ; it != list.end(); it++) 
     this->pushBack(*it); 

} 

//Destructor 
template <class T> 
LinkedList<T>::~LinkedList() 
{ 
    this->clear(); //delete all nodes 
    delete this->Tail_; 
} 

//Begin & end() 
template <class T> 
ListIterator<T> LinkedList<T>::begin() 
{ 
    iterator it= this->Head_; 
    return it; 
} 

template <class T> 
ListIterator<T> LinkedList<T>::end() 
{ 
    iterator it= this->Tail_; 
    return it; 
} 

//Clear 
template< class T> 
void LinkedList<T>::clear() 
{ 
    iterator it= this->begin(); 

    while(it != this->end()) 
     this->removeAt(it); 
} 

這些都是方法，讓我錯誤：

//Insert At 
    template <class T> 
    void LinkedList<T>::insertAt(const T value, iterator& atPos) 
    { 
     Node<T>* newNode= new Node<T>; 

     newNode->data_= value; 
     //Add links 
     if(atPos == this->begin()) 
     { 
      newNode->pNext_=this->Head_; 
      this->Head_=newNode; 

     } 

     else if (atPos == this->end()) 
      //Still to implement 
      this->Tail_= newNode; 
     else 
     { 
      newNode->pNext_ = atPos.curNode_; 
      atPos.curNode_->pPrev_ = newNode; 

      atPos.curNode_->pPrev_->pNext_ = newNode; 
      newNode->pPrev_=atPos.curNode_->pPrev_; 
     } 


     atPos.curNode_= newNode; 

     this->Size_++; 
    } 

    template <class T> 
    void LinkedList<T>::pushFront(const T value) 
    { 
     iterator it= this->begin(); 
     this->insertAt(value, it); 

    } 

這裏也有線路測試ADT：

#include <iostream> 
#include <stdlib.h> 
#include <string> 
#include "LinkedList.h" 
using namespace std; 

int main() { 


    Node<int> nd(4); 
    ListIterator<int> it; 
    LinkedList<int> lst; 

    for(int i=0; i < 25;i++) 
     lst.pushFront(i); 


    for(it=lst.begin(); it != lst.end();it++) 
    { 
     cout << *it << endl; 
     system("Pause"); 

    } 

    cout << "iia"; 


    system("Pause"); 
    return 0; 
} 

Answer 1

有在輸出中沒有錯誤：

24 
Press any key to continue . . . 
23 
Press any key to continue . . . 
22 
Press any key to continue . . . 

... 

Press any key to continue . . . 
0 
Press any key to continue . . . 
iiaPress any key to continue . . . 

附：請勿使用this您可以避免的地方。代碼將更容易閱讀。