哪种数据结构在C中广泛使用？

Question

几天前,我问自己在C函数中应该使用哪种数据结构.我通常用C++编写,选择将落到std :: vector.

有一些可能的选择:

• 一个静态(足够大)的数组
• 一个动态数组,在需要时增长(例如,它的大小加倍)
• 一个自己的列表实现为结构的指针下一个

最后一个选项似乎不寻常.有没有更大的项目,有人使用自己的结构,如列表？数组或自己的数据结构之间的决策是否有一般规则？

当我需要一个树形结构时,我不会想到只写一棵树.有没有广泛使用的具有这种结构的库(比如boost for C++)？或者这被认为是不好的风格,因为你必须存储一个void*而不是实际的类型？

非常感谢您的体验!

Answer 1

不同的数据结构为插入,查找和其他操作提供了不同的计算复杂性.

举一个具体的例子,数组和链表之间存在许多差异:

• 按索引查找是O(1)在数组和O(n)列表中;
• 插入到列表中是O(1)或O(n)(取决于它们是否需要遍历),O(1)如果做得好,则进入数组中进行摊销;
• 从数组删除是O(n)某些类型的列表删除可以及时完成O(1);
• 数组提供更好的引用局部性,从而提高缓存性能.

您可能会发现以下页面非常有用:http://essays.hexapodia.net/datastructures/

作为一般规则,在选择数据结构时,我首先考虑是否有充分的理由相信相关代码的性能将变得很重要:

• 如果我不这样做,我选择最简单的数据结构来完成这项工作,或者选择最适合最清晰代码的数据结构;
• 如果我这样做,我会仔细考虑我将在结构上执行哪些操作并相应地进行选择,然后可能会进行分析.

至于好的C数据结构库的建议,看看是否有任何具有通用数据结构的开源C库？

Answer 2

每个都有自己的优点和缺点。

• 静态数组：非常适合查找表和在整个程序执行过程中不改变其大小的数据。它们在程序启动时分配，因此您不必以任何方式管理该内存。缺点是您无法调整静态数组的大小或释放静态数组 - 它会一直保留在那里，直到程序终止。

• 动态增长数组：一种易于管理的数据结构，几乎可以替代 C++ 中的向量数组。缺点是在运行时分配内存的开销，但如果一次分配更大的块，则可以减轻这种开销。

• 链接列表：如果您将拥有大量元素，请小心，因为在不使用内存池的情况下单独分配每个元素可能会导致内存浪费和碎片。