链表节点的结构体定义问题

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.2k 阅读时长 ≈ 4 分钟

链表节点的结构体定义理解和不完整类型声明

链表节点的结构体定义问题

在单向链表的学习中，一直忽略了一个技术问题，先看链表节点的结构体定义

1
2
3
4
struct node {
    int data;
    struct node *next;
};

仔细观察上述结构体定义，会发现在定义结构体 struct node 时，在其中又定义了一个struct node *next, 可是明明这个时候，struct node 的类型还没有定义完成，就在内部使用自己的类型，有点让人难以理解，感觉很奇怪

其实在C语言中，你可以定义结构体来表示链表节点，链表节点结构体包含了数据和指向下一个节点的指针，通常，你可以在定义节点类型之前使用正在定义的类型，但是需要使用指针来解决类型未定义的问题

其实，这种定义方式，和编译器本身的 处理方式 紧密相关

1. 结构体内部的大小是确定的

1
2
3
4
struct Node {
    int data;
    struct Node *next;
};

首先，Node 这个结构体的大小是可以明确的, int data 是4个字节，struct Node *next 也是4个字节(32位系统)，因为它仅仅只是一个指针变量，大小是确定的，因此整个Node 的大小也是确定的，总共是8个字节大小(32位系统)，包括其中存放的数据类型，一个是数据域部分的数据，一个是指针域部分的指针，这对于编译器来说是明确的

错误的写法其实是下面这种:

1
2
3
4
struct Node {
    int data;
    struct Node subnode;
};

其中Node的类型还正在定义中，在 Node 里面又定义struct Node类型的变量，编译器根本无法确定它的大小是多少，编译时就会出错，而且这是很明显的递归定义，是错误的定义形式

总之，你可以在定义节点类型之前使用正在定义的类型，只要你使用指针来解决类型未定义的问题。这是因为指针的大小是已知的，即使它指向的类型尚未完全定义

2. 编译会自己更新结构体的声明

实际上，这种方式称为 不完整类型声明，典型的例子就是结构体中的自引用指针

对于这种声明方式，编译器有自己的处理步骤：

  • 分配足够的内存空间：当编译器遇到不完整类型声明时，他知道其中的指针域变量是一个指针，但是无法确定指针指向的内存的确定大小，因为结构体的定义尚未完整，因为结构体本身的大小是确定的，内部各个成员的大小也是确定的，所以编译器会为其分配足够的内存大小
  • 生成代码：编译器会生成与结构体的定义不完整的部分的相关代码，相当于中间部分
  • 结构体的完整定义：当编译器走到完整的结构体定义结束后（通常在后续代码中或在不同的源文件中），它会了解结构体的确切布局和字段的大小
  • 更新不完整类型声明：编译器这时会回头更新之前的不完整类型声明，也就是中间部分
  • 生成正确的机器代码：现在，编译器具有完整的结构体定义，可以生成正确的机器代码，以确保结构体的成员被正确访问和操作

总之，编译器在编译过程中通过逐步处理不完整类型声明来处理自引用结构体。它为这些声明分配足够的内存以容纳指向相同类型的指针，然后在结构体的完整定义可用时，更新这些声明以反映完整的结构体定义，并生成正确的机器代码以处理结构体的成员。这使得在链表节点等数据结构中引用自身成为可能

简单来说，对于不完整类型声明，编译器在编译的过程中会进行更新，由不完整到完整，由不明确到明确，最终生成确定的定义和声明代码

参考：

  1. Chatgpt的问答
  2. 不完全类型和复杂声明