Проблема с распечаткой связанного списка - PullRequest
Новая
       2

Проблема с распечаткой связанного списка

4 голосов
/ 30 июля 2010

Я пытаюсь создать свой собственный тип данных, похожий на вектор или массив.

У меня проблемы с моей функцией печати;Когда я иду печатать список, он печатает только последний элемент в списке. 

// LinkedListClass.cpp : Defines the entry point for the console application.

#include "stdafx.h"
#include <iostream>

class Node
{
public:
 int value;
 Node* next;

 Node::Node(int val)
 {
  value = val;
 };
};

class List
{
public:
 Node* firstNode;
 Node* currentNode;
 int size;

 List::List()
 {
  firstNode = NULL;
  currentNode = firstNode;
  size = 0;
 };

 void push(Node* node)
 {
  if(firstNode == NULL)
  {
   firstNode = node;
   firstNode->next = currentNode;
   size++;
  }
  else
  {
   currentNode = node;
   currentNode = currentNode->next;
   size++;
  }
 };

 void print()
 {
  if(firstNode != NULL)
  {
   Node* printNode = firstNode;
   while(printNode->next != NULL)
   {
    std::cout << "List Item " << printNode->value << std::endl;
    printNode = printNode->next;
   }
  }
 };
};

int _tmain(int argc, _TCHAR* argv[])
{
 List ll = List();
 for(int i = 0; i < 10; ++i)
 {
  Node val = Node(i);
  ll.push(&val);
 }
 std::cout << ll.firstNode->value << std::endl;
 ll.print();
 std::cout << "Size " << ll.size << std::endl;
 std::cin.ignore();
 return 0;
}

/* Output

9
Size 10

*/

Я знаю, что это еще далеко не завершено, но если у вас есть другие указатели (смеется), пожалуйста, не стесняйтесьпредложить.

Ответы [ 4 ]

4 голосов
/ 30 июля 2010

Есть три важные ошибки:

push () --- исправлено 

void push(Node* node)
 {
  if(firstNode == NULL)
  {
   firstNode = node;
   currentNode = node;
   // firstNode->next = currentNode; --> this does nothing useful!
   size++;
  }
  else
  {
   currentNode->next = node;
   currentNode = node;
   //currentNode = node;               -|
   //currentNode = currentNode->next;  -|----> why? what? Do explain.
   size++;
  }
 }

Я думаю, назначив firstNode->next = currentNode;, вы ожидали, когда в следующий раз currentNode будет обновлено, этотакже обновит firstNode->next.

Это не сработает.

firstNode->next = currentNode; подразумевает, что адрес, сохраненный в currentNode, теперь находится в firstNode->next.Поэтому в следующий раз, когда вы сохраняете что-то в currentNode = node;, вы не сохраняете это в firstNode->next.Итак, у вас есть неверный связанный список - вот почему ваш вывод не зашёл слишком далеко.

Кроме того, это действительно плохо .Установив currentNode=node перед , установив указатель next текущего узла на node, вы снова разбили список.Сначала вы должны указать currentNode->next на node, а затем установить currentNode как node (node - это узел, который вы помещаете в свой список).

Node val = Node (i);

Область действия val находится только в пределах этой итерации вашего цикла.Как только вы зациклились, он покинул стек и больше не существует.Но вы скопировали указатель val в свой список - так что теперь с правильным методом push вы просто добавляете висячий указатель.

Node *val = new Node(i);
ll.push(val);

Вам нужно положить его в кучу, чтобы он оставался включенным, пока он вам больше не нужен.

... что ведет нас к вашему деструктору!

Поскольку вы выделили узел, вам нужно освободить его.Так что сделайте это в своем деструкторе - пройдитесь по списку и освободите все эти узлы.

1 голос
/ 30 июля 2010

Следующее поведение приводит к неопределенному поведению: 

  Node val = Node(i);
  ll.push(&val); // take address of temporary
  ...
  firstNode = node; // store address of temporary here
  ...
  ll.print(); // temporary `val` was destroyed, but all nodes are point to it

Вы можете изменить свой код следующим образом: 

  Node* val = new Node(i);
  ll.push( val );

И не забудьте позже удалить все узлы.

0 голосов
/ 30 июля 2010

попробуй как 

Node* val=new Node(i)
ранее вы хранили временную переменную. поэтому не следует хранить это в динамической памяти, поэтому можно выделить отдельную память. когда вы создавали узел, он создавался для временных целей & временный адрес были сохранены, поэтому, когда вы вернетесь назад, временная память была освобождена, вы найдете там мусор. значение.
0 голосов
/ 30 июля 2010

Ваш метод push () неверный. Когда вы нажимаете узел в первый раз, он правильно назначает его firstNode, но каждое последующее нажатие () просто устанавливает currentNode в новый узел, а затем устанавливает currentNode в NULL - вы фактически ничего не добавляете в свой список. *

Я думаю, стоит упомянуть, что указатели не являются ссылочными по имени в C ++. Например, установка firstNode-> next = currentNode не делает currentNode следующим элементом в списке; он просто указывает firstNode-> next на тот же адрес, что и currentNode (в данном случае NULL).

Я не собираюсь писать код для вас, но вот как должна работать ваша функция push (). Ключ заключается в том, что вы должны установить поле 'next' существующего узла для вашего нового узла, а не currentNode для нового узла:

  1. В случае, когда firstNode равен NULL, установите firstNode на новый узел и установите firstNode-> рядом с NULL (так как у него нет следующего элемента). Вы можете также установите currentNode = firstNode здесь для удобства.

  2. В случае, когда firstNode не является NULL, нам нужно идти с первого узла вниз по цепочке, пока мы не найдем узел следующее поле которого равно NULL, затем установите его следующее поле для нового узла. В качестве альтернативы, мы можем использовать это указатель currentNode для доступа к последний элемент в списке и сделать то же самое вещь, будучи уверенным, чтобы установить currentNode чтобы указать на новый узел, когда мы сделал.

По сути, у вас есть часть 1, но часть 2 все еще нуждается в реализации. Не стесняйтесь просить разъяснений / давать критику. :)

...