1、抽象數(shù)據(jù)類型Abstract Data Types2022-4-10Institute of Computer SoftwareNanjing University1摘要從面向過程到面向?qū)ο笕绾我?guī)約對(duì)象？抽象！Abstract data typeADT與軟件開發(fā)2022-4-10Institute of Computer SoftwareNanjing University2回顧：結(jié)構(gòu)化軟件開發(fā)何謂“結(jié)構(gòu)化（structured）”開發(fā)方法？The Big Name “E.W. Dijkstra”開發(fā)過程側(cè)面自頂向下，逐步求精程序設(shè)計(jì)側(cè)面小結(jié)構(gòu)：順序，選擇，循環(huán) 大結(jié)構(gòu)：過程抽象，避免全局變量

2、2022-4-10Institute of Computer SoftwareNanjing University3回顧：結(jié)構(gòu)化軟件開發(fā)“結(jié)構(gòu)化（structured）”的合理性管理復(fù)雜性的有效手段分解, 抽象, 層次Correctness規(guī)約與實(shí)現(xiàn)Extendibility? Reusability?2022-4-10Institute of Computer SoftwareNanjing University4從面向過程到面向?qū)ο蟆敖Y(jié)構(gòu)化”的基本思想已經(jīng)深入人心但對(duì)于復(fù)雜、易變、交互性軟件系統(tǒng)，以“功能”為中心的分解方式有局限完全自頂向下的功能分解？線性過程式的程序組織？應(yīng)變？2022-

3、4-10Institute of Computer SoftwareNanjing University5The first step程序運(yùn)行：在某個(gè)數(shù)據(jù)體上施以某些操作。兩個(gè)要素 操作（功能）Functions or: Operations, Actions 客體（對(duì)象）Objects or: Data2022-4-10Institute of Computer SoftwareNanjing University6ActionObjectProcessor如何導(dǎo)出軟件系統(tǒng)的結(jié)構(gòu)？?jī)蓷l途徑：從操作/功能入手從客體/對(duì)象入手形成兩種抽象方法：基于過程的抽象基于數(shù)據(jù)的抽象2022-4-10Ins

4、titute of Computer SoftwareNanjing University7過程抽象 vs. 數(shù)據(jù)抽象過程抽象：指任何一個(gè)明確定義功能的操作都可以被使用者看作單個(gè)的實(shí)體，盡管這個(gè)操作實(shí)際上可能由一系列更低級(jí)的操作完成數(shù)據(jù)抽象：定義了數(shù)據(jù)類型和施加于該類型對(duì)象上的操作，并限定了對(duì)象的值只能通過使用這些操作修改和觀察。包含了2個(gè)概念：1.模塊封裝2.信息隱蔽2022-4-10Institute of Computer SoftwareNanjing University8數(shù)據(jù)抽象的意義數(shù)據(jù)抽象提供了面向?qū)ο笥?jì)算的起點(diǎn)：系統(tǒng)應(yīng)該被分解為概念上的實(shí)體，實(shí)體的內(nèi)部細(xì)節(jié)應(yīng)該被隱藏！2022

5、-4-10Institute of Computer SoftwareNanjing University9數(shù)據(jù)抽象發(fā)展第一階段：從無類型的二進(jìn)制到基本數(shù)據(jù)類型Fortran, Algol: 整型、實(shí)數(shù)、布爾數(shù)第二階段：從基本類型到用戶自定義類型Algol68, Pascal第三階段：從用戶自定義類型到抽象數(shù)據(jù)類型（Abstract Data Types）- 面向?qū)ο竽K化程序設(shè)計(jì)和模塊2022-4-10Institute of Computer SoftwareNanjing University10面向?qū)ο蟮姆纸夂迷诤翁帲縍eusability: 數(shù)據(jù)（結(jié)構(gòu)）及其上之操作的整體復(fù)用，而非僅

6、僅復(fù)用操作功能；Extendibility, Continuity: 對(duì)象更直接對(duì)應(yīng)問題空間的概念，因而較“功能”更穩(wěn)定.2022-4-10Institute of Computer SoftwareNanjing University112022-4-10Institute of Computer SoftwareNanjing University現(xiàn)實(shí)世界現(xiàn)實(shí)世界問題世界問題世界軟件世界軟件世界Reality抽象抽象例：考慮一個(gè)工資系統(tǒng)一開始，客戶說他的需求很“簡(jiǎn)單明確”：2022-4-10Institute of Computer SoftwareNanjing University13

7、Employee informationHours workedProduce PaychecksPaychecks例：考慮一個(gè)工資系統(tǒng)這種功能明確的系統(tǒng)確實(shí)適合結(jié)構(gòu)化的開發(fā)方法：自頂向下，逐步求精。你完美地完成了任務(wù)。而后，極有可能，客戶會(huì)跑過來跟你說：給我加個(gè)統(tǒng)計(jì)報(bào)表撒 下個(gè)月我想一些人發(fā)記時(shí)工資，一些人發(fā)計(jì)件工資啊行啊，有人每月一發(fā)，有人每周一發(fā)哦加個(gè)個(gè)人所得稅系統(tǒng)接口再加個(gè)圖像用戶界面，用來交互查詢吧2022-4-10Institute of Computer SoftwareNanjing University14“面向?qū)ο蟮能浖?gòu)造”含義（1）面向?qū)ο蟮能浖?gòu)造（OOSC）乃是基于

8、系統(tǒng)所操作之對(duì)象類型（而非系統(tǒng)需實(shí)現(xiàn)之功能）來架構(gòu)系統(tǒng)的途徑。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.”2022-4-10Institute of Computer SoftwareNanjing University15面向

9、對(duì)象設(shè)計(jì)的相關(guān)問題如何找到對(duì)象類型？如何描述對(duì)象類型？如何描述對(duì)象類型之間的關(guān)系和共性？如何使用對(duì)象類型來構(gòu)造程序？2022-4-10Institute of Computer SoftwareNanjing University16對(duì)象刻畫考慮一類具有相似屬性的對(duì)象而不是單個(gè)對(duì)象定義對(duì)象的類型不是通過定義對(duì)象的物理表述，而是通過定義它們的行為：即它們提供給外部的服務(wù)External, not internal view: ABSTRACT DATA TYPES2022-4-10Institute of Computer SoftwareNanjing University17對(duì)象刻畫問題主要

10、問題：如何描述程序?qū)ο螅〝?shù)據(jù)結(jié)構(gòu)）？Completely Unambiguously Without overspecifying?(Remember information hiding)2022-4-10Institute of Computer SoftwareNanjing University18A stack, concrete object1919countrepresentation(array_up)capacityrepresentation count := xfree(array_down)1representationnnew(linked)itemitemprevi

11、ousitempreviousprevious“Push” operation:count := count + 1representation free := x“Push” operation:free := free - 1new (n)n.item := x“Push” operation:n.previous := lasthead := nAbstract Data Type數(shù)據(jù)類型由一個(gè)對(duì)象集合(值集合)以及在該集合上定義的若干合法運(yùn)算所組成的運(yùn)算集合組成。抽象數(shù)據(jù)類型(ADT)：用數(shù)學(xué)方法數(shù)學(xué)方法定義對(duì)象集合和運(yùn)算集合，僅通過運(yùn)算的性質(zhì)刻畫數(shù)據(jù)對(duì)象，而獨(dú)立于計(jì)算機(jī)中可能的表示方

12、法2022-4-10Institute of Computer SoftwareNanjing University20ADT規(guī)約方法代數(shù)方法模型方法C.A.R. Hoare的前后斷言方法：通過已定義的(抽象)數(shù)據(jù)類型來給出要定義的新類型的抽象模型2022-4-10Institute of Computer SoftwareNanjing University21代數(shù)規(guī)范語法部分ADT名運(yùn)算(函數(shù))的定義域和值域公理部分給出一組刻畫各運(yùn)算之間相互關(guān)系的方程來定義各運(yùn)算的含義語義正確性：相應(yīng)代數(shù)滿足規(guī)約中公理部分的所有語義正確性：相應(yīng)代數(shù)滿足規(guī)約中公理部分的所有公理。公理。2022-4-10In

13、stitute 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 G2022-4-10Institute of Computer SoftwareNanjing University23U

14、sing functions to model operations2022-4-10Institute of Computer SoftwareNanjing University24put,=()sxsADT函數(shù)分類一個(gè) ADT T 中可有三種函數(shù)（算子）: Creators（構(gòu)造算子）:OTHER T e.g. new Queries（觀察算子）:T . OTHERe.g. item, empty Commands（運(yùn)算算子）: T . T e.g. put, remove2022-4-10Institute of Computer SoftwareNanjing University2

15、5Reminder: 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 / x2022-4-10Institute of Computer SoftwareNanjing University26The STACK ADT (contd)Precondit

16、ions: 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)2022-4-10Institute of Computer SoftwareNanjing

17、 University27put (,) =sxsThe STACK ADT2022-4-10Institute 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)2022-4-10Institute of Computer SoftwareNanji

18、ng University29Expression reduction (1/10)2022-4-10Institute of Computer SoftwareNanjing University30Expression reduction (2/10)2022-4-10Institute of Computer SoftwareNanjing University31Expression reduction (3/10)2022-4-10Institute of Computer SoftwareNanjing University32Expression reduction (4/10)

19、2022-4-10Institute of Computer SoftwareNanjing University33Expression reduction (5/10)2022-4-10Institute of Computer SoftwareNanjing University34Expression reduction (6/10)2022-4-10Institute of Computer SoftwareNanjing University35Expression reduction (7/10)2022-4-10Institute of Computer SoftwareNan

20、jing University36Expression reduction (8/10)2022-4-10Institute of Computer SoftwareNanjing University37Expression reduction (9/10)2022-4-10Institute of Computer SoftwareNanjing University38Expression reduction (10/10)2022-4-10Institute of Computer SoftwareNanjing University39Expressed differently202

21、2-4-10Institute 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 (

22、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 expression2022-4-10Institute of Computer SoftwareNanjing University41x8x7x6x8x7s2s3(empty)s1x5x4s5(empty)s4x5s6y1x8x7x5s7 (s9, s11)x8x7x5s8x2x8x7x5s10 x

23、1value = 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 .

24、 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 T2022-4-10Institute of Computer SoftwareNanjing University42ADT ConsistencyAn ADT specification is consistent

25、if and only if, for any well-formed query expression e, the axioms make it possible to infer at most one value for e.2022-4-10Institute of Computer SoftwareNanjing University43ADT and software architectureIdentify every module with an implementation of an abstract data type, i.e. the description of

26、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 th

27、e operations. Auxiliary operations may also be included. 2022-4-10Institute 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 (

28、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.)2022-4-10Institute of Computer SoftwareNanjing University45A choice of stack representation2022-4-10Institute of

29、 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信息隱蔽原則2022-4-10Institute of Computer SoftwareNanjing University47Secret part:Choice of representation (E2)I

30、mplementation of functions by features (E3)ADT specification (E1)Public part:使用ADT的程序應(yīng)該只依賴于它的規(guī)約保證的性質(zhì)，而不依賴于它的任何特定實(shí)現(xiàn)“面向?qū)ο蟮能浖?gòu)造”含義（1）面向?qū)ο蟮能浖?gòu)造（OOSC）乃是基于系統(tǒng)所操作之對(duì)象類型（而非系統(tǒng)需實(shí)現(xiàn)之功能）來架構(gòu)系統(tǒng)的途徑。Meyer: “Object-oriented software construction is the approach to system structuring that bases the architecture of softw

31、are systems on the types of objects they manipulate not on “the” function they achieve.”2022-4-10Institute of Computer SoftwareNanjing University48“面向?qū)ο蟮能浖?gòu)造”含義（2）面向?qū)ο蟮能浖?gòu)造乃是將系統(tǒng)構(gòu)造為抽象數(shù)據(jù)類型實(shí)現(xiàn)（可能是部分實(shí)現(xiàn)）的結(jié)構(gòu)化組合。Meyer:“Object-oriented software construction is the construction of software systems as structur

32、ed collections of possibly partial abstract data type implementations.”這個(gè)這個(gè)“抽象數(shù)據(jù)類型的實(shí)現(xiàn)抽象數(shù)據(jù)類型的實(shí)現(xiàn)”就是類（就是類（class）2022-4-10Institute of Computer SoftwareNanjing University49從ADT到類一般說類是抽象數(shù)據(jù)類型的實(shí)現(xiàn)抽象數(shù)據(jù)類型乃是一種規(guī)約；類是OOPL實(shí)現(xiàn)這種類型的設(shè)施；但是Meyer說：“A class is an abstract data type equipped with a possibly partial impleme

33、ntation.” Meyer在Eiffel中強(qiáng)調(diào)將ADT規(guī)約作為類的一部分強(qiáng)調(diào)從規(guī)約到實(shí)現(xiàn)的一致表達(dá)和平滑過度類可能只是部分實(shí)現(xiàn)Deferred and effective class2022-4-10Institute of Computer Software, Nanjing University50類：對(duì)象程序的基本結(jié)構(gòu)模塊module與類型type的統(tǒng)一：Module = Unit of decomposition: set of servicesType = Description of a set of run-time objects(“instances” of the type)二者聯(lián)系:The servic