【软件构造】抽象数据类型ADT

1.ADT定义

除了java等编程语言自带的数据类型外，用户也可以自定义数据类型。ADT指的是封装在类内的一些数据属性与公开给用户的方法接口。与自带数据类型相比，ADT更关注于操作，即ADT是由操作定义的，与内部如何实现无关。

2.ADT的操作分类

一般而言，抽象数据类型（ADT）的操作可分为如下4种：

• 构造器（Creators）：从无到有构造一个对象实例的方法，t^*->T。
• 生产器（Producer）：由旧的对象产生新的对象。T+,t^*->T
• 观察器（Observers）：返回与ADT内部属性相关的值。T+,t^*->t
• 变值器（Mutators）：改变对象内部属性值的方法。（本类的上一篇博客介绍过，有无变值器是immutable类与mutable类的本质区别，但immutable类中也可以有变值器），T+,t^*->void | t | T

T：抽象类型

t：其他类型

+：出现1次或者多次

*：出现0次或多次

实例如下：

package Test;
/*
@author HIT_Why 120L021418
@create 2022-05-16 11:11
*/
public class ADT {

    // 内部属性
    private boolean is_ADT;

    // 构造器
    public ADT(boolean io){
        is_ADT=io;
    }
    // 生产器
    public ADT anD(ADT a,ADT b){
        return new ADT(a.is_ADT&&b.is_ADT);
    }
    // 观察器
    public boolean getValue(){
        return is_ADT;
    }
    // 变值器
    public void setValue(boolean io){
        is_ADT=io;
    }
}

3.ADT设计要求

一个好的ADT需满足：

• 满足表示独立性。
• 支持用户对数据操作需求，且实现需求难度低。
• 设计简洁一致的操作，通过简单行为的组合实现复杂的操作，对于复杂的操作为客户端提供方法使其简单地调用。

这里，表示独立性介绍如下：

3.1表示独立性定义

表示独立性（Representation Independence），简称为RI，指用户使用ADT时无需考虑其实现，内部表示的变化不应影响外部。而外部也只能通过ADT提供的操作影响到内部，避免表示暴露。

3.2表示独立性实践

我们将上述代码稍作修改，得到如下代码：

package Test;

/*
@author HIT_Why 120L021418
@create 2022-05-16 11:11
*/
public class ADT {

    // 内部属性
    public StringBuilder is_ADT;

    // 构造器
    public ADT(StringBuilder io){
        this.is_ADT=io;
    }
    // 生产器
    public ADT anD(ADT a){
        return new ADT(a.is_ADT.append(1));
    }
    // 观察器
    public StringBuilder getValue(){
        return is_ADT;
    }
    // 变值器
    public void setValue(StringBuilder io){
        is_ADT=io;
    }
}

不难发现，该ADT设计出现了表示暴露，问题分析如下：

1. 内部属性为public，使得用户可以直接修改内部属性，违背RI，应修改隐藏为private；
2. 构造器中将StringBuilder类对象作为参数，StringBuilder类为mutable类，使得用户可以通过修改该类的实例值，间接修改ADT的内部属性is_ADT，违背RI；
3. 观察器中直接返回内部属性值，出现了表示暴露，违背RI，故需要避免immutable类对象的使用。

修改如下：

package Test;

/*
@author HIT_Why 120L021418
@create 2022-05-16 11:11
*/
public class ADT {

    // 内部属性
    private StringBuilder is_ADT;

    // 构造器
    public ADT(StringBuilder io){
        this.is_ADT=new StringBuilder(io);
    }
    // 生产器
    public ADT anD(ADT a){
        return new ADT(a.is_ADT.append(1));
    }
    // 观察器
    public StringBuilder getValue(){
        return new StringBuilder(this.is_ADT);
    }
    
}

4.表示空间与抽象空间

表示空间（R空间）：实现实例的值得集合，为程序员看到并使用的值，称为表示值。

抽象空间（A空间）：抽象值构成的空间，为用户可以看到并使用的值，称为抽象值。

建立二者之间的映射如下图：

该映射解释如下：

• 每个抽象值都被某个表示值映射到
• 某些抽象值由多个表示值映射到
• 并非所有表示值都映射

将上面的抽象为函数，得到抽象函数的定义。

抽象函数（AF）：R空间与A空间之间映射关系的函数，描述了如何将R空间中的值解释为A空间中的值。

例如：设计一个表示集合的ADT，但ADT内部的实际存储形式为列表形式，则这个ADT建立了一个从列表到抽象的集合的映射。由于集合的不重复性，并非所有序列都能被解释为集合，即R空间的值并非全部合法。x是否合法，由RI(x)确定。则此时的AF是一个满射但非双射。

5.总结

1. RI就是一种判定规则，是合法变量应符合的标准，返回yes or no；AF就是一种解释，向用户解释内部属性。
2. 在设计ADT时，要选择R空间和A空间，还要定义RI和与AF。
3. 同一ADT可以有多个表示，不同的内部表示，需要设计不同的AF和RI。
4. 在每个ADT的方法中使用，必须满足RI，在各个操作之后需要通过编写checkRep函数检查是否满足RI。

Ending~??