初识ADT抽象数据类型

主人Github主页

ADT&＃xff08;抽象数据类型&＃xff09;

1.认识接口&＃xff08;interface&＃xff09;

接口是java程序设计中的一种抽象的数据类型&＃xff0c;我们可以通过对某接口的实施来具体到某一类的实现&＃xff0c;也就是说我们可以通过对一个接口不同的实现来设计出满足不同要求的我们需要的class。

举个例子&＃xff0c;

List list &＃61; new ArrayList<>();


这个例子中&＃xff0c;List声明为一个接口&＃xff0c;由interface关键字标识&＃xff0c;而ArrayList是就是实现了List这个接口的具体的类。

关于接口这种抽象的数据类型&＃xff0c;其内定义的方法只有方法名和参数列表&＃xff0c;而没有实体&＃xff0c;&＃xff08;除非你定义了一个静态方法&＃xff0c;否则都将是不可用的没有实体的方法&＃xff09;&＃xff0c;比如像这样&＃xff1a;

看到了&＃xff0c;接口类型中的方法并没有实体&＃xff0c;只是说我声明了这样一个方法&＃xff0c;我有关于这个方法的规约&＃xff08;简要说是对一个方法的说明&＃xff0c;详细说明详见主人博客&＃xff09;&＃xff0c;方法的名称和参数列表&＃xff0c;而没有方法的具体实现。

形象一点说&＃xff0c;这可以是一个模板。好比一个List的接口能派生出两个具体实现的类&＃xff08;ArrayList&＃xff0c;LinkedList&＃xff09;一样&＃xff0c;你定义的接口也可以通过不同类的实施去达到派生出不同类的效果。但是注意&＃xff01;你的实现必须都能等价到接口中方法的各种定义&＃xff0c;包括参数和返回值&＃xff0c;形象一点&＃xff0c;我们说ArrayList和LinkedList从方法实现来说必须是等价的

为什么这么说呢&＃xff1f;因为我们自己的类继承了这个接口&＃xff0c;就必须覆盖掉接口中声明的函数&＃xff08;可以理解为为方法加实体&＃xff09;&＃xff0c;而这个函数的定义必须和接口中的声明相同&＃xff0c;换句话说&＃xff0c;接口中声明的函数的spec你都必须以这个为标准去设计你的函数&＃xff0c;因而我们说一个接口派生出来的n多个类都必须等价。

用三张图来解释操作&＃xff1a;
图一&＃xff1a;

图二&＃xff1a;

图三&＃xff1a;

图一为接口数据类型&＃xff0c;我之中定义了抽象方法&＃xff08;无实体有声明&＃xff09;。
图二为实现该接口的具体的类&＃xff0c;implements关键字表示实施。
图三左图为我在具体的类中实现的接口中定义方法的实例&＃xff0c;&＃64;override关键字表示覆盖掉原有方法。

懂了这些起码在操作上不会有什么问题了。

2.抽象数据类型&＃xff08;Abstract Data Type&＃xff09;

好了&＃xff0c;现在了解了什么是接口之后&＃xff0c;我们来进入我今天的主题&＃xff0c;ADT&＃xff08;抽象数据类型&＃xff09;&＃xff0c;有了它&＃xff0c;我们的编程将不再局限于既定的基本数据类型&＃xff08;如int String等等&＃xff09;和 对象数据类型&＃xff08;ArrayList&＃xff0c;LinkedList等等&＃xff09;&＃xff0c;而是可以自己创造出适合自己设计程序的数据类型。

有关数据的抽象&＃xff0c;我们说是一组以操作刻画的数据类型&＃xff0c;并不关心其内部的具体实现&＃xff0c;只是我们能用它干什么&＃xff0c;为什么用它成了关键。关于抽象类型&＃xff0c;我们将不关心它的内部实现&＃xff0c;而是如何使用它定义的操作成了我们的关心。

同样通过List 接口来说明&＃xff1a;

查了一下java8&＃xff0c;jdk的文档&＃xff0c;找到了一个这样的解释&＃xff0c;其中你会看到 这样的一种结构&＃xff0c;你可以叫它泛型&＃xff0c;这个什么意思呢&＃xff0c;就是你可以定义任何一种类型去替换它&＃xff08;包括String&＃xff0c;int&＃xff0c;或者是你自定义的一些类&＃xff09;&＃xff0c;然而并不会改变它内部功能的实现&＃xff0c;想想是不是很容易理解但是想不明白怎么实现的&＃xff1f;但是目前你只要知道这个泛型给这个接口的调用带来了很多的可能&＃xff0c;这有时间在讨论。

言归正传&＃xff0c;我们说一个抽象数据类型是并不关心它内部的实现的&＃xff0c;因而作为定义方法却没有方法体的接口成为了首要说明对象

剖析接口中的方法我们可以看到&＃xff0c;所有的方法都有其独特的说明&＃xff08;在spec中声明出来的&＃xff09;&＃xff0c;仔细看他定义的方法&＃xff0c;可以看到完全是基于数据层面上的n多操作。

仔细想想&＃xff0c;有很多时候我们在程序定义一个现有的对象是为了应用它之中定义的API&＃xff0c;甚至我们会直接调用某一个类中定义的某一个方法而不需要去实例化一个类别。这个时候我们就是客户&＃xff0c;我们只关心它能为我们实现什么功能&＃xff0c;而不关心它怎么实现的。因而我们说一个抽象数据类型的关键就在于它是“基于数据的操作”。

3.ADT的构成

ADT中的抽象方法的构成主要有四个方面&＃xff1a;构造器&＃xff08;Creators&＃xff09;&＃xff0c;生产器&＃xff08;Producers&＃xff09;&＃xff0c;观察器&＃xff08;Observers&＃xff09;&＃xff0c;变值器&＃xff08;Mutators&＃xff09;。

首先&＃xff0c;构造器&＃xff0c;顾名思义&＃xff0c;创建一个新的对象&＃xff0c;这是每一个类中所必需的&＃xff0c;即便说你没有定义一个构造器在你的类中&＃xff0c;其实编译器也隐含的创建了一个参数为空的构造器给你。

再者&＃xff0c;生产器&＃xff0c;实现从原有的数据类型中派生出一个新的数据类型出来&＃xff0c;不难理解&＃xff0c;我们说String这个数据类型是不可变&＃xff08;immutable&＃xff09;的&＃xff0c;因而在我们对其进行某些字符串分割比如subString&＃xff08;&＃xff09;等操作的时候&＃xff0c;就会产生一个新的和原来不一样的String类型变量出来&＃xff0c;能够完成这种操作的方法我们叫它生产器。

其次&＃xff0c;观察器&＃xff0c;你可以形象的理解为这是对一个对象的现有状态的观察方法。举一个小例子&＃xff0c;size&＃xff08;&＃xff09;函数&＃xff0c;能够返回你定义的容器类型对象的现有大小&＃xff0c;而不对其相应的值和各种参数做任何的改变。

最后&＃xff0c;变值器&＃xff0c;这和观察器是两种不同的概念&＃xff0c;变值器的操作在于改变对象&＃xff0c;可以有意识地改变对象的任何属性&＃xff0c;比如add&＃xff08;&＃xff09;&＃xff0c;向容器中加入一个对象&＃xff0c;整个容器的尺寸加一&＃xff0c;内容变化。

注意&＃xff1a;一个可变数据类型&＃xff08;mutable&＃xff09;中一定会有变值器&＃xff0c;而定义一个ADT是immutable的关键就在于&＃xff0c;其内部定义的任何方法都不能改变他的表示不变量&＃xff08;rep invariablity&＃xff09;

4.ADT的设计

设计一组抽象数据类型&＃xff0c;就要求我们提供一组操作&＃xff0c;并规定其行为规约&＃xff08;spec&＃xff0c;详见主人博客规约设计&＃xff09;。

首先&＃xff0c;需要我们设计一组简单一致的操作。繁杂的操作可能会给用户带来极其糟糕的体验&＃xff0c;以至于生命周期不长&＃xff0c;而一组简单的操作&＃xff0c;附上明确清晰的说明&＃xff0c;会给用户一种不同的体验。一组API操作的简单与否可能与用户的数量息息相关。

其次&＃xff0c;你的操作必须是有意义的&＃xff0c;比如我们不能再List接口中定义有关求和的方法&＃xff0c;因为那是针对于int&＃xff0c;float类型数据才有意义的类型&＃xff0c; 而诸如String等的类型则不适用&＃xff0c;也因而失去了定义这个方法的意义。

再者&＃xff0c;你的操作必须满足client对数据所需要做的所有操作需要&＃xff0c;同时针对客户来说使用起来方便永远是设计ADT的第一原则。

最后&＃xff0c;我们要分清具体和抽象的不同&＃xff0c;你的设计要么基于抽象&＃xff0c;要么基于具体应用。因为针对于不同的设计理念&＃xff0c;作为开发者需要考虑的方面会有差异&＃xff0c;同时也会改变相应的操作结构&＃xff0c;因而如果分不清具体和抽象是会踩坑的。

5.有关编程

• 表示独立性&＃xff08;Representative Independence&＃xff09;

• spec契约

• 测试优先编程&＃xff08;Test-First Programming&＃xff09;