HIT软件构造：ADT学习笔记

最近正在学软构的第六章ADT，老师一直在强调ADT很重要，需要我们认真地去学习和对待

既然这么重要，这篇就记录一下ADT的学习吧

什么是ADT？

（百度百科）抽象数据类型（Abstract Data Type，ADT）是计算机科学中具有类似行为的特定类别的数据结构的数学模型；或者具有类似语义的一种或多种程序设计语言的数据类型。抽象数据类型是间接定义的，通过其上的可执行的 *** 作以及这些 *** 作的效果的数学约束（与可能的代价）。

我的理解：抽象数据类型，首先是数据类型。接触这个概念是在大一学习C语言的时候，数据类型像整型、浮点型、字符型……这些都是基本数据类型，可以说1、2、3就是整型的数据，5.498就是浮点型的数据。而抽象数据类型就是一种自定义的不那么容易可以直接说出他的对象的数据类型，就像整型可以加减一样，抽象数据类型也可以有对象之间的和自己本身的 *** 作，比如堆栈（stack）可以推入push，d出pop 。而之所以说他抽象，是因为相对于传统数据类型关注数据的具体表示之外，抽象数据类型强调“作用于数据上的 *** 作”。其实抽象数据类型的实体并不存在，或者说可以随时被改变，他的存在只是我们想象出来这类事物中有着什么样的属性，他的对象可以执行或者被执行什么样的 *** 作。

Java中的ADT

Java 2软件开发包(SDK)提供了一些新类来支持大多数常用的ADT。这些类被称为Java集合类(类似于MFC中的集合类)，它们协同工作从而形成Java 集合架构。这个集合架构提供了一套将数据表示成所谓的集合抽象数据的接口和类。

java.util.Collection接口被用来表示任意的成组的对象，也就是元素。这个接口提供基本的诸如添加，删除，和查询这样的 *** 作。Collection接口还提供了一个iterator方法。iterator方法返回java.util.Iterator接口的一个实例。而Iterator接口又提供了hasNext, ext, 和 remove方法。使用Iterator接口提供的方法可以实现从头到尾循环遍历一个Collection对象中的实例并能够安全的删除响应的元素。

java.util.AbstractCollection 是所有集合架构类的基础。AbstractCollection 类提供了对　　java.util.Collection 接口中除iterator和size方法以外的所有方法的实现。这两个例外的方法由所有继承java.util.AbstractCollection的子类实现。

可变类型与不可变类型

Java中理解ADT，必须首先要清楚可变类型与不可变类型

可变数据类型：当该数据类型的对应变量的值发⽣了改变，那么它对应的内存地址不发⽣改变，对于这种数据类型，就称可变数据类型。
不可变数据类型： 当该数据类型的对应变量的值发⽣了改变，那么它对应的内存地址也会发⽣改变，对于这种数据类型，就称不可变数据类型。

这张图很清晰地展现了二者之间的区别，其中String类型的变量s如果想更改他的内容，就只能另外创造一个新的字符串并让s指向新的字符串。而对于StringBuilder类型的变量sb却可以更改自身的内容，不必另外开空间。

！老师讲的要记住：

mutable类型的类就是这个类的方法中存在一个或多个其功能是改变自己的内部属性。

immutable类型的类则是类中不存在可以改变自身属性的方法，所以如果需要改变就必须创建新的对象。

ADT的 *** 作方法

构造器(Creator)：构造器将某一个（某一些）与被构造数据类型不同的数据类型的对象作为参数，构造某个数据类型的具体对象。

所有事物被创造都需要一个工程，工厂生产、种植、甚至是人被孕育的过程都一样，构造器就是完成了产生这个类型的对象的工作。

这里简单区分一个叫做工厂方法和构造器的区别。

工厂方法的作用和构造器一样都是根据类自身的属性来构造这个类的对象，而不同点在于构造函数名称必须同类的名称一致。如果想创建多个构造函数，那么就只能通过形参列表的不同进行区分。因为Java不允许出现两个名称、形参列表均一样的方法，所以后两个构造函数的参数顺序不能一样。在构造对象的时候就会出现调用方法的名字相同而参数不同的情况，比较难以理解。

比如：

public class BookOrder {
    private String bookName;
    private double price; // 单价
    private int number; // 购书数量
    private double totalPrice; // 总价
    // get，set方法省略
    
    // 构造方法
    public BookOrder() {
    }
    public BookOrder(String bookName, int number, double price) {
        this.bookName = bookName;
        this.number = number;
        this.price = price;
        this.totalPrice = number * price;
    }
    public BookOrder(String bookName, double totalPrice, int number) {
        this.bookName = bookName;
        this.number = number;
        this.price = totalPrice / number;
        this.totalPrice = totalPrice;
    }
}

// 仅仅创建对象
BookOrder bookOrder1 = new BookOrder();
// 计算总价
BookOrder bookOrder2 = new BookOrder("bookName", 10, 23.50);
// 计算单价
BookOrder bookOrder3 = new BookOrder("bookName", 235, 10);

如果使用工厂方法，就可以这样来定义类：

public class BookOrder {
    private String bookName;
    private double price; // 单价
    private int number; // 购书数量
    private double totalPrice; // 总价
    // get，set方法省略
    
    // 静态工厂方法
    private BookOrder() {
        
    }
    public static BookOrder getTotalPrice(String bookName, int number, double price) {
        BookOrder bookOrder = new BookOrder();
        bookOrder.setBookName(bookName);
        bookOrder.setNumber(number);
        bookOrder.setPrice(price);
        bookOrder.setTotalPrice(bookName * price);
        return bookOrder;
    }
    public static BookOrder getUnitPrice(String bookName, int number, double totalPrice) {
        BookOrder bookOrder = new BookOrder();
        bookOrder.setBookName(bookName);
        bookOrder.setNumber(number);
        bookOrder.setTotalPrice(totalPrice);
        bookOrder.setPrice(totalPrice / number);
        return bookOrder;
    }
}

在创建对象的时候也可以相应的：

// 仅仅创建对象
BookOrder bookOrder1 = new BookOrder(); // 因为构造函数被私有化，因此创建失败
// 计算总价
BookOrder bookOrder2 = BookOrder.getTotalPrice("bookName", 10, 23.50);
// 计算单价
BookOrder bookOrder3 = BookOrder.getUnitPrice("bookName", 2350, 10);

生产器(Producer）：生产器利用某一类型的数据对象构造出该类型的新的数据对象。例如String.concat()。

个人理解构造器和生产器的区别只是传参的差异，构造器是传入不同于该类型的数据对象来建造本类型的对象，生产器传入参数的类型不加以限制。

观察器(Observer)：观察器以某一类型的数据作为被观测对象，会返回一个不同数据类型的值。例如List.size()。

产生用来反映这个对象的性质的"指标"

变值器(Mutator)：变值器改变某个对象的属性。例如List.add()。

mutable类型中的那些可以改变自身属性的方法,一般返回void。

设计一个抽象类的原则

原则一：设计的 *** 作要简洁且全面，一些复杂的功能由多个简单的功能组合完成。

原则二：设计的方法要足够多（足以满足客户的需要），并且 *** 作难度不可以太高。

表示独立性

表示独立性（Representation Independence）:具体表现为用户使用ADT时无需关心其内部实现，ADT内部变化时也不会影响到外部的规约和客户端。

我的理解：用户使用ADT的对象自身的方法来得到想要的数据，ADT具体内部的方法是如何将数据得到并返回给用户的，这个过程是可以更改的，改与不改不能影响到用户的是使用。表示独立性是一种性质，保证了ADT的内部表示和用户是区分开来的。

老师讲的例子：这个例子中ADT发生改变，people由List类改变为Set类，而反映到了客户端people.get *** 作由于本次改变而变的不可行，这就是ADT内部的变化影响到了客户端，破坏了RI。

对抽象数据类的测试方法

测试构造器、生产器和变值器：调用观察器来确认这些 *** 作的结果是否满足规约。

测试观察器：通过调用构造器、生产器和变值器，对某些数据进行修改，观察修改的结果是否符合预期。

ADT的特性

1.抽象函数（Abstraction Function）：抽象函数是表示空间到抽象空间的映射。

表示空间（Representation Space）是由表示值，即实现者看到和使用的值构成的空间；

抽象空间（Abstraction Space）是由抽象值，即用户看到和使用的值构成的空间。

抽象函数的映射一定是满射但未必是单射或者双射。

2.表示不变量（Representation Invariant）

不变量（Invariant）表示程序在任何时候总是为真的性质。

在一个类中将其成员变量修饰为public或者方法的返回值为mutable类的对象引用的行为会导致客户端能够直接访问其成员变量，很可能破坏不变量。这就是表示泄露（Representation Exposure）。

表示泄露（Rep Exposure）指的是在某些情况，ADT向外部泄漏了内部的表示，从而使得调用者有能力修改ADT的内部表示。这种情况下可能会破坏ADT的不变量，并且也可能威胁到ADT的表示独立性。

为防止表示泄露，ADT中的属性使用final和private等修饰属性，用户不能通过的对象来直接更改它的属性。如果ADT中的属性是mutable类型的数据，则ADT中的方法的返回值不能是该属性的引用，不然用户可以直接通过方法的返回值来改变属性的值。一种有效方法就是防御性拷贝defensive copy，即让方法的返回一个可以提供用户需要数据的新对象。

表示不变性RI：某个具体的表示方式是否符合规约。（R中不符合RI的元素难以映射到A）

可以将其看成一个所有表示值的子集，里面包含了所有的合法表示；

还可以将其看成一个“条件”，这个条件描述了什么是合法的表示。

 

注意对于一个ADT 来说，其内部的方法可能会改变属性导致其不满足RI，所以要在方法执行后随时用checkRep（）来检查是否满足RI（Observer可以不检查）。这样可以保证不变量在对象发生变化时仍为true。

 

检查ADT是否保持不变量：

1.由构造器和生产器创建        2.checkRep（）保护        3.没有表示泄露        

设计ADT的过程

1.选择空间R和A。

2.设计RI来表示所有合法的表述。

3.设计AF，来解释所有的合法表述过程。

RI和AF要在代码中用注释形式记录！不能在Javadoc文档中，防止泄露。

有益的可变性：对immutable的ADT来说，可能不同的域值经AF映射到的A空间的值是一样的，比如：域定义分子分母，映射出一个有理数，那么2/4=0.5&3/6=0.5。这种immutableADT内部可以用mutation，前提是这个mutation只是改变了R空间的值，而对A空间每有影响。

文末致谢：

静态工厂方法与构造器方法_BohouZhang的博客-CSDN博客_静态工厂方法和构造器

关于Java ADT的学习总结 - 御用马铃薯 - 博客园

【软件构造】抽象数据类型的表示不变性（RI）、抽象函数（AF）和表示泄漏 Rep Invariantand，Abstraction Function and Rep Exposure of ADT_蠢萌_小二爷的博客-CSDN博客