解读自定义循环双向链表的循环条件

Question

我在结构中有一个列表，

struct A{
    list B;
};

我也有一个指向这个结构的指针，比如

struct A *a;

现在，假设列表已经实现，其元素的类型为 elem。

然后，我执行以下操作 -

(i) 我在 nodeL 中得到列表的头部（elem 类型的指针）

elem * nodeL = list_get_head(&(a->B));

(ii) 我现在以这种方式遍历列表：

while(nodeL != (elem *)(&a->B)){ // did not get this part ----- I
    ; //some code here
    nodeL = list_get_next(&(a->B), nodeL);
}

假设 list_get_head 获得指向列表头部的指针，并且 list_get_next 获得指向传递的第二个参数 elem 的下一个元素的指针。

现在我的问题是：

这里我的循环条件是什么？我希望循环到什么列表？（见I）也就是说，如果&(a->B)是链表的起始地址，那么这里的&a->B是什么？

我认为这应该循环到列表末尾，但它似乎不是 while 循环条件正在做的事情。另外，这是一个循环双向链表。

Answer 1

假设您有一个 variable 和一个 pointer 的 structure:

A var;
A* pntr;

现在要访问 structure 的数据成员，我们执行以下操作：

var.B    // For a variable use dot 
(*pntr).B or pntr->B    //For a pointer we can use * . or ->

在您的代码中 while(nodeL != (elem *)(&a->B)) 遍历列表直到再次遇到循环列表的头部。

我们可以通过 :

A* a;
//SOME INITIAL CODE
A* pntr;
pntr = a;
head = (elem*)&(pntr->B)

所以看看长什么样：

while( nodeL != (elem *) ( & ( a->B ) ) )

Answer 2

不清楚你说的是不是std::list。但是由于您提到的是不熟悉的 list_get_head 和 list_get_next，我认为这是一个非标准实现。

所以猜测是：在列表中head也是一个元素。条件 while(nodeL != (elem *)(&A->B)) 看起来像是在检查循环何时遍历回循环列表的头部。

但是，有两个观察结果：

列表的元素通常是从堆或内存池中分配的。因此，如果 B 是头，它应该是一个指针。除非是typedef elem * list.
循环可能不会运行，因为nodeL已经在开头。

Answer 3

elem* x = list_get_head(&a->B);
elem* y = (elem *)(&a->B);

首先，x 和 y 在你的情况下有多大不同？

要完全有效，list 的第一个成员无论如何都必须是 elem* 类型。我个人会假设这是列表的头部，但是你的 while 循环永远不会被输入，所以它一定是尾部？？？但是你在循环中考虑的第一个元素是尾巴......

如何表示空列表？空指针？如果是这样，这不在您的代码中。

while(nodeL != (elem *)(&a->B))

did not get this part

想法很简单：我们从头部开始迭代，只要没有到达头部再次，我们仍然在循环中......问题是，虽然，你要分清两种情况：

当前节点在循环开始时是头部
当前节点是所有元素迭代后的head

我建议现在对迭代进行不同的处理：

elem* nodeL = list_get_head(&a->B);
if(nodeL) // based on assumption(!): otherwise, empty list
{
    do
    {
        //some code here
        nodeL = list_get_next(&a->B, nodeL);
    }
    while(nodeL != list_get_head(&a->B));
}

一个元素保证在列表中，所以我们可以无条件地使用它（因此是一个 do-while 循环）。然后我们迭代到下一个元素，直到我们再次到达起点。我用对 list_get_head 的另一个调用替换了可疑的转换，使整个事情更安全（不再依赖假设）。

解读自定义循环双向链表的循环条件

Interpreting the loop condition of custom circular doubly linked list

c

list

circular-list

doubly-linked-list