Computer Science-Data Structures :Abstract DataType (ADT)

Data Structures :Abstract DataType (ADT) Praseetha E Assistant Professor Department of Computer Science&Applications St. Mary’s College Thrissur-680020 Kerala

Data Structures,Praseetha E,St.Mary’s College Abstract Data Type (ADT)  To process data with a computer, we need to define the data type and the operation to be performed on the data.  The definition of the data type and the definition of the operation to be applied to the data is part of the idea behind an abstract data type (ADT)  ADT means to hide how the operation is performed on the data.  In other words, the user of an ADT needs only to know that a set of operations are available for the data type, but does not need to know how they are applied.

Data Structures,Praseetha E,St.Mary’s College Simple ADTs  Many programming languages already define some simple ADTs as integral parts of the language.  For example, the C language defines a simple ADT as an integer. The type of this ADT is an integer with predefined ranges.  C also defines several operations that can be applied to this data type (addition, subtraction, multiplication, division and so on).  C explicitly defines these operations on integers and what we expect as the results. A programmer who writes a C program to add two integers should know about the integer ADT and the operations that can be applied to it.

Data Structures,Praseetha E,St.Mary’s College Complex ADTs  Although several simple ADTs, such as integer, real, character, pointer and so on, have been implemented and are available for use in most languages, many useful complex ADTs are not.  As we will see in this session, we need a list ADT, a stack ADT, a queue ADT and so on. To be efficient, these ADTs should be created and stored in the library of the computer to be used.

Data Structures,Praseetha E,St.Mary’s College Stack  A stack is a restricted data structure in which all additions and deletions are made at one end, the top.  If we insert a series of data items into a stack and then remove them, the order of the data is reversed. This reversing attribute is why stacks are known as last in, first out (LIFO) data structures. Fig: Three representations of stacks

Data Structures,Praseetha E,St.Mary’s College Operations on stack There are two basic operations can be applied to a stack:  Push operation  Pop operation The push operation The following shows the format. Fig :Push operation

Data Structures,Praseetha E,St.Mary’s College The pop operation The following shows the format. Fig :Pop operation  The pop operation deletes the item at the top of the stack.

Data Structures,Praseetha E,St.Mary’s College Stack: Applications 1.Parsing 2.Recursive Function 3.Expression Evaluation 4.Expression Conversion 1.Infix to Postfix 2.Infix to Prefix 3.Postfix to Infix 4.Prefix to Infix 5.Towers of hanoi

Data Structures,Praseetha E,St.Mary’s College Queue  A queue is a linear list in which data can only be inserted at one end, called the rear, and deleted from the other end, called the front.  These restrictions ensure that the data is processed through the queue in the order in which it is received. In other words, a queue is a first in, first out (FIFO) structure. Fig: Two representation of queues

Data Structures,Praseetha E,St.Mary’s College Operations on queue There are two basic operations that can be applied to a queue:  Enqueue operation  Dequeue operation The enqueue operation The following shows the enqueue operation: Fig: The enqueue operation

Data Structures,Praseetha E,St.Mary’s College The dequeue operation  The dequeue operation deletes the item at the front of the queue. The following shows the enqueue operation: Fig: The dequeue operation

Data Structures,Praseetha E,St.Mary’s College Queue :Applications Queue is used when things don’t have to be processed immediately, but have to be processed in First In First Out order. 1. When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling. 2. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.

Data Structures,Praseetha E,St.Mary’s College Linked list  Linked list is a list in which operations, such as insertion and deletion, can be done anywhere in the list-at the beginning, in the middle or at the end. Fig. shows a general linked list. Fig: Linked list

Data Structures,Praseetha E,St.Mary’s College Operations on Linked list There are two basic operations that can be applied to a linked list:  Insert operation  Delete operation The insert operation  Since in a general linked list, insertion can be done in any position. To determine where the element is to be placed, searching is needed. Fig:The insert operation

Data Structures,Praseetha E,St.Mary’s College The delete operation  Deletion from a linked list also requires that the list be searched to locate the data to be deleted. After the location of the data is found, deletion can be done. Fig: The dequeue operation The following shows the Eg:

Data Structures,Praseetha E,St.Mary’s College Linked list :Applications 1.Implementation of stacks and queues 2.Implementation of graphs : Adjacency list representation of graphs is most popular which is uses linked list to store adjacent vertices. 3.Dynamic memory allocation : We use linked list of free blocks. 4.Performing arithmetic operations on long integers 5.Manipulation of polynomials by storing constants in the node of linked list 6.Representing sparse matrices

Data Structures,Praseetha E,St.Mary’s College Tree  A tree consists of a finite set of elements, called nodes (or vertices) and a finite set of directed lines, called arcs, that connect pairs of the nodes. Fig: Tree representation

Data Structures,Praseetha E,St.Mary’s College  Each node in a tree may have a subtree. The subtree of each node includes one of its children and all descendents of that child. Figure shows all subtrees for the above tree Fig: Subtrees

Data Structures,Praseetha E,St.Mary’s College Operations on tree: There are three basic operations that can be applied on a tree:  Insert operation  Delete operation  Traversal operation

Data Structures,Praseetha E,St.Mary’s College Tree traversals  A tree traversal requires that each node of the tree be processed once and only once in a predetermined sequence. There are 3 approaches used in traversing a tree : Fig: Tree representation

Data Structures,Praseetha E,St.Mary’s College Tree :Applications 1.Heap is a tree data structure which is implemented using arrays and used to implement priority queues. 2.B-Tree and B+ Tree : They are used to implement indexing in databases. 3.Syntax Tree: Used in Compilers. 4.Expression evaluation

Data Structures,Praseetha E,St.Mary’s College  An arithmetic expression can be represented in three different formats: infix, postfix and prefix.  In an infix notation, the operator comes between the two operands.  In postfix notation, the operator comes after its two operands.  In prefix notation it comes before the two operands. These formats are shown below for addition of two operands A and B. Expression tree

Data Structures,Praseetha E,St.Mary’s College Fig: Expression tree

Data Structures,Praseetha E,St.Mary’s College Reference : “Data Structures and Program Design in C” by Kruse Robert L “Data Structure Using C” by A K Sharma “Data structures” by Seymour Lipschutz

Computer Science-Data Structures :Abstract DataType (ADT)

More Related Content

What's hot

Similar to Computer Science-Data Structures :Abstract DataType (ADT)

More from St Mary's College,Thrissur,Kerala

Recently uploaded

Computer Science-Data Structures :Abstract DataType (ADT)