理解 C 中的代码（链表）

Question

我在理解链表时遇到了很大的问题，如果有人能向我解释以下内容，我将不胜感激。

Element_t *pushfront(Element_t *list)
{ 
if(list==0)
return allocate();

list->prev=allocate();

list->prev->next=list;

list=list->prev;

return list;
}

这里是什么意思 list->prev->next=list ?

这是什么意思：f->next->prev=f->prev？

我知道这只是程序代码的一部分，但我希望有人能尽可能简单地告诉我这些的一般含义？

Answer 1

这是带有注释的代码，可以告诉您发生了什么。

Element_t *pushfront(Element_t *list)
{ 
if(list==0) // If the list is emtpy
return allocate(); /* then you simply create a new node, which 
represents your list and return it. The size of your list grew from 0 to 1.*/

list->prev=allocate(); /*If the list is not empty, you add a new node by creating it,
and then the prev pointer of the first element in the list (list->prev) 
is set to this new element, as you want it to be first.*/

list->prev->next=list; /*Then you need to set the next pointer 
to the element you just added. The new element is at list->prev, 
so by list->prev->next, you just say, that the next element of the one
 you just created is the element that was first before you added the new one*/

list=list->prev; /* Here you just set the new element as the head of the list*/

return list; /*And here you return the new list*/
}

请注意，您的列表总是作为指向第一个元素的指针传递，因为这就是您所需要的。然后，您可以通过为列表中的每个元素设置的 next 指针访问所有元素。

Answer 2

首先，linked 列表通过指针相互 linked。它们不是按顺序排列的，实际上它们分布在内存中。

让我回答你的问题-1 list->prev->next=list; 在这里，您 link 将前一个节点与当前节点相结合。此代码表示 link 当前节点的前一个或下一个。然后前一个节点现在 link 使用结构中定义的下一个指针编辑。得到问题2f->next->prev=f->prev；我不知道这是在哪里定义的，但在这里你正在做一个带圆圈的 linked 列表。通过此代码将最后一个节点 link 编辑到第一个节点。

Answer 3

列表中的节点引用了列表中的前一个节点和下一个节点。

函数获取列表的第一个节点。所以这个第一个节点没有前一个节点。

在此声明中

list->prev=allocate();

创建了一个先前的节点，因为它从函数名称中推入列表开头的新节点。

在此声明中

list->prev->next=list;

expression list->prev 产生新创建节点的地址。这个创建的节点应指向列表的当前第一个节点。因此它的数据成员 next 应包含节点的地址 list.

和这个声明

list->prev->next=list;

这样做。

引入一个中间变量可以想象的更简单

例如

Element_t *new_node = allocate();

list->prev = new_node;      // list->prev=allocate();
new_node->next = list;     //list->prev->next=list;
list = new_node;           //list=list->prev;

return list;

关于这个问题

What means this: f->next->prev=f->prev?

那么节点 f 似乎已从列表中删除。现在它的下一个节点 (f->next) 将不会指向 f 而是指向 f.

的前一个节点

再次引入中间变量会更清楚

Element_t *previous_node_of_f = f->prev;
Element_t *next_node_of_f = f->next;

next_node_of_f->prev = previous_node_of_f;  // f->next->prev=f->prev

如果还要添加这样的语句

previous_node_of_f->next = next_node_of_f;

然后节点 f 将从列表中完全删除。

       --------------------------------------------------------
       |                                              prev    ^
       |                                                      |
----------------------    ----------------------    ----------------------
| previous_node_of_f |    |         f          |    |    next_node_of_f  |    
----------------------    ----------------------    ----------------------
       |                                                     ^  
       |    next                                             | 
       -------------------------------------------------------

Answer 4

Element_t 可能是一个 typedef 类似于以下内容：

typedef struct Element {
    struct Element * next;
    struct Element * prev;
    void * data;
} Element_t;

假设这样，你的链表基本上是这样工作的：

                  (list)
                     A               B               C
                +----------+    +----------+    +----------+
                | next=B   |--->| next=C   |--->| next=0   |
                | prev=0   |<---| prev=A   |<---| prev=B   |
                | data="A" |    | data="B" |    | data="C" |
                +----------+    +----------+    +----------+

所以现在你想在A前面添加一个新的节点N

                  (list)
     N               A               B               C
+----------+    +----------+    +----------+    +----------+
| next=A   |--->| next=B   |--->| next=C   |--->| next=0   |
| prev=0   |<---| prev=N   |<---| prev=A   |<---| prev=B   |
| data="N" |    | data="A" |    | data="B" |    | data="C" |
+----------+    +----------+    +----------+    +----------+

所以，1.A->prev需要设置为N，2.N->next需要设置为A。

list->prev=allocate(); 这分配了新的 N 并且已经分配了 A->prev=N.

下一行：list->prev->next=list：读取 list->prev 作为刚刚分配的新节点。然后就是N->next=A——第二步。

您的新元素已链接到列表中。显然，allocate()需要将next和prev初始化为NULL。

What means this: f->next->prev=f->prev?

取决于它写在哪里。在这里，它可能是一个函数的一部分，从列表中删除一个节点。

理解 C 中的代码（链表）

Understanding code in c (linked lists)

c

pointers

linked-list

doubly-linked-list