【软件构造】抽象数据类型ADT
1.前言
在Lab2中，涉及到了大量的ADT、RI、AF的设计，仅以此篇博客做一个小小的总结。🥰
2.ADT定义
除了java等编程语言自带的数据类型外，用户也可以 自定义数据类型。ADT指的是封装在类内的一些数据属性与公开给用户的方法接口。与自带数据类型相比，ADT更关注于操作，即ADT是 由操作定义的，与内部如何实现无关。
3.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;
}
}
4.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设计 出现了表示暴露，问题分析如下：
- 内部属性为public，使得用户可以直接修改内部属性，违背RI，应修改隐藏为private；
- 构造器中将StringBuilder类对象作为参数，StringBuilder类为mutable类，使得用户可以通过修改该类的实例值，间接修改ADT的内部属性is_ADT，违背RI；
- 观察器中直接返回内部属性值，出现了表示暴露，违背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);
}
}
5.表示空间与抽象空间
表示空间（R空间）：实现实例的值得集合，为程序员看到并使用的值，称为表示值。
抽象空间（A空间）：抽象值构成的空间，为用户可以看到并使用的值，称为抽象值。
建立二者之间的映射如下图：
该映射解释如下：
- 每个抽象值都被某个表示值映射到
- 某些抽象值由多个表示值映射到
- 并非所有表示值都映射
将上面的抽象为函数，得到抽象函数的定义。
抽象函数（AF）：R空间与A空间之间映射关系的函数，描述了如何将R空间中的值解释为A空间中的值。
例如：设计一个表示集合的ADT，但ADT内部的实际存储形式为列表形式，则这个ADT建立了一个从列表到抽象的集合的映射。由于集合的不重复性，并非所有序列都能被解释为集合，即R空间的值并非全部合法。x是否合法，由RI(x)确定。则此时的AF是一个满射但非双射。
6.总结
ADT的核心在于其结构上的方法，我们从spec中得知对client的输入限制以及implement的返回输出，通过ADT进行spec的落实，通过R–>RI–>–>AF–>A的过程进行实现。
- RI就是一种 判定规则，是合法变量应符合的标准，返回yes or no；AF就是一种 解释，向用户解释内部属性。
- 在设计ADT时，要选择R空间和A空间，还要定义RI和与AF。
- 同一ADT可以有多个表示，不同的内部表示，需要设计不同的AF和RI。
- 在每个ADT的方法中使用，必须满足RI，在各个操作之后需要通过编写 checkRep函数检查是否满足RI。
Ending~😊
Original: https://www.cnblogs.com/ganzhi/p/16276404.html
Author: 甘之
Title: 【软件构造】抽象数据类型ADT
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/569908/
转载文章受原作者版权保护。转载请注明原作者出处！