18-08-2012, 01:45 PM
Abstract Data Types Information Hiding
Abstract Data Types.pdf (Size: 1.2 MB / Downloads: 24)
Data Types
Data types are an integral part of every programming language. ANSI-C has int,
double and char to name just a few. Programmers are rarely content with what’s
available and a programming language normally provides facilities to build new data
types from those that are predefined. A simple approach is to form aggregates
such as arrays, structures, or unions. Pointers, according to C. A. R. Hoare ‘‘a step
from which we may never recover,’’ permit us to represent and manipulate data of
essentially unlimited complexity.
What exactly is a data type? We can take several points of view. A data type
is a set of values — char typically has 256 distinct values, int has many more; both
are evenly spaced and behave more or less like the natural numbers or integers of
mathematics. double once again has many more values, but they certainly do not
behave like mathematics’ real numbers.
Alternatively, we can define a data type as a set of values plus operations to
work with them. Typically, the values are what a computer can represent, and the
operations more or less reflect the available hardware instructions. int in ANSI-C
does not do too well in this respect: the set of values may vary between machines,
and operations like arithmetic right shift may behave differently.
Abstract Data Types
We call a data type abstract, if we do not reveal its representation to the user. At a
theoretical level this requires us to specify the properties of the data type by
mathematical axioms involving the possible operations. For example, we can
remove an element from a queue only as often as we have added one previously,
and we retrieve the elements in the same order in which they were added.
Memory Management
We may have overlooked something: how does one obtain a set? Set is a pointer,
not a type defined by typedef; therefore, we cannot define local or global variables
of type Set. Instead, we are only going to use pointers to refer to sets and elements,
and we declare source and sink of all data items in new.h:
Summary
For an abstract data type we completely hide all implementation details, such as the
representation of data items, from the application code.
The application code can only access a header file where a descriptor pointer
represents the data type and where operations on the data type are declared as
functions accepting and returning generic pointers.
The descriptor pointer is passed to a general function new() to obtain a pointer
to a data item, and this pointer is passed to a general function delete() to recycle
the associated resources.