Transcript Data Abstraction

Chapter 1
Data Abstraction: The Walls
CS 302 - Data Structures
Mehmet H Gunes
Modified from authors’ slides
Contents
• Object-Oriented Concepts
• Achieving a Better Solution
• Specifications
• Abstract Data Types
• The ADT Bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
2
The Software Life Cycle
•
•
•
•
•
•
•
•
•
Problem analysis
Requirements elicitation
Software specification
High- and low-level design
Implementation
Testing and Verification
Delivery
Operation
Maintenance
3
Cost of an Error
4
Controlling Errors
• Robustness: The ability of a program to recover
following an error
– the ability of a program to continue to operate within its
environment
• Preconditions: Assumptions that must be true on
entry into an operation or function for the
postconditions to be guaranteed
• Postconditions: Statements that describe what
results are to be expected at the exit of an operation
or function
– assuming that the preconditions are true
5
Procedural vs. Object-Oriented Code
• “Read the specification of the software you
want to build.
• Underline the verbs if you are after procedural
code,
• the nouns if you aim for an object-oriented
program.”
Grady Booch, “What is and isn’t Object Oriented Design,” 1989
6
Approaches to Building Manageable Modules
PROCEDURAL
DECOMPOSITION
OBJECT-ORIENTED
DESIGN
Divides the problem
into more easily handled
subtasks, until the
functional modules
(subproblems) can
be coded
Identifies various
objects composed of
data and operations,
that can be used
together to solve
the problem
FOCUS ON: processes
FOCUS ON: data objects
7
Functional Design Modules
Main
Prepare
File for
Reading
Get Data
Print Data
Find
Weighted
Average
Print
Weighted
Average
Print Heading
8
Object-Oriented Design
• A technique for developing a program in which
the solution is expressed in terms of objects
– self- contained entities composed of data and
operations on that data
cout
cin
<<
>>
get
.
.
.
Private data
setf
Private data
.
.
.
ignore
9
Object-Oriented Concepts
• Code using a solution design
• Specify a system of interacting objects
• Object-oriented analysis specifies
– What to do
• Not how to do it
• Object-oriented design specifies
– Models of how it might be done
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
10
Object-Oriented Solution
• Create a good set of modules
– Store, move, alter data
– Communicate with one another
• Use classes of objects
– Combines attributes and behaviors
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
11
Principles of Object-Oriented Programming
• Encapsulation:
– Objects combine data and operations
• Inheritance:
– Classes inherit properties from other classes
• Polymorphism:
– Objects determine appropriate operations at
execution
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
12
Achieving a Better Solution
• Cohesive modules perform single well-defined
tasks
• Coupling:
– measure of dependence among modules
• Loosely coupled modules desired
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
13
Specifications
• Operation Contracts
• Unusual Conditions
• Abstraction
• Information Hiding
• Minimal and Complete Interfaces
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
14
Operation Contract
• Documents use and limitations of a method
– purpose, assumptions, input, output
• Specifies data flow
• Does not specify how module will perform its
task
• Specifies pre- and post-conditions
• Precise documentation is essential
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
15
Unusual Conditions
Options
• Assume they never happen
• Ignore invalid situations
• Guess at client’s intent
• Return value that signals a problem
• Throw an exception
!!! Has security implications !!!
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
16
Abstraction
• Separates purpose of a
module from its implementation
• Possible to use a module without knowing
implementation
• Think “what” not “how”
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
17
Information Hiding
• Tasks communicate through a slit in wall
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
18
Minimal and Complete Interfaces
• Signature
– function’s name;
– the number, order, and type of arguments;
– any qualifiers such as const
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
19
Data
• The representation of information in a manner
suitable for communication or analysis by
humans or machines
• Data are the nouns of the programming world:
– The objects that are manipulated
– The information that is processed
20
Abstract Data Type
• A collection of data and
• A set of operations on the data
• A data type whose properties (domain and
operations) are specified independently of any
particular implementation
• Carefully specify an ADT’s operations before
you implement them
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
21
Abstract Data Type
• ADT is a specification for a group of values and
the operations on those values
• A dispenser of chilled water, crushed ice, and
ice cubes
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
22
Abstract Data Type
• A wall of ADT operations isolates a data
structure from the program that uses it
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
23
Data from 3 different levels
• Application (or user) level: modeling real-life
data in a specific context. WHY
• Logical (or ADT) level: abstract view of the
domain and operations.
WHAT
• Implementation level: specific representation
of the structure to hold the data items, and
the coding for operations. HOW
Collection ordered in different ways
Viewing a library from 3 different levels
• Application (or user) level: Library of
Congress, or Baltimore County Public Library.
• Logical (or ADT) level: domain is a collection
of books;
– operations include: check book out, check book
in, pay fine, reserve a book.
• Implementation level: representation of the
structure to hold the “books”, and the coding
for operations.
Designing an ADT
• Ask the questions
• What data does the problem require?
– Names
– IDs
– Numerical data
• What operations will be done on that data?
– Initialize
– Display
– Calculations
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
27
C++ Built-In Data Types
Simple
Composite
Integral
Floating
array struct union class
char short int long enum
float double long double
Address
pointer
reference
Records
• A composite data type made up of a finite
collection of not necessarily homogeneous
elements called members or fields
• For example . . .
thisCar at Base Address 6000
.year
.maker
.price
2008
‘h’‘o’‘n’‘d’ ‘a’‘\0’ . . .
18678.92
The ADT Bag
The ADT Bag
• A bag is a container
– Contains finite number of data objects
– All objects of same type
– Objects in no particular order
– Objects may be duplicated
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
31
Identifying Behaviors
•
•
•
•
•
Get the number of items currently in the bag
See whether the bag is empty
Add a given object to bag
Remove occurrence of specific object from bag
Remove all objects from bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
32
Identifying Behaviors
• Count the number of times certain object
occurs in bag
• Test whether bag contains particular object
• Look at all objects in bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
33
Identifying Behaviors
• A CRC card for a class Bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
34
Specifying Data and Operations
• UML notation for the class Bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
35
The ADT Bag
• View code listing for Bag interface,
– Listing 1-1
• Note use of ADT Bag, Program for Card
Guessing
– Listing 1-2
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
36