抽象数据类型(ADT)

本文是阅读完MIT的讲义Reading 12: Abstract Data Types后做出的一些总结,涉及到类中私有域的访问、ADT的概念和ADT的设计原则


由于本人水平有限,本文难免会有不当之处,欢迎读者批评指正

私有域的访问

  • 私有域和私有方法可以被相同类中的任意代码访问
  • 相同类的对象可以直接访问彼此的私有域
  • 不太严谨的说(不考虑嵌套类的情况),一个类花括号内的任何代码(包括main()方法)都可以访问这个类的任何对象的私有域和私有方法

什么是抽象(abstraction)

几个重要的概念:

  • 抽象(Abstraction):用更简单、更好层次的概念来省略或隐藏底层细节
  • 模块化(Modularity):将整个系统分割成组件或模块,让他们可以被单独设计、实现、测试、分析和重用。
  • 封装(Encapsulation):给模块建立一个外壳,使得它仅对自己的内部行为负责,而系统其他部分的bug不能影响到它。
  • 信息隐藏(Information hiding):隐藏模块实现的细节,使得当对模块内部细节做出改变时,对系统其他部分没有影响。
  • 关注点分离(Separation of concerns):实现一个功能或关注是单个模块的责任,而不是跨越多个模块

数据抽象的关键思想是:类型的特点由可以对它进行的操作反应出来。例如,数字就是你可以对齐加或乘的东西;字符串就是你可以连接或取字串的东西;布尔类型就是你可以否定的东西,等等。

设计抽象类型的原则

  • 操作应该是通用、连贯的,而不是只适用于一些特殊情况。例如,我们不应该给List添加一个sum操作,因为它可能适用于一个整数列表,但是字符列表呢?嵌套的列表(列表的列表)呢?
  • 操作应该是充足的,完善的。也就是说必须有足够的操作来完成客户的各种计算。测试这种充足性的一个很好的方法是检查是否可以提取到这个类型对象的每个属性。例如,如果List中没有get操作,我们就不能知道列表中的元素是什么。另外,应该设计一些操作来快速方便的获取一些基本属性,例如,严格来讲,Listsize操作并不是必须的,因为我们可以通过不断执行get操作直到list末尾来获得大小,但这是低效、不方便的,所以我们设计一个size操作来完成这个功能。
  • 不能混淆泛型和特定领域的类型。比如,给一个用来装扑克牌的Deck类型设计一个通用的add操作(意思是可以添加任意的类型)就是不合适的。相反,给List设计一个适用于特定领域的dealCards(洗牌)操作也是没有意义的。

    小结

  • 抽象数据类型的特征由他们的操作决定
  • 操作可以被分类成creators, producers, observers和mutators
  • 一个ADT的规约是它的操作集和操作集的规约
  • 一个好的ADT是简单的、连贯的、充足的和表示独立的

    讲义原文地址

    Reading 12: Abstract Data Types