c - 使用链表并删除节点或使用数组并对字符串进行小计算以查看是否可以跳过元素是否更有效？

Question

我正在用 C 语言编写一个读取文件的程序。文件的每一行都是一个字符串，将对其进行计算。对特定字符串的计算结果可能意味着文件中后面的字符串不需要对它们进行任何计算。此外，如果字符串的反转按字母顺序出现在（当前，非反转）字符串之前，则不需要检查它。

我的问题是将每个字符串放在一个链表中并在找到不需要检查的特定字符串或使用数组并检查字符串的最后几个字符以及它是否按字母顺序之后删除每个节点会更好吗字符串中的前一个元素跳过吗？无论哪种方式，列表或数组都只需要迭代一次。

score 3 · Accepted Answer

经验法则是，如果您正在处理小对象（< 32 字节），std::vector 对于大多数常规操作来说都比链表好。

但是对于较大的对象（比如 1K 字节），通常需要考虑列表。

有一篇文章详细比较你可以查看，链接在这里

score 0 · Accepted Answer

很难理解您要做什么，但听起来您应该创建一个记录数组，每个记录都包含一个字符串和一个布尔标志，以指示是否应该处理它。

当您从文件加载数组时，您将每条记录的标志设置为 true。

您使用一个指针扫描数组一次，只处理标志仍然为真的记录中的字符串。

对于处理的每条记录，您使用第二个指针从第一个指针 + 1 扫描到数组的末尾，识别不需要处理的字符串（根据当前字符串），并将它们的标志设置为 false。

-阿尔。

score 0 · Accepted Answer

如果没有关于您的需求的更多详细信息，很难告诉您哪一个更适合您的要求。

数组很容易访问，特别是如果您打算以非顺序方式进行操作，但是如果您需要对其执行删除操作或者如果您对最终元素数量没有很好的近似值，则它们很难维护.

如果您打算按顺序访问列表，列表很好，但如果您需要在其元素之间跳转，则很糟糕。如果您已经在要删除的节点中，也可以在恒定时间内完成对它们的删除。

我不太明白你打算如何访问它们，因为你说任何一个都只会迭代一次，但如果是这种情况，那么任何一个结构都会给你类似的性能，因为你没有真正利用它们的主要好处.

3 回答 3