0

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


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

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

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

4

7 回答 7

3

您可能需要确保 prevNode->link 也不是空引用，以防 currentNode 实际上没有链接。

于 2009-10-05T22:58:08.150 回答
1

那应该工作得很好。你试过了吗？

于 2009-10-05T22:57:12.053 回答
1

while代码看起来不错，但我建议您对您的情况稍作改动

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

有两个原因

  • prevNode如当前所述，如果我们正在寻找的节点由or指向，您的代码可能会停止prevNode->link（因此我们将不知道这两个点中的哪一个特定currentNode- 如果我们想知道，我们将不得不检查if条件）。通过上面的更改，保证目标节点被存储prevNode（如果有的话——见下一点）。
  • 为了安全起见，最好检查一下prevNodeis not NULL。但是，正如 Pavel 提到的，如果currentNode保证在列表中，则无需进行此测试。

编辑以回应评论

鉴于您不需要知道是否currentNode在prevNodeorprevNode->link中，并且由于您想停止（如果可能） on currentNode == prevNode->link，那么您的原件while就可以了。然而...

代码中有一个 if 语句可以防止 prevNode已经为空

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

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

如果您绝对确定它currentNode会在列表中，那么我想检查也是不必要的，但这确实是一个好习惯。

于 2009-10-05T23:07:40.253 回答
1

该代码将遍历列表的某些部分，但哪一部分取决于列表的链接方式。如果它从头->尾（阅读：头节点链接到指向尾的节点），那么您将从随机位置开始遍历您的列表到尾。如果链接是 head<-tail，那么您将从随机位置遍历到头部。无论哪种情况，您都不会触及列表中的所有节点。

以上所有内容都假设有一些链接列表：

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

链接可以是任何一种方式。

此外，您可以链接头节点和尾节点并创建循环链表。在这种情况下，可以通过简单地遍历直到回到原始节点来访问所有节点。

于 2009-10-05T23:16:19.947 回答
1

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

  • 会发生什么randomNode等于firstNode？你回什么？你应该返回什么？
  • 当randomNode列表中的最后一个节点出现时会发生什么？
  • 什么时候会发生randomNode什么NULL？
  • 当randomNode不在列表中时会发生什么？

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

如果您非常仔细地考虑所有这些，那么有一个简单而优雅的解决方案可以处理所有这些。

于 2009-10-05T23:44:51.177 回答
0

你甚至可以拥有：

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

但是你所拥有的看起来不错。

于 2009-10-05T23:06:16.857 回答
0

我会用发布的代码更改的一件小事（除了在其他答案中讨论的如果 currentNode 不在列表中或其他错误处理中运行列表末尾的可能性之外）是当 while 循环完成时你不知道是否prevNode或prevNode->link指向currentNode. 这不是一个大问题（因为您可以轻松测试它），但在我看来，最好在搜索之前测试这种特殊情况，因此很明显这是一个特殊情况。

于 2009-10-05T23:28:35.640 回答