DATA STRUCTURES

UNIT-I
INTRODUCTION
TO
DATA STRUCTURES

DATA AND INFORMATION

DATA : value or set of values
INFORMATION: meaningful data or
processed data
Eg:
Data Information
34 - Age of a person
12/01/2001Date of birth

INFORMATION AND ITS

STORAGE REPRESENTATION
STORAGE OF INFORMATION
- TWO TYPES OF MEMORY UNITS
OPERATIONAL UNITS
STORAGE UNITS

Operational Unit:
Register: temporary storage
present in CPU
aids in arithmetic calculations
stores operands and results
Storage Units:
permanent storage
store instructions and data
main memory, secondary memory
Main memory : semiconductor memory
has voltage representation
stored in flip-flops(2-state device)
Secondary : magnetic core memory

DATA STRUCTURE
the organization of data
and its storage allocations in a computer

PRIMITIVE DATA STRUCTURES

Data structures that normally are directly operated
upon by machine-level instructions are known as
primitive data structures.
eg: integers, reals, logical data, character data,
pointer and reference
Non-primitive data structures are more complex
data structures, derived from the primitive data
structures eg: arrays

Operations on data structures

 CREATION
int a;
Creates memory space for integer variable a
DESTROY
Destructor function in C++ ; free( ) in C
Useful for efficient usage of memory
SELECT
To access data within data structure
UPDATE
int a=2;
To change data in the data structure

CLASSIFICATION OF DATA STRUCTURES

Linear DS: traverses the data elements sequentially, in which only one data
element can directly be reached.
Non-linear DS: Every data item is attached to several other data items in a way
that is specific for reflecting relationships. The data items are not arranged in a
sequential structure.

CONCEPTS & TERMINOLOGY FOR

NON-PRIMITIVE DS
Non-primitive DS: arrays, lists, files
Array: ordered set of fixed no. of objects;
no insertion and deletion operation (no change in array size)
List : ordered set of variable no.of elements, with
insertion, deletion, combine, split, copy, sort,
search operations
File : large list stored in external memory of
computer

Obtaining address of an element:

computed address :
using description of data being sought
Eg: array element
link/pointer address:
storing data in known memory of computer
eg: pointer in a linked list

ARRAYS
DEFINITION
Is a finite and ordered collection of homogeneous data
elements
Finite: has limited no. of elements
Ordered: elements are stored one by one in contiguous
memory locations
Homogeneous: all elements are of the same data type
Example:
An array of integers to store age of students
An array of strings to store student names

TERMINOLOGY
SIZE no. of elements in an array
TYPE data type of elements
BASE address of memory location
where first element is stored

..

456
455
454
453

Base address

TERMINOLOGY.
INDEX all elements in an array are
referenced by a subscript
eg: a[i], where i=index

Index is always an integer value

RANGE OF INDEX indices vary from lower
bound (L) to upper bound (U) called boundary of
the array

eg: int A[100]

range : 0 - 99

TERMINOLOGY.
Index of ith element is A[i] = L + i 1
To get index of 3rd element:
0+31=2
Size of array : U L + 1
To get the size of array A[5]
40+1=5
WORD size of an element
Word size varies from machine to machine

ONE-DIMENSIONAL ARRAY
If only one subscript or index is required
to reference all the elements in an array,
then the array is termed one-dimensional
array

MEMORY ALLOCATION
Physical representation of one-dimensional array
1000

A[0]

Address of A[1]=
=1000 + (1 0 ) * 4
=1004

.
.

where M = base address

i = index
L = lower bound
w = word length

1008

.
.

A[
Address ( A[i] ) = M + ( i L ) * w1]

1004

100
A[100]

MEMORY ALLOCATION .
Address mapping between logical and physical views of an array

Address ( A[i]) = M + (i L ) * w
where M=base address
L=lower bound
w=word length

OPERATIONS ON ARRAY
Traversing
Sorting
Searching
Insertion
Deletion
Merging

Algorithm..

Traversing
This operation is used to visit all the elements in the array
Algorithm TRAVERSE_ARRAY( )
Input: An array A with elements
Output: According to PROCESS ( )
Data structure: Array A [ L U ]

// L = lower bound; U = Upper bound

Steps:
1. i = L
2. While i <= U do
1. PROCESS A[i] //procedure to perform an action Eg: display element on
screen

2. i=i+1
3. EndWhile
4. Stop

SortingThis operation is used to arrange the elements in

the array in ascending or descending order
Algorithm SORT_ARRAY( )
Input: An array A with integer elements
Output: Array A with elements in an order according to ORDER ( )
Data structure: Array A [ L U ]
bound

// L = lower bound; U = Upper

Sorting
Steps:
1. i = U
2. While i >= L do
1. j= L
2. While j < i do
1. If ORDER(A[j], A[j+1])=FALSE // procedure to check if
elements are in order
1. SWAP (A[j],A[j+1])
2. EndIf
3. j=j+1
3. EndWhile
4. i=i-1
3. EndWhile
4. Stop

// interchange the elements

SearchingThis operation is used to search for an element in the array

Assumptions: Let the array A be unordered.
Algorithm : SearchArray(KEY)
Input :KEY is the element to be searched
Output:Index of KEY in the arrayA, or failure message
Data Structure: Array A [ L . U ] // L=lower bound & U=upper bound of
A

Searching

INSERTION.
element into the array

This operation is used to insert an

Insertion ..

Algorithm : InsertArray(KEY, LOCATION)

Input:KEY is item to insert,
LOCATION is index where KEY is to be inserted
Output: The arrayAwith KEY element
Data Structure: Array A [ L . U ] // L=lower bound & U=upper bound of A

Insertion

While i >= LOCATION do

DELETIONThis operation is used to delete

an element into the array

Deletion

Algorithm DELETE(KEY)
Input:KEY is the element to be deleted
Output: ArrayAwithout KEY element
Data Structure: Array A [ L . U ] // L=lower bound & U=upper bound of
A

Deletion

MERGING

This operation is used to compact the

elements from two different arrays into a single array

Merging

Algorithm MERGE(A1, A2, A)

Input:Two arrays A1[L1.U1] and A2[L2.U2]
Output: Resultant Array A[LU] where L=L1 and U=U1+ ( U2-L2+1)
when A1 is appended after A2
Data Structure: Array structure

Merging

APPLICATIONS OF
ARRAYS
To store students records:
maintains 6 arrays;

array size = no.of students in the class

MULTI-DIMENSIONAL ARRAYS :
DIMENSIONAL ARRAYS

TWO-

-Collection of homogeneous elements ordered in a

number of rows and columns
m=rows
n=columns
aij: represents element at row i, col j
-Example:
Rows = 3 ; columns = 4

Memory representation of a matrix

-Matrices are stored in contiguous memory locations
- Two ways of storing matrix in memory:

- ROW major order:

elements stored on a row-by-row basis
- COLUMN major order:
Elements are stored on a column-bycolumn basis

Example:
Consider matrix A of order 3 x 4:

REFERENCE OF ELEMENTS IN A MATRIX

-Matrix logically appears as two-dimensional array
-But physically stored in a linear fashion
-Indexing formula maps logical view to physical structure
-Indexing formula for ROW MAJOR ORDER
where i = row, j = col; n = no.of cols in matrix
- Eg: a32: ( 3 1 ) * 4 + 2 = 2 * 4 + 2 = 10
-Indexing formula for COLUMN MAJOR ORDER
where i = row, j = col; m = no.of rows in matrix
- Eg: a32: ( 2 1 ) * 3 + 3 = 1 * 3 + 3 = 6

SPARSE MATRICES
A Sparse matrix is a two-dimensional array having
the value of majority elements as null
* denotes non-null values
Uses:
- Wastage of memory if entire matrix is stored
- So, store only the non-null values
- Helps to compress the matrix

SPARSE MATRICES- CLASSIFICATION

Square Matrix:
A square matrix has the same
number of rows as columns .

Symmetric Matrix:

A square matrix is called

symmetric matrix if it is equal to its transpose

Different symmetric sparse matrices

-Triangular matrices
- Upper left, upper right, lower-left, lower-right
-Diagonal matrices
- Diagonal matrices
- Tridiagonal matrices

TRIANGULAR MATRICES

DIAGONAL MATRIX -

a matrix having non-zero

elements only in the diagonal running from the upper left to the
lower right or upper right to lower left

TRIDIAGONAL MATRICES -has

nonzero elements
only on the main diagonal, the first diagonal below this, and the
first diagonal above the main diagonal

EXAMPLE
:

- BAND MATRIX : non-zero entries are confined to a diagonal band,

comprising the main diagonal and zero or more diagonals on either side

POINTER ARRAYS
Pointer : holds address of memory variable or array
Pointer array: array containing pointers as elements
Example: Students marks record
Semester : 6 [S1, S2, S3, S4, S5, S6]
Has 5 subjects in each semester:
Sem 1: [S1-1, S1-2,S1-3,S1-4,S1-5]
Sem 2: [S2-1, S2-2,S2-3,S2-4,S2-5]
.
.
Sem 6: [S6-1, S6-2,S6-3,S6-4,S6-5]
No. of students:30

Requires array of size 6 x 5 x 30 =900

Maintains 3 arrays:
1st array stores semesters
[ size:6],
2nd array stores subjects
[size 6 x 5 = 30],
3rd array stores student marks [size 6 x 5 x 30 = 900]
To get marks scored by
ith student in
jth subject in
kth semester :

12MCA101

89

12MCA102

75

SEM
1

12MCA103

90

SEM 2

12MCA104

85

12MCA105

79

SEM3
SEM4
SEM5
SEM6

12MCA201
.
.
.
.

.
.
.
.

ARRAY AS ADT
[ABSTRACT DATA TYPE]
Consists of
Collection of data items
Basic operations performed on them

An abstract data type is a data type solely defined

in terms of a type and a set of operations on that
type. Each operation is defined in terms of its input
and output without specifying how the data type is
implemented.
A stack is an example of an ADT, defined in terms of
push and pop operations.
A data structure is an implementation of an ADT.
The Stack ADT, for example, can be implemented
by means of an array.

ARRAY AS ADT
[ABSTRACT DATA TYPE]
An abstract data type is a data type
defined in terms of a type and a set of
operations on that type. Each operation is
defined in terms of its input and output
without specifying how the data type is
implemented.
A stack is an example of an ADT, defined in
terms of push and pop operations.
A data structure is an implementation of
an ADT. The Stack ADT, for example, can be
implemented by means of an array.

Stack as ADT
Definition A stack is a restricted list in which entries are added and
removed
from the same end, called the top. This strategy is known as last-infirst-out
(LIFO) strategy.
Operations (methods) on stacks:
push (item)
pop ()
size ()
empty ()
full()
ontop()
the stack

Inserts item on the top of the stack

Removes the top item
Returns the number of items in the stack
Returns true if the stack is empty
Returns true if the stack is full
Returns the top element without removing it from