arrays - 使用数组实现图

Question

我想实现一个生成图形的工具，其内存将分配在所谓的“磁带”数据结构上。您可以将磁带视为一个元素数组，每个元素都包含“节点 ID”，链接到其“父节点”以及“子节点”。

我正在寻找一种方法，在该方法中识别阵列中的可用插槽很便宜，因此当要添加新节点时，可以快速识别空插槽。

如果我使用动态数组来实现磁带呢？在需要调整数组大小的情况下，是否可以避免将整个磁带复制到新分配的数组中？

这里有人知道吗？

Answer 1

我假设您想预先分配一个大的“磁带”，例如数千个节点。

您应该结合两个概念：

• 首先将最后使用的条目存储在磁带上。下次需要新条目时，只需选择上次使用的条目之后的条目即可。
• 其次保留一个免费列表。使用磁带条目的前 4 个字节（或 64 位中的 8 个字节）作为指向下一个空闲条目的指针。磁带的开头应指向第一个空闲条目。

每当磁带上的条目被释放时，将其添加到空闲列表中。

每当磁带中需要新条目时：

• 检查空闲列表中是否有元素。如果有第一个条目并将其从空闲列表中删除
• 如果空闲列表为空，则使用最后使用的条目并立即获取它之后的条目。

您还可以将此与重新分配方案结合使用，在该方案中，您保留磁带的总分配大小，并在最后使用的条目到达磁带末尾时重新分配。