c++ - 您可以使用什么数据结构来动态存储元素并有效地访问它们？

Question

你可以使用什么数据结构来动态存储元素并高效地访问它们？这是一道面试题。我应该回答 std::list (我的意思是在 C++ 中)吗？还是其他人？

作为后续问题，在最坏情况下，在链表中查找任意元素的复杂度是多少？

谢谢大家的意见。

Answer 1

这个问题很模糊。我们拥有多个数据结构的全部原因是它们都比其他结构或多或少地支持不同的访问模式。例如:

• 如果所有访问都从列表的开头向前，则链表是一个不错的选择。
• 如果访问是随机的并且插入/删除是在末尾，那么动态数组是一个不错的选择。
• 如果访问始终是 FIFO，则堆栈是一个不错的选择。
• 如果访问总是后进先出，队列是一个不错的选择。
• 如果访问总是在末尾，双端队列是一个不错的选择。
• 如果访问始终是最小的元素，则优先级队列是一个不错的选择。
• 如果访问是完全随机的并且不需要排序，那么哈希表就很好。
• 如果访问是完全随机的并且需要排序，则平衡二叉搜索树是好的。
• 如果存储的元素是字符串或其他数字元素，那么 trie 就很好。
• 如果元素是空间中的点并且您希望支持范围查询或最近邻搜索，则 kd 树很好。
• 如果您想知道元素如何相互连接， union 查找结构是个不错的选择。
• 如果值是整数、访问是随机的并且您希望它们是有序的，则 van Emde Boas 树是好的。
• 如果您想将元素存储为几何结构并想要访问特定面附近的点和边(反之亦然)，则四边形非常适合
• 等等

这个问题有无数好的答案，具体取决于您尝试对数据执行的操作。这个列表只是现有数据结构的一小部分，根据具体情况，所有这些都可能是正确的答案。根据具体情况，它们也可能都是错误答案。请记住 - 选择数据结构时，确保您知道要解决的问题!

关于你的第二个问题:在最坏的情况下，在链表中找到一个元素可能需要 O(n) 的时间。当您要搜索的元素不在链表中或接近末尾时，就会发生这种情况。在这种情况下，您需要一次扫描整个链表一个元素，然后才能断定所讨论的元素是否包含在列表中。

希望这对您有所帮助!