C语言中管理100个项目的有效方法，开销小

Question

我在一个只有512 is的系统上，我的应用程序可用(其余的用于缓冲区)。我需要尽可能有效率。

我有大约100个项目是快速添加/删除一个列表。在C中存储这些文件的有效方法是什么?是否有一个库(拥有良好的许可证)将有所帮助？该列表从未超过256项，其平均大小为15项。

• 我应该使用二叉树吗？
• 红黑树

Answer 1

如果列表不再是256，最好的选择是保存一个哈希表，并使用散列函数添加/删除每个新元素。这样，每个add/remove只需要占用O(1)，所用内存的大小就不需要很大。

Answer 2

在平均大小为15的情况下，所有这些解决方案都不必要的过度；这里最好使用一个简单的动态数组。搜索是对数组的线性传递，插入和删除需要移动插入点后面的所有元素。但是，这种移动将被如此少的元素缺乏开销所抵消。

更好的是，因为您无论如何都是在进行线性搜索，所以可以通过将最后一个元素交换到已删除的位置来完成删除操作，因此不需要进一步移动元素--生成O(1)表示插入和删除，O(非常小的n)用于查找。

Answer 3

我会用一个双重链接的列表。当处理几十个或数百个项目时，搜索速度并不比数组慢，而且它的优点是只占用它绝对需要的空间。添加和删除元素非常简单，并且只会带来很少的额外开销。

树结构搜索速度更快，但添加或删除元素时开销更大。也就是说，在处理几十个或数百个项目时，差异可能并不显著。如果我是您，我将构建每个实现，并查看哪一个在实际使用中更快。