Advantages of ADT

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)

• 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)

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

1. Provides a description of element in terms of data types
2. Defines relationship among individual elements
3. Valid operations and parameters to be passed
4. 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

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

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

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

Data structure are classified into two types

1. Linear Data Structure
2. 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)

• 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)

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

Primitive data type in Java
Java defines eight primitives

1. int
2. char
3. byte
4. short
5. long
6. float
7. Boolean
8. double

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

1. int
2. float
3. char
4. double
5. short
6. long
7. signed
8. unsigned

Primitive Data in Visual Basic

1. Integer
2. Long
3. Single
4. Souble
5. Boolean
6. Byte
7. Dim
8. Private
9. Public
10. 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)

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

1. Primitive Data types
2. 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

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"