我有兴趣找出人们认为在编程中最有用的数据结构。你发现自己一直在使用什么数据结构？
这篇文章的答案应该可以帮助有兴趣为他们的问题找到有用的数据结构的新程序员。答案可能应该包括数据结构、关于它或相关链接的信息、它的使用情况以及为什么它是解决这个问题的好选择（例如理想的计算复杂性、简单性和理解等）
每个答案应该只与一个数据结构有关。
感谢人们可以分享的任何智慧和经验。
Greg Sexton
问问题
22149 次
15 回答
24
我使用最多的数据结构之一（当然，除了向量）是 Hashtable。如果您需要能够在 O(1) 时间内搜索大量数据，那么它是唯一的选择，这意味着搜索时间不会随着集合大小的增长而增长。
问题是插入和删除时间比其他数据结构中的要长，并且您需要使用某种键来搜索集合。每个元素都必须有一个键。该算法获取每个元素的密钥并计算一个哈希码，该哈希码指示哈希表中要搜索的槽。然后根据实现，它要么遵循落在该存储桶上的项目列表来查找您的项目，要么搜索附近的存储桶。哈希表的大小决定了哈希的效率，而哈希的效率很大程度上受到键之间哈希码冲突数量的影响。
每当您需要映射并且映射的预期元素数量超过大约 10 时使用它。它比其他结构更占用内存，因为它需要在表中使用大量未使用的插槽才能提高效率。
C# 有一个很好的实现，Dictionary<keytype, valuetype>甚至有一个 HybridDictionary，它在内部决定何时使用哈希表或向量。任何好的编程书籍都会描述它，但维基百科会很好地为您服务：
http ://en.wikipedia.org/wiki/Hashtable
于 2008-09-28T15:05:28.460 回答
5
我将不得不忽略您对每个帖子一个数据结构的要求 - 这些是我使用最多的那些，我发现大多数程序大多需要其中一个或组合。
数组- 最基本的并提供最快的访问。向量是对普通旧数组的即兴创作，是当今常用的事实上的替代品。 dequeue是这个主题的另一个变体，它再次提供恒定时间/随机访问，但针对开始和结束的快速插入和删除进行了优化。
链接列表- 对于维护频繁删除和插入但迭代/搜索非常慢的数据列表非常有用。例如内存页面内的空闲/使用列表
树- 形成更复杂结构的基础的基本结构。这种结构有多种形式。当树保持排序时提供登录搜索时间。对于字典等大数据项很有用。二叉树/AVL 和红黑树是最常见的。
映射和散列- 不完全是数据结构，而是使用巧妙的逻辑和上述数据结构的组合实现的复杂快速查找算法。
这些数据结构及其实现在 C++ 的 STL 库中可用。其他语言也有它们的本地实现。一旦您了解了这些基本数据结构和它们的一些变体（队列、堆栈、优先队列）以及有关搜索算法的一些知识，我会说基础知识将得到很好的涵盖。
于 2008-09-28T17:29:21.517 回答
2
我发现自己经常使用关联数组，基本上是以字符串为索引的数组。
于 2008-09-28T13:47:07.823 回答
2
链表的优点是添加/删除节点非常便宜。与数组 [...] 不同，它们在扩展时不需要重新分配更多内存。
如果您有一个数组并且每次填充它时都将分配大小加倍，那么您将摊销 O(1) 附加。此外，由于缓存效果，循环遍历数组的所有元素可能比循环遍历链表更快（在墙上时间）（除非您将链接分配为大块并且不要过多地弄乱它们）。
此外，数组更小：您节省了每个元素的字开销，加上每个分配的开销（可能至少有两个字：一个用于大小，一个用于下一个空闲列表指针）。
于 2009-02-01T12:40:54.383 回答
1
链表/双向链表/其他变体
每个人都应该知道链表的优缺点，而且由于完全缺乏使用，它似乎是很多人似乎忘记的东西。
链表的优点是添加/删除节点非常便宜。与在核心使用数组的数组或数据结构不同，它们不需要在扩展时重新分配更多内存。
缺点是它们在搜索方面表现不佳。对于链表，数组中的 O(1) 查找是 O(n)。
像所有结构一样，链表仅在某些条件下才是理想的。但是在正确的时间使用，它们非常强大。
于 2008-09-28T13:47:47.213 回答
1
我喜欢二叉树。特别是 Splay-Tree 变体。它有点类似于自平衡二叉树，但也适应应用程序的使用模式。您几乎从未遇到过最坏情况的 O(n) 行为。
一个很好的好处是它们也比其他自平衡二叉树更容易编写并且需要更少的代码。这是我最喜欢的数据结构之一，因为它在实践中表现得非常好。
于 2008-09-28T14:38:06.250 回答
1
我发现自己经常将数组与“foreach”控制结构结合使用来遍历项目。过去，我使用带有数字索引和“for(i=1;i<n;i++)”的数组。我发现使用“foreach”而不是显式数字索引循环遍历数组提供了更通用和可读的解决方案。
于 2008-09-28T15:35:37.110 回答
1
图是一种非常强大的被忽视的数据结构。
很多问题可以通过构建一个图来建模你的问题，然后在图上使用一个众所周知的算法来解决。一些示例自然语言处理（连接节点的边权重可以表示一个单词跟随另一个单词的可能性）视频游戏（使用图表来确定 AI 字符的最短路径）和网络拓扑。
我从Steve Yegge 在一篇博文中推荐的The Algorithm Design Manual中了解了图表。
于 2009-02-18T03:24:09.720 回答
0
这有点像询问木匠工具箱中的哪些工具最适合学习使用。它们中的每一个都适合某种类型的工作，你需要平等地学习基本的（地图、列表、包、套装等）。
于 2008-09-28T13:40:53.673 回答
0
我不认为必须知道一种数据结构。每个数据结构都有自己的属性，因此适用于特定问题。
于 2008-09-28T13:41:08.007 回答
0
我一直发现堆栈有无数种用途，尽管在面向对象编程中使用较少。确实，所有数据结构都有其用途，而且它们并不复杂。尽你所能学习。
于 2008-09-28T14:05:53.423 回答
0
我不认为这里有一个普遍的答案。它应该受限于某些用例。例如，在我 10 多年的程序员/经理职业生涯中，我从未使用过二叉树。我怀疑这是否意味着二叉树没有用，但在内核和嵌入式世界中，链表可能更适合。
实际上，当我考虑删除一些异常时，我只使用了简单的链表。
然后即使在嵌入式中，它也可能不是我生活在低级硬件协议世界中唯一使用的结构，可能“上山”使用更多的数据结构......
于 2008-09-28T14:08:02.140 回答
0
对于基本的了解，您应该了解一些抽象数据类型（集合、字典、有序列表、队列、堆栈等）以及实现每种数据类型及其相关权衡的几种方法。
这可能需要您了解数组、链表（单链和双链）、哈希表、二叉搜索树（对简单的平衡启发法有一些了解）和二叉堆。从里到外了解这些，您将在理解更复杂和有趣的数据结构方面走得很远。另外，如果您已经实现了所有这些，您将拥有一个现成的库，您可以理解它用于编程项目（尽管显然更多像 Boost 或其他更适合生产代码的久经沙场的库）。
这提供了一个非常有用的数据结构词汇表，这可能会对您编写程序的方式产生重大影响。您可能会发现您一直在解决队列的许多部分实现的问题，例如，您现在可以将其替换为规范实现。
于 2008-09-28T14:51:33.423 回答
-1
这个帖子太模糊了。有无数的数据结构：数组、字典等。每种数据结构都可以用来解决不同的问题。
针对特定问题要求 DS 会更有成效。
于 2008-09-28T13:40:35.217 回答
-3
快速排序
合并排序
冒泡排序
这些真的很好学习和理解它们是如何工作的。排序很有趣，可以应用于许多领域:)
于 2009-02-01T12:50:30.867 回答