Chapter 11: Abstract Data Types and
Encapsulation Concepts
•
•
•
•
•
•
•
The Concept of Abstraction
Introduction to Data Abstraction
Design Issues for Abstract Data Types
Language Examples
Parameterized Abstract Data Types
Encapsulation Constructs
Naming Encapsulations
11-1
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
11-2
Introduction to Data Abstraction
• An abstract data type is a user-defined
data type that satisfies the following two
conditions:
– The representation of, and operations on,
objects of the type are defined in a single
syntactic unit
– The representation of objects of the type is
hidden from the program units that use these
objects, so the only operations possible are
those provided in the type's definition
11-3
Advantages of Data Abstraction
• Advantage of the first condition
– Program organization, modifiability
(everything associated with a data structure is
together), and separate compilation
• Advantage of the second 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
11-4
Example of Implementation hiding
• A bounded buffer with indexes front & rear:
• The public view is different from the private view
(implementation)
11-5
Design Issues
• A syntactic unit to define an ADT
• Built-in operations
– Assignment
– Comparison
• Common operations
– Accessors
– Constructors
– Destructors
• Parameterized ADTs
11-6
Language Examples: Ada
• The encapsulation construct is called
packages
– Specification package (the interface)
– Body package (implementation of the entities
named in the specification)
• Two ways for Information Hiding
– The representation of type appears in a part of the
specification called the private part
• More restricted form with limited private types:
objects of this type have no built-in operations
– Define the ADT as a pointer and provide the pointedto structure’s definition in the body package, whose
entire contents are hidden from clients.
11-7
An Example in Ada
package Stack_Pack is
-- public interface
type stack_type is limited private;
max_size: constant := 100;
function empty(stk: in stack_type) return Boolean;
procedure push(stk: in out stack_type; elem:in Integer);
procedure pop(stk: in out stack_type);
function top(stk: in stack_type) return Integer;
private -- hidden from clients
type list_type is array (1..max_size) of Integer;
type stack_type is record
list: list_type;
topsub: Integer range 0..max_size) := 0;
end record;
end Stack_Pack
11-8
Language Examples: C++
• Based on C struct type and Simula 67
classes
• The class is the encapsulation device
• 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
11-9
Language Examples: C++ (continued)
• Information Hiding
– Private clause for hidden entities
– Public clause for interface entities
– Protected clause for inheritance (see Ch 12)
11-10
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 num) {…};
void pop () {…};
int top () {…};
int empty () {…};
}
void main() {.......
stack stk; //Create an instance of the stack class
..........
}
11-11
Language Examples: C++ (continued)
• Constructors:
– Name is the same as the class name
– Implicitly called when an instance is created
– initialize the data members of instances (they do not create
the objects)
– May also allocate storage if part of the object is heapdynamic
– Can include parameters to provide parameterization of the
objects
– Example:
struct Complex { float re; float im;
Complex(float r, i) {re = r; im= i;}
};
Complex x (1, 2);
//need to give parameters for the
//constructer
11-12
Language Examples: C++ (continued)
• Destructors
– Name is the class name, preceded by a tilde (~)
– Implicitly called when the object’s lifetime ends
– cleanup after an instance is destroyed; usually
just to reclaim heap storage
11-13
Language Examples: C++ (continued)
• A friend declaration within a class gives
nonmember function access to the private
members of the class.
– Necessary in C++
• See the next two pages for an example.
– The class List defines a circularly linked list
• push: add to the front
• put: add at the back
– The class Cell is used to form lists.
11-14
Example of a circularly linked list
• The definition of the class Cell:
class Cell {
int info;
Cell * next;
Cell (int i) {info = i; next =
this;}
Cell(int i, Cell * n) {info =
i; next = n; }
friend class List;
};
11-15
Example of a circularly linked list
(cont)
• The definition of the class List:
class List {
cell *rear;
public:
void put(int x) {rear->info = x;
rear = rear->next =
new Cell(0, rear->next);};
void push(int x) {rear->next =
new Cell(x, rear->next);
int pop ( );
int empty ( ) {return rear == rear-> next;}
List( ) {rear = new Cell(0);}
~List( ) { while (!empty( )) pop( );}
};
int List::pop( ){
if (empty( )) return 0;
Cell *front = rear->next; rear->next = front->next;
int x = front->info; delete front; return x;}
11-16
Language Examples: Java
• Similar to C++, except:
– All user-defined types are classes
– All objects are allocated from the heap and
accessed through reference variables (see the
next page)
– Individual entities in classes have access control
modifiers (private or public), rather than clauses
– Java has a second scoping mechanism, package
scope, which can be used in place of friends
• All entities in all classes in a package that do not
have access control modifiers are visible throughout
the package (also see page 28)
11-17
An Example in Java
class StackClass {
private:
private int [] stackRef;
private int maxLen, topIndex;
public StackClass() { // a constructor
stackRef = new int [100];
maxLen = 99;
topPtr = -1;
};
public void push (int num) {…};
public void pop () {…};
public int top () {…};
public boolean empty () {…};
}
...........
StackClass myStack = new StackClass();
11-18
Parameterized Abstract Data Types
• Parameterized ADTs allow designing an
ADT that can store any type elements
• Also known as generic classes
• C++ and Ada provide support for
parameterized ADTs
11-19
Parameterized ADTs in C++
• Classes can be somewhat generic by writing
parameterized constructor functions
• The following makes the stack generic in size
– Change the constructor function in page 12 as follows:
stack (int size) {
stkPtr = new int [size];
maxLen = size - 1;
top = -1;
};
…
stack stk(100);
11-20
Parameterized ADTs in C++
(cont)
• The following makes the type of the stack generic
– element of the stack has the type Type:
template <class Type> class stack{
int topPtr;
int maxLen;
Type * stkPtr;
public:
Stack(){stkPtr = new Type[100]; maxLen = 99;
topPtr = -1;}
Stack(int size){stkPtr = new Type[size];
maxLen = size-1; topPtr = -1;}
~Stack( ) {delete stkPtr;}
void push(Type a) {stkPtr[++topPtr] = a;}
Type pop( ) {topPtr--; return stkPtr[topPtr+1];}
};
11-21
Parameterized ADTs in C++
(cont)
• When the class is used as a type name, it must be supplied a
type as an explicit parameter, e.g.,
stack <int> s (99);
stack <char> t (80);
• If the body of a member function appears outside a class
declaration, then a type parameter has to be introduced
afresh, e.g.,
template <class x> void stack <x>::push(x a){
topPtr++;
stkPtr[topPtr] = a;
}
Another name x can be used instead of T
11-22
Overloaded Subprograms
• An overloaded subprogram is one that has
the same name as another subprogram in
the same referencing environment
– Every version of an overloaded subprogram has
a unique protocol
• C++, Java, C#, and Ada
– include predefined overloaded subprograms
– allow users to write multiple versions of
subprograms with the same name
– usually used to define overloading constructors
11-23
Encapsulation constructs for large
programs
• Large programs have two special needs:
– Some means of organization, other than simply
division into subprograms
– Some means of partial compilation (compilation
units that are smaller than the whole program)
• Obvious solution: a grouping of
subprograms that are logically related into
a unit that can be separately compiled
(compilation units)
• Such collections are called encapsulation
11-24
Encapsulation in C
• Files containing one or more subprograms
can be independently compiled
• The interface to such file (library) is placed
in a header file
• The header file is used in the client code,
using the #include preprocessor
specification, so that references to
functions and data in the client code can be
type-checked.
11-25
Ada Packages
• Ada specification packages can include
any number of data and subprogram
declarations
• Ada packages can be compiled separately
• A package’s specification and body parts
can be compiled separately
11-26
Naming Encapsulations
• Large programs may consist of many
independently written codes, where naming
conflicts might occur.
• A naming encapsulation define name scopes that
assist in avoiding name conflicts.
• C++ Namespaces
– Can place each library in its own namespace and qualify
names used outside with the namespace
– Example of declaration:
namespace MyStack{…}
– Example of references:
using MyStack::topPtr;
using namespace MyStack;
11-27
Naming Encapsulations
(cont)
• Java Packages
– Packages can contain more than one class
definition;
– Clients of a package can use fully qualified
name or use the import declaration
– Example of declaration:
package myStack;
– Example of references:
import myStack.*
import myStack.topPtr;
11-28
© Copyright 2024 ExpyDoc
