1.5.为什么要学习数据结构和抽象数据类型
Last updated
Last updated
为了管理问题的复杂性和解决问题的过程,计算机科学家使用抽象使他们能够专注于 “大局” 而不会迷失在细节中。通过创建问题域的模型,我们能够利用更好和更有效的问题解决过程。这些模型允许我们以更加一致的方式描述我们的算法将要处理的数据。
之前,我们将过程抽象称为隐藏特定函数的细节的过程,以允许用户或客户端在高层查看它。我们现在将注意力转向类似的思想,即数据抽象的思想。抽象数据类型
(有时缩写为 ADT )是对我们如何查看数据和允许的操作的逻辑描述,而不用考虑如何实现它们。这意味着我们只关心数据表示什么,而不关心它最终将如何构造。通过提供这种级别的抽象,我们围绕数据创建一个封装。通过封装实现细节,我们将它们从用户的视图中隐藏。这称为信息隐藏。
Figure 2 展示了抽象数据类型是什么以及如何操作。用户与接口交互,使用抽象数据类型指定的操作。抽象数据类型是用户与之交互的 shell。实现隐藏在更深的底层。用户不关心实现的细节。
Figure 2
抽象数据类型(通常称为数据结构)的实现将要求我们使用一些程序构建和原始数据类型的集合来提供数据的物理视图。 正如我们前面讨论的,这两个视角的分离将允许我们将问题定义复杂的数据模型,而不给出关于模型如何实际构建的细节。 这提供了独立于实现的数据视图。由于通常有许多不同的方法来实现抽象数据类型,所以这种实现独立性允许程序员在不改变数据的用户与其交互的方式的情况下切换实现的细节。 用户可以继续专注于解决问题的过程。