Page 21 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes memory locations to the program for array. In case the required number of memory cells exceeds
the available memory the operating system returns an error code to the program that made the
request.

Memory Allocation to One-dimensional Array

A one dimensional array is a list of finite number n of Homogeneous data elements (i.e. data

elements of the same type) such that:
1. The elements of the Array are referenced respectively by an index set consisting of n
consecutive numbers.

2. The elements of the Array are stored respectively in successive memory locations.
The number n of elements is called the length or size of the Array.
If not explicitly stated, we will assume the index set consists of the integers 1, 2, ...n. In general,
the length or the number of data elements of the Array can be obtained from the index set by the
formula
Length = UB – LB + 1 …(1)
where,

UB is the largest index, called the upper bound and
LB is the smallest index, called the lower bound, of the Array.

Note Note that length = UB when LB = 1.

The elements of an Array A may be denoted by the subscript notation A[1], A[2], A[3],... A[n].
In general a linear Array A with a subscript lower bound of “one” can be represented pictorially

as in figure given below.
LB

.
.
.
A[1]

If s words are allocated for each element or node (i.e. size of data types of elements of Array is s),
then total memory space allocated to array is given by:

Memory Space Request (UB – LB + 1)*s …(2)
If we want to calculate the memory space required for first i-1 elements of an Array then slight

modification in formula (2) will be needed. i.e.

Space Required = (i – 1 - LB + 1)*s

16 LOVELY PROFESSIONAL UNIVERSITY