C语言链表/->运算符

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的另一个结构的指针。我将链表可视化如下:

enter image description here

这种方式的可视化正确吗?


代码片段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"。然后,它将每个结构的第一个成员(data)分别设置为0、1、2,第二个成员(next)指向NULL。所以我的可视化现在是这样的:
现在有更多问题:
问题1:当我们最初将指针指向NULL时,它指向什么都没有,对吗?为什么要这样做?它最初不是指向什么的吗?
代码片段3:
   a.next = &b;
   b.next = &c;

这使得变量a、b(一个结构体)中的next分别指向b和c的内存地址。

我的想象:enter image description here

问题:它是如何做到的?结构体本身不是存储在多个内存地址上的吗(例如int需要4个内存地址)?


代码片段 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,但不确定它到底是做什么的。有人能创建一个快速图解吗?
此外:如果有人有任何好的资源/链接(没有双关语)可以帮助我更好地理解链表,请随意发布它们。

斯坦福大学的链表基础知识 http://cslibrary.stanford.edu/103/ - stev
回答第一个问题:我们将其初始化为零,以确保指针不指向任何位置,否则如果我们不将它们初始化为零,则可能会拾取任何垃圾值。 - Coffee_lover
回答问题2。是的,你说得对,但当我们执行a.next =&b时,它会将b的基地址分配给a.next。我们可以使用此地址访问整个b。 - Coffee_lover
@Bobby 希望这能有所帮助! - Coffee_lover
但是我稍后在代码中指向其他东西,初始化为零会有影响吗?谢谢 Stev 和 Coffee Lover! - Bobby
2
完整解释问题是可以的,但像这样长的问题,我的天啊:P - 0decimal0
3个回答

2

问题1:未初始化的指针并不指向“空”。如果您不设置其值,它可以(而且会)指向几乎 任何东西,包括(但不限于)空值、越界内存或您在网站上输入的最后一个密码。

这实际上与询问您在执行以下操作时counter 的值没有什么不同

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

next指针设置为NULL有两个不同的目的。首先,您可以确保它是一个“已知”的值,而不是任意随机值。其次,按照惯例,NULL值表示它不指向任何有效位置。
(这是一种“惯例”,因为NULL实际上存储了数值“0”。由于您正在谈论指针,因此作为内存地址,这是完全有效的。只是没有太多日常用途。)

谢谢!我会记下来的!哇,你在一个网站上输入的最后一个密码好可怕啊。;P - Bobby

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  

最初在 for 循环中,你将节点 a 的地址分配给表达式 i = &a 中的 i,然后它就变成了这样:

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


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

-> 运算符被称为 通过指针选择成员,请注意这里的 i 是类型为 struct ListItem* 的指针。
您也可以使用点运算符 .,它被称为 通过对象名称选择成员,如下所示:

  i = (*i).next;       

在编程中,操作员->.均可用于访问对象的成员。操作员->适用于地址,而.适用于值变量。

问题-3:我们设置了一个整数计数器,并将其初始化为零。此外,我们创建了一个名为i指向类型结构体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"

“另外,如果有人有任何好的资源/链接(无意冒犯),可以帮助我更好地理解链表,请随意发布。”
“从一个解释概念并附有图表和代码的来源进行阅读。您可以参考:如何使用C语言创建链表?

1
不,它确实有帮助,我正在尝试半读着它并保持清醒,这里已经很晚了。我已经好几个小时没睡觉了。非常感谢你的努力。我的考试结束后,我会亲自感谢你和在这里的每个人 ^_^ - Bobby
@Bobby abcstruct ListItem类型变量的名称(类似于int i = 10)。 a不是0,它是一个结构体变量而不是整数,a由两个数据成员datanext组成。 - Grijesh Chauhan
@Bobby:“此外,图中不应该有两个块吗?还是说这只是简化了?”我不明白。 - Grijesh Chauhan
@Bobby 不,它永远不会变成 a = 0,请阅读我的第一条评论:“a 不是 0,它是一个结构体变量而不是 int,a 由两个数据成员 data 和 next 组成” - Grijesh Chauhan
@Bobby 应该接受一个答案,阅读接受答案的工作原理是什么?,不是我的回答,而是任何一个 - Grijesh Chauhan
显示剩余2条评论

0

问题1的答案:不,结构体最初未初始化,其next字段很可能指向无效地址,但有可能它并不包含NULL

至于问题2:每个结构体变量在内存中都有其地址。当然,其各个字段(组件)也有各自的地址。整个结构体的地址是其第一个字段的地址。

至于代码段4中的i = i->nexti是当前列表项的指针(最初设置为a的地址)。该赋值语句将当前列表项的next字段的值取出,并将该值移动到i中。因此,i现在指向下一个列表项。这只是将i向右移动了一项(即正在遍历列表)。当i指向列表的最后一项时,i->nextNULL,因此在处理完最后一项后,i变成NULL,循环终止。


感谢你的有益回复Inspired。当你说next指向可能为nothing,但不包含NULL时,我想NULL代表它指向了空值?这意味着在我的代码中,a.next指向b.data,b.next指向c.data是吗?谢谢! - Bobby
从技术上讲,a.next 只是指向 b,而不是特别指向 b.data。如果您在源代码中交换 .next.data 的顺序,则您的最小程序仍将正常工作,但此时 a.next 将指向 b.next - Jongware
NULL是指向空的特殊值。最初,“next”字段根本不包含任何值(使用该值是未定义行为;好吧,可能它包含了某个指针,但它很可能不是NULL,尽管对其进行解引用会导致程序崩溃)。我不会说“a.next”指向“b.data”(尽管这可能是正确的,因为“b”和“b.data”的数字地址可能相同)。把它看作“a.next指向整个b”。 “b”是一个复合类型的变量,仅此而已。 - nullptr

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接