Array is a linear data structure in which the elements are stored in a proper sequence or linear relationship between the elements and is represented by means of sequential memory location. Array can store multiple values which can be referenced by a single name.
All elements are of same type. All the elements are stored at the contiguous memory locations i.e. one after the other.
An array is a multi element box, like a filing cabinet, and uses an indexing system to find each variable stored within it. Its indexing start from zero.
Arrays are declared using the following syntax:
data_type array_name [size];
where,
Data type- what kind of value it can store. For example: int, float, char
Array name- to identify the array
Size- the maximum number of values an array can hold
Definition: An array is a collection of homogeneous data elements of a specific data type (i.e. int or float or char) that have been given a single name, which are stored at contiguous memory locations i.e. one after the other.
Each individual elements of an array is referenced by a subscripted variable. The subscript or an index is enclosed in brackets after array name.
➢ If two subscripts are used to refer to an element of an array the array is known as two dimensional array or matrix and so on. In a matrix, the two dimensions are represented by rows and columns.
➢ Array which has two or more subscripts are known as multidimensional array. Multidimensional arrays is a extension of 2D matrices and use additional subscripts for indexing.
Calculating the Address of Array Elements
Address of data element,
A[k]= BA(A) + w( k - lower bound)
where,
A is the array
k is the index of element whose address we have to calculate
BA is the base address of the array A
w is the word size of one element in memory. For example: size of int is 2.
marks[6]= 1000 + 2(6-0)
= 1000 + 2(6)
= 1000 + 12
= 1012
Calculating the Length of an Array
Length = upper_bound - lower_bound + 1
where,
upper_bound is the index of the last element
lower_bound is the index of the first element in an array
Here, upper_bound= 8 and lower_bound= 0
Length = 8 - 0 + 1
= 9
Types of Array
There are two types of Array
- Linear Array
- Non Linear Array
There is one to one relationship between each data element and its subscript or index.
Only one subscript is used.
General Syntax of One Dimensinal Array:
data_type array_name [size];
2) Non Linear Array: Non linear arrays like Two Dimensional Array and N Dimensional array.
Two Dimensional array are in the form of row and column.
First subscript will depict the row size and second subscript will depict the column size.
General Syntax of Two Dimensional Array:
data_type array_name [row_size] [column_size];
N Dimensional array has n size of row, column and spaces and so on.
General Syntax of N Dimensional Array:
data_type array_name [size1] [size2] ..... [sizeN];
Memory Representation of Array
We can initialize array in 2 ways:
- Compile time initialization
- Run time initialization
➢ One Dimensional Array:
Suppose we have one dimensional array declaration as follows:
int S[9] = {3, 5, 11, 15, 23, 29, 43, 56, 78};
Since we know that array elements are stored at contiguous memory locations, so its memory map can be shown as:
As int data type takes 2 bytes of memory to store, so the addresses are in the gap of 2 bytes each.
➢ Two Dimensional Array
There are two ways of storing a 2D array in memory.
The first way is row-major order and the second is column-major order.
Lets take Two Dimensional 3 x 4 array:
In the row-major order the elements of the 1st row are stored before the elements of the 2nd and 3rd rows. That is, the elements of the array are stored row by row where n elements of the 1st row will occupy the first nth locations.
In the column-major order, the elements of the 1st column are stored before the elements of the 2nd and 3rd columns. That is, the elements of the array are stored column by column where n elements of the 1st column will occupy the 1st nth locations.
Row-major order:
Address (A[I] [J]) = Base_Address + w[N(I-1) + (J-1)]
Column-major order:
Address (A[I] [J]) = Base_Address + w[M(J-1) + (I-1)]
where,
w = number of bytes required to store one element
N = number of columns in 2D array
M = number of rows
I and J are the subscripts
I = Ith Row
J = Jth column
Example:
Consider a 20 x 5 two-dimensional array marks[20][5] which
has its base address = 1000 and the size of an element = 2. Now compute the
address of the element, marks[18][4] assuming that the elements are stored in
row major order.
Solution:
Address(A[I][J]) = Base_Address + w{N (I – 1)
+ (J – 1)}
Address(marks[18][4]) = 1000 + 2 {5(18 – 1) + (4 – 1)}
=
1000 + 2 {5(17) + 3}
=
1000 + 2 (88)
=
1000 + 176 = 1176
Sparse Matrix
Sparse Matrices are those matrices which have the majority of their elements equal to zero.
For example:
This means storing non-zero elements with triples( Row, Column, Value).
2D array is used to represent a sparse matrix in which there are three rows named as:
Row: index of row where non-zero element is located
Column: index of column where non-zero element is located
Value: value of non-zero element located at index
For Example:
Tags:
Data Structure