算法(4th ed)(82):基础——数据抽象 4.2.2

阅读数:11 2019 年 11 月 2 日 12:08

算法(4th ed)(82):基础——数据抽象 4.2.2

(抽象数据类型举例:信息处理)

无论是需要处理数百万信用卡交易的银行,还是需要处理数十亿点击的网络分析公司,或是需要处理数百万实验观察结果的科学研究小组,无数应用的核心都是组织和处理信息。抽象数据类型是组织信息的一种自然方式。虽然没有给出细节,表 1.2.6 中的两份 API 也展示了商业应用程序中的一种典型做法。这里的主要思想是定义和真实世界中的物体相对应的对象。一个日期就是一个日、月和年的集合,一笔交易就是一个客户、日期和金额的集合。这只是两个例子,我们也可以为客户、时间、地点、商品、服务和其他任何东西定义对象以保存相关的信息。每种数据类型都包含能够创建对象的构造函数和用于访问其中数据的方法。为了简化用例的代码,我们为每个类型都提供了两个构造函数,一个接受适当类型的数据,另一个则能够解析字符串中的数据(细节请见练习 1.2.19)。和以前一样,用例并不需要知道数据的表示方法。用这种方式组织数据最常见的理由是将一个对象和它相关的数据变成一个整体:我们可以维护一个Transaction 对象的数组,将 Date 值作为参数或是某个方法的返回值等。这些数据类型的重点在于封装数据,同时它们也可以确保用例的代码不依赖于数据的表示方法。我们不会深究这种组织信息的方式,需要注意的只是这种做法,以及实现继承的方法toString()compareTo()equals()hashCode() 可以使我们的算法处理任意类型的数据。我们会在 1.2.5.4 节中详细讨论继承的方法。例如,我们已经注意到,根据 Java 的习惯,在数据结构中包含一个 toString() 的实现可以帮助用例打印出由对象中的值组成的一个字符串。我们会在 1.3 节、2.5 节、3.4 节和 3.5 节中用 Date 类和 Transaction 类作为例子考察其他继承的方法所对应的习惯用法。1.3 节给出了有关数据类型和 Java 语言的类型参数(泛型)机制的几个经典例子,它们都遵循了这些习惯用法。第 2 章和第 3 章也都利用了泛型和继承的方法来实现可以处理任意数据类型的高效排序和查找算法。

表 1.2.6 商业应用程序中的示例 API(日期和交易)

public class   Date implements Comparable<Date>
               Date(int month, int day, int year)创建一个日期
               Date(String date)创建一个日期(解析字符串的构造函数)
          int  month()
          int  day()
          int  year()
       String  toString()对象的字符串表示
      boolean  equals(Object that)该日期和 that 是否相同
          int  compareTo(Date that)将该日期和 that 比较
          int  hashCode()散列值
public class   Transaction implements Comparable<Transaction>
               Transaction(String who, Date when, double amount)
               Transaction(String transaction)
创建一笔交易(解析字符串的构造函数)
       String  who()客户名
         Date  when()交易日期
       double  amount()交易金额
       String  toString()对象的字符串表示
      boolean  equals(Object that)该笔交易和 that 是否相同
          int  compareTo(Transaction that)将该笔交易和 that 比较
          int  hashCode()散列值

每当遇到逻辑上相关的不同类型的数据时,你都应该考虑像刚才的例子那样定义一个抽象数据类型。这么做能够帮助我们组织数据并在一般应用程序中极大地简化使用者的代码。它是我们在通向数据抽象之路上迈出的重要一步。

评论

发布