Связанный список, выводящий разные значения в 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 из Node<T>* в моем списке.

Это проблема с управлением памятью или сборкой мусора? если нет, то что я делаю не так?

Answer 1

Одна вещь, которая выделяется здесь, это то, что ваша подпись:

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

Вместо:

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

Итак, вы вызываете копию своего LinkedList. Я подозреваю, что проблема в том, что вы неправильно реализовали свои операторы копирования и назначения для LinkedList1, так что копия ссылается на исходное содержимое, а деструктор превращает исходный объект в мусор.

Я бы рекомендовал добавить следующее к вашему определению LinkedList1:

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

Добавление вышеуказанного приведет к ошибкам компоновщика исходной подписи, которая у вас была. Затем я бы рекомендовал передать связанный список по константной ссылке, и ваша проблема должна исчезнуть.

Кроме того, я замечаю, что многие из ваших функций могут быть выполнены const, но это не так. Например, у вас есть int Size() вместо int Size()const. Как правило, следует помечать как все, что может быть помечено. Это известно как «правильная константность» и позволяет избежать большого количества проблем.

Кроме того, незначительный стиль: у вас есть операторы if ... else, где у одного есть фигурные скобки, а у другого нет. Я настоятельно рекомендую использовать скобки во всех случаях, так как это приводит к более читаемому коду.