从内到外了解哪些最有用的数据结构？

我很想知道在编程中人们会认为最有用的数据结构.您发现自己一直使用哪种数据结构？

这篇文章的答案应该有助于新的程序员有兴趣为他们的问题找到有用的数据结构.答案应该包括数据结构,有关它的信息或相关链接,它正在使用的情况以及为什么它是这个问题的好选择(例如理想的计算复杂性,简单性和理解等)

每个答案应仅限于一个数据结构.

感谢任何人们可以分享的智慧和经验珍珠.

我最常使用的数据结构之一(当然除了向量)是Hashtable.如果您需要能够在O(1)时间内搜索大量数据,那么它就是唯一的选择,这意味着搜索时间不会随着集合规模的增长而增长.

问题是插入和删除时间比其他数据结构大,并且您需要使用某种键来搜索集合.每个元素都必须有一个键.该算法获取每个元素的密钥并计算散列码,该散列码指示要在其中搜索的散列表中的槽.然后,根据实施情况,它可以跟随一个项目列表,这些项目落在该存储桶上以查找您的项目,或者搜索附近的存储桶.hastable的大小决定了哈希的效率,哈希受到密钥之间哈希码冲突的影响.

在需要地图时使用它,并且地图的预期元素数量超过10个.它比其他结构更加节省内存,因为它需要表中大量未使用的插槽才能高效.

C#有很好的实现,Dictionary甚至还有一个HybridDictionary,可以在内部决定何时使用哈希表或向量.任何好的编程书都会描述它,但维基百科将为您提供良好的服务:http: //en.wikipedia.org/wiki/Hashtable

我将不必理会您对每个帖子一个数据结构的要求-这些是我使用最多的程序，我发现大多数程序在这些程序或组合程序中大多都需要一个。

数组 -最基本，提供最快的访问。向量是在简单的旧阵列上的即兴创作，并且是近来常用的事实替代品。 出队是此主题的另一种变体，再次提供了恒定的时间/随机访问，但针对在开始和结束时的快速插入和删除进行了优化。

链接列表 -维护经常删除和插入的数据列表非常有用，但是迭代/搜索非常慢。例如，内存页面中的空闲/已用列表

树木 -构成更复杂结构基础的基本结构。这种结构有很多形式。提供对树进行排序时的登录搜索时间。对字典等大型数据项很有用。二进制/ AVL和红黑树是最常见的。

映射和哈希 -并非完全是数据结构，而是结合了巧妙的逻辑和上述数据结构实现的复杂快速查找算法。

这些数据结构及其实现在C ++中的STL库中可用。其他语言也有其本机实现。一旦您知道了这些基本数据结构及其一些变量（队列，堆栈，优先级队列）以及有关搜索算法的知识，我就会说基本知识将被很好地介绍。