面向对象技术课件

抽象数据类型Abstract Data Types2024/7/30Institute of Computer SoftwareNanjing University1摘要从面向过程到面向对象如何规约对象？抽象！Abstract data typeADT与软件开发2024/7/30Institute of Computer SoftwareNanjing University2回顾：结构化软件开发何谓“结构化（structured）”开发方法？The Big Name“E.W.Dijkstra”开发过程侧面自顶向下，逐步求精程序设计侧面小结构：顺序，选择，循环 大结构：过程抽象，避免全局变量2024/7/30Institute of Computer SoftwareNanjing University3回顾：结构化软件开发“结构化（structured）”的合理性管理复杂性的有效手段分解,抽象,层次Correctness规约与实现Extendibility?Reusability?2024/7/30Institute of Computer SoftwareNanjing University4从面向过程到面向对象“结构化”的基本思想已经深入人心但对于复杂、易变、交互性软件系统，以“功能”为中心的分解方式有局限完全自顶向下的功能分解？线性过程式的程序组织？应变？2024/7/30Institute of Computer SoftwareNanjing University5The first step程序运行：在某个数据体上施以某些操作。两个要素 操作（功能）Functions or:Operations,Actions 客体（对象）Objects or:Data2024/7/30Institute of Computer SoftwareNanjing University6ActionObjectProcessor如何导出软件系统的结构？两条途径：从操作/功能入手从客体/对象入手形成两种抽象方法：基于过程的抽象基于数据的抽象2024/7/30Institute of Computer SoftwareNanjing University7过程抽象vs.数据抽象过程抽象：指任何一个明确定义功能的操作都可以被使用者看作单个的实体，尽管这个操作实际上可能由一系列更低级的操作完成数据抽象：定义了数据类型和施加于该类型对象上的操作，并限定了对象的值只能通过使用这些操作修改和观察。包含了2个概念：1.模块封装2.信息隐蔽2024/7/30Institute of Computer SoftwareNanjing University8数据抽象的意义数据抽象提供了面向对象计算的起点：系统应该被分解为概念上的实体，实体的内部细节应该被隐藏！2024/7/30Institute of Computer SoftwareNanjing University9数据抽象发展第一阶段：从无类型的二进制到基本数据类型Fortran,Algol:整型、实数、布尔数第二阶段：从基本类型到用户自定义类型Algol68,Pascal第三阶段：从用户自定义类型到抽象数据类型（Abstract Data Types）-面向对象模块化程序设计和模块2024/7/30Institute of Computer SoftwareNanjing University10面向对象的分解好在何处？Reusability:数据（结构）及其上之操作的整体复用，而非仅仅复用操作功能；Extendibility,Continuity:对象更直接对应问题空间的概念，因而较“功能”更稳定.2024/7/30Institute of Computer SoftwareNanjing University112024/7/30Institute of Computer SoftwareNanjing University现实世界现实世界问题世界问题世界软件世界软件世界Reality抽象抽象例：考虑一个工资系统一开始，客户说他的需求很“简单明确”：2024/7/30Institute of Computer SoftwareNanjing University13Employee informationHours workedProduce PaychecksPaychecks例：考虑一个工资系统这种功能明确的系统确实适合结构化的开发方法：自顶向下，逐步求精。你完美地完成了任务。而后，极有可能，客户会跑过来跟你说：给我加个统计报表撒 下个月我想一些人发记时工资，一些人发计件工资啊行啊，有人每月一发，有人每周一发哦加个个人所得税系统接口再加个图像用户界面，用来交互查询吧2024/7/30Institute of Computer SoftwareNanjing University14“面向对象的软件构造”含义（1）面向对象的软件构造（OOSC）乃是基于系统所操作之对象类型（而非系统需实现之功能）来架构系统的途径。Meyer:“Object-oriented software construction is the approach to system structuring that bases the architecture of software systems on the types of objects they manipulate not on“the”function they achieve.”2024/7/30Institute of Computer SoftwareNanjing University15面向对象设计的相关问题如何找到对象类型？如何描述对象类型？如何描述对象类型之间的关系和共性？如何使用对象类型来构造程序？2024/7/30Institute of Computer SoftwareNanjing University16对象刻画考虑一类具有相似属性的对象而不是单个对象定义对象的类型不是通过定义对象的物理表述，而是通过定义它们的行为：即它们提供给外部的服务External,not internal view:ABSTRACT DATA TYPES2024/7/30Institute of Computer SoftwareNanjing University17对象刻画问题主要问题：如何描述程序对象（数据结构）？Completely Unambiguously Without overspecifying?(Remember information hiding)2024/7/30Institute of Computer SoftwareNanjing University18A stack,concrete object1919countrepresentation(array_up)capacityrepresentation count:=xfree(array_down)1representationnnew(linked)itemitempreviousitempreviousprevious“Push”operation:count:=count+1representation free:=x“Push”operation:free:=free-1new(n)n.item:=x“Push”operation:n.previous:=lasthead:=nAbstract Data Type数据类型由一个对象集合(值集合)以及在该集合上定义的若干合法运算所组成的运算集合组成。抽象数据类型(ADT)：用数学方法数学方法定义对象集合和运算集合，仅通过运算的性质刻画数据对象，而独立于计算机中可能的表示方法2024/7/30Institute of Computer SoftwareNanjing University20ADT规约方法代数方法模型方法C.A.R.Hoare的前后断言方法：通过已定义的(抽象)数据类型来给出要定义的新类型的抽象模型2024/7/30Institute of Computer SoftwareNanjing University21代数规范语法部分ADT名运算(函数)的定义域和值域公理部分给出一组刻画各运算之间相互关系的方程来定义各运算的含义语义正确性：相应代数满足规约中公理部分的所有语义正确性：相应代数满足规约中公理部分的所有公理。公理。2024/7/30Institute of Computer SoftwareNanjing University22Stack:An abstract data typeTypes:STACK G -G:Formal generic parameterFunctions(Operations):put:STACK G G STACK G remove:STACK G STACK G item:STACK G G empty:STACK G BOOLEAN new:STACK G2024/7/30Institute of Computer SoftwareNanjing University23Using functions to model operations2024/7/30Institute of Computer SoftwareNanjing University24put,=()sxsADT函数分类一个 ADT T 中可有三种函数（算子）:Creators（构造算子）:OTHER T e.g.new Queries（观察算子）:T.OTHERe.g.item,empty Commands（运算算子）:T.T e.g.put,remove2024/7/30Institute of Computer SoftwareNanjing University25Reminder:Partial functionsA partial function,identified here by,is a function that may not be defined for all possible arguments.Example from elementary mathematics:inverse:,such that inverse(x)=1/x2024/7/30Institute of Computer SoftwareNanjing University26The STACK ADT(contd)Preconditions:remove(s:STACK G)require not empty(s)item(s:STACK G)require not empty(s)Axioms:For all x:G,s:STACK G item(put(s,x)=x remove(put(s,x)=s empty(new)(or:empty(new)=True)not empty(put(s,x)(or:empty(put(s,x)=False)2024/7/30Institute of Computer SoftwareNanjing University27put(,)=sxsThe STACK ADT2024/7/30Institute of Computer SoftwareNanjing University28Formal stack expressionsvalue=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1)2024/7/30Institute of Computer SoftwareNanjing University29Expression reduction(1/10)2024/7/30Institute of Computer SoftwareNanjing University30Expression reduction(2/10)2024/7/30Institute of Computer SoftwareNanjing University31Expression reduction(3/10)2024/7/30Institute of Computer SoftwareNanjing University32Expression reduction(4/10)2024/7/30Institute of Computer SoftwareNanjing University33Expression reduction(5/10)2024/7/30Institute of Computer SoftwareNanjing University34Expression reduction(6/10)2024/7/30Institute of Computer SoftwareNanjing University35Expression reduction(7/10)2024/7/30Institute of Computer SoftwareNanjing University36Expression reduction(8/10)2024/7/30Institute of Computer SoftwareNanjing University37Expression reduction(9/10)2024/7/30Institute of Computer SoftwareNanjing University38Expression reduction(10/10)2024/7/30Institute of Computer SoftwareNanjing University39Expressed differently2024/7/30Institute of Computer SoftwareNanjing University40s1=news2=put(put(put(s1,x8),x7),x6)s3=remove(s2)s4=news5=put(put(s4,x5),x4)s6=remove(s5)y1=item(s6)s7=put(s3,y1)s8=put(s7,x2)s9=remove(s8)s10=put(s9,x1)s11=remove(s10)value=item(s11)value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1)An operational view of the expression2024/7/30Institute of Computer SoftwareNanjing University41x8x7x6x8x7s2s3(empty)s1x5x4s5(empty)s4x5s6y1x8x7x5s7(s9,s11)x8x7x5s8x2x8x7x5s10 x1value=item(remove(put(remove(put(put(remove(put(put(put(new,x8),x7),x6),item(remove(put(put(new,x5),x4),x2),x1)x8x7x5s11Sufficient completenessThree forms of functions in the specification of an ADT T:Creators:OTHER T e.g.new Queries:T.OTHERe.g.item,empty Commands:T.T e.g.put,remove Sufficiently complete specification:a“Query Expression”of the form:f(.)where f is a query,may be reduced through application of the axioms to a form not involving T2024/7/30Institute of Computer SoftwareNanjing University42ADTConsistencyAn ADT specification is consistent if and only if,for any well-formed query expression e,the axioms make it possible to infer at most one value for e.2024/7/30Institute of Computer SoftwareNanjing University43ADT and software architectureIdentify every module with an implementation of an abstract data type,i.e.the description of a set of objects with a common interface.The interface is defined by a set of operations(implementing the functions of the ADT)constrained by abstract properties(the axioms and preconditions).The module consists of a representation for the abstract data type and an implementation for each of the operations.Auxiliary operations may also be included.2024/7/30Institute of Computer SoftwareNanjing University44Implementing an ADTThree Elements (E1)The ADTs specification:functions,axioms,preconditions.(Example:stacks.)(E2)Some representation choice.(Example:.)(E3)A set of subprograms(routines)and attributes,each implementing one of the functions of the ADT specification(E1)in terms of the chosen representation(E2).(Example:routines put,remove,item,empty,new.)2024/7/30Institute of Computer SoftwareNanjing University45A choice of stack representation2024/7/30Institute of Computer SoftwareNanjing University46countrepresentation(array_up)capacityput(x:G)is -Push x onto stack -no check for possible stack overflow docount:=count+1representation count:=x end信息隐蔽原则2024/7/30Institute of Computer SoftwareNanjing University47Secret part:Choice of representation(E2)Implementation of functions by features(E3)ADT specification(E1)Public part:使用ADT的程序应该只依赖于它的规约保证的性质，而不依赖于它的任何特定实现“面向对象的软件构造”含义（1）面向对象的软件构造（OOSC）乃是基于系统所操作之对象类型（而非系统需实现之功能）来架构系统的途径。Meyer:“Object-oriented software construction is the approach to system structuring that bases the architecture of software systems on the types of objects they manipulate not on“the”function they achieve.”2024/7/30Institute of Computer SoftwareNanjing University48“面向对象的软件构造”含义（2）面向对象的软件构造乃是将系统构造为抽象数据类型实现（可能是部分实现）的结构化组合。Meyer:“Object-oriented software construction is the construction of software systems as structured collections of possibly partial abstract data type implementations.”这个这个“抽象数据类型的实现抽象数据类型的实现”就是类（就是类（class）2024/7/30Institute of Computer SoftwareNanjing University49从ADT到类一般说类是抽象数据类型的实现抽象数据类型乃是一种规约；类是OOPL实现这种类型的设施；但是Meyer说：“A class is an abstract data type equipped with a possibly partial implementation.”Meyer在Eiffel中强调将ADT规约作为类的一部分强调从规约到实现的一致表达和平滑过度类可能只是部分实现Deferred and effective class2024/7/30Institute of Computer Software,Nanjing University50类：对象程序的基本结构模块module与类型type的统一：Module=Unit of decomposition:set of servicesType=Description of a set of run-time objects(“instances”of the type)二者联系:The services offered by the class,viewed as a module,are the operations available on the instances of the class,viewed as a type.2024/7/30Institute of Computer SoftwareNanjing University512024/7/30Institute of Computer SoftwareNanjing University52模块与类型的统一模块是软件分解的单元，是语法概念类型是某些动态对象的静态描述，是语义概念传统语言模块与类型分离对象语言模块与类型统一类型：类是抽象数据类型的实现模块：类是对象式程序的基本组成单元基于类的面向对象的语言机制的强有力之处在于“类”统一了类型和模块类之间的关系允引Client继承Heir2024/7/30Institute of Computer SoftwareNanjing University532024/7/30Institute of Computer SoftwareNanjing University54层次性封装性帮助隐藏细节；模块化使结构更加有序，但仍然不够！层次性是对抽象的排序和定位类结构关系（”is a”）对象结构关系（”part of”）实现方式继承：子类，父类单继承，多继承聚合：拥有关系/组合关系Overall system structure2024/7/30Institute of Computer SoftwareNanjing University55CHUNKword_countjustified?add_wordremove_wordjustifyunjustifylengthfontFIGUREPARAGRAPHWORDspace_beforespace_afteradd_space_beforeadd_space_afterset_fonthyphenate_onhyphenate_offQUERIESCOMMANDSFEATURESInheritanceClient小结ADTWhyWhatHow2024/7/30Institute of Computer SoftwareNanjing University56提问与解答环节Questions And Answers谢谢聆听 学习就是为了达到一定目的而努力去干,是为一个目标去战胜各种困难的过程,这个过程会充满压力、痛苦和挫折Learning Is To Achieve A Certain Goal And Work Hard,Is A Process To Overcome Various Difficulties For A Goal