Abstract Data Types (ADTs)

Abstract Data Types (ADTs)

AU: May-19, Marks 9

The abstract data type is a triple of D- Set of domains, F - Set of functions, A - Axioms in which only what is to be done is mentioned but how is to be done is not mentioned.

In ADT, all the implementation details are hidden. In short

ADT = Type + Function names + Behavior of each function

1. ADT Operations

• While modeling the problems the necessary details are separated out from the unnecessary details. This process of modeling the problem is called abstraction. It is why represented by Fig. 3.2.1.

• The model defines an abstract view to the problem. Thus the model focuses only on problem related stuff and that you try to define properties of the problem.

• These properties include

i) The data which are affected and

ii) The operations which are identified

• Various Abstract Data Type operations are

1. Create: This operation creates the database

2. Display: This operation is for displaying all the elements of the data structure.

3. Insertion: By this operation the element can be inserted at any desired position.

4. Deletion: By this operation any desired element can be deleted from the data structure.

5. Modification: This operation modifies the desired element's value by any desired new value.

2. ADT Data Structures

The ADT operations are carried out with the help of data structure. This part describes the structure of the data used in the ADT in an informal way. Various data structures that can be used for ADT are Arrays, Set, Linked list, Stack, Queues and so on.

Examples

1. ADT for Set

If we want to write ADT for a set of integers, then we will use following method AbstractDataType Set

{

Instances: Set is a collection of integer type of elements.

Preconditions: none

Operations:

1. Store (): This operation is for storing the integer element in a set.

2. Retrieve (): This operation is for retrieving the desired element from the given set.

3. Display (): This operation is for displaying the contents of set.

}

There is a specific method using which an ADT can be written. We begin with keyword AbstractDataType which is then followed by name of the data structure for which we want to write an ADT. In above given example we have taken Set data structure.

• Then inside a pair of curly brackets ADT must be written.

• We must first write instances in which the basic idea about the corresponding data structure must be given. Generally in this section definition of corresponding data structure is given.

• Using Preconditions or Postconditions we can mention specific conditions that must be satisfied before or after execution of corresponding function.

• Then a listing of all the required operations must be given. In this section, we must specify the purpose of the function. We can also specify the data types of these functions.

 2. ADT for Arrays

AbstractDataType Array

{

Instances: An array A of some size, index i and total number of elements in the array n.

Operations:

1. Store () - This operation stores the desired elements at each successive location.

2. display () This operation displays the elements of the array.

}

Review Question

1. Define data abstraction. Write the ADT for the data structure in which the same condition can used appropriately, for checking over flow and underflow. Define all basic function of this ADT. (Hint: Check stack ADT in section 4.2) AU: May-19, Marks 9