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

Question

几天前，我在C函数中询问应该使用哪种数据结构。平时我写的是C++代码，我的选择会是std::vector。

有几种可能的选择：

一个静态（足够大）数组

动态数组，当需要时增长（例如，将其大小翻倍）

一种自己实现的带有指针“next”的结构列表

最后一个选项似乎不太常见。是否有任何更大的项目使用自己的结构，如列表？ 在数组或自己的数据结构之间做决策是否有通用规则？

如果我需要树形结构，我会毫不犹豫地编写一棵树。是否有广泛使用的类库含有这样的结构（例如C++的boost库）？还是因为你必须存储void *而被认为是不好的风格？

非常感谢您分享的经验！

- tgmath

Answer 1

不同的数据结构对于插入、查找和其他操作具有不同的计算复杂度。

以您的具体示例为例，数组和链表之间存在许多差异：

- 通过索引查找数组是O(1)，链表是O(n)； - 插入到链表中是O(1)或O(n)(取决于它们是否需要遍历)，而插入到数组中则是平摊的O(1)； - 从数组中删除是O(n)，而某些类型的列表删除可以在O(1)时间内完成； - 数组提供更好的引用局部性和更好的缓存性能。

您可能会发现以下页面有用：http://essays.hexapodia.net/datastructures/ 一般来说，在选择数据结构时，我首先考虑代码的性能是否重要：

- 如果不重要，我选择最简单的数据结构来完成工作，或者选择最清晰的代码所适合的数据结构。 - 如果重要，我会仔细考虑我将在结构上执行哪些操作，并相应地进行选择，可能会跟随着性能分析。

至于好的C数据结构库的建议，请看：Are there any open source C libraries with common data structures?

- NPE

---

非常感谢。我发现对我来说最好的答案是GLib。通常情况下，我很容易选择正确的结构。但我不知道GLib。在纯C中，如果没有任何库，我通常会选择数组，因为可以使其正常工作，而且当前位置不是瓶颈。 - tgmath

你能解释一下，如何将元素插入到数组中可以达到O(1)的时间复杂度吗？我只能想象出类似于展开的链表之类的数据结构，但不是“纯粹”的数组。 - S.J.

@S.J.：关键词是摊销。它的意思是，对于一个数组，可以在总时间为O(n)的情况下进行n次插入。这并不意味着每个插入都是O(1)。例如，请参见https://dev59.com/OXVC5IYBdhLWcg3wtzyt。 - NPE

Answer 2

这完全取决于您将在数据结构上执行哪些操作。如果您将通过索引检索数据（例如，data [3]），那么列表是一个可怕的选择，因为每次读取都需要遍历整个列表。如果您将经常插入到第一个位置（例如，data [0] = x），那么数组将非常糟糕，因为每次插入都需要移动所有数据。

如果您要使用std :: vector，则动态数组可能是最佳替代品。但是也许std :: vector不是正确的选择。

- William Pursell

Answer 3

我记得有一段时间前，我读过苹果公司发布的一份文档，其中说这样的事情可以用类似下面的结构天真地实现：

struct {
    void *data; //other type rather than void is easier
    int length;
} MyArray;

MyArray *MyArrayCreate(){
    //mallocate memory
    return ...
}
void MyArrayRelease(){
    free(...);
}

实现一个函数，检查数组的长度，如果不够长，则会分配另一个足够大的数组，将原始数据复制到其中并添加新数据。

MyArrayInsertAt(MyArray *array, index, void *object){
    if (length < index){
        //mallocate again, copy data
        //update length
    }
    data[index] = object;
}

这样它就可以像这样使用：

MyArray *array = MyArrayCreate();
MyArrayInsertAt(array, 5, something);
MyArrayRelease(array); 

MyArrayInsertAt() 函数的性能不会获得奖项，但它可能是非高要求程序/应用的解决方案。

我就是找不到那个链接...也许有人也看到了？

添加： 我发现 GNU NSMutableArray (Objective-C) 方法的实现是用 C 语言完成的，它们做的与上述方法相同。每次需要添加一个对象且无法适应数组时，它们会将数组大小加倍。请参见第 131 至 145 行。

- nacho4d

Answer 4

动态链表在C语言中被广泛使用，特别是当需要存储的项目数量未知时。

- Rumple Stiltskin

Answer 5

向量是一种动态数组，内部实现为动态数组。我建议您使用向量，因为机器优化了检索连续的内存位置，而链表不会存储在连续位置。

话虽如此，如果您的用例不需要通过索引快速检索元素，则也可以选择链表。链表还具有不浪费空间的好处（不像动态数组那样在即将满时加倍），并且在开头或元素之间插入比数组更便宜。

- deovrat singh

Answer 6

每种数据结构都有其优缺点。

• 静态数组：适用于查找表和在程序执行期间大小不变的数据。它们在程序启动时分配，因此您无需以任何方式管理此内存。缺点是您无法调整静态数组的大小或释放它 - 它会一直存在，直到程序终止。

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

• 链表：如果要有很多元素，请注意，如果不使用内存池单独分配每个元素可能会导致内存浪费和碎片化。

- Blagovest Buyukliev

Answer 7

在纯C中，我大多使用静态数组。这与嵌入式设备的编程有关，这些设备在分配和释放内存时存在问题 - 堆碎片化。

但是，如果需要使用列表，则我会自己实现一个 - 有时其实现基于静态数组（再次）。

我认为，对于C语言，有一些库提供了更复杂数据结构的良好实现。据我所知，glib被广泛使用，并至少提供了链表。

- smbear