Linked List 替换前面的节点而不是弹出到后面

Question

我正在创建一个双向链表。我似乎对 pushBack 函数有问题（应该在列表末尾添加一个节点）。不知何故，它只是替换了第一个节点并指向自己作为前一个节点和下一个节点。当我去打印列表时，它会永远持续下去，因为下一个节点不是 NULL（因为正如我所说，它出于某种原因指向自身）。下面贴出整个程序。我想我可能遇到了范围问题，或者可能我使用的指针不正确。

#include <iostream>

class Node {
public:
  Node();
  Node(int *val, Node *nx = NULL, Node *prev = NULL) {
    value = val; next = nx; previous = prev;
  }

  void setPrev(Node* prev) { previous = prev; }
  void setNext(Node* nx) { next = nx; }
  void setVal(int* x) { value = x; }
  Node* getPrev() { return previous; }
  Node* getNext() { return next; }
  int* getVal() { return value; }

private:
  int* value;
  Node *next;
  Node *previous;
};

class LinkedList {
 public:
  LinkedList() : front(NULL), back(NULL) {}

  bool empty() { return front == NULL; }
  void pushBack(Node *nd) {
    if (back == NULL) {
      front = nd;
      back = nd;
    }
    else {
      back->setNext(nd);
      nd->setPrev(back);
      back = nd;
    }
    std::cout << "Front: " << *front->getVal() << std::endl;
    std::cout << "Back: " << *back->getVal() << std::endl;
  }
  Node* topFront() { return front; }
  void printFront() {
    int *x = front->getVal();
    std::cout << *x << std::endl;
  }

  void print() {
    if (empty()) {
      std::cout << "List is empty" << std::endl;
    }
    else {
      std::cout << "Print list" << std::endl;

      Node *x = front;
      int count = 1;

      // First just print the first element, then the rest
      int *y = front->getVal();
      std::cout << count << ": ";
      std::cout << *y << std::endl;

      x = x->getNext();

      while (x != NULL) {
        std::cout << count << ": ";
        int *z = x->getVal(); std::cout << *z << std::endl;

        x = x->getNext();
      }
    }
  }
 private:
  Node* front;
  Node* back;
};

int main() {
  LinkedList ll;
  char input;
  char const *menu = {"Options:\n\n" \
                      "0. Quit\n" \
                      "1. Print linked-list\n" \
                      "2. pushBack -- add to the end of the LinkedList\n"};

  while (input != '0') {
    std::cout << menu << std::endl;
    std::cout << ":";

    std::cin >> input;

    if (input == '1') {
      ll.print();
    }
    else if (input == '2') {
      std::cout << "Value: ";
      static int init;
      std::cin >> init;
      static Node x(&init);
      ll.pushBack(&x);
    }
  }

  return 0;
}

以下是我使用的输入法。我打印了一些值来尝试调试程序。您会注意到，我只是尝试将值为 1、2、3 和 4 的节点放入列表

Options:

0. Quit
1. Print linked-list
2. pushBack -- add to the end of the LinkedList

:2
Value: 1
Front: 1
Back: 1
Node Prev: 0
Node Next: 0
Options:

0. Quit
1. Print linked-list
2. pushBack -- add to the end of the LinkedList

:2
Value: 2
Front: 2
Back: 2
Node Prev: 0x602300
Node Next: 0x602300
Options:

0. Quit
1. Print linked-list
2. pushBack -- add to the end of the LinkedList

:2
Value: 3
Front: 3
Back: 3
Node Prev: 0x602300
Node Next: 0x602300
Options:

0. Quit
1. Print linked-list
2. pushBack -- add to the end of the LinkedList

:2
Value: 4
Front: 4
Back: 4
Node Prev: 0x602300
Node Next: 0x602300
Options:

0. Quit
1. Print linked-list
2. pushBack -- add to the end of the LinkedList

:0

Answer 1

当您在下面的代码中使用静态变量时，您的所有节点都将具有您输入的第一个值。

static int init;
std::cin >> init;
static Node x(&init);

按如下方式更正，然后重试

int *init = new int;
std::cin >> *init;
Node *x = New Node(init);

你的 pushBack 方法很适合我。只需进行上述更改并尝试即可。

Answer 2

这里有很多好的提示，但是 none 到目前为止将解决根本问题：您需要在堆而不是堆栈上分配 Node 实例。

为了使这更容易，我建议您按值而不是指针存储整数。将所有使用 int* 的地方更改为普通的 'int'.

然后改代码把后面的一个节点push成这样：

else if (input == '2') {
  std::cout << "Value: ";
  int init;
  std::cin >> init;
  Node *x = new Node(init);
  ll.pushBack(x);
}

我已经用你的代码测试过了，它对我有用。

当你做这样的事情时：

    else if (input == '2') {
  std::cout << "Value: ";
  int init;
  std::cin >> init;
  Node x(init);
  ll.pushBack(&x);
}

您正在堆栈上分配一个节点，这意味着一旦您退出 "else" 块，节点 'x' 就会被销毁并且您添加到列表中的指针不再有效.您需要使用 new 运算符在堆上分配 Node 。这将使节点保持活动状态并保留在内存中，直到您稍后将其删除。

说到删除——一旦您使这部分工作正常，您将需要编写一个析构函数来遍历列表中的所有节点并删除它们。但现在，我会专注于让您的其他操作正确无误。

Linked List 替换前面的节点而不是弹出到后面

Linked List replaces the front node instead of popping onto back

c++

linked-list

doubly-linked-list