代码之家 › 专栏 › 技术社区 › Charles Ray

打印链表时出现问题

linked-list data-structures c++

Charles Ray · 技术社区 · 14 年前

我试图创建自己的数据类型,就像一个向量或数组。

我的打印功能有问题;当我去打印列表时,它只打印列表中的最后一项。

// 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 回复 | 直到 14 年前

Community Paul Sweatte 4 年前

有三个重要错误:

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

这样不行。

表示存储在 当前节点 现在在 . 所以下次你把东西放进 currentNode = node; 你是 不把它储存在 第一个节点->下一个 . 所以你有一个坏链表---这就是为什么你的输出没有走得很远。

也, 这真的很糟糕 . 通过设置 currentNode=node 之前设置当前节点的 next 指向的指针 node currentNode->next 到 节点 然后设置 当前节点 作为 节点 节点 成为你要推到列表上的节点)。

Node val=节点(i);

范围 val 只在循环的那个迭代中。一旦你循环,它就不存在了。但是您已经将val的指针复制到了您的列表中——所以现在使用右边的 push

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

你需要把它放在堆上,这样它就会一直放下去,直到你不再需要它为止。

... 我们找到了你的毁灭者!

既然已经分配了一个节点,就需要取消分配它。所以在析构函数中这样做——遍历列表并释放所有节点。

Kirill V. Lyadvinsky 14 年前

以下情况会导致未定义的行为:

  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 );

以后不要忘记删除所有节点。

Faisal 14 年前

push()方法不正确。第一次推送节点时,它会正确地将其分配给firstNode,但随后的每一次push()都会将currentNode设置为新节点,然后将currentNode设置为NULL—实际上并没有向列表中添加任何内容。

我不打算为您编写代码,但下面是push()函数的工作方式。关键是您应该将现有节点的“下一个”字段设置为新节点,而不是将currentNode设置为新节点:

如果firstNode为空, 它没有下一个元素)。你可以同时设置currentNode=firstNode
如果firstNode不是 NULL,我们需要从firstNode出发直到找到一个节点列表中的最后一个元素,并执行相同的操作一定要设置currentNode 指向新节点完成。

您基本上已经完成了第1部分,但是第2部分仍然需要实现。请随时要求澄清/提出批评。:)

Black Diamond 14 年前

像这样试试看

 Node* val=new Node(i)

以前u存储的是临时变量。因此,没有存储动态内存中的ndoe,所以可以给出seprate内存。创建节点时,它是临时创建的