节点与指向节点的指针有何关系?
链表里的节点本质上是结构体(即 struct Node),而不是结构体指针(即 struct Node*)。
typedef struct Node //定义结构体节点 struct Node
{
int value;
struct Node* next;
} Node; //将struct Node重命名为Node
Node *first = (Node*)malloc(sizeof(Node))
我们平常所说的 “用 malloc 申请 节点”,这个表述其实是不严谨的,准确来说是用 malloc 申请一个节点的地址。
因为 malloc(sizeof(Node)) 的返回值是指向这块内存空间起始地址的指针,其类型是 void*(一种通用的指针类型,可以指向任何类型的数据),再用 (Node*) 将其强制转化为 Node* 类型,就变成了一个 Node 结构体的指针。
所以说 first 是一个指向 Node 结构体的指针,是指向节点的指针,不是节点。
一个节点的类型是 struct Node 或 重命名成的 Node,它表示一个具有 value 和 next 成员的结构体。
而一个节点的指针的类型是 struct Node* 或 重命名成的 Node*,它表示一个指向结构体的指针。
搞清楚了什么是指向节点的指针、什么是节点,接下来考虑一个问题:
为什么非要定义指向节点的指针,而不是直接创建节点呢?
struct Node{
int value;
struct Node next;
};
也就是说这样来定义节点,然后创建节点:struct Node p = null,使用结构体的点操作获取结构体内元素(即通过 p.next 找到下一个节点),不是和指针一样吗?为什么一定要用指针指向节点进行链表操作呢?
原因如下:
首先,没有办法定义一个节点,上面这个写法会报错:[Error] field 'next' has incomplete type 'Node'
因为在 struct Node 的定义中,next 成员被声明为 struct Node 类型,而不是指向 struct Node 的指针类型。这样会导致结构体的无限嵌套,因为每个 Node 结构体都包含了另一个完整的 Node 结构体,无法确定结构体的大小。
其次,就算可以这样写,也会因为在实现插入或删除节点操作时,需要复制整个结构体(比如另p.next = q),如果结构体里数据较多的话,影响运行效率。
反观,使用指针来操作的话,指针只需要存储节点的地址,不需要复制整个节点的数据,插入、删除节点时也只需调整指针,不需要移动大量的数据。
如果定义一个指针 p 指向一个节点 struct Node,即 struct Node *p = (struct Node*)malloc(sizeof(struct Node)),可以用指针的箭头操作 p->value 来获取所指向的节点中的数据,用 p->next 获取指向 ’p所指向节点的下一个节点‘ 的指针,很方便实现链表中节点的增删改。
所以,才会用指针来指向节点进行链表操作。无论是节点的定义还是节点的操作,都很方便。
下面是参考的chatgpt的回答: