C语言typedef结构体展开规则与无名结构体类型名称归属的技术问询

考虑一个单元格链表，每个单元格包含一些整数信息和一个指向链表中下一个单元格的指针。对应于链接和单元格的Pascal类型名称声明如下：

type link = ↑ cell;
cell = record
    info : integer;
    next : link
end;

注意，类型名称link是基于cell定义的，而cell又是基于link定义的，因此它们的定义是递归的。如果我们愿意在类型图中引入循环，就可以替换掉递归定义的类型名称。如果用pointer(cell)替换link，就得到了cell的类型表达式，如图6.8(a)所示。使用图6.8(b)中的循环，我们可以在标记为record的节点下方的类型图部分中消除对cell的提及。

示例：C语言通过对除记录类型外的所有类型使用结构等价性来避免类型图中的循环。在C语言中，cell的声明如下：

struct cell {
    int info;
    struct cell *next;
};

C语言使用关键字struct而非record，且名称cell成为该记录类型的一部分。实际上，C语言使用的是图6.8(a)中的无环表示。C语言要求类型名称在使用前声明，但允许指向未声明记录类型的指针作为例外。因此，所有潜在的循环都是由指向记录类型的指针引起的。由于记录的名称是其类型的一部分，当遇到record构造器时，结构等价性测试会停止——要么被比较的类型是等价的（因为它们是相同的命名记录类型），要么不等价。

问题1解答 #

针对这段模拟C代码：

typedef struct cell* link;
struct cell{
    int info;
    link next;
};

它会被展开为《龙书》摘录中给出的代码形式。

我们可以一步步拆解来看：

• 第一行的typedef struct cell* link;只是给struct cell*这个指针类型起了一个别名link，并没有改变底层类型的本质。
• 当定义struct cell时，里面的link next;会被直接替换为struct cell* next;，这和龙书里给出的struct cell *next;完全等价。

从类型系统的角度来说，这个typedef只是语法层面的别名简化，最终的类型结构和龙书里的声明完全一致，都是定义了一个带自引用指针的递归结构体类型。

问题2解答 #

对于这个匿名结构体的typedef定义：

typedef struct {
    int info;
}cell;

这里的cell不属于该记录类型的一部分。

龙书里提到的“名称cell成为该记录类型的一部分”，特指带标签的结构体（比如struct cell）——这里的cell是结构体的标签，是绑定到该记录类型本身的，属于类型标识的核心组成部分。而上面的代码中，结构体是匿名的（struct后面没有紧跟标签名称），cell只是给这个匿名结构体类型起的一个别名而已，和结构体类型本身没有绑定关系。

简单来说：带标签的struct cell中，cell是类型的“本名”；而匿名结构体的cell只是一个“外号”，哪怕换成typedef struct { int info; } foo;，这个结构体类型本身还是那个匿名结构，和别名无关。

内容的提问来源于stack exchange，提问作者Abhishek Ghosh