Liste liée affichant différentes valeurs à cout

Question

J'écris un conteneur de liste chaînée pour mes devoirs. En utilisant Qt 4.7 et gcc 4.4, j'ai trouvé quelques problèmes dans le code que je suppose qu'ils sont liés à la gestion de la mémoire ou à la récupération de place.

Après avoir utilisé l'opérateur << pour afficher la liste, toutes les données de la liste est modifiée. par exemple, après la construction et la mise en liste comme l,

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

impressions:

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

Ma liste chaînée est:

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

premier élément de sortie de deuxième appel est toujours 0 . Donc je pensais que j'ai mis first à NULL dans quelque part dans le code; mais j'ai vérifié toutes les méthodes et il n'y avait rien comme ça. De plus, la valeur imprimée n'est pas le pointeur lui-même; c'est Data du pointeur. Quelque part quelqu'un change Data s de tous les Node<T>* s dans ma liste.

Est-ce un problème de gestion de mémoire ou de récupération de place? sinon, ce que je fais mal?

Answer 1

Une chose qui se démarque ici est que votre signature est:

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

Au lieu de:

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

Ainsi, vous invoquez une copie de votre LinkedList. Je suppose que le problème ici est que vous n'avez pas correctement implémenté vos opérateurs de copie et d'affectation pour LinkedList1, de sorte que la copie fait référence au contenu d'origine et que le destructeur transforme l'objet d'origine en vidange.

Je recommande d'ajouter ce qui suit à votre définition de LinkedList1:

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

Ajout ce qui précède va conduire à des erreurs de l'éditeur de liens pour la signature originale que vous aviez. Je recommanderais alors de passer la liste liée par référence de const, et votre problème devrait disparaître.

En aparté, je remarque que beaucoup de vos fonctions peuvent être faites const mais ne sont pas. Par exemple, vous avez int Size() au lieu de int Size()const. On devrait généralement marquer comme const tout ce qui peut être marqué. Ceci est connu comme "const-correct" et peut éviter un grand nombre de problèmes.

En outre, nitpick mineur de style: vous avez if ... else où l'on a des accolades et l'autre ne fonctionne pas. Je recommande fortement que vous utilisiez des accolades dans tous les cas, car cela conduit à un code plus lisible.