抽象数据类型和封装概念

1 .Chapter 11 Abstract Data Types and Encapsulation Concepts

2 .Copyright © 2015 Pearson. All rights reserved. 1- 2 Chapter 11 Topics Steve Adds: Motivation and History of Abstraction The Concept of Abstraction Introduction to Data Abstraction Design Issues for Abstract Data Types Language Examples Parameterized Abstract Data Types Encapsulation Constructs Naming Encapsulations

3 .As Software has Become more Complex, it Requires more Software Engineers F. Brooks - Mythical Man Month - 1970s Work done in 2 months by 1 Software Engineer > Work done in 1 month by 2 SEs! “Adding Software Engineers to a Late Project will only Make it Later!” WHY? Interconnectedness: Interdependencies in Code Individual Portions can’t be Written in Isolation Information Exchange Needed Between SEs Complexity Historically Controlled by Abstracting Away Less Important Details Motivation of Abstracti

4 .Separation of Concerns Divide and Conquer Problem Solving Technique Identify the Different Aspects of Problem Time Considerations - Scheduling Focus on Qualities of Primary Concern Alternate Views of Problem - Data vs. Control Size-Oriented Decomposition Today’s Applications involve Interoperability of New C/S, Legacy, COTS, Databases, etc. Multiple Prog. Languages (C, C++, Java, etc.) Heterogeneous Hardware/OS Platforms Separation of Concerns is Critical!

5 .Procedures The “First” Abstraction Mechanism Repeated Execution of Same Code without Duplication Inefficient at Information Hiding Modules: Managing Name Spaces Public: Portion Accessible Outside Module Private: Portion Accessible Inside Module Users can Only “See” Information Needed to Utilize Module SE can Only “See” Information Needed to Code Module Supports Information Hiding History of Abstraction Procedures and Modules

6 .Modularity Compose and Design Systems as Set of Modules Two-Phase Application of Separation of Concerns Define Details of Individual Modules Characterize Interactions Among All Modules Three Goals of Modularity Decomposability : Problem to Subproblems Composability : Combine to Solution Abstraction : Capability of Understanding Levels of Modules in Programming C: “.h/.c” Pairs - Ad-hoc Modularity C++: “.h/.c” Pairs for Classes Ada95/Java: Adds the Package Concept Maximize Cohesion and Minimize Coupling

7 .Abstraction Remove/Hide Unimportant Details to Allow more Important Aspects of a Product to be Considered Widely Utilized to Reduce Complexity Abstractions Dominate Computing Paradigms (OO, Top-Down, Functional, etc.) Design Models (CRC, OMT, UML, etc.) Programming Languages (C, C++, Java, etc.) People Think and Learn in Abstractions Goals of Advances in Design and Programming Provide Robust Sets of Abstractions Allow Modeling to Occur Close to Real World

8 .Copyright © 2015 Pearson. All rights reserved. 1- 8 The Concept of Abstraction An abstraction is a view or representation of an entity that includes only the most significant attributes The concept of abstraction is fundamental in programming (and computer science) Nearly all programming languages support process abstraction with subprograms Nearly all programming languages designed since 1980 support data abstraction

9 .Copyright © 2015 Pearson. All rights reserved. 1- 8 The Concept of Abstraction An abstraction is a view or representation of an entity that includes only the most significant attributes The concept of abstraction is fundamental in programming (and computer science) Nearly all programming languages support process abstraction with subprograms Nearly all programming languages designed since 1980 support data abstraction

10 .Copyright © 2015 Pearson. All rights reserved. 1- 10 Advantages of Data Abstraction Advantages the first condition Reliability--by hiding the data representations, user code cannot directly access objects of the type or depend on the representation, allowing the representation to be changed without affecting user code Reduces the range of code and variables of which the programmer must be aware Name conflicts are less likely Advantages of the second condition Provides a method of program organization Aids modifiability (everything associated with a data structure is together) Separate compilation

11 .Proposed by B. Liskov (MIT) for CLU in 1975 ADTs Promote Application Development From Perspective of Information and its Usage ADT Design Process: Identify “Kinds” or “Types” of Information Encapsulate Information and Provide a Public Interface of Methods Hide Information and Method Code in the Private Implementation ADTs Correspond to User-Defined Data Types Analogous to Integer Data Type and +, -, *, etc. Abstract Data Types (ADTs)

12 .Consider the following Example Stack ADT: Abstract Data Types (ADTs) Public Interface User PUSH POP TOP EMPTY Private Implementation Designer Head: Int; ST: Array[100] of Int; Push(X Int) … End; Int Pop() … End; TOP 5 10 15 20 PUSH 5 20 15 10 5 20 15 10 5 ST

13 .Separation of Concerns and Modularity Problem Decomposable into Components Abstraction and Representation Independence Hiding Implementation of Components Changing without Impacting External View Incrementality and Anticipation of Change Components are Changed, Added, Refined, etc., as Needed to Support Evolving Requirements Cohesion : Well-Defined Component Performs a Single Task or has a Single Objective Coupling : Component Interactions are Known and Minimal ADT Design Guidelines

14 .Supports Reusable Software Components Creation and Testing in Isolation Integration of Working Components Designers/Developers View Problem at Higher Level of Abstraction Controls Information Consistency Public Interface Limits Access to Data Private Implementation Unavailable Promotes/Facilitates Software Evolution/Reuse Inheritance to Extend Design/Class Library Multiple Instances of Same Class Benefits of ADT Paradigm

15 .High-Tech Supermarket System (HTSS) Automate the Functions and Actions Cashiers and Inventory Updates User Friendly Grocery Item Locator Fast-Track Deli Orderer Inventory Control User System Interfaces Cash Register/UPC Scanner GUI for Inventory Control Shopper Interfaces Locator and Orderer Deli Interface for Deli Workers We’ll Introduce and Utilize Throughout Course

16 .The HTSS Software Architecture IC IC CR CR CR CR IL IL IL SDO SDO EDO EDO Order Payment Item ItemDB Local Server Non-Local Client Int. Inventory Control ItemDB Global Server OrderDB SupplierDB CreditCardDB ATM-BanKDB IL: Item Locator CR: Cash Register IC: Invent. Control DO: Deli Orderer for Shopper/Employee

17 .Programming with ADTs ADTs Promote Applications Development From Perspective of Information and Its Usage ADT Design Process and Steps: Identify Major “ Kinds/Types ” of Information Describe Purpose Each Kind or Type Encapsulate Information Define and Characterize Methods Process Iterates/Cycles from Bottom Up Focus on Lowest Level of Info. - Build ADTs Next Level of ADTs Use Lowest Level Next Level Combines most Recent Levels Repeat to Achieve Desired System level

18 .ADTs in HTSS ADT Item; PRIVATE DATA: SET OF Item(s), Each Item Contains: UPC, Name, WCost, RCost, OnShelf, InStock, Location, ROLimit; PTR TO Current_Item; PUBLIC OPS: Create_New_Item(UPC, ...) : RETURN Status; Get_Item_NameCost(UPC) : RETURNS (STRING, REAL); Modify_Inventory(UPC, Delta) ; Get_InStock_Amt(UPC) : RETURN INTEGER; Get_OnShelf_Amt(UPC) : RETURN INTEGER; Check_If_On_Shelf(UPC): RETURN BOOLEAN; Time_To_Reorder(UPC): RETURN BOOLEAN; Get_Item_Profit(UPC): RETURN REAL; ... {notes: - OPS span the entire application - not limited to a single, functional component} END Item; ADT DeliItem; ADT CustomerInfo; PRIVATE DATA: SET OF (Item, Weight, ... CostLb, Increm); END CustomerInfo; ... END DeliItem;

19 .ADTs in HTSS ADT Process_Order; {middle-level ADT} PRIVATE DATA: {local variables to process an order} PUBLIC OPS : {what do you think are appropriate?} {this ADT uses the ADT/PUBLIC OPS from Item, Deli_Item, Receipt, Coupons, and Customer_Info to process and total an Order.} END Process_Order; ADT Sales_Info; {middle-level ADT} PRIVATE DATA: {local variables to collate sales information} PUBLIC OPS : {what do you think are appropriate?} {this ADT uses the ADT/PUBLIC OPS from Receipt so that the sales information for the store can be maintained.} END Sales_Info; ADT Cashier; {high-level ADT} {this ADT uses the ADT/PUBLIC OPS from the middle-level ADTs (Process_Order, Sales_Info, etc.).) END Cashier;

20 .Advantages/Drawbacks of ADTs Advantages: Abstraction is Promoted and Achieved Concurrent Engineering is Feasible Reuse and Evolution are Attainable Emphasizes Static System Behavior Drawbacks: Without Inheritance, Redundancies Likely Dynamic System Behavior Still Difficult Associations Between ADTs Difficult Only Inclusion Association Supported Do Drawbacks Outweigh Advantages?

21 .Copyright © 2015 Pearson. All rights reserved. 1- 21 Language Requirements for ADTs A syntactic unit in which to encapsulate the type definition A method of making type names and subprogram headers visible to clients, while hiding actual definitions Some primitive operations must be built into the language processor

22 .Copyright © 2015 Pearson. All rights reserved. 1- 22 Design Issues Can abstract types be parameterized? What access controls are provided? Is the specification of the type physically separate from its implementation?

23 .Copyright © 2015 Pearson. All rights reserved. 1- 23 Language Examples: C++ Based on C struct type and Simula 67 classes The class is the encapsulation device A class is a type All of the class instances of a class share a single copy of the member functions Each instance of a class has its own copy of the class data members Instances can be static, stack dynamic, or heap dynamic

24 .Copyright © 2015 Pearson. All rights reserved. 1- 24 Language Examples: C++ (continued) Information Hiding Private clause for hidden entities Public clause for interface entities Protected clause for inheritance (Chapter 12)

25 .Copyright © 2015 Pearson. All rights reserved. 1- 25 Language Examples: C++ (continued) Constructors: Functions to initialize the data members of instances (they do not create the objects) May also allocate storage if part of the object is heap-dynamic Can include parameters to provide parameterization of the objects Implicitly called when an instance is created Can be explicitly called Name is the same as the class name

26 .Copyright © 2015 Pearson. All rights reserved. 1- 26 Language Examples: C++ (continued) Destructors Functions to cleanup after an instance is destroyed; usually just to reclaim heap storage Implicitly called when the object’s lifetime ends Can be explicitly called Name is the class name, preceded by a tilde (~)

27 .Copyright © 2015 Pearson. All rights reserved. 1- 27 An Example in C++ class Stack { private : int *stackPtr, maxLen, topPtr; public : Stack() { // a constructor stackPtr = new int [100]; maxLen = 99; topPtr = -1; }; ~Stack () { delete [] stackPtr;}; void push ( int number) { if (topSub == maxLen) cerr << ″Error in push - stack is full

28 .A Stack class header file // Stack.h - the header file for the Stack class #include <iostream.h> class Stack { private : //** These members are visible only to other //** members and friends (see Section 11.6.4) int *stackPtr; int maxLen ; int topPtr ; public : //** These members are visible to clients Stack(); //** A constructor ~Stack(); //** A destructor void push( int ); void pop(); int top(); int empty(); } Copyright © 2015 Pearson. All rights reserved. 1- 28

29 .The code file for Stack // Stack.cpp - the implementation file for the Stack class #include <iostream.h> #include "Stack.h" using std::cout; Stack::Stack() { //** A constructor stackPtr = new int [100]; maxLen = 99; topPtr = -1; } Stack::~Stack() { delete [] stackPtr;}; //** A destructor void Stack::push( int number) { if (topPtr == maxLen) cerr << "Error in push--stack is full