c - 通过重复存储单词的最佳树型

Question

我需要在 c 中实现一个数据结构来按顺序重复存储单词(一个包含单词和重复次数的结构)，其中单词的重复可以递增或递减。

我需要找到改变它们重复次数的单词，并将其移动到适当的位置(可以有更多重复次数相同的单词)。

我想不出什么是最好的数据结构。我在树上思考，但我需要能够通过重复来改变单词的位置。那么这种问题有树吗？我什么也找不到。

关于如何有效地执行此操作的任何建议或想法？

如有任何帮助，我将不胜感激。谢谢。

Answer 1

我的建议是根本不要使用树。相反，请使用您保持排序的排序数组。保持排序很简单:每当你递增/递减一个重复计数时，你只需要在正确的位置重新插入该元素，这只需要与你需要移动字符串的地方一样多的操作(与在插入排序中)。为了增加计数，这与

//pos is the index of the string within the array
struct node temp = array[pos];
for(; pos + 1 < stringCount && temp.repCount > array[pos + 1].repCount; pos++) {
    array[pos] = array[pos + 1];
}
array[pos] = temp;

只要预期的位置调整平均较小，这可能比任何基于树的方法都快:它避免构建/维护需要大量代码且对缓存不友好的树结构。上面的循环只接触连续的内存，因此尽可能地对缓存友好。