2

我经常在 C 中使用线性链表结构

typedef struct _node {
    ...node guts...
    struct _node *next
} node;

和枚举成语

for (node *each = headNode; each != NULL; each = each->next)

我现在处于一种情况，循环列表对我很有吸引力（例如，最后一个节点的下一个节点设置为 headNode）。天真地，我以为我会使用类似于那里的for表达式的东西，而且我盯着它看的次数越多，我想我已经说服自己你不能用循环链表做这样的事情。

似乎无论我为结束条件想出什么样的表达式，我都会遇到一个基本问题，即我希望所说的条件在第一次遇到相同节点时评估为真，第二次为假。我可以做一些有循环副作用的事情：

for (BOOL traversed = FALSE, node *each = headNode;
    traversed && each != headNode;
    traversed = TRUE, each = each->next)

但这肯定会失去空终止列表方法的优雅/简单性。这么晚了，有什么逻辑技巧让我无法理解吗？

显然我可以使用 while() 构造，也许这是唯一的方法。

4

5 回答 5

3

假设如下：

  • 空列表意味着起点为 NULL。
  • 最后一个节点将是next指针引用您的起点的节点，包括next指针自引用的单节点列表。
  • NOnext指针为 NULL。

然后以下将使用三次表达式作为增量步骤来执行您想要的操作。

// node* start comes from "somewhere'
for (node *p=start; p; p = (p->next==start ? NULL : p->next))
{
    // do something with p
}

注意：p当它以一种或另一种方式退出时将为 NULL；start将保持不变，并且start可以接受 NULL，就像单自引用节点一样。

也就是说，我会使用 while 循环来执行此操作，但是由于您特别要求使用 for 循环，因此您得到了 =P。

于 2012-12-12T04:00:34.087 回答
1

正如您已经指出的那样，任何“当前”指针都将简单地循环遍历整个列表，第二次与第一次没有什么不同。

因此，您必须使用其他一些信息。由于您承认最简单/最小的附加变量布尔值太复杂或不优雅，因此可以推断出这是无法完成的。

...除非您已经使用了一些额外的数据，否则说一个最初为 null 的“prev”指针（在这种情况下，traversed可以使用与您的示例非常相似的东西）。

为了记录，我会使用 do...while：

struct _node *node = head;
do {
    ...
    node = node->next;
} while (node != head);
于 2012-12-12T01:34:28.653 回答
0 
p = (pointer to some node)
pfirst = p
while true:
    do whatever with node (p)...
    p = p->next
    if (p==pfirst)  break

请注意，这适用于一个元素列表。

于 2012-12-12T01:11:19.473 回答
0

以下重新安排的循环看起来并不太糟糕：

for (node * n = head; ; )
{
    // process n

    if ((n = n->next) == head) { break; }
}

顺便说一句，这只适用于非空列表。无论您的空虚概念是什么，都应该作为初始检查添加 - 除非您通过使用虚拟头节点来避免该问题（以便空列表包含一个n带有的节点n == head == n.next，在这种情况下，您实际上并不想打印虚拟头节点完全可以使用真正的for循环（只需将上述条件放回循环语句中）！

于 2012-12-12T01:11:28.730 回答
0

我建议不要只是循环链条。它本身并不美丽。你如何检查你没有在链的第二个元素处循环等等？

如果我们有 a 的概念，head那么我们应该在每个节点中保存一个指向 a 的指针，head或者让它成为静态的。此外，我们应该有特殊的标志，而不是循环到头部。

于 2012-12-12T01:15:12.457 回答