题

我想知道是否可以像这样遍历链表：


currentNode = randomNode;//where randomNode may or may not = firstNode
prevNode = firstNode;
while(prevNode != currentNode && prevNode->link != currentNode)
{
    prevNode = prevNode->link;
}

当我尝试在单链表中查找 currentNode 之前的节点时，是否可以在 C++ 中执行此操作？

我试图在控制台应用程序中为学校作业实现类似的东西，所以假设我不能使用任何花哨的东西，比如升压库/列表/任何让生活更轻松的东西，等等。所以基本上，我只有相当原始的数据类型和库可供使用。

有帮助吗？

解决方案

您可能希望确保prevNode->链接不是空引用或者，万一currentNode实际上并没有联系。

其他提示

这应该只是罚款。你有没有尝试过呢？

这代码会遍历列表的某些部分，但部分取决于哪种方式列表链接。如果从头戴式>尾云（读：头节点链接到其对尾连接的节点），那么你会遍历您的列表从随机位置到尾开始。如果链接头<-tail那么你会从随机位置的头部穿过。在这两种情况下，你不会碰的所有节点在列表中。

所有上述假定一些链接列表作为这样：

[head]<->[0...N Nodes]<->[Tail]

在链路可以是任何一种方式。

此外，您还可以链接头和尾节点，并创建一个循环链表。在这种情况下，可以通过简单的穿越，直到你回到你原来的节点访问的所有节点。

确保考虑所有可能的边缘情况：

  • 会发生什么 randomNode 等于 firstNode？你返回什么？什么 应该 你回来吗？
  • 当发生什么 randomNode 是列表中的最后一个节点吗？
  • 当发生什么 randomNode 是 NULL?
  • 当发生什么 randomNode 不在列表中？

现在，并非所有这些情况都适用，具体取决于您是否了解 randomNode, ，其中一些可能是微不足道的。但它们都值得思考。

如果您仔细考虑所有这些问题，就会发现有一个简单而优雅的解决方案可以处理所有这些问题。

代码看起来不错，但我建议对你的 while 状况

while(prevNode != currentNode && prevNode != NULL)

有两个原因

  • 正如目前所述，如果我们正在查找的节点被以下任意一个指向，您的代码可能会停止 prevNode 或者 prevNode->link （因此我们不知道两者中哪一个指向 currentNode ——如果我们想知道，我们必须向 if 健康）状况）。通过上述更改，保证目标节点存储在 prevNode （如果有的话——请参阅下一点）。
  • 为了安全起见，最好检查一下 prevNode 不是 NULL. 。然而，正如帕维尔提到的，如果 currentNode 保证在列表中。

编辑回应评论

鉴于您不需要知道是否 currentNode 是在 prevNode 或者 prevNode->link, ，并且因为您想停止（如果可能） currentNode == prevNode->link, ，那么你原来的 while 很好。然而...

代码中有一个if语句较高 prevNode 从无效

看来您错过了为什么应该检查的要点 NULL. 。是的，你之前检查过就好了，但是我们之所以有 NULL 检查循环中的情况是 currentNode 是 不是 在列表中，所以您最终到达最后一个节点。大概（如果你像大多数其他链接列表一样这样做）的值 link 你的最后一个节点是 NULL. 。如果是这样，您当前的代码最终将调用 NULL->link 这当然会让你的程序崩溃。这就是为什么你仍然应该检查 NULL

while(prevNode != NULL && prevNode != currentNode && prevNode->link!=currentNode)

如果你是 绝对确定 那 currentNode 将在列表中，然后我 猜测 这项检查也是不必要的，但这确实是一个值得养成的好习惯。

您甚至可以有：

while (prevNode && prevNode != currentNode)
    prevNode = prevNode->link;

但是，你有什么看起来不错。

我的代码张贴（除了在如果currentNode不在列表或其它错误处理上运行关闭列表的末尾的其他的答案讨论的可能性）改变一个小的事情是，当同时循环完成，你不知道，如果prevNode或prevNode->link点currentNode。这是不是一个巨大的问题（因为你可以很容易地测试），但在我看来，这是最好的测试搜索之前这种特殊情况下的情况，所以很明显，这是一个特例。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top