静态和动态数据结构之间的差异

Question

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

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

我怎么知道在哪种情况下使用它们？

Answer 1

首先是过度简化:

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

在这些结构中,阵列是静态的(即,它们的存储器占用空间随着对它们执行操作而不随时间变化)并且其他一切都是动态的(即,在一般情况下,存储器占用面积改变).

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

• 静态需要提前知道最大尺寸,而动态可以随时适应
• 静态无论如何都不会重新分配内存,因此您可以保证内存需求

还有其他差异,但只有在您的数据可能被排序时才会发挥作用.我不能给出一个广泛的列表,因为有许多动态数据结构对于不同的操作("添加","删除","查找")表现出不同的性能特征,因此它们不能放在同一屋檐下.

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

所以,回顾一下:

1. 如果您需要最大内存使用量的保证,除了数组之外别无选择.
2. 如果数据大小有硬上限,请考虑使用数组.数组很适合主要需要添加/删除操作(保持数组未排序)的问题以及主要需要查找操作(保持数组排序)的问题,但不能同时兼顾两者.
3. 如果您没有硬上限,或者您需要快速添加/删除/查找,请使用适当的动态结构.

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