哈工大2022软件构造4-ADT知识笔记_adt实现者关注表示空间r,用户关注抽象空间a 例如,假设我们选择使用一个字符串来表

【ADT的基本概念】

• 抽象数据类型（Abstract Data Type，ADT）是是指一个数学模型以及定义在该模型上的一组操作；即包括数据数据元素，数据关系以及相关的操作。
• ADT具有以下几个能表达抽象思想的词：
  • 抽象化：用更简单、更高级的思想省略或隐藏低级细节。
  • 模块化： 将系统划分为组件或模块，每个组件可以设计，实施，测试，推理和重用，与系统其余部分分开使用。
  • 封装：围绕模块构建墙，以便模块负责自身的内部行为，并且系统其他部分的错误不会损坏其完整性。
  • 信息隐藏： 从系统其余部分隐藏模块实现的细节，以便稍后可以更改这些细节，而无需更改系统的其他部分。
  • 关注点分离： 一个功能只是单个模块的责任，而不跨越多个模块。
• 与传统类型定义的差别：
  • 传统的类型定义：关注数据的具体表示。
  • 抽象类型：强调“作用于数据上的操作”，程序员和client无需关心数据如何具体存储的，只需设计/使用操作即可。

• ADT是由操作定义的，与其内部如何实现无关！

可变与不可变类型

• 可变类型的对象：提供了可改变其内部数据的值的操作。Date
• 不变数据类型： 其操作不改变内部值，而是构造新的对象。String

 

四种类型

• Creators（构造器）：
  • 创建某个类型的新对象，⼀个创建者可能会接受⼀个对象作为参数，但是这个对象的类型不能是它创建对象对应的类型。可能实现为构造函数或静态函数。（通常称为工厂方法）
  • t* ->  T
  • eg：Integer.valueOf( )
• Producers（生产器）：
  • 通过接受同类型的对象创建新的对象。
  • T+ , t* -> T
  • eg：String.concat( )
• Observers（观察器）：
  • 获取抽象类型的对象然后返回一个不同类型的对象/值。
  • T+ , t* -> t
  • eg：List.size( ) ；
• Mutators（变值器）：
  • 改变对象属性的方法 ，
  • 变值器通常返回void，若为void，则必然意味着它改变了对象的某些内部状态；当然，也可能返回非空类型 
  • T+ , t* -> t || T || void
  • eg：List.add( )

 

ADT设计原则

• 原则 1：设计简洁、一致的操作。
  • 最好有一些简单的操作，它们可以以强大的方式组合，而不是很多复杂的操作。
  • 每个操作应该有明确的目的，并且应该有一致的行为而不是一连串的特殊情况。
• 原则 2：要足以支持用户对数据所做的所有操作需要，且用操作满足用户需要的难度要低。
  • 提供get()操作以获得list内部数据
  • 提供size()操作获取list的长度
• 原则 3：要么抽象、要么具体，不要混合 —— 要么针对抽象设计，要么针对具体应用的设计。

抽象函数AF与表示不变量RI

 

• 在研究抽象类型的时候，先思考一下两个值域之间的关系：
  • 表示域（rep values）里面包含的是值具体的实现实体。一般情况下ADT的表示比较简单，有些时候需要复杂表示。 
  • 抽象域（A）里面包含的则是类型设计时支持使用的值。这些值是由表示域“抽象/想象”出来的，也是使用者关注的。
• ADT实现者关注表示空间R，用户关注抽象空间A 。
• R->A的映射特点：
  • 每一个抽象值都是由表示值映射而来 ，即满射：每个抽象值被映射到一些rep值
  • 一些抽象值是被多个表示值映射而来的，即未必单射：一些抽象值被映射到多个rep值
  • 不是所有的表示值都能映射到抽象域中，即未必双射：并非所有的rep值都被映射。

用注释写AF和RI

• 在抽象类型（私有的）表示声明后写上对于抽象函数和表示不变量的注解，这是一个好的实践要求。我们在上面的例子中也是这么做的。
• 在描述抽象函数和表示不变量的时候，注意要清晰明确：
  • 对于RI（表示不变量），仅仅宽泛的说什么区域是合法的并不够，你还应该说明是什么使得它合法/不合法。
  • 对于AF（抽象函数）来说，仅仅宽泛的说抽象域表示了什么并不够。抽象函数的作用是规定合法的表示值会如何被解释到抽象域。作为一个函数，我们应该清晰的知道从一个输入到一个输入是怎么对应的。