双链表小谜题

Question

免责声明

所以最初当我发布这个时，它是我的错误的转发列表，即使我打算将它作为一个双链表来做 - 这就是为什么有一些回复与问题不匹配。

问题

我正在做一些编码，我在下面编写了代码。乍一看，代码似乎没什么问题，但是逻辑上有漏洞。你能找到吗？

class Node {
  int val;
  Node *next, *prev;

 public: 
  Node(int val, Node *prev, Node *next) {
    this->val = val;
    this->prev= prev;
    this->next = next;
  }
  int get() {return val;}
  Node* getNext() {return next;}
  Node* getPrev() {return prev;}
};

int main() {
  Node *n1, *n2, *n3;
  n1 = new Node(1, NULL, n2);
  n2 = new Node(2, n1, n3);
  n3 = new Node(3, n2, NULL);

  Node *next = n1;
  while (next != NULL) {
    cout << next->get() << endl;
    next = next->getNext();
  }
}

问题是指针n1, n2, n3 只有在使用运算符new 分配内存后才能获得正确的地址。这意味着这些指针的地址在 Node class 实例化时并不相同。例如。在 n2 = new Node(2, n1, n3); 行中，n3 将是一个错误的指针（因为内存尚未分配 jet，目前指向一些废话）。

问题

解决问题不是问题，但这让我想知道：

你能找到一种方法来修复它而不向 class 节点添加任何新属性或方法吗？
更进一步，您能否找到一种无需更改 class 节点内的任何代码即可修复它的方法？

我的看法

对于第一个问题，我想到了最快的解决办法。我只是将属性 next 和 prev 指针指向指针并更改代码，以便它将引用传递给构造函数。还必须更改 while 循环的语法以获取取消引用的值。

对于第二个问题，我们在回复中得到了一种可能的解决方案。我们可以简单地制作一个节点数组。这样我们就知道每个成员的确切地址，因为 n-数组的第一个成员的地址是第一个成员的地址 + n - 1 ;

Answer 1

Eg. in line n2 = new Node(2, n3); n3 would be a bad pointer

有一个简单的解决方案。固定初始化顺序，以便从没有依赖关系的对象开始，并在初始化对象的依赖关系后初始化对象。在这种情况下，“1”依赖于“2”，“2”依赖于“3”，因此：

n3 = new Node(3, nullptr);
n2 = new Node(2, n3);
n1 = new Node(1, n2);

Is it possible to allocate memory in advance?

当然可以。可以分配内存。如果你在做其他事情之前分配内存，那么你就是在做那件事之前分配内存。

您可以使用数组一次性创建所有节点。你甚至不需要任何动态分配：

Node nodes[] {
    {1, nodes + 1},
    {2, nodes + 2},
    {3, nullptr},
};
Node* next = nodes;

P.S.

我建议不要只拥有指针。您的示例内存泄漏。
不要在 C++ 中使用 NULL。它已被 nullptr.
无论出于何种原因，您忘记初始化 prev 成员。

Answer 2

我认为改为使用指向指针的指针是一个非常非常糟糕的主意，而且会非常奇怪。

最简单的方法是反向构建树：

Node * n3 = new Node(3, nullptr);
Node * n2 = new Node(2, n3);
Node * n1 = new Node(1, n2);

这会在创建 n2 之前使用 n2 消除 n1。

但是，你还是有问题。您决不会管理上一个。所以你可能想这样做：

节点（int val，节点*下一个）{ 这个->val = val；这个->下一个=下一个；

 // Add these lines.
 if (next != nullptr) {
     next->prev = this;
 }

}

另请注意，使用 NULL 引用未初始化的指针是非常古老的 C 风格。如果您要编写现代 C++ 程序，请改用 nullptr，如您在我的示例中所见。

我还做了一处和你不一样的改动。我个人不喜欢这段代码：

Node *n1, *n2, *n3;

我不喜欢它有两个原因，这两个原因至少会在一些企业风格指南中被引用。首先，一些风格指南会告诉你每行只引用一个变量，而不是像你那样引用三个。而且，一些指南会警告您不要让您的指针处于未初始化状态。所以我把它分解了，正如你在上面的例子中看到的那样。

这最后一部分只是风格，但我无法告诉您由于其中一个或其他原因我追查的错误数量。例如，这可以隐藏：

Node *n1, n2, *n3;

根据您的字体大小、眼睛的锐度和月相，您可能看不到 n2 未声明为指针。现在，现代编译器可能会发现错误的用法，但仍然......此外，如果你同意所有变量在创建时都应该初始化为合理的东西，那么你的代码可能会变得冗长，并且很容易看不到你没有' t 初始化一切。

Answer 3

您似乎在尝试创建一个双向链表。错误是您在构造函数中将 null 作为参数传递。如果您按以下顺序分配内存，则可以解决此问题：

Node *n3=new Node(3,NULL);
Node *n2=new Node(2,n3)
Node *n1=new Node(1,n2)
Node *next=n1
while(next!=NULL){
  cout<<next->get();
  next=next->getNext();
}

双链表小谜题

A little double-linked list puzzle

c++

puzzle

免责声明

问题

问题

我的看法