数据结构和算法之间的关系是什么？

Question

我一直在寻找一门关于数据结构的好的在线课程，但我发现Google还会返回算法课程的结果，比如：

在本课程中，您将学习算法设计的几个基本原则:分而治之的方法、图算法、实际的数据结构(堆、哈希表、搜索树)、随机算法等等。[来源]

和

在本课程结束时，您将了解为图和其他重要数据结构设计新算法所需的关键概念，并评估这些算法的效率。[来源]

和

本课程介绍计算问题的数学建模。它涵盖了用于解决这些问题的常用算法、算法范例和数据结构。[来源]

我的问题是:算法和数据结构是紧密相连的，这意味着它们必须被理解在一起，还是一个主题比另一个主题更基础？

编辑:对于那些投票结束这个问题的人，你能告诉我为什么或者如何改进这个问题吗？学习提出正确的问题是教育过程的一部分。

Answer 1

各种混合物确实存在。您有数据结构，它们与算法、算法没有关联，它们不需要(真实的)数据结构，但是这两者通常都是在一个包中出现的。

编辑:正如@Doval正确指出的那样，数据结构本身没有任何与它们相关的操作。将数据结构和算法相结合形成抽象的数据类型。

没有算法的

数据结构

例如，考虑一个用于存储二维坐标的数据结构，恰当地称为Point。对于一个点，在算法方面没有什么可做的，它实际上只是一个x和y值的容器。当然，给出这个数据结构，您现在可以在上面添加各种算法(距离计算，凸壳，什么的)。

您可以想到很多数据结构，它们只是单个数据的积累。虽然这些在实践中确实经常发生，但它们并不是很好的教材，因为一旦您了解到单个数据项可以累积到一个新的数据结构中，就没有什么可学到的了(就像在上面的Point示例之后，如果我为您提供了一个很棒的数据结构Point3D，它可以为三维空间做同样的事情)？

没有(实)数据结构的

算法

"Real"，因为很明显，每个有趣的算法都需要原始数据类型，比如整数或布尔值，我们不想在这种情况下将它们作为数据结构来考虑。与上面类似，这些算法通常都相当简单。特别是，它们不具有任何类型的复杂状态，因为这通常会进入数据结构(请参阅下一节)。

这种算法的一个例子是计算两个数的最大公因子。尤克利德的gcd算法实际上只需要持有两个整数并对它们进行操作。

一旦事情变得更加有趣，您很快就进入了抽象数据类型的世界。例如，Eratosthenes的筛子是基于数组的。我们现在可以讨论数组是否仍然是原始的，或者实际上，您可以讨论一个整数是否已经是一个数据结构。无论哪种方式，完全没有数据结构的算法都是相当枯燥的，即使你接受它们的孤立存在。

算法与数据结构相结合，也称抽象数据类型

这些都是有趣的原因，但有两个非常不同的原因。通常，您可以从两个方向来处理这些问题:数据结构优先，或算法优先。

虽然抽象数据类型是通过数据结构+算法/操作的组合来定义的，但是我们经常将它们集中在其中的一种，并将另一种视为使能器。

数据结构，然后是算法

您将遇到抽象数据类型，这些数据类型使用起来相当简单，但涉及到或多或少复杂的算法，以使它们在内部工作。例如，使用HashMap很简单，但涉及到一个漂亮的散列函数和处理内部的哈希冲突。然而，从你作为一个用户的角度来看，你把它看作是为你保存数据的东西，而不是为你做一些事情的东西。

与下面的最后一组不同，这些数据结构不向用户公开这些算法。您不需要知道，也不需要关心一个HashMaps内部哈希函数才能使用它。(然而，要有效地使用它，您可能想知道这些事情;)

算法，然后是数据结构

另一个方向意味着您有一个算法，您希望它能够简单地使用，但它需要内部的数据结构来使它按预期工作。一个例子是二进制空间分区(BSP)算法，您可以简单地从一组距离给定的查询点最近的点请求二维Point。但是，您需要内部的树结构(甚至是其他的算法，比如距离计算)来编写算法。

一般来说，可以说这个组中的算法使用涉及到的数据结构作为内部状态表示。我认为，这组算法是最多样的，你会发现很多不同的算法符合这个总体方案。关于观点，我们认为这些是有趣的，因为它们做了一些事情(f.ex )。为我们排序)，而不太关心数据持有部分。

密切相关的数据结构和算法

最后，您有数据结构，它们与直接对应它们的算法非常密切相关。一个典型的例子是二叉树，当你想要用它做任何有意义的事情时，它会强迫你来讨论树走算法的主题(深度优先，宽度优先，随便什么)。

对于这些情况，我们经常会改变我们对结果抽象数据类型的看法的焦点。有时候你关心你的树的结构，几分钟后你会关心能够在它上运行一个查找操作，然后你会想要删除一个节点，然后马上考虑这个结构之后的样子。尽管上述其他部分也是如此，但这并不是您心目中的主要关注点，例如，当您将数据存储/检索到Map或对链接列表进行排序时。

Answer 2

数据结构常常会影响算法的细节。正因为如此，这两个人经常携手并进。

例如，考虑一种修剪草坪的算法。你如何修剪你的草坪很可能会受到你的草坪的实际结构的影响。如果你住在郊区人口稠密的小房子里，而你的草坪只是一个面积几米的小长方形，你可能更喜欢用推割草机而不是拖拉机/骑割草机割草。如果你的草坪涉及许多英亩平坦的草甸土地，你可能更喜欢骑割草机，而不是推式割草机(尽管这两台割草机最终都可能完成这项工作)。如果你的草坪涉及大片平坦的土地，但有几座小山和一些树木，你可能会开发出一种更有趣的算法来切割草坪，其中包括一台骑行割草机和一台推割草机，或者其他一些割草技术。

不过，最终，数据的结构可能会对您决定如何开发算法(或使用哪种算法)产生重大影响。由于这个原因，这两个主题往往是并驾齐驱的。

反之亦然:有时，我们希望使用的算法(至少在计算开始时)会影响您为支持该算法而开发的数据结构。例如，从数组列表到链接列表的概念，并最终进入BST存储有序列表，这将允许快速查找。