Data Structure
Data structure is a particular way of
storing and organizing data in a computer so that it can be used efficiently.
There are different ways to organize the data such as organization of data into
the list, queue, stack and tree, graph and so on.
Different types of data structures are used for
different types of applications, and some are highly specialized to specific
tasks. Data structures are used in almost every program or software system.
Specific data structures are essential for many efficient algorithms, and make
possible the management of huge amounts of data, such as large databases and internet
indexing services. Some formal design methods and programming languages
emphasize data structures, rather than algorithms, as the key organizing factor
in software design.
Characteristics of Data
Structure
Data
structure
|
Advantage
|
Disadvantage
|
Array
|
Quick inserts Fast access if index known |
Slow search Slow delete Fixed size |
Stack
|
Last-in, first-out access
|
Slow access to other items
|
Queue
|
First-in, first-out access
|
Slow access to other items
|
List
|
Quick insert
Quick delete |
Slow search
|
Binary Tree
|
Quick search
Quick insert Quick delete (If the tree remains balanced) |
Deletion algorithm is complex
|
Hash Table
|
Very fast access if key is known
Quick insert |
Slow delete
Access slow if key is not known Inefficient memory usage |
Heap
|
Quick insert
Quick delete Access to largest item |
Slow access to other items
|
Graph
|
Best models real-world situations
|
Some algorithms are slow and very
complex
|
Data structure defined above are the Abstract
Data Types.
Abstract Data Types
Data type is a collection of values and a set of
operations on those values. Those collection and that operations form a
mathematical construct that may be implemented using a particular hardware or
software data structure and ADT is a basic mathematical concept that defines
the data type. ADT focuses on what it does and ignoring how it does its job. A
stack or a queue is an example of an ADT.
An
ADT consists of two parts that are
-
Value definition and
-
Operator definition
The
value definition defines the collection of values for the ADT and consists of
two parts:
-
definition clause and
-
condition clause
-
In definition clause permissible
data values are defined and condition clause is used to specify any conditions
that may be on the data values.
-
Immediately after the value
definition, operator definition is defined which describe all possible
operators that may be implemented on those data defined in definition clause.
Each operator is defined as a function with three pares
o
Header
o
Pre-condition
o
Post-condition
The header is just like C function header which consists of
header name, arguments and appropriate data type
The optional pre-condition specifies any restrictions that
must be satisfied before the operations can be applied.
The post condition specifies the actual operations done by
the operator.
and
the operator definition come immediately after the value definition. Each
operator is defined as an abstract function with three parts: a header, the
optional pre-conditions and the post-conditions.
Explain how a class acts as an ADT?
In OOP, class implements the concept
of ADT by defining both the set of values of a given type and the set of
operations that can operate on those values i.e. class can be thought as a description
of the data in the class and list of operations that operate on this data and
instructions on how to use these operations. What is excluded is the details of
how the methods carry out their tasks. End users tell what methods to call, how
to call them, and the results that should be expected, but not HOW they work.
e.g.
class Rational
{
long numerator;
long denominator;
public:
Rational add(Rational);
Rational mult(Rational);
}
Here, in above
class template, a set of values that are numerator and denominator and the set
of operations that are add and mult are declared without giving the definition
of the function.
Comments
Post a Comment