MIT_6.031之抽象数据类型（Abstract Data Type, ADT）

1. 抽象数据类型的定义

抽象数据类型（ADT）是指一种数据结构，其主要特征在于对数据的操作和行为的定义，而不关注数据的具体实现方式。这种分离使得客户端在使用数据结构时不必了解其内部表示。

关键点：

数据结构与操作：数据结构的使用方式与其特定形式是分开的。
内部表示的隐私：ADT通过隐藏内部实现，避免客户端对类型的内部表示形式进行假设。

2. 抽象的意义

抽象使得我们可以用更简单的高级概念来处理复杂问题，忽略底层细节。

主要概念：

规范：提供操作的前提条件和后置条件，让客户理解如何使用而不需关心内部实现。
模块化：将系统分解为独立的组件，使每个模块可以单独设计、实现、测试和重用。

3. 抽象数据类型的特点

操作定义：抽象类型的核心在于可以对其执行的操作，而非具体的存储方式。
不透明性：抽象类型的值是不透明的，客户端不需要关心内部实现细节，只需了解操作。

示例：

数字类型可以执行加法和乘法。
字符串可以连接和提取子串。

4. 抽象类型的操作

抽象类型的操作可以分类为以下四种：

操作类别	描述	示例
Creators	创建该类型的新对象。	`new ArrayList<>()`
Producers	从旧对象创建新对象。	`String.concat(String s)`
Observers	获取对象并返回不同类型的对象。	`List.size()`
Mutators	改变对象。	`List.add(T element)`

1. Creators（创建者）

描述: 创建该类型的新对象。创建者通常是构造函数或工厂方法，用于初始化新实例。

表示形式: $ t^* T $ 其中，$ t^* $表示接受0个或多个其他类型的参数，$ T $表示返回的抽象类型。

示例:

new ArrayList<>(): 创建一个新的空ArrayList。
String.valueOf(int i): 将整数i转换为String类型。

2. Producers（生产者）

描述: 从已有的对象创建新对象。生产者的作用是基于现有对象生成新的对象，通常会返回与输入对象相关的新实例。

表示形式: $ T^+, t^* T $ 其中，$ T^+ $表示至少一个本类型对象，$ t^* $表示0个或多个其他类型对象，返回一个新创建的抽象类型$ T $。

示例:

String.concat(String s): 接受另一个字符串并返回与之拼接的新字符串。
Collections.unmodifiableList(List list): 返回一个不可修改的List，但对原List的修改仍会反映到该返回的List中。

3. Observers（观察者）

描述: 获取对象并返回不同类型的对象。观察者操作通常用于查询对象的状态或属性。

表示形式: $ T^+, t^* t $ 其中，$ T^+ $表示至少一个本类型对象，$ t^* $表示0个或多个其他类型对象，返回的类型$ t $通常是其他基本类型或对象类型。

示例:

List.size(): 返回List中的元素数量，类型为int。
String.length(): 返回字符串的长度，类型为int。
List.get(int index): 返回List中指定索引位置的元素。

4. Mutators（变异者）

描述: 改变对象的状态。变异者用于修改现有对象的内容或状态。

表示形式: $ T^+, t^* | t | T $ 其中，$ T^+ $表示至少一个本类型对象，$ t^* $表示0个或多个其他类型对象。变异者可以返回任意类型，通常返回void表示状态改变不返回结果。

示例:

List.add(T element): 向List中添加新元素，返回值为void。
List.remove(int index): 从List中移除指定索引的元素，返回被移除的元素。
Collections.sort(List list): 对List进行排序，返回值为void。

具体示例分析

1. Creators

1	ArrayList<String> list = new ArrayList<>();

这里使用new ArrayList<>()创建了一个新的ArrayList实例。

2. Producers

1 2	String str1 = "Hello"; String str2 = str1.concat(" World");

通过concat方法，str2生成了一个新的字符串"Hello World"，而不改变str1。

3. Observers

1	int size = list.size();

调用size()方法返回List中的元素数量。

4. Mutators

1 2	list.add("Hello"); list.remove(0);

add方法向List中添加元素，而remove方法则根据索引移除元素。

5. 抽象类型设计

核心思想：

设计抽象类型时，需要考虑简单、明确的操作，每个操作应具有一致的行为。

示例设计：

public class Family {
    private List<Person> people;

    public List<Person> getMembers() {
        return new ArrayList<>(people); // 返回人员列表的拷贝以保护内部状态
    }
}

表现形式、规范和实现

规范: 类名、Javadoc和公共方法的说明。
表现形式: 私有字段及对字段的假设和要求。
实现方法: 方法的具体实现。

6. 使用Java实现抽象数据类型

在Java中实现ADT通常涉及类、接口和枚举。示例包括：

抽象数据类型: String, List, ArrayList, DayOfWeek
Creators: ArrayList(), Collections.singletonList()
Observers: List.get(), Collections.max()
Producers: String.trim(), Collections.unmodifiableList()
Mutators: List.add(), Collections.copy()

7. 测试抽象数据类型

每个操作都应有相应的测试，确保操作的正确性。测试通常会使用创建者、生产者和观察者。

示例测试：

@Test 
public void testValueOfTrue() {
    MyString s = MyString.valueOf(true);
    assertEquals(4, s.length());
    assertEquals('t', s.charAt(0));
}

@Test 
public void testValueOfFalse() {
    MyString s = MyString.valueOf(false);
    assertEquals(5, s.length());
    assertEquals('f', s.charAt(0));
}