Arrays and Records

1.0 Linear or One-dimensional Arrays

An array (of any dimension) is a linear and structured data type with the following properties and characteristics:

1. It is made up of finite n homogenous (of same type) data elements such that

a. Every data element is of fixed size. Size depends upon the specific nature of structure of the data elements.

b. The elements of the array are referenced respectively by an index set consisting of n consecutive numbers.

c. The elements of the array are stored respectively in successive contiguous memory locations. Array is a data–structure that uses memory statically unlike linked list, which is constructed on dynamic memory allocation.

2. The accessing mechanism of an array is direct access, which means we can access any element directly, without first accessing the preceding elements. The desired element is specified using an index, which gives its relative position in the collection. e.g.

A [0], A[1],…….. A[n-1]

3. Arrays are built–in data types in most of the programming languages including C and C++.

4. The length or size or number of data elements of the array, A[LB:UB], can be obtained from the index set by the formula.

Length of Array A = UB – LB + 1

where UB is the largest index, called the upper bound, and LB is the smallest index, called the lower bound, of the array. In C and C++ languages, LB is always zero.

We shall use C/C++ languages for implementation purposes. Therefore, our first index in case of arrays will always be zero.

2.0 Representation of Linear Arrays in Memory (Dope Vector Method)

To implement array data structure, memory bytes must be reserved and the accessing functions must be coded. In case of linear arrays, the declaration statements tell how many cells are needed to store the array. The following characteristics of the array are used to calculate the number of cells needed and to find the location or address of any element of the array.

1. The upper bound (UB) of the index range.

2. The lower bound (LB) of the index range. In C/C++, LB is zero.

3. The location in memory of the first byte in the array, called base address of the array (Base)

4. The number of memory bytes needed for each cell containing one data element in the array (size, denoted by W)

By cell we mean a unit of memory bytes that will be assigned to hold a value of respective data element.

During the compilation of the program, the information about characteristics of the array is stored in a table called DOPE VECTOR. When compiler comes across references to an array element, it uses this information that will calculate the element’s location in memory at runtime.