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

Question

静态数据结构与动态数据结构之间的主要区别、优缺点是什么？

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

如何确定在哪种情况下使用每种数据结构？

- Carlos

Answer 1

简单来说:

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

在这些结构中，数组是静态的（即它们的内存占用量随着对它们进行操作而不会变化），而其他结构是动态的（即通常情况下，内存占用量会发生变化）。

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

• 静态需要预先知道最大尺寸，而动态可以根据需要调整大小
• 静态不管怎样都不会重新分配内存，因此您可以保证内存要求

还有其他差异，但仅在您的数据可能被排序时才会发挥作用。我无法给出详尽的列表，因为许多动态数据结构在不同的操作（“添加”、“删除”、“查找”）下表现出不同的性能特征，因此它们不能被放在一起。

非常明显的区别是排序数组除了“查找”操作外，对于任何其他操作都需要在内存中移动（可能会有很多）内容，而动态结构通常需要执行更少的工作。

所以，总结一下：

1. 如果您需要保证最大内存使用量，则除了使用数组没有其他选择。
2. 如果您对数据大小有硬性上限，请考虑使用数组。数组可以很好地解决主要需要添加/删除操作的问题（保持数组未排序），也可以很好地解决主要需要查找操作的问题（保持数组排序），但不能同时处理两者。
3. 如果您没有硬性上限或者需要快速完成所有添加/删除/查找操作，请使用适当类型的动态结构。

编辑：我没有提到图形，这是另一种动态数据结构，可以说不能由更简单的部分组成（树的定义是除了根节点外，每个节点只有一个指向“内部”的链接，而图可能有多个）。然而，图形在“什么情况下最好使用”方面无法与其他结构进行比较，因为你要么需要使用图形，要么不需要（其他结构可能表现出不同的性能，但最终它们都支持相同的操作集）。

- Jon

---

在某种程度上，列表只是一种退化的树形结构。你可以说有两种数据结构，块状和基于节点的（以及两者的各种混合形式）。 - Drew Hall

另外，我不同意第一点。你完全可以编写一个“BoundedList”类，在添加第N+1个元素时生成错误（或其他操作）。但我同意这并不是一个基本的数据结构，更像是一个hack。 - Drew Hall

@Drew：你两点都说得对。说实话，我最初打算写关于两种结构并将树和图形排除在外，但我认为肯定会有人纠正我。看起来你无法避免这个问题 :-）。至于有界列表，我认为你会同意，原始问题所涉及的知识水平的人被告知这个技术细节是没有任何收获的。 - Jon

你可以通过列表构建图形：节点之间的链接列表和节点列表。 - user21037

一个类（或来自C的结构体）也是一个非常重要的静态结构。 - Justin

Answer 2

静态数据结构（SDS）是固定大小的（例如数组），一旦为它们分配了内存，就无法在运行时更改其大小，而动态数据结构（DDS）（例如链表）具有灵活的大小，它们可以根据需要增长或缩小以包含要存储的数据。

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

大多数DS都是动态DS。

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

- Nidhi

Answer 3

简单提示

动态数据结构具有以下特点：

• 能够高效地添加、删除或修改元素
• 大小灵活
• 有效利用资源 - 因为资源在运行时按需分配。
• 访问元素较慢（与静态数据结构相比）

静态数据结构具有以下特点：

• 不能直接添加、删除或修改元素。如果这样做，将消耗大量资源。
• 固定的大小。
• 即使元素不包含任何值，也会在创建数据结构时分配资源。
• 访问元素更快（与动态数据结构相比）

总之，对于已知且不会改变的数据集，使用动态结构来存储是不有效的。在这种情况下使用静态数据结构可以节省系统资源，并提供更快的元素访问。另一方面，如果数据的大小可能会发生变化，则使用动态结构。

- Menezes Sousa

Answer 4

这总是反过来的，如果你选择静态方式，那么会损失内存，而在动态方面，性能会降低。最好的设计应该有效地使用数据结构，没有完美的答案。

- Phani