向cout輸出不同值的鏈接列表

Question

我正在爲我的作業寫一個鏈表容器。使用Qt 4.7和gcc 4.4，我發現代碼中存在一些問題，我猜它們與內存管理或垃圾收集有關。

使用<<運算符顯示列表後，列表中的所有數據都會更改。例如，在建設和設置像l列表，

std::cout<<l<<std::endl; 
std::cout<<l<<std::endl; 

打印：

Data = [-10, 3, 2, 8, 1, -1, -2, ] // this is correct 
Data = [0, 149560240, 149560192, 149558336, 149560256, 149558320, 149560208, ] 

我的鏈表是：

#ifndef LINKEDLIST1_H_ 
#define LINKEDLIST1_H_ 

#include <iostream> 

template<class T> class LinkedList1; 
template<class T> class Node; 

template<class T> 
class Node 
{ 
    friend class LinkedList1<T> ; 
public: 
    Node(const T& value) : 
     Data(value), Next(NULL) 
    { 
    } 
    Node() : 
     Next(NULL) 
    { 
    } 
    T Data; 
    Node* Next; 
}; 

template<class T> 
class LinkedList1 
{ 
public: 
    LinkedList1() : 
     size(-1), first(NULL) 
    { 
    } 
    ~LinkedList1() 
    { 
     Node<T>* i = this->first; 
     Node<T>* j = this->first; 
     while(j!=NULL) 
     { 
     j=i->Next; 
     delete i; 
     i=j; 
     } 
    } 
    // Operations on LinkedList 
    Node<T>* First() 
    { 
     return first; 
    } 

    int Size() 
    { 
     return size + 1; 
    } 

    int Count() 
    { 
     int size = 0; 
     Node<T>* current = this->firstFirst(); 
     while(current != NULL) 
     { 
     size++; 
     current = current->Next; 
     } 
     this->size = size; 
     return this->Size(); 
    } 

    bool IsEmpty() 
    { 
     return this->Size() == 0; 
    } 

    void Prepend(Node<T>* value) //O(1) 
    { 
     value->Next = this->first; 
     this->first = value; 
     this->size++; 
    } 
    void Prepend(const T& value) //O(1) 
    { 
     Node<T>* item = new Node<T>(value); 
     item->Next = this->first; 
     this->first = item; 
     this->size++; 
    } 
    void Append(Node<T>* value) 
    { 
     if(this->IsEmpty()) 
     { 
     this->first = value; 
     this->size++; 
     } 
     else 
     { 
     Node<T>* current = this->First(); 
     while(current->Next != NULL) 
      current = current->Next; 
     current->Next = value; 
     value->Next = NULL; 
     this->size++; 
     } 
    } 
    void Append(const T& value) 
    { 
     Node<T>* temp= new Node<T>(value); 
     this->Append(temp); 
    } 
    void Insert(Node<T>* location, Node<T>* value) //O(n) 
    { 
     Node<T>* current = this->first; 
     Node<T>* before = current; 
     while(current != NULL) 
     { 
     before = current; 
     current = current->Next; 
     if(current == location) 
     { 
      before->Next = value; 
      value->Next = current; 
      this->size++; 
      break; 
     } 
     } 
    } 
    void Insert(Node<T>* location, const T& value) 
    { 
     Node<T>* temp = new Node<T>(value); 
     this->Insert(location,temp); 
    } 

    Node<T>* Pop() 
    { 
     if(this->IsEmpty()) 
     return NULL; 
     else 
     { 
     Node<T>* current = this->first; 
     Node<T>* before = current; 
     while(current->Next != NULL) 
     { 
      before = current; 
      current = current->Next; 
      before->Next = current; 
     } 
     before->Next = NULL; 
     this->size--; 
     return current; 
     } 
    } 
    Node<T>* PopF() 
    { 
     if(!this->IsEmpty()) 
     { 
     Node<T>* head = this->first; 
     this->first = this->first->Next; 
     this->size--; 
     return head; 
     } 
     else 
     return NULL; 
    } 
    Node<T>* Remove(Node<T>* location) 
    { 
     // validating by IsEmpty is not necessary for this operation, 
     // while statement's condition guarantees validation 
     Node<T>* current = this->first; 
     Node<T>* before = current; 
     while(current != NULL) 
     { 
     before = current; 
     current = current->Next; 
     before->Next = current; 
     if(current == location) 
     { 
      before->Next = current->Next; 
      current->Next=NULL; 
      return current; 
     } 
     } 
     return NULL; // Not found... 
    } 
    void Inverse() 
    { 
     if(this->IsEmpty()) 
     return; 
     else 
     { 
     Node<T>* r = NULL; 
     Node<T>* q = this->first; 
     Node<T>* p = this->first; 
     while(q != NULL) 
     { 
      p = p->Next; 
      q->Next = r; 
      r = q; 
      q = p; 
     } 
     this->first = r; 
     } 
    } 
    // Ordered insertion. implement this: foreach i,j in this; if i=vale: i+=vale, break; else if i<=value<=j: this.insert(j,value),break 
    friend std::ostream& operator<<(std::ostream& out, const LinkedList1 item) 
    { 
     out<<"Data = ["; 
     Node<T>* current = item.first; 
     while(current != NULL) 
     { 
     out << current->Data << ", "; 
     current = current->Next; 
     } 
     out<<"]"; 
     return out; 
    } 

    void HelperOutput(std::ostream& out, const LinkedList1 item) const 
    { 
     out<<item; 
    } 

    Node<T>* operator[](const int& index) 
    { 
     int i=0; 
     Node<T>* current = this->first; 
     while(i<=index && current!=NULL) 
     { 
     if(i=index) 
      return current; 
     else 
     { 
      i++; 
      current=current->Next; 
     } 
     } 
    } 
public: 
    int size; 
    Node<T>* first; 

}; 

#endif /* LINKEDLIST1_H_ */ 

    friend std::ostream& operator<<(std::ostream& out, const LinkedList1 item) 
    { 
     out<<"Data = ["; 
     Node<T>* current = item.first; 
     while(current != NULL) 
     { 
     out << current->Data << ", "; 
     current = current->Next; 
     } 
     out<<"]"; 
     return out; 
    } 

在第二個電話的輸出的第一項總是0 。所以我想我已經在代碼的某處設置了first到NULL;但我檢查了所有的方法，並沒有這樣的。另外，打印的值不是指針本身;它的指針是Data。有人在我的列表中更改了Data s的所有Node<T>* s。

這是內存管理還是垃圾回收問題？如果不是，我做錯了什麼？在這裏脫穎而出

Answer 1

的一件事是你的簽名是：

std::ostream& operator<<(std::ostream& out, const LinkedList1 item) 

相反的：

std::ostream& operator<<(std::ostream& out, const LinkedList1& item) 

所以，要調用您的鏈表的副本。我懷疑這裏的問題是，你沒有正確實現你的LinkedList1的複製和賦值操作符，這樣複製引用了原始內容，並且析構函數正在將原始對象變成垃圾。

我會建議增加以下到您LinkedList1的定義：

private: 
    // The following declarations disallow copy and assignment. Do not implement. 
    LinkedList1(const LinkedList1&); 
    LinkedList1& operator=(const LinkedList1&); 

添加上述將導致對你有原始簽名鏈接錯誤。然後我會推薦通過const引用傳遞鏈表，並且你的問題應該消失。

順便說一句，我注意到你的許多函數可以作成const但不是。例如，您有int Size()而不是int Size()const。一般應標記爲常量，可標記的任何東西。這被稱爲「常量正確性」，可以避免大量問題。

另外，小樣式nitpick：你有if ... else語句，其中一個有大括號，另一個沒有。我強烈建議你在所有情況下使用大括號，因爲這會導致更易讀的代碼。