|
|
|
|
|
|
Data abstraction is a technique that allows us to focus on the important properties of a data structure, while leaving less important aspects unspecified. An abstract data type (ADT) consists of a data structure declaration, plus a set of operations involving the data structure. The client, or user, of an ADT calls these operations to create, destroy, manipulate, and interrogate objects or instances of the abstract data type.
Dr. David Parnas pioneered this specific technique. The key idea is called information hiding, or data encapsulation. ADT modules maintain private data that is accessible outside the module only through well-defined operations. Parna's goal was to provide a software design technique that would permit many parts of a large project to be worked on independently, yet still fit together and function correctly.
The main design an be carried out using the ADT operations, without deciding how to implement these operations. After the algorithm is designed at this level, we can undertake an analysis to count how many of each ADT operation the algorithm uses. The ADT operations can then be steered in a direction that makes the more frequently used operations the least expensive.
A programming language supports data abstraction as it permits the programmer to restrict clients' access to an abstract data type: access is restricted to the defined operations and other public parts of the ADT class. The maintenance of private data is called encapsulation or information hiding, which provides a tool for the programmer to ensure that certain invariants of the ADT objects are preserved.
For more information on Data abstraction: Data Abstraction
Also read book by Dr.
Robert W. Sebesta
The Specifications of an ADT describe how the operations behave, in terms that are meaningful to the clients of ADT. They should avoid reference to private instance fields as the clients are unaware of them. They describe the logical relationships among the public parts of the ADT, such as operations and constants. They can be broken into preconditions and postconditions. Preconditions are assumed true when the operation is called and is stated in terms of parameter names. Postconditions are statements that the client may assume to be true when the operation returns and should also be stated in terms of parameter names. They are also called objectives of the operations. Comments beginning with "/**" begin a javadoc comment.
Types of ADT operations:
Constructors
create a new object and return a reference to it.
Access function
return information about an object, but do not modify it.
Manipulation procedures modify
an object, but do not return information.
After an object is created, an operation may either modify the state of the object or return information about its state, but not both.
ADT Design Techniques
For simple and standard ADTs, such as linked lists, stacks, trees, and FIFO queues, the ADT used during design can be carried right through to the final implementation. Sometimes other ADTs may be clients of these standard ADTs and use them in building blocks. Fore more complex or nonstandard ADTs, like the Dictionary, Priority Queue, and Union-Find, the ADT can be used during design for its logical advantages (simplifying the analysis of correctness), but then for the final implementation "unwrap" the ADT and implement a special case for the algorithm that uses it.
Elementary ADTs - Lists and Trees
Recursive ADTs
An ADT is recursive if any of its access functions returns the same class as the ADT. (Some part of the object is the same type as the ADT). The ADT has a constructor that has a parameter of the same class as the ADT. (It has a nonrecursive constructor, a constant function that takes no parameters also). An object in a recursive data type is a structure that includes not only the fields that are immediately accessible, but also the fields that are indirectly accessible through access functions in the ADT, some of which return objects of the same type as the ADT.
The List ADT
The kind of list needed most often in algorithms, particularly algorithms on graphs, is a list of integers. The specification for intList ADT is:
intList cons(int newElement, intList oldList)
Precondition: none
Postcondition: If x = cons(newElement, oldList)
then:
1. x refers to a newly created object;
2. x != nil;
3. first(x) = newElement;
4. rest(x) = oldList;
int first(IntList aList)
Precondition: aList != nil.
IntList rest(IntList aList)
PreCondition: aList != nil.
IntList nil
Constant denoting the empty list.
Binary trees have many applications. They are nonlinear generalization
of lists; instead of having one way to continue to another element, there
are two alternatives that lead to two different elements. A Binary
tree T is a set of elements called nodes, that is either empty or satisfies
two conditions:
1. There is a node r at the root
2. The remaining nodes are divided into two disjoint
sets, L and R, each of which is a binary tree. L is called the left
subtree of T, and R is called the right subtree of T.
Examples of Binary Trees are shown below
If a node v is the root of a binary tree T and a node w is the root of the left (right) subtree of T, then w is called the left (right) child of v and v is called the parent of w; there is a directed edge from v to w. The direction in the absence of an arrowhead is downward. The depth of the root is 0 and the depth of any other node is one plus the depth of its parent. A complete binary tree is a binary tree in which all internal nodes have degree 2 and all leaves are at the same depth. The height of a binary tree is the maximum of the depths of its leaves. The height of any node in a binary tree is the height of the subtree of which it ts the root. In the figure above, the depth of 4 is 1 and its height is 2. The depth of 7 is 2 and its height is 1.
A traversal of a binary tree is like a boat journey around the tree, starting at the root. Each node is like an island, and each edge is like a bridge, too low for the boat to pass under. The boat starts at the node and sails along edges, visiting nodes along the way. The first time a node is visited (white dot) is called its preorder time, the second time it is visited (gray dot, returning from the left child) is called its inorder time, and the last time it is visited (black dot, after returning from its right child) is called its postorder time. For the tree graph above, the traversal orderings are:
Preorder (white dot)
2 4 7 10
15 6 8 9
13 11
Inorder (gray dot)
10 7 15 4
8 6 2
13 9 11
Postorder (black dot)
10 15 7 8
6 4 13 11
9 2
For More Information: Binary Trees
The Tree ADT
A general out-tree is a nonempty structure with nodes and directed edges. The root has no incoming edge, while all other nodes have one incoming edge. There is a path from the root to all other nodes. There is no restriction on the number of outgoing edges (in Binary trees there cannot be more than two). A forest is a collection of separate trees. Every node is the root of its own subtree, consisting of all the nodes it can reach including itself. Each edge goes from parent to the child. If node v is parent of node w, then the tree rooted at w is a principal subtree of the tree rooted at v. Each principal subtree has fewer nodes than the whole tree. The subtrees do not have an inherent order. There is no representation for an empty general tree. If the edges are oriented towards the root rather than away, the structure is an in-tree, with edges going from child to parent.
Stacks and queues keep track of tasks that need to be done in situations where one task might generate an unpredictable number of other tasks.
Stack ADT
A stack is a linear structure where insertions and deletions are always made at one end, called the top. This updating policy is called Last In First Out (LIFO). The top item is the one most recently inserted, and only this element can be inspected. To push an item on a stack is to insert it. To pop the stack means to delete the top entry. The top element of a nonempty stack can be accessed with top. If the maximum size to which the stack might grow is not known in advance, an array-doubling technique can be used to expand its size.
For more details click the following two links: Stack ADT Lecture Notes
Queue ADT
A Queue is a linear structure in which all insertions are one at one end, called the rear or back, and all deletions are one at the other end, called the front. Only the front element can be inspected. This updating policy is called First In First Out (FIFO). The manipulation procedures are enqueue to insert and dequeue to delete. A queue may be implemented efficiently using an array. An array-doubling technique can be used to expand its size.
For more details click: Queue ADT Slides of queues
A dynamic set is a set whose elements change during the course of the algorithm using the set. The object of the algorithm is to build the set itself. But it needs to access the set as it is being constructed to determine how to continue the construction. Set of operations include priority queues, collections of disjoint sets requiring union and find operations, and dictionaries. Dynamic sets impose the most rigorous requirements on their data structures. It is not possible to implement all the needed operations in constant time.
Priority Queue ADT
In a priority queue element order is related to each element's priority, rather than its chronological arrival time. As each element is inserted, it is inserted in order of its priority. The one element that can be inspected and removed is the most important element currently in the priority queue. The notion of priority can be either that the most important element has the smallest priority (a cost viewpoint, which is prevailing in optimization problems) or the largest priority (a profit viewpoint)
For more information try the following links: Priority Queue ADT Priority Queue
Union-Find ADT for Disjoint Sets
Initially all elements of interest are placed in separate singleton sets with the constructor operation create or they are added individually with the manipulation procedure makeSet. The find access function returns the current set id of an element. Through a union operation, the two sets can be combined, after which they no longer exist as separate entities. Therefore, no element can be in more than one set.
For more information: Union_Find ADT Union -Find Blob Coloring
Dictionary ADT
A dictionary is a general associative storage structure. Items have an identifier and certain information that needs to be stored and retrieved. There is no implied order for the identifiers. Any stored information can be retrieved at any time. The Dictionary ADT is used in the design of dynamic programming algorithms and for recording external names (strings read from input) so that a program can determine when it has seen a name before and when it is seeing it for the first time.
For more information: Dictionary ADT