View Full Document


Unformatted text preview:

Abstract Data Types Contents 1 Description and and definition on an ADT 2 Terminology 3 Notation 4 Example 1 ADT WaterTank 5 Implementing an ADT description 6 Example 2 ADT Bag 7 Interface Bag Abstract Data Types An Abstract Data Type ADT is a description of the operations performed on a collection of data It has the following components Name of the ADT Types represented in the collection of data Each type has previously been defined in an ADT or is a well known primitive type Functions that operate on the data Functions will specify the domain parameters and range return type Preconditions for any function that is not a total function Post conditions for each of the functions Abstract Data Types Terminology Total Function A Total Function is one that is defined for every value in the domain Correspondingly Partial Function is a function that is defined only on a subset of the domain Examples SQR square is a function that is defined for all real numbers SQR Real Real SQRT square root is a partial function on the real numbers SQRT Real Real Partial functions have a precondition specifying the subset of the domain over which they are defined The precondition for SQRT is that it is defined only for real numbers greater than or equal to 0 Terminology Abstract Data Types For container classes transformations such as remove are usually partial functions and observations such as isEmpty are almost always total functions Given the following function remove Container Integer Container This partial function expresses the fact that remove takes as its arguments a Container object and an integer index and returns a transformed container It is a partial functions because it is not defined on the empty container and is only defined over integers greater than 0 and less than the size number of items contained of the container Note In this terminology a Container is mapped into another container much as SQR maps a real into a different real The transformed container has a different

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...

Join to view Abstract Data Types and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Abstract Data Types and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?