logo标签列表

哪些数据结构是最有用的并值得深入了解的？

data-structures
14

我对了解人们认为在编程中最有用的数据结构感兴趣。你经常使用哪种数据结构?

回答此帖应该帮助有兴趣找到适用于其问题的有用数据结构的新程序员。回答应该包括数据结构，相关信息或链接，它所使用的情况以及为什么它是解决这个问题的好选择（例如，理想的计算复杂度，简单性和理解等）。

每个答案只应涉及一个数据结构。

感谢任何人能够分享的智慧和经验。

15个回答
24

在编程中，我最常使用的数据结构之一（除了向量）就是哈希表。 如果你需要能够在O(1)时间内搜索大量数据，那么哈希表几乎是唯一的选择，这意味着搜索时间不会随着集合大小的增长而增加。

问题在于，插入和删除的时间比其他数据结构要长，并且你需要有某种键来搜索集合。每个元素都必须有一个键。 算法会获取每个元素的键并计算出一个哈希码，该哈希码指示在哈希表中搜索的槽位。 然后，根据实现方式，它要么遍历落在该桶上的项目列表以找到你的项目，要么搜索附近的桶。 哈希表的大小对哈希的效率起决定性作用，而哈希码之间的碰撞数量会对其产生相当大的影响。

当你需要一个映射，并且预期的映射元素数量超过10个时，请使用哈希表。由于需要大量未使用的槽位才能提高效率，所以它比其他结构占用更多内存。

C#中有一个很好的实现，使用Dictionary<keytype, valuetype>，甚至还有一个HybridDictionary，它会在内部决定何时使用哈希表或向量。 任何一本好的编程书都会描述它，但你也可以通过维基百科得到很好的服务： http://en.wikipedia.org/wiki/Hashtable

5
我需要忽略您关于每篇文章一个数据结构的要求 - 这些是我使用最多的，而且我发现大多数程序都需要其中一个或它们的组合。 数组 - 最基本的并提供最快的访问。 向量 是普通数组的改进，是目前常用的替代品。 双端队列 是这一主题的另一种变化，同样提供常数时间/随机访问，但优化了在开头和结尾进行快速插入和删除。 链表 - 用于维护经常删除和插入的数据列表非常有用，但迭代/搜索非常缓慢。例如内存页面中的空闲/已用列表。 树 - 基本结构，是更复杂结构的基础。这种结构有许多形式。当树保持排序时，提供logn搜索时间。对于像字典这样的大型数据项非常有用。二叉/AVL和红黑树是最常见的。 映射和哈希 - 不完全是数据结构，而是使用聪明的逻辑和上述数据结构的组合实现的复杂快速查找算法。
这些数据结构及其实现可在C ++的STL库中获得。其他语言也有其本地实现。一旦您了解这些基本数据结构及其几个变体（队列，堆栈，优先级队列）以及搜索算法的一些内容，我认为基础知识就已经覆盖了。
2
链表的优点在于它们非常便宜地添加/删除节点。与数组不同[...]，它们在扩展时不需要重新分配更多内存。
如果您有一个数组，并且每次填充它时都将分配大小加倍，那么您将具有平摊O（1）的附加项。此外，由于缓存效应（除非您将链接分配给大块并且不会太多地处理它们），循环遍历所有数组元素可能比循环遍历链表要快（在墙时间上）。
另外，数组更小：您可以节省每个元素的字开销，以及每个分配的开销（这可能至少是两个字：一个用于大小，一个用于下一个空闲列表指针）。
2

我经常使用关联数组，基本上就是以字符串为索引的数组。

1
关联数组更多是一种抽象数据类型，其中哈希表是其可能的一种实现。 - Miles
1

链表/双向链表/其他变体

每个人都应该知道链表的优缺点，但由于完全不使用，似乎很多人忘记了它。

链表的优点是添加/删除节点非常便宜。与使用数组或数据结构的数组核心不同，它们在扩展时不需要重新分配更多内存。

缺点是它们对搜索的性能非常差。在数组中是O(1)查找，在链表中为O(n)。

像所有结构一样，链表只在特定条件下才是理想的。但在正确的时间使用它们，它们非常强大。

1
你的意思是指随机访问吗？ - Corey
它们还需要2-3倍于数组支持列表的内存，并且在添加/删除方面的速度优势只有在节点数量巨大（100,000+）时才微不足道... 但它们具有非常可预测的增长模式，因此在内存较小的情况下很有用。 - kdgregory
1

我喜欢二叉树。尤其是Splay-Tree变种。它与自平衡二叉树有些相似，但也适应了应用程序的使用模式。你几乎不会遇到最坏情况的O(n)行为。

一个好处是它们比其他自平衡二叉树更容易编写，需要的代码也更少。这是我最喜欢的数据结构之一，因为它在实践中表现出色。

http://en.wikipedia.org/wiki/Splay_tree

“几乎从不”是指“不超过log（n）/ n的时间”吗？;-p - Steve Jessop
这取决于使用模式。迄今为止，我还没有对此进行O分析，因为在实践中从未发生过。 - Nils Pipenbrinck
1

我发现自己经常使用数组与“foreach”控制结构相结合来循环遍历项目。过去，我使用带有数字索引的数组和“for(i=1;i<n;i++)”。我发现使用“foreach”循环遍历数组而不是显式数字索引提供了更通用和可读的解决方案。

1

图形是一个非常强大而被忽视的数据结构。

很多问题都可以通过构建描述问题的图形，然后在图形上使用众所周知的算法来解决。一些例子包括自然语言处理（连接节点的边权可以表示一个单词跟随另一个单词的可能性），视频游戏（使用图形确定AI角色的最短路径）以及网络拓扑。

我从算法设计手册中了解到了图形，这是由Steve Yegge在博客文章中推荐的。

0
这有点像问木匠工具箱里哪些工具最好学习使用。每个工具都适用于不同类型的工作，你需要平等地学习基本工具（如地图、列表、袋子和集合等）。
嗯...什么是“bag”？！！ - ljs
我认为一个包就像一个集合，但是你可以有多个具有相同值的条目。 - Scottm
从Commons Collections：“[一个bag]定义了一个集合，该集合计算对象在集合中出现的次数。” http://commons.apache.org/collections/api-release/org/apache/commons/collections/Bag.html - skaffman
0

我认为没有一种数据结构是必须要了解的。每种数据结构都有其自身的特性，因此适用于特定的问题。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接