Data Structure & Application

Advantages of ADT

2011-09-11T15:18:00.002+05:00

Some advantages of ADT over the conventional data structures are

ADT is reusable, robust, and is based on principles of Object Oriented Programming (OOP) and Software Engineering (SE)
An ADT can be re-used at several places and it reduces coding efforts
Encapsulation ensures that data cannot be corrupted
Working of various integrated operation cannot be tampered with by the application program
ADT ensures a robust data structure

ADT approach is based on the SE concepts of coupling and cohesion

Coupling property determines

How strongly two separate parts of programs are linked together
Extend to which changes made in one part impacts the other parts of a software module

Well designed software has a minimum coupling. An ADT promotes weak coupling.

Cohesion determines how well-integrated are components of software. An ADT inherently promotes maximum cohesion.

Abstract Data Types (2)

2011-09-11T14:59:00.001+05:00

All built-in primitive data types are in fact abstrat data types
In floating point type, for example we cannot add a new operation, say, exponentiation
We cannot enhance or shrink the set of allowed values
ADT does not specify how the data structure would be coded
It does not describe whether data elements are stored in consecutive or disjoint locations
The implementation details are hidden from the application program

In software module, an ADT can be viewed as layer between application that uses it and a component that implements ADT.

Some high level languages provide support for ADT in different ways

C has built-in struct type
In C++, a class construct can be used
In Java, an ADT can be expressed as Interface

Abstract Data Types (1)

2011-09-10T19:00:00.001+05:00

An Abstract data type (ADT) combines the description of data structure, and associated operations
ADT has following characteristics:

Provides a description of element in terms of data types
Defines relationship among individual elements
Valid operations and parameters to be passed
Error conditions associated with the operations

For Example an ADT stack can be defined by pakaging together the following operations

Push - Inserts an item into the stack stk
Pop - Returns a data item from stack stk
Peek() - Returns top most element with out removing it from the stack
Size() - Returns no of elements currently in the stack
isEmpty() - Returns true if stack is empty, and false otherwise
Set of operations associated with ADT is called interface
Elements of ADT data structure are manipulated through an interface
The figure shows how elements of ADT are accessed using interface
Implementation of operations and data items are hidden from the application program

Abstract Data Types Part (2) Coming..

Storage Structures

2011-09-10T18:50:00.001+05:00

It describes how the data items are stored in the memory.

It provides a map of how data elements are allocated memory space
Elements are stored in conseccutive or in disjoint storage locations
Each location is identified by unique number called memory address
The figure contigous allocation of storage space to set of characters

To access any element, the address of the first element is needed

As shown in the figure character A, B, C are stored in non-contigous locations
Each character A is followed by integer 3000, which is the storage address of character B.

User-Defined Data Structures

2011-09-10T08:30:00.001+05:00

Stackes, queues and trees are classical general purpose data structures. Some programming languages, such as JAVA, provide built-in support for some of these structures.

We can also create our own data structures, which are called user-defined. For example we can define a data structre to store recored of 100 employees.

Each record consist of employee's name, deignation and salary
The code fragment in C might be as follows:

The elements of employee array can be accessed using C notation as follows:

employ[0]<-name, employ[0]<-title, employ[0]<-salary

Operation on Data Strucutures

2011-09-10T08:24:00.001+05:00

In order to process elements of a data strucutre some kind of operation is required. A basic operation involves creating a data structure, and reserving storage space for the elements.
A another operation is deleting the data structure, which removed the data items and releases the allocated storage space.

Other common operation are: inserting, sorting, searching, merging, traversing.

Inserting: involves adding a data item in a specified position

Sorting is arranging of data items in specific order

Searching means finding an item which matches with a given key

Merging involves combining two sets of data items with according to some criterion

Traversing means accessing each element of a data strucutre

Introduction to Data Structure

2011-09-10T08:18:00.001+05:00

Data structure are classified into two types

Linear Data Structure
Non-Linear Structure

1) Linear Data Structure:

A structure in which data element are organized in sequence is referred to as linear

Example are: arrays, linked lists, stacks, and queues.
In a stack, last item added can be taken off first and In a queue an item can be added at one end, and removed from the other end.

2) Non-Linear Data Structure:
Relationship among elements can be hierarchical. Linkage may be single or bi-directional

Common example are: Trees and Graphics. See figure

It contains an information field and a link field, which is address of related element. Trees can be binary, A V L, Red and Black, Splay, B-trees or heaps.

Graph is set of data items, called vertices or nodes, connected by links termed as edges or arcs

Data Types (3)

2011-09-09T08:20:00.001+05:00

In C/C++ Ada and Pascal string data are stored with a special delimiter
Forton 90 and Visual Basic supports stings as primitive data types
Basic operations on strings are assigning, joining and comparing

Primitve and composite data types are suffiecient solving simple problems
The ear;y computer applications depended on the vuilt in data types of programming langyages
Primitve types are not always sufficient to solve advanced problems
Need for advanced data types arose due to the new paradigm of object oriented approach
Data structures are meant to serve these special needs
It is a programming construct that stores a collection of data items
Dta structure are not just an extention of composite data ypes

Thow significant diferences are
First data structure encompassed primitve and compostire data types
Second, data structures it includes some kind of relationship among the data items. For example, string has definite order of organized character.

Data Types (2)

2011-09-09T08:19:00.000+05:00

Primitive Data Types:
Primitive data types are described in a program by language specific keywords

Primitive data type in Java
Java defines eight primitives

int
char
byte
short
long
float
Boolean
double

Primitive data type in C++
C/C++ basic data types are :

int
float
char
double
short
long
signed
unsigned

Primitive Data in Visual Basic

Integer
Long
Single
Souble
Boolean
Byte
Dim
Private
Public
Static

Now we discuss the second type of Data Types
Composite Data Types
Complex data types are defined using combination of priimitve types. Composite data types can be arrays, vector and strings.
Array : An array is a collection of homogenous data types
Vectors: Vector are mathematical representation of arrays
String: A strings is a combination of characters

Data Types (1)

2011-09-08T18:47:00.000+05:00

Data types are required for efficient coding of programs. There are two types

Primitive Data types
Composite Data types

Primitive Data Types:
Primitive data types includes Boolean, which stores logical values true or false. Operation on Boolean data type include AND, OR and NOT. Ranges of primitives data types depend on the number of bits allocated by the compiler and hardware circuitry.

Typocally an integer type ranges from -2,147,483,648 to 2,147,483,647.
Character type can range from 0 to 65,000

Operation on primitives types are often included in the CPU instructions set. On some systems the primitives data types are implemented using software routines.
On small computers, for example, real number are often processed using software instructions.

Table below summarizes ranges of different primitive data types.

More Coming soon

Introduction to Data Structure & Application

2011-09-08T18:26:00.000+05:00

What is Data Structure ?
The study of various ways of organizing data in a computer called Data structure.

Information is manipulated by systematic and step by step procedure call algorithm.
Manipulation involves adding, searching, deleting, rearrange data items.

See figure.

Data Structure are used in several disciplines
Used by operating system, compilers and database management systems, data communications and so on
Algorithm together with data structures are used in several applications.
Common application are: image processing, digital signal processing, simulation, numerical computations, cryptography, data compressions and genetic studies.

Next Lesson is "Data Types"