链表中的节点是单独的结构还是同一结构的一部分？

Question

我在C中有一个链表如下：

typedef struct intSet *link;

typedef struct intSet {
    int num;
    link next;
} intSet;

当我打印结构的各个成员的大小时，我得到以下信息：

sizeof(List) = 8 bytes  //List is a newly created list
sizeof(curr->num) = 4 bytes  // curr is just a node within the list
sizeof(curr->next) = 8 bytes

我的问题是：无论我们在列表中有多少元素，结构本身是否总是有 8 个字节的大小，或者这 8 个字节仅与列表中的第一个节点和下一个节点有关是同一结构的不同实例吗？

我问的原因是因为我计划在 PostgreSQL 中将其实现为用户定义的数据类型，因此它需要我声明数据类型的长度是常量还是可变的：

CREATE TYPE list (
    internallength = 8? or internallength = variable
    input = ..., output = ... );

如果它是可变的，我必须将我的结构表示更改为：

typedef struct intSet {
    int size;
    int num;
    link next;
} intSet;

而且我怀疑如果节点是分开的并且不是同一结构的不同部分，因为下一个节点的大小可能比最后一个节点多 4 个字节，我可能必须不断更新大小。任何提示或指示将不胜感激。

Answer 1

sizeof 指针在系统中是相同的。在您的情况下，无论它指向什么（无论是 int、char、struct 等），它总是 4 个字节。在你的情况下它将是 4 个字节。因此，您的结构大小始终为 8 个字节（int 为 4 个字节 + 指针为 4 个字节）。

Answer 2

你的类型 link 是一个指针，如果你没有用 typedef 混淆它会更明显。指向的东西是一个单独的 struct（它也有自己的 next 点等），它需要自己的存储空间。

现在 sizeof(curr->next) 和 sizeof(List) 是指向结构的 指针的大小，而不是 struct intSet 的大小。 sizeof(*(curr->next)) 和 sizeof(struct intSet) 都是结构本身的大小，即您需要为单个结构分配的 space 的数量。

从不sizeof遍历指针来找出整个列表的大小。如果需要求出list的整个大小，需要自己遍历，统计元素，那么总大小为count * sizeof(struct intSet)。但是，您不太可能需要链表的这些信息，因为如果您一次分配整个列表，您可以只使用一个没有 next 链接的数组…

Answer 3

对 sizeof 的担忧不是主要问题，尤其是在 32 位中 sizeof(intSet) 将为 8 而在 64 位中 sizeof(intSet) 将为 32 位。

关于 PostgreSQL，您要存储的对象是一个 int 容器，因此具有可变长度。因此，您要处理的对象不是 intSet，而是一个包含列表大小和第一个元素的结构。

typedef struct intSet *link;

typedef struct intSet {
    int num;
    link next;
};

struct intSetSized
{
    int size;
    intSet begin;
};

您要将 intSetSized 声明为您的用户定义类型，如 udt。

每添加或删除列表中的内容，您都会调整 size。

注意如何为对象实现输入和输出函数 intSetSized udt.

中给出的示例更加棘手

链表中的节点是单独的结构还是同一结构的一部分？

Are nodes in a linked list separate structs or part of the same struct?

c

struct

linked-list

sizeof

singly-linked-list