Verknüpfte Liste, die unterschiedliche Werte an cout ausgibt

Question

Ich schreibe einen Container mit verknüpften Listen für meine Hausaufgaben. Mit Qt 4.7 und gcc 4.4 habe ich einige Probleme im Code gefunden, von denen ich denke, dass sie mit der Speicherverwaltung oder der Speicherbereinigung zusammenhängen.

Nachdem der Operator << zum Anzeigen der Liste verwendet wurde, werden alle Daten der Liste geändert. zum Beispiel nach dem Aufbau und Einstellen eine Liste wie l,

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

druckt:

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

Meine verknüpften Liste ist:

#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; 
    } 

erstes Element im Ausgang des zweiten Anrufs ist immer 0 . So dachte ich, ich habe first auf NULL irgendwo in Code festgelegt; aber ich habe alle Methoden überprüft und es gab nichts dergleichen. Außerdem ist der gedruckte Wert nicht der Zeiger selbst; es ist Zeiger Data. Irgendwo ändert jemand Data s von allen Node<T>* s in meiner Liste.

Ist dies ein Problem mit der Speicherverwaltung oder der Speicherbereinigung? wenn nicht, was mache ich falsch?

Answer 1

Eine Sache, die hier auffällt, ist, dass Ihre Unterschrift ist:

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

Statt:

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

Also, Sie eine Kopie Ihrer LinkedList aufrufen. Ich vermute, dass das Problem hier ist, dass Sie Ihre Kopier- und Zuweisungsoperatoren für LinkedList1 nicht korrekt implementiert haben, so dass die Kopie den ursprünglichen Inhalt referenziert und der Destruktor das ursprüngliche Objekt in den Müll verwandelt.

Ich würde empfehlen, das folgende in der Definition von LinkedList1 Zugabe:

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

die oben Hinzufügen zu Linkerfehler für die Original-Unterschrift führen wird, die Sie hatten. Ich würde dann empfehlen, die verknüpfte Liste durch const-Verweis zu übergeben, und Ihr Problem sollte verschwinden.

Nebenbei bemerke ich, dass viele Ihrer Funktionen const gemacht werden können, aber nicht sind. Zum Beispiel haben Sie int Size() anstelle von int Size()const. Man sollte generell alles bezeichnen, was so markiert werden kann. Dies wird als "Const-Korrektheit" bezeichnet und kann eine große Anzahl von Problemen vermeiden.

Auch, kleiner Stil Nitpick: Sie haben wenn ... sonst Aussagen, wo man Klammern hat und die andere nicht. Ich würde dringend empfehlen, dass Sie in allen Fällen Klammern verwenden, da dies zu besser lesbarem Code führt.