关于数据结构的建议
我一直在努力寻找符合以下要求的合适的数据结构：
- 这种数据结构的元素被组织成块。这些块的顺序有点不相关，但是块中的元素保持一定的顺序。
- 插入次数不多。
- 搜索的频率要高得多。
- 检索数据结构中元素的索引至关重要。
- 一旦搜索了数据结构的元素，数据结构中的下一个或前一个元素应该是容易访问的。
考虑到这一点，我有以下考虑：
- 链接列表或双链接列表对于需求1、2、4和5可能是最优的，但强制进行线性搜索，这会折衷req。3.
- 哈希表解决了req问题。但据我所知，这在req方面是个问题。5因为在使用散列时，会失去对数据结构中元素的位置的控制。
开发一个与我需要的顺序相匹配的散列函数可能很棘手，因为输入键可以是部分随机的。
我正在考虑的一个可能的解决方案(在C中)是保留一个指向保持插入顺序(或我需要的顺序)的元素的指针数组，然后是第二个指针数组，它使用哈希函数对元素进行排序。第一个数组可用于快速访问元素和查找邻居，而第二个数组可用于快速搜索元素。但不知何故，我给人的印象是，事情过于复杂，我不想重新发明轮子。
你认为如何？任何建议都将不胜感激。
非常感谢
回答 3
Stack Overflow用户
发布于 2018-11-13 14:27:01
在这种情况下，数组可能是最好的数据结构。
插入数组需要搜索新元素的正确插槽，然后使用memmove将所有较大的元素向右移动。如果插入频繁，这可能会很昂贵，但如果不像您所说的那样频繁，那么它就不会是一个问题。然后通过索引和O(1)搜索进行O(log n)检索。
维护指向实际数据的指针数组是一个很好的步骤，因为这意味着在插入新元素时只复制指针而不是完整的数据结构。
因此，您有一个数组，该数组包含仅附加到的数据，以及用于每个插入的指针数组(即找到正确的位置和移位)。
Stack Overflow用户
发布于 2018-11-13 14:12:57
搜索树呢？这是一个很好的适合您的所有要求，除了4。
为了处理这个要求，您可以为每个节点维护一个额外的计数器。此计数器将记录节点下方子树中的节点数。
添加计数器将允许在执行搜索操作时查找目标节点的索引(有关示例如何，请参见here )。这将使插入操作更加复杂，因为插入节点之后，您还需要更新所有祖先树中的计数器，但是既然您说不会有很多插入，就不会有问题。
Stack Overflow用户
发布于 2018-11-13 14:32:49
可能是一个“链式哈希表”，其中哈希表中的每个索引都是一个双链接列表。在您的示例中，我想每个“块”都将由这样一个双链接列表来表示。
这样可以快速搜索块，但对块中的单个元素的搜索相对较慢。块内的项数很重要。但是，您将立即得到下一个/上一个项目，并且从那里遍历列表也会很快。链接列表也可以实现为数组，这比单个节点的堆分配对数据缓存内存更友好。
或者，您也可以使用类似的哈希表，但是对每个索引使用二进制搜索树。你会得到快速的搜索，它将与大量的数据很好地扩展。在检索下一个/上一个项目时，它会稍微慢一些，因为您必须检查是否存在左/右叶，否则检查父节点。
https://stackoverflow.com/questions/53282597
复制相似问题
腾讯云开发者
