4

阅读这个跳过列表实现我遇到了这个代码片段：

typedef struct nodeStructure{
    keyType key;
    valueType value;
    node forward[1]; /* variable sized array of forward pointers */
    };

对我来说，这似乎forward[1]表示一个元素数组。评论称它为可变大小的数组。

我是否误解了某些东西，或者这只是我正在阅读的来源中的一个错误？

4

4 回答 4

5

它被称为struct hack。它是C99 中引入的灵活数组成员的旧形式。

这在过去被用来模拟结构的最后一个成员中的变量数组，但它不是 C 中严格符合的构造。

于 2012-11-08T20:02:39.113 回答
3

这是您有时会看到的 C 中的程序范例。分配结构体时，会分配sizeof(struct nodeStructure + numNodes * sizeof(node))。

这允许您为该结构拥有多个前向节点，即使它仅被声明为有一个。这有点丑陋，但它确实有效。

通常，当您这样做时，还会有一个名为“count”之类的文件，以便您知道节点之后有多少额外的条目。

于 2012-11-08T20:04:33.923 回答
2

这是较旧的 C 编译器（C99 之前）的常见技巧：当 ;forward的最后一个元素时，编译器允许您取消引用超过声明长度末尾的元素struct。然后，您可以为其他元素malloc提供足够的内存，如下所示：node

nodeStructure *ptr = malloc(sizeof(nodeStructure)+4*sizeof(node));
for (int i = 0 ; i != 5 ; i++) { // The fifth element is part of the struct
    ptr->forward[i] = ...
}
free(ptr);

该技巧使您可以在结构中嵌入可变大小的数组，而无需单独的动态分配。另一种解决方案是声明node *forward，但随后您需要将其malloc与free分开nodeStructure，不必要地将 s 的数量加倍malloc并可能增加内存碎片：

以下是没有 hack 的上述片段的外观：

typedef struct nodeStructure{
    keyType key;
    valueType value;
    node *forward;
};

nodeStructure *ptr = malloc(sizeof(nodeStructure));
ptr->forward = malloc(5*sizeof(node));
for (int i = 0 ; i != 5 ; i++) {
    ptr->forward[i] = ...
}
free(ptr->forward);
free(ptr);

编辑（回应 Adam Rosenfield 的评论）：C99 允许您定义没有大小的数组，如下所示：node forward[];这称为灵活数组成员，它在 C99 标准的第 6.7.2.1.16 节中定义。

于 2012-11-08T20:03:11.720 回答
2

数据结构实现很可能是针对 C90 标准编写的，该标准没有灵活的数组成员（在 C99 中添加）。那时，在结构的末尾使用 1 甚至 0 大小（*）的数组是很常见的，以允许访问那里动态可变数量的元素。

该注释不应被解释为 C99 风格的可变长度数组；此外，在 C99 中，成员的惯用且符合标准的定义forward将是node forward[];. 具有此类struct nodeStructure成员的类型称为不完整类型。您可以定义一个指向它的指针，但您不能定义这种类型的变量或获取它的大小、所有允许node forward[0]或node forward[1]允许的操作，尽管这些操作可能与程序员的意图不匹配。

(*) 标准禁止使用 0 大小的数组，但 GCC 接受了这些数组作为这种用途的扩展。

于 2012-11-08T20:05:55.247 回答