面向对象技术.ppt

抽象数据类型 AbstractDataTypes 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 1 摘要 从面向过程到面向对象如何规约对象 抽象 AbstractdatatypeADT与软件开发 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 2 回顾 结构化软件开发 何谓 结构化 structured 开发方法 TheBigName E W Dijkstra 开发过程侧面自顶向下 逐步求精程序设计侧面小结构 顺序 选择 循环大结构 过程抽象 避免全局变量 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 3 回顾 结构化软件开发 结构化 structured 的合理性管理复杂性的有效手段分解 抽象 层次Correctness规约与实现Extendibility Reusability 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 4 从面向过程到面向对象 结构化 的基本思想已经深入人心但对于复杂 易变 交互性软件系统 以 功能 为中心的分解方式有局限完全自顶向下的功能分解 线性过程式的程序组织 应变 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 5 Thefirststep 程序运行 在某个数据体上施以某些操作 两个要素操作 功能 Functions or Operations Actions 客体 对象 Objects or Data 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 6 Action Object Processor 如何导出软件系统的结构 两条途径 从操作 功能入手从客体 对象入手形成两种抽象方法 基于过程的抽象基于数据的抽象 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 7 过程抽象vs 数据抽象 过程抽象 指任何一个明确定义功能的操作都可以被使用者看作单个的实体 尽管这个操作实际上可能由一系列更低级的操作完成数据抽象 定义了数据类型和施加于该类型对象上的操作 并限定了对象的值只能通过使用这些操作修改和观察 包含了2个概念 模块封装信息隐蔽 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 8 数据抽象的意义 数据抽象提供了面向对象计算的起点 系统应该被分解为概念上的实体 实体的内部细节应该被隐藏 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 9 数据抽象发展 第一阶段 从无类型的二进制到基本数据类型Fortran Algol 整型 实数 布尔数第二阶段 从基本类型到用户自定义类型Algol68 Pascal第三阶段 从用户自定义类型到抽象数据类型 AbstractDataTypes 面向对象模块化程序设计和模块 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 10 面向对象的分解好在何处 Reusability 数据 结构 及其上之操作的整体复用 而非仅仅复用操作功能 Extendibility Continuity 对象更直接对应问题空间的概念 因而较 功能 更稳定 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 11 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 现实世界 问题世界 软件世界 Reality 抽象 例 考虑一个工资系统 一开始 客户说他的需求很 简单明确 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 13 Employeeinformation Hoursworked ProducePaychecks Paychecks 例 考虑一个工资系统 这种功能明确的系统确实适合结构化的开发方法 自顶向下 逐步求精 你完美地完成了任务 而后 极有可能 客户会跑过来跟你说 给我加个统计报表撒下个月我想一些人发记时工资 一些人发计件工资啊行啊 有人每月一发 有人每周一发哦加个个人所得税系统接口再加个图像用户界面 用来交互查询吧 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 14 面向对象的软件构造 含义 1 面向对象的软件构造 OOSC 乃是基于系统所操作之对象类型 而非系统需实现之功能 来架构系统的途径 Meyer Object orientedsoftwareconstructionistheapproachtosystemstructuringthatbasesthearchitectureofsoftwaresystemsonthetypesofobjectstheymanipulate noton the functiontheyachieve 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 15 面向对象设计的相关问题 如何找到对象类型 如何描述对象类型 如何描述对象类型之间的关系和共性 如何使用对象类型来构造程序 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 16 对象刻画 考虑一类具有相似属性的对象而不是单个对象定义对象的类型不是通过定义对象的物理表述 而是通过定义它们的行为 即它们提供给外部的服务External notinternalview ABSTRACTDATATYPES 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 17 对象刻画问题 主要问题 如何描述程序对象 数据结构 CompletelyUnambiguouslyWithoutoverspecifying Rememberinformationhiding 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 18 Astack concreteobject 19 19 count representation array up capacity representation count x free array down 1 representation n new linked item item previous item previous previous Push operation count count 1 representation free x Push operation free free 1 new n n item x Push operation n previous last head n AbstractDataType 数据类型由一个对象集合 值集合 以及在该集合上定义的若干合法运算所组成的运算集合组成 抽象数据类型 ADT 用数学方法定义对象集合和运算集合 仅通过运算的性质刻画数据对象 而独立于计算机中可能的表示方法 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 20 ADT规约方法 代数方法模型方法C A R Hoare的前后断言方法 通过已定义的 抽象 数据类型来给出要定义的新类型的抽象模型 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 21 代数规范 语法部分ADT名运算 函数 的定义域和值域公理部分给出一组刻画各运算之间相互关系的方程来定义各运算的含义语义正确性 相应代数满足规约中公理部分的所有公理 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 22 Stack Anabstractdatatype Types STACK G G FormalgenericparameterFunctions Operations put STACK G G STACK G remove STACK G STACK G item STACK G Gempty STACK G BOOLEANnew STACK G 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 23 Usingfunctionstomodeloperations 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 24 put s x s ADT函数分类 一个ADTT中可有三种函数 算子 Creators 构造算子 OTHER Te g newQueries 观察算子 T OTHERe g item emptyCommands 运算算子 T Te g put remove 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 25 Reminder Partialfunctions Apartialfunction identifiedhereby isafunctionthatmaynotbedefinedforallpossiblearguments Examplefromelementarymathematics inverse suchthatinverse x 1 x 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 26 TheSTACKADT cont d Preconditions remove s STACK G requirenotempty s item s STACK G requirenotempty s Axioms Forallx G s STACK G item put s x xremove put s x sempty new or empty new True notempty put s x or empty put s x False 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 27 put s x s TheSTACKADT 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 28 Formalstackexpressions value item remove put remove put put remove put put put new x8 x7 x6 item remove put put new x5 x4 x2 x1 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 29 Expressionreduction 1 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 30 Expressionreduction 2 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 31 Expressionreduction 3 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 32 Expressionreduction 4 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 33 Expressionreduction 5 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 34 Expressionreduction 6 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 35 Expressionreduction 7 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 36 Expressionreduction 8 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 37 Expressionreduction 9 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 38 Expressionreduction 10 10 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 39 Expresseddifferently 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 40 s1 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 Anoperationalviewoftheexpression 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 41 x8 x7 x6 x8 x7 s2 s3 empty s1 x5 x4 s5 empty s4 x5 s6 y1 x8 x7 x5 s7 s9 s11 x8 x7 x5 s8 x2 x8 x7 x5 s10 x1 value item remove put remove put put remove put put put new x8 x7 x6 item remove put put new x5 x4 x2 x1 x8 x7 x5 s11 Sufficientcompleteness ThreeformsoffunctionsinthespecificationofanADTT Creators OTHER Te g newQueries T OTHERe g item emptyCommands T Te g put removeSufficientlycompletespecification a QueryExpression oftheform f wherefisaquery maybereducedthroughapplicationoftheaxiomstoaformnotinvolvingT 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 42 ADTConsistency AnADTspecificationisconsistentifandonlyif foranywell formedqueryexpressione theaxiomsmakeitpossibletoinferatmostonevaluefore 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 43 ADTandsoftwarearchitecture Identifyeverymodulewithanimplementationofanabstractdatatype i e thedescriptionofasetofobjectswithacommoninterface Theinterfaceisdefinedbyasetofoperations implementingthefunctionsoftheADT constrainedbyabstractproperties theaxiomsandpreconditions Themoduleconsistsofarepresentationfortheabstractdatatypeandanimplementationforeachoftheoperations Auxiliaryoperationsmayalsobeincluded 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 44 ImplementinganADT ThreeElements E1 TheADT sspecification functions axioms preconditions Example stacks E2 Somerepresentationchoice Example E3 Asetofsubprograms routines andattributes eachimplementingoneofthefunctionsoftheADTspecification E1 intermsofthechosenrepresentation E2 Example routinesput remove item empty new 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 45 Achoiceofstackrepresentation 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 46 count representation array up capacity put x G is Pushxontostack nocheckforpossiblestackoverflowdocount count 1representation count xend 信息隐蔽原则 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 47 Secretpart Choiceofrepresentation E2 Implementationoffunctionsbyfeatures E3 ADTspecification E1 Publicpart 使用ADT的程序应该只依赖于它的规约保证的性质 而不依赖于它的任何特定实现 面向对象的软件构造 含义 1 面向对象的软件构造 OOSC 乃是基于系统所操作之对象类型 而非系统需实现之功能 来架构系统的途径 Meyer Object orientedsoftwareconstructionistheapproachtosystemstructuringthatbasesthearchitectureofsoftwaresystemsonthetypesofobjectstheymanipulate noton the functiontheyachieve 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 48 面向对象的软件构造 含义 2 面向对象的软件构造乃是将系统构造为抽象数据类型实现 可能是部分实现 的结构化组合 Meyer Object orientedsoftwareconstructionistheconstructionofsoftwaresystemsasstructuredcollectionsofpossiblypartialabstractdatatypeimplementations 这个 抽象数据类型的实现 就是类 class 2020 3 14 InstituteofComputerSoftwareNanjingUniversity 49 从ADT到类 一般说类是抽象数据类型的实现抽象数据类型乃是一种规约 类是OOPL实现这种类型的设施 但是Meyer说 Aclassisanabstractdatatypeequippedwithapossiblypartialimplementation Meyer在Eiffel中强调将ADT规约作为类的一部分强调从规约到实现的一致表达和平滑过度类可能只是部分实现Deferredandeffectiveclass 2020 3 14 InstituteofComputerSoftware NanjingUniversity 50 类 对象程序的基本结构 模块module与类型type的统一 Module Unitofdecomposition setofservicesType Descriptionofasetofrun timeobjects instances ofthetype 二者联系 Theservicesofferedbytheclass viewedasamodule aretheoperationsavailableontheinsta