11

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

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) 对吗？

4

7 回答 7

20

#1：head = NULL

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

有关更多信息，请参阅Steve McConnell 的Code Complete：软件构建实用手册或防御性编程的Wikipedia 页面。

#2：curr->next = head

构建链表。该curr节点正在“链接”到序列中先前创建的节点。

#3：head = curr

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

下图可视化了步骤 #2 和 #3：

第一的 第二 第三 第四和最后

#4：curr = head

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

前

后

#5：while(curr)

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

于 2013-03-15T21:02:34.303 回答
5
  1. head 指向列表的头部。由于列表当前为空，因此设置为 null
  2. 当您将一个节点添加到列表中时，您将“下一个”指针设置为列表的当前头部。将新节点放在列表的头部。
  3. 您将“head”设置为“curr”以使新节点成为列表的头部。
  4. 循环结束后，您将重新使用“curr”变量来遍历列表。
  5. 您将依次遍历每个节点的列表设置“curr”，直到您离开列表底部（其中 curr->next 为空）
于 2013-03-15T20:45:56.627 回答
3

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

(2)。head指向列表的第一个节点。起初，它是 NULL，这意味着列表是空的，因此head没有指向任何东西。cur是要插入到列表中的新节点。curr->next想要指向现有列表的第一个节点，所以curr->next设置为head.

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

curr-->node1-->NULL
         头--^

但总的来说它看起来像这样

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

所以我们需要更新head指向第一个节点。由于curr指向的是新创建的节点，它位于最前面，我们只需设置head为指向与 相同的节点curr。

(4)。程序的第一部分已经完成。 curr不再需要，因为它用于跟踪我们创建的新节点。这是一个临时变量。这一行curr = head意味着我们将初始化curr到列表的开头。我们本可以使用另一个变量来使其更具可读性，但您通常会看到临时变量的重用。

(5)。对。您可能会看到NULL定义为(void*)0，因此它与 0 相同。除了 60 或 70 年代的真正旧机器之外，您可能永远不会看到除 0 之外的其他值。所以从逻辑上讲，它相当于： while (curr != 0)与while (curr).

于 2013-03-15T21:18:07.460 回答
2

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。

于 2013-03-15T20:54:09.983 回答
2

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

于 2013-03-15T20:54:23.543 回答
2

我们从一无所有开始。就是这样

head = NULL;

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

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

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

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

head = curr;

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

环境

head = curr;

需要完成，以确保在下一个循环中该 head 包含正确的指针。它被称为 head，因为它总是存储到那时创建的列表的开头。

//4 并不是必须的。

之前的最后一次操作是：

head = curr;

所以

curr = head;

是没有意义的。

第 5 个遍历列表。“curr”指向第一项（具有非 NULL 地址）并在每个循环中设置为 curr->next。一旦 curr 为 NULL（在最后一项），该语句就不再成立。

于 2013-03-15T20:56:16.787 回答
0

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

于 2014-03-06T07:16:48.757 回答