基础知识总结：哈工大2021年软件构造第6讲-ADT

一、ADT的基本属性

　　1.定义：Abstract Data Type，是一种程序员可以自己定义的数据类型。所谓“抽象”，意思是它的具体含义是由它的功能（操作）定义的。

　　2.与传统类型的差别：传统的数据类型更注重数据的表示。例如Date类，是用一些Integer类型的数据来精确表示一个日期的年月日属性。而ADT是由它所承载的操作活动定义的，更强调操作而非数据本身，这意味着程序员和用户都无需过于关心一个ADT类型的数据是如何存储的，而可以把更多的精力放在设计和使用它的操作。

　　3.举例：提及List这个抽象类时，我们不会把它具体化为LinkedList或Array等，而更关注于它能带给我们的操作方式，例如get()或是size()。　　

二、关于可变和不可变数据类型

　　1.区分：可变数据类型(mutable)是指某一个提供了能改变其内部数据信息的方式的数据类型，比如定义一个类Period，里面有成员变量startTime和endTime，在Period中我提供了setStartTime方法和setEndTime方法，意味着使用者可以调用这两个方法，达到对Period类内部数据进行修改的目的，所以称之为可变数据类型。而相比之下，不可变数据类型(Immutable)就是当使用者试图改变startTime时，实质上这种操作并没有改变原有的startTime，而是构建了一个新的startTime1。String是常见的不可变类型。某些特殊的类型（例如StringBuilder）提供两种形式。

三、关于抽象类的操作方法

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

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

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

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

四、设计一个抽象类的原则

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

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

五、表示独立性

　　1.理解：Representation Independence。具体表现为用户使用ADT时无需关心其内部实现，ADT内部变化时也不会影响到外部的规约和客户端。

　　2.举例理解：

　　本例中错误之处在于，people由List类改变为Set类，而反映到了客户端people.get操作由于本次改变而变的不可行，这就是ADT内部的变化影响到了客户端，破坏了RI。

六、对抽象数据类的测试方法

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

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

七、有关不变量Invariant

　　1.ADT中的不变量的重要性：（1）一个优质的ADT需要始终保持它自己的不变量

　　　　　　　　　　　　　　  （2）将某个量设定为不变量，而不是仅仅在规约中规定其不变性，使得代码可维护性更好（易于检查）。

　　　　　　　　　　　　　　  （3）不是所有用户都是可信的，ADT维护自身的不变量是代码安全性的保障。

　　2.设置不变量：声明时利用关键词private。

八、表示不变性和抽象函数

　　1.抽象函数：将程序内部涉及到的所有的数据看成一个数据空间，这个空间称为R(Representation space)，这些数据中的某一部分（也许是全部）会以一些不同的形式展示在用户眼前，这种展示出的数据的集合也构成了一个数据空间，被称为A(Abstract space)。抽象函数(Abstract function)就是这两个空间中数据的一种映射关系。这个定义中也可以将“映射关系”解释为对数据的一种形式上的变换、一种解读，一种“运算”。由这些定义也不难看出，用户跟关注的是A空间中的内容，即程序员将数据抽象地展示在用户眼前的结果；而程序员则更关心空间R中的数据。

　　2.表示不变性：某个具体的表示方式是否符合规约。也可以将其看成一个所有表示值的子集，里面包含了所有的合法表示。还可以将其看成一个“条件”，这个条件描述了什么是合法的表示。

　　3.抽象函数和表示不变性的举例说明：

　　本示例中可以看到：RI和AF都是针对某个抽象类中的某个不变量而产生的，以注释的形式写在该不变量的声明附近。

　　4.RI和AF的特殊性：对于同样的空间R，从不同的角度解读数据，可以有不同的RI表达。而对于同样的空间R和同样的表述RI，也可能会有不同的AF描述方式。

　　5.由此完善设计ADT的过程：

　　　　　　（1）选择空间R和A。

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

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

　　6.RI的检查：对于任何可能改变rep的场景，可以设置并调用一个checkRep函数对rep对于RI的遵守情况进行评判。