3

所以我一直在尝试理解链表的概念（一直在看一些示例代码，我在互联网上找到了这个。现在如果我可以请有人确认我是否正确掌握了一些概念。我会画我认为每个代码链接所做的图表。

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

   struct ListItem {
   int data;
   struct ListItem *next;
};

int main (int argc, char *argv[]){

   struct ListItem a;  
   a.data = 0;
   a.next = NULL;
   struct ListItem b;
   b.data = 1;
   b.next = NULL;
   struct ListItem c;
   c.data = 2;
   c.next = NULL;

   a.next = &b;
   b.next = &c;

   int counter = 0;
   struct ListItem *i;
   for (i = &a; i != NULL; i = i->next){

      printf("Item %d value is %d\n\r", counter, i->data);
      counter++;
   }


   return 0;
}

代码 1 的片段：

struct ListItem {
    int data;
    struct ListItem *next;
};

这将创建一个名为 ListItems 的结构。该结构有两个组件，一个用于存储数据的组件和一个指向另一个 struct ListItem 类型的结构的指针。我将链表可视化如下：

在此处输入图像描述

这是一种正确的可视化方式吗？

代码片段2：

struct ListItem a;  
a.data = 0;
a.next = NULL;
struct ListItem b;
b.data = 1;
b.next = NULL;
struct ListItem c;
c.data = 2;
c.next = NULL;

是的，我知道它可以缩短，但我只是这样做，看看我是否能理解这个概念。现在这个片段创建了一个类型为 struct ListItem 的变量“a”、“b”和“c”。然后它将每个结构的第一个成员（数据）分别设置为 0、1、2，并将第二个成员（下一个）指向 NULL。所以我现在的可视化是这样的：

在此处输入图像描述

现在有更多问题：

问题1：当我们最初将指针指向NULL时，它指向什么都正确？我们为什么要做这个？原来不是指什么都没有吗？

片段 3：

   a.next = &b;
   b.next = &c;

这让我们接下来在每个变量a、b（这是一个结构体）中分别指向b和c的地址内存位置。

我的可视化：在此处输入图像描述

问题：它怎么能做到这一点？结构本身是否存储在多个内存地址上（4个用于int等）

片段4：

   int counter = 0;
   struct ListItem *i;
   for (i = &a; i != NULL; i = i->next){

      printf("Item %d value is %d\n\r", counter, i->data);
      counter++;
   }

这是我有点困惑的片段。现在，我们留出一个称为计数器的整数并将其初始化为零。此外，我们创建了一个名为 i 的变量，它指向类型 struct ListItem。现在有人可以向我解释 for 循环吗？我对它在做什么有点困惑。特别是i=i->next，这个我不熟悉。我知道它相当于 i=(*i).next 但不确定它的真正作用。有人可以创建一个快速图表吗？

还：如果有人有任何好的资源/链接（不是双关语）到一些有用的网站来帮助我更好地理解链接列表，请随时发布它们。

4

3 回答 3

2

Q1：未初始化的指针不指向“无”。如果您不设置它的值，它可以（并且将）指向几乎任何东西，包括（但不限于）nul 值、越界内存或您在网站上输入的最后一个密码。

这真的和counter你做的时候问你的价值是什么没有什么不同

int counter;
...
printf ("counter is %d\n", counter);

next因此，将指针设置为 NULL 有两个不同的目的。首先，您确定这是一个“已知”值，而不是任何随机值。其次，按照惯例，NULL 值意味着它不指向任何有效位置。

（这是一个“约定”，因为 NULL 有效地存储了数值“0”。作为内存地址——因为你在谈论指针——是完全有效的。它的日常用途并不多。）

于 2013-07-27T11:55:38.800 回答
0

对问题 1 的回答：不，最初结构是未初始化的，它的next字段很可能指向不正确，但很可能它不包含NULL.

问题2：每个结构变量在内存中都有它的地址。当然，它的字段（组件）也有它们的地址。整个结构的地址是它的第一个字段的地址。

至于i = i->next在 Snippet 4 中：i是指向当前列表项的指针（它最初设置为 的地址a）。赋值获取next当前列表项的字段值并将该值移动到i. 所以i现在指向下一个列表项。这只是向右移动i一项（它正在遍历列表）。当i指向列表的最后一项时，则为i->next，NULL因此在处理完最后一项后，循环终止。iNULL

于 2013-07-27T11:49:46.413 回答
0

问题 1：当我们最初是指向 的指针时NULL，它指向什么都不正确？我们为什么要做这个？原来不是指什么都没有吗？

是的。NULL 不能是任何节点的地址，所以它不指向任何东西。我们初始化为 NULL 以避免程序中的错误。它还假定使用一些默认值初始化变量的良好做法。

假设如果您不使用 NULL 初始化 next，那么 next 将指向某个垃圾节点，并且如果您的代码有错误，则访问未分配的内存是未定义的行为。并且 next 的未初始化值是垃圾，不同的运行会表现出不同的方式。但是如果你初始化为 NULL 它将产生恒定的结果，因此很容易跟踪错误。阅读：初始化一个变量。

问题2：特别是，i = i->next我不熟悉这个。我知道它相当于i = (*i).next 但不确定它的真正作用。有人可以创建一个快速图表吗？

在表达式 i = i->next;中，您将下一个节点的地址分配给 i指针。您在内存中的链表可以假设为： 

 a         b        c 
+---+    +---+    +---+                               
| a |--->| 1 |--->| 2 |---+
+---+    +---+    +---+   |                                
                         null

最初，您将节点的地址分配给afor循环i中的表达式i = &a，它变成这样： 

 a         b        c 
+---+    +---+    +---+                               
| a |--->| 1 |--->| 2 |---+
+---+    +---+    +---+   |                                
  ▲        ▲             null  
  i        i->next    


  i = i->next; 
  ^      ^
  |      next to `i` in linked list
   current node

运算符->调用Member selection via pointer，注意这里i是指针类型struct ListItem*。
您也可以使用如下 .调用的运算符来执行相同操作：Member selection via object name

  i = (*i).next;

这两个运算符 ->都.可以用来访问对象的成员。运算符对地址和值变量 ->很有用。.

问题 3：我们留出一个称为 counter 的整数并将其初始化为零。此外，我们创建了一个名为 i 的变量，它指向类型 struct ListItem。现在有人可以向我解释 for 循环吗？

在您的代码中，i如上所述，用于在通过链表时保留当前节点的地址，而counter仅用于对链表中的节点进行计数。 

   int counter = 0;  <-----" count value is 0, not Garbage"
   struct ListItem *i;

   for (i = &a; i != NULL; i = i->next){ 
                   ^
                   |<------ "loop will run till `i` not point to NULL"
                   |        "this means loop will run once for all nodes"
      printf("Item %d value is %d\n\r", counter, i->data);
      counter++;  <---"each time `counter` incremented by `1` (one for each node)"
   }
   "after the loop counter value is = number of nodes in list"

另外：如果有人有任何好的资源/链接（不是双关语）到一些有用的网站来帮助我更好地理解链接列表，请随时发布它们。

从用图表和代码解释概念的来源阅读。可以参考：How to create Linked list using C?

于 2013-07-27T11:50:19.630 回答