C结构体中的自引用

Question

这部分K&R（C语言书）让我深思：

从书中得知：

struct tnode {
             char *word;
             int    count;
             struct tnode *left;
             struct tnode *right;
};

节点的递归声明可能看起来有些冒险，但它是正确的。

因为tnode的定义并不使用tnode本身，而仅仅是指向tnode的指针，所以编译器给了我们一个免费通行证。但我想知道当tnode被声明时，计算机如何知道要分配多少内存？

- user485498

Answer 1

指针具有固定的大小（根据平台而定，为32/64位），因此编译器知道左侧和右侧指针需要多少内存，并可以计算出结构体的整个大小。

出于同样的原因，如果你需要一个指针，只需进行前向声明struct tnode;并可以使用该结构体的指针，例如：struct tree { struct tnode* root; };

- Karoly Horvath

---

从技术上讲，允许指向不同类型的指针具有不同的大小，只要对于所有对象类型T，sizeof(void *) >= sizeof(T *)。 - Chris Lutz

@Chris Lutz：...而且，在这种情况下很重要的是，所有指向“struct”类型的指针具有相同的大小和对齐要求。 - caf

@Chris：从技术上讲，并不能保证 sizeof(void*) >= sizeof(T*)。一个故意的恶意实现可以将未使用的填充字节放入非 void 指针中，或者更现实地考虑一个只有 24 位可寻址空间的 16/16 分段架构。然后，合法地，void* 可以被“压缩”为 3 个字节，而 char* 是一个完整的 4 字节远指针（方便解引用）。实现者是否会费心去做另当别论，重点是许多奇怪的事情都是允许的，保证的是 void* 可以保存任何对象的地址。 - Steve Jessop

@Steve - 其实，我认为在标准下char *和void *需要具有相同的表示形式。6.2.5¶26 "指向void的指针应具有与指向字符类型的指针相同的表示和对齐要求。" - Chris Lutz

@Chris：哎呀，应该是int*，哈哈。不过，如果一个char*的格式难以解引用，那就特别奇怪了。我完全同意你的预测，即sizeof(void*) >= sizeof(T*)，但据我所知，这只是常识而非标准的保证。 - Steve Jessop

Answer 2

简单来说，您有一个结构体中的4个成员，每个成员都有已知的内存需求。

虽然 left 和 right 是 tnode 类型的指针，但在使用 malloc() 创建 tnode 实例并将实例的地址分配给它们之前，不需要为它们的成员分配内存。

- Shamim Hafiz - MSFT