C语言 为什么我们在初始化链表的根时使用node*而不是只说node?

Question

假设我们有这些链表的代码：

#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
node* next;
}

上面的代码是有意义的，因为它有一个指针来指出另一个结构(我想它有一个递归的存在，如果我错了，请纠正我(。

但是，我正在努力处理持续的代码：

int main (){
node* root;
}

为什么初始化根时需要放星号？结构根本身已经有一个指针，用于指出下一个节点。

Answer 1

这看起来像一个链表。从理论上讲，你可以做

node root;

但问题是：你将如何表示一个空链接结构，其中没有任何内容？通常，我们可以使用nullptr(C中的NULL(来表示空结构。如果在没有指针的情况下生成第一个节点，则它不能为 null。因此，数据结构必须至少包含一个节点(除非这是您想要的(。

Answer 2

对于初学者来说，这个结构声明(如果甚至不考虑右大括号后被遗忘的分号(

struct node {
int data;
node* next;
}

是不正确的。

struct node和node是两个不同的类型说明符。结构应该声明为类似

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

因此，单向链表由相同类型的节点组成，每个节点都指向另一个下一个节点。

列表的头部或开头由表示列表开头的单个指针指定，最初设置为 NULL，因为列表最初为空。

int main( void ){
node* root = NULL;
}

因此，如果每个节点都包含指向下一个节点的引用(指针(，那么我们需要有一个指向列表潜在第一个节点的初始引用(指针(，该节点将附加到列表或插入列表的前面。

如果此初始引用(指针(不等于 NULL，则表示列表至少有一个实际节点，并且引用指向列表的第一个节点。

通常，节点被合并到表示列表的结构中。例如

struct SinglyLinkedList
{
struct node *head;
};

并且主要声明结构的对象，例如

int main( void )
{
SinglyLinkedList list = { NULL );
//…
}

列表的用户不应直接处理结构节点类型的对象。

例如，将新节点向前推的函数可能看起来像

int push_front( struct SinglyLinkedList *list, int data )
{
struct node *new_node = malloc( sizeof( struct node ) );
int success = new_node != NULL;
if ( success )
{
new_node->data = data;
new_node->next = list->head;
list->head = new_node;
}
return success;
}

类似的东西

#include <stdio.h>
#include <stdlib.h>
struct node 
{
int data;
struct node* next;
};
struct SinglyLinkedList
{
struct node *head;
};
int push_front( struct SinglyLinkedList *list, int data )
{
struct node *new_node = malloc( sizeof( struct node ) );
int success = new_node != NULL;
if ( success )
{
new_node->data = data;
new_node->next = list->head;
list->head = new_node;
}
return success;
}
int main(void) 
{
struct SinglyLinkedList list = { NULL };
const int N = 10;
for ( int i = 0; i < N; i++ )
{
push_front( &list, i );
}
//…
return 0;
}