c - 动态扩展数组C

Question

我有一个程序可以计算文本文件中单词的出现次数并将它们存储在数组中。到目前为止，我使用的是固定数组，一切正常，但现在我想将其更改为动态数组，这样就不会浪费/需要任何内存。我知道必须使用 malloc 和 realloc 来完成此操作，但我不太明白如何去做。

我的第一个想法是简单地计算文本文件中的单词，然后为所有单词分配足够的空间，但这会留下浪费的空间，因为重复的单词将增加计数器，但不会再次添加到数组中。

这种方法听起来是否有意义并且是实现这一目标的最佳方法？如果我首先 malloc 一个小数组，足以找到一个单词及其计数器。然后，每次我找到一个需要添加到数组中的新单词时，只需重新分配足够的空间以容纳另一个单词并计数器。如果它是重复的，则不需要重新分配，因为现有计数器只会递增。

Answer 1

通常最好不要以 100% 的内存利用率为目标(就交易速度与内存使用而言)；特别是如果您的程序仅运行有限的时间，总体而言，使用比所需多一点的内存实际上并不会“花费”太多。

一种典型的方法是使动态数组具有初始大小，例如 8 或 128 或其他值，然后在填满时将其加倍。

与在填满时将大小增加 1 相比，这减少了重新分配的次数(成本高昂)。当然，这会浪费一些内存。