数据结构可以包含多种类型的元素吗？

Question

This program 是同一个旧的单链表的不同方法。我没有创建单个结构并将同一类型的下一个节点的指针保留为结构的成员，而是在这里使用了三个不同的结构，每个结构中都有一个普通的 long nextaddress 成员来指向下一个节点的地址节点，因为指针也做同样的事情。

每个节点还有一个int flag成员作为结构的第一项，data部分由于其长度可变而位于结构的末尾。

这三个结构是内置类型long、double和char的基本扩展。在访问结构时，我首先将节点的地址转换为 int *，这样我就可以访问 flag，而无需将地址完全转换为三者中的确定结构。

然后分析flag，各种操作就搞定了

所以这是我的问题。能叫有效链表吗？而且，它甚至是一个有效的数据结构吗？

Answer 1

你的代码有很多问题，但仅指你对结构体的具体问题

Standard C 证明您的解决方案有效

6.7.2.1 Structure and union specifiers

Sub chapter 15

Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared. A pointer to a structure object, suitably converted, points to its initial member (or if that member is a bit-field, then to the unit in which it resides), and vice versa. There may be unnamed padding within a structure object, but not at its beginning.

^强调我的

您应该在其他 struct:this 赠款中使用 gen_struct 以尊重“初始成员”的规则。

struct gen_type {
    int flag;
    void *nextaddress;
};

struct node_type_int {
    struct gen_type header;
    long data;
};

struct node_type_real {
    struct gen_type header;
    double data;
};

struct node_type_char {
    struct gen_type header;
    char data;
};

如您所见，我还更改了 nextaddress 的类型：本来是指针，所以使用指针。

旁注：do-i-cast-the-result-of-malloc

Answer 2

不错。开箱即用，我喜欢不同的方式！但是...

考虑到内存对齐差异，您是否认为以下代码可能存在问题：

dataaddress = ((long)(&generic->nextaddress)) + sizeof(long);

这里假设数据是连续存储的，因此通过将 sizeof long 添加到下一个地址的地址来计算数据的地址。但这不一定总是这样吧？

相反，我觉得最好在读取标志值后转换为适当的结构类型，然后再读取数据。

考虑到这些挑战，虽然您节省了一些内存但增加了更多处理。因此，尽管它看起来像一个有效的链表，但实现可以根据内存与处理的选择来决定。

Answer 3

您的代码至少有两个弱点：

1.) long 和指针之间的相互转换。仅当整数类型可以容纳必要的范围时，C 标准才允许这样做，而在具有 32 位 long 整数和 64 位指针的体系结构上可能并非如此。

我正在添加 C11 标准中的引用，第 6.3.2.3 节指针：

An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation.67)

Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

67) The mapping functions for converting a pointer to an integer or an integer to a pointer are intended to be consistent with the addressing structure of the execution environment

2.) 实现假定两个不同结构中的字段（前面字段的类型匹配）存储在结构中的相同位置（偏移量）。虽然这对于大多数实现都是正确的，但只有当这两个结构是联合的一部分时，标准才保证这一点。

第 6.5.2.3 节结构和联合成员：

One special guarantee is made in order to simplify the use of unions: if a union contains several structures that share a common initial sequence (see below), and if the union object currently contains one of these structures, it is permitted to inspect the common initial part of any of them anywhere that a declaration of the completed type of the union is visible. Tw o structures share a common initial sequence if corresponding members have compatible types (and, for bit-fields, the same widths) for a sequence of one or more initial members.

Answer 4

只要您有办法判断每个节点包含哪种类型，就可以这样做，例如 flag 变量。

无论您使用哪种结构类型，您都可以假设 flag 和 nextaddress 将位于相同的结构偏移量上，这似乎是合理的。虽然严格来说 C 语言并不能保证这一点，但我相信它可以在任何系统上实际工作。

但是，您不能假设 data 位于 (uint8_t*)&my_struct + sizeof(int) + sizeof(long)。由于不同的对齐要求，此偏移量可能因结构而异。

一个更严重的问题是指针别名。您不能将指针 struct* x 转换为另一种指针类型 struct* y。它将编译，但这违反了 C 中的类型规则并调用未定义的行为（除非两个结构具有完全相同的成员）。使用积极优化的符合标准的编译器（如 GCC）不会按预期编译此类代码。 (What is the strict aliasing rule?)

为了安全起见并获得更好的整体程序设计，我建议您改为这样做：

typedef struct node
{
  long   nextaddress;
  type_t type; // some enum
  void*  data;
} node_t;

其中data与节点分开分配。你会得到一个链式链表。

数据结构可以包含多种类型的元素吗？

Can a data structure contain multiple type of elements?

c

linked-list

data-structures

singly-linked-list