静态数据结构与动态数据结构的区别

Question

静态数据结构和动态数据结构的主要区别和优缺点是什么？

最常见的数据结构属于哪些类别？

我如何知道在哪种情况下使用每种方法？

Answer 1

从过于简化开始的：

只有几种基本的数据结构:数组、列表和树。其他的一切都可以通过使用这两种结构的不同类型来组成(例如，哈希表可以用一个用于哈希值的数组和一个用于每个哈希值的列表来实现，以处理冲突)。

在这些结构中，数组是静态的(即，当对其执行操作时，它们的内存占用不会随时间变化)，而其他一切都是动态的(即，在一般情况下，内存占用发生变化)。

这两种结构之间的差异可以从上面得出：

• Static需要预先知道最大大小，而dynamic可以动态调整
• Static无论如何都不会重新分配内存，因此您可以保证

的内存要求

还有其他差异，但是只有在数据可能被排序的情况下才会发挥作用。我不能给出一个详细的列表，因为有许多动态数据结构，它们对不同的操作("add"，"remove"，"find")表现出不同的性能特征，因此它们不能放在同一屋檐下。

一个非常明显的区别是，对于"find“以外的任何操作，排序数组都需要在内存中移动(可能需要很多)内容，而动态结构通常执行的工作较少。

所以，重述一下：

1. 如果您需要保证最大内存使用量，则除了数组之外别无选择。
2. 如果您对数据大小有严格的上限，请考虑使用数组。对于主要需要添加/删除操作(保持数组未排序)的问题，以及主要需要查找操作(保持数组排序)但不能同时执行这两种操作的问题，数组非常适合。
3. 如果您没有硬性的上限，或者如果您要求所有的添加/删除/查找操作都很快，请使用适当的动态结构。

编辑：我没有提到图，这是另一种动态数据结构，可以说它不能由更简单的部分组成(根据定义，树只有一个链接可以“连接到”除根节点之外的任何节点，而图可能有多个)。然而，在“使用哪个更好”的场景中，图不能真正与其他结构进行比较，因为您要么需要使用图，要么不使用图(其他结构可能表现出不同的性能，但最终它们都支持相同的操作集)。

Answer 2

静态数据结构(SDS)是固定大小的(例如数组)，一旦分配给它们的内存量在运行时就不能改变，而动态数据结构(DDS)(例如链表)具有灵活的大小，它们可以根据需要增加或缩小以包含要存储的数据。

SDS是线性数据结构，允许快速访问存储在其中的元素，但与DDS相比，插入/删除操作代价较高，DDS对元素的访问较慢，但插入/删除较快。

大多数DS都是动态DS。

在SDS空间是在实际数据插入之前分配的情况下，因此空间可能浪费或有时可能不足，因此只有在预先知道要插入的确切数据量的情况下才应该使用它们，如果在运行时知道的话，则应该使用DDS。

Answer 3

它总是反之亦然，如果你使用静态，那么你就会失去内存，而在动态的情况下，性能会降低。一个最好的设计应该有效地利用数据结构，没有一个完美的答案。