当前位置 : 主页 > 编程语言 > 其它开发 >

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

来源:互联网 收集:自由互联 发布时间:2022-05-30
【软件构造】抽象数据类型ADT 1.ADT定义 除了java等编程语言自带的数据类型外,用户也可以 自定义数据类型 。ADT指的是封装在类内的一些数据属性与公开给用户的方法接口。与自带数据

【软件构造】抽象数据类型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~

网友评论