代码解释（链表C）

Question

这不是我的代码。我从这个网站上获取了这段代码：

http://www.macs.hw.ac.uk/~rjp/Coursewww/Cwww/linklist.html

我正在使用它作为构建链表的参考资料。我有一点困惑，不太清楚发生了什么。能否请有经验的人解释一下呢？我将用1-5标记我感到困惑的地方。

#include<stdlib.h>
#include<stdio.h>

struct list_el {
   int val;
   struct list_el * next;
};

typedef struct list_el item;

void main() {
   item * curr, * head;
   int i;

   head = NULL;   //1

   for(i=1;i<=10;i++) {
      curr = (item *)malloc(sizeof(item));
      curr->val = i;
      curr->next  = head; //2
      head = curr; //3
   }

   curr = head; // 4

   while(curr) {  //5
      printf("%d\n", curr->val);
      curr = curr->next ;
   }

1. head = NULL → 为什么要将head设置为NULL？我知道应该这样做（我习惯性地这样做），但我不是很清楚为什么。

2. curr->next = head → 我也从来没有真正理解过这个。也许我的“头”节点定义有误，但在常规链表中，它是起始节点还是列表中的最后一个节点？我一直认为它是起始节点，但在这行代码中，它看起来像是最后一个节点。

3. head = curr → 为什么我们要将它设置为curr？

4. curr = head → 然后在循环结束后将curr = head。

5. while(curr) → 只是为了确保，这是遍历列表，等价于 while(curr != NULL) 对吗？

- ShadyBears

---

该列表是通过在前端附加节点并调整头指向新节点来构建的。 - user66363

这段代码构建了一个链表，因此最好先清楚地了解什么是链表：http://zh.wikipedia.org/wiki/链表 - The Jonas Persson

Answer 1

#1: head = NULL

初始化指针。一般建议在声明或声明后立即将指针初始化为NULL。如果程序员错误地引用未初始化的指针，则会返回垃圾值。如果您的静态分析器和编译器不显示关于未初始化指针的警告或错误消息，通常很难调试。

有关更多信息，请参考Steve McConnell的《代码大全：软件构造的实用手册》或维基百科关于防御性编程的页面。

#2: curr->next = head

构建链表。当前节点curr被“链接”到先前创建的节点序列中。

#3: head = curr

更新头指针。 head指针正在更新以指向最近的malloc节点。

下面的插图展示了步骤#2和#3：

#4: curr = head

将curr指向头结点。

重新初始化指针。 步骤类似于步骤 #2：curr->next = head。通过将curr节点设置为head，curr准备好在while循环中遍历链表。类比来说，这就像在循环开始时将迭代变量初始化为0（即i = 0）。请参考下面的插图，显示执行此语句之前/之后的情况：

#5: while(curr)

遍历列表。 鉴于curr指向第一个节点（来自步骤#4），这个while循环遍历列表，直到curr->next返回NULL。以更少抽象的形式，我们可以重写此语句为while(curr != NULL)。

- melvynkim

---

一个真正优秀的回答。非常详细且易于理解。我目前正在苦苦挣扎地处理链表问题，这篇文章为我解决了难题。谢谢。 - Finlandia_C

Answer 2

1. "head"指向列表的头部。由于列表当前为空，因此将其设置为null。
2. 当您向列表添加节点时，将“next”指针设置为当前列表的头部。这将把新节点放在列表的头部。
3. 将“head”设置为“curr”，以使新节点成为列表的头部。
4. 循环结束后，您正在重复使用“curr”变量来遍历列表。
5. 您正在遍历该列表，将“curr”逐个设置为每个节点，直到您到达列表底部（其中curr->next为null）

- Paul Tomblin

Answer 3

(1). 您需要将其设置为某个值，使用 NULL 是一种表示它没有指向任何内容的方法。通常情况下，NULL 与 0 是相同的。在一些语言中，您不需要初始化变量，因为它会自动将其设置为 nil。但是 C 不会这样做，所以您必须自己初始化。

(2). head 指向列表的第一个节点。一开始，它是 NULL，这意味着列表为空，因此 head 没有指向任何内容。cur 是要插入到列表中的新节点。curr->next 希望指向现有列表的第一个节点，因此 curr->next 设为 head。

(3). 此时 head 不再指向第一个节点。第一次循环时，它看起来像这样:

curr->node1->NULL head--^

但一般来说，它会像这样:

curr->node3->node2->node1->NULL head--^

因此，我们需要更新 head，使其指向第一个节点。由于 curr 指向新创建的节点，该节点位于最前面，所以我们只需将 head 设置为与 curr 指向相同的节点即可。

(4). 程序的第一部分完成了。cur 不再需要，因为它用于跟踪我们创建的新节点。它是一个临时变量。这个行 curr = head 表示我们将 cur 初始化为列表的开头。我们可以使用另一个变量使它更容易阅读，但通常会看到临时变量的重用。

(5). 是的。您可能会看到 NULL 定义为 (void*)0，因此它与 0 相同。除了来自60年代或70年代的非常旧的机器之外，您可能永远不会看到除 0 以外的任何其他值。因此，从逻辑上讲，它等价于 while (curr != 0)，即 while (curr)。

- ckim

Answer 4

我们从零开始。这就是开始的状态。

head = NULL;

告诉我们，我们还没有列表，因此无法访问它。

现在我们正在从1到10循环。我们从后往前构建一个列表。HEAD为空，因此“last”（第一个创建的）指向NULL：

curr->next  = head; // head is NULL in the first loop

现在HEAD已经设置为这个新元素：

head = curr;

在这个循环的第二次运行中，head存储了指向最后创建的项的指针。然后新创建的项将指向它。我们将这个新项设置在最后一项的前面。

设置

head = curr;

需要完成的任务是，确保在下一次循环中头部包含正确的指针。它被称为头部，因为它始终存储到目前为止已创建的列表的开头。

//4并不是必需的。

之前的最后一个操作是：

head = curr;

所以

curr = head;

没有意义。

第五个迭代遍历列表。 "curr" 指向第一个项目（具有非 NULL 地址）并在每次循环中设置为 curr->next。一旦 curr 为 NULL（在最后一个项目处），该语句不再成立。

- flyingOwl

Answer 5

1. head = NULL → 为什么要将head设置为NULL？
初始化变量是良好的编程习惯。在某些系统上，声明的变量在地址空间被占用时具有内存中的任意值。

2. curr->next = head → 我从来没有真正理解过这个。也许我的“头”定义有误，但在常规链表中，它是起始节点还是列表中的最后一个节点？我一直认为它是起始节点，但在这行代码中，它看起来像是最后一个节点。
是的，头是起始节点。

3. head = curr → 为什么我们要将其设置为curr？
这里的循环将新节点添加为头部。就像堆栈一样。其他方法会在尾部添加新节点。两种方法仍然是“链接列表”。

4. curr = head → 然后在循环结束后将curr设置为head。
curr充当索引，工作变量，以便不破坏数据结构。他在完成后重置它。“倒带磁带”。

5. while(curr) → 只是为了确保，这是遍历列表，相当于while(curr != NULL)，对吗？
是的，这是C语言中隐含的一些东西。在while循环中单独使用的任何内容都隐含着while(whatnot != 0)和null == 0。

- Philip

---

好的，这就是我感到困惑的地方...http://en.wikipedia.org/wiki/Linked_list在单向链表部分...带有“x”的框是头还是尾？ - ShadyBears

@juice：带有“X”内部的方框是NULL地址。最后一个元素指向它以显示“嘿，我是最后一个，没有人在我的后面”。通过此列表的循环将在最后一个项目中看到此NULL指针，然后退出循环。 - flyingOwl

是的，在那个例子中，#12是头部的值，而#37是尾部的值。 - Philip

Answer 6

首先，您可以在Linked List Head Is Always Null和Simple C++ Linked List中找到为什么头指针始终为NULL的答案。对于初学者的教程，您可以在C语言单向链表中找到。语句head=curr将指针head的值（原本为NULL）与当前指针的值相关联，后者通过分配内存而获得非零值。while(curr)是一个循环，只要curr与NULL不同，就会一直运行；而NULL作为宏关联着指向地址的零值。

- Mihai8

Answer 7

在第四个问题中，我认为curr=head是不必要的。因为当循环结束时，curr和head已经指向了同一个节点（i=10的节点）。但这是一个好习惯。

- Chandler's Sexyface