ARRAY is an ordered collection of similar data elements, so it is called as Linear Data Structure. The elements are arranged in Linear order i.e. one after the other, at consecutive memory locations. Each element of the array is naturally bound together by means of consecutive memory allocation to each respective element.
ARRAY may be either one-dimensional or two –dimensional or multidimensional depending on the characteristics that are explained by the elements. In one-dimensional the elements simply explain
ARRAY may be either one-dimensional or two –dimensional or multidimensional depending on the characteristics that are explained by the elements. In one-dimensional the elements simply explain
One Dimensional Arrays
Array is a Linear Data Structure in which homogeneous (similar)
element are stored. Array is used to represent a real life List. The elements stored explain one and only one characteristic. For example you may find an array of makes of students, height of students, salary of employees, employee structures etc.
Sequential Allocation
One-dimensional array is stored consecutively or sequentially in memory. Contiguous memory is allocated for an array to store the elements. The address of an element of an array is the location in memory where that element is stored. The address of first element is the starting address of the array and it is called ‘Base Address’. Total memory needed for storage of an array depends on the number of element (size of array) in it and the size of each element. The size of element is termed as ‘Word Size’.
WS – size of element stored in bytes (basic memory unit)
a1, a2,… a10 are the address of each element
a1 First element’s address – The Base Address a2=a1+word size.
a3=a2+word size OR a1+(word size) * 2
a4=a1+(word size) * 3
…
an=a1+(word size) * (n-1)
IF a1=1000, so Base Address=1000 and WS=4 bytes, then
a2=BA+WS *(2-1) a5=BA+WS *(5-1)
=1000+4 * 1 =1000+4 * 4
=1004 =1016
In case of “C” language one-dimensional array is declared in the declaration part of the program part of the program as follows:
data _type name _of _the _array[size];
where data _type may be any of the standard data types available in C like int, float, long, char, double etc.
name _ of _ the _ array is an identifier or user defined variable name to represent array name. [size] is an integer constant that specifies the size of the array and it represents number element that can be stored in one-dimensional array.
For example, int marks [5] is an array of size 5 and of the type integer.
In “C” language the lower bound of the array is fixed to 0(Zero) and the upper bound of is size-1. User only has to take care of the array boundary. So in the above example, makes [0] represents the first element whereas marks [4] represents the last element of the array.
Two Dimensional Arrays
Two-dimensional array are called as Tables in case of business and Matrix in case of Mathematics. The elements stored in a two-dimensional array explain two characteristics. Row and Columns are used to explain the two dimensions of two-dimensional array. Two-dimensional is a collection of multiple columns. Row index and column indexes are used to access an individual element stored in two-dimensional array.
Row size of the above two-dimensional array is 3 and column size is also 3. So it is called a 3*3 matrix or two-dimensional array. Two-dimensional array is represented as
NameOfTheArray (RLB: RUB, CLB:CUB) OR
NameOfTheArray (M, N)
NameOfTheArray(M X N)
Where RLB- Lower bound of Row, RUB-Upper bound of Row .
CLB-Lower bound of column, CUB-Upper bound of Column.
M- Row size, N- Column size. (In this case 1 is lower bound, for both row and column).
When row size M and column size N are not given they are calculated as M=RUB-RLB+1 and N=CUB-CLB+1.
M*N elements are stored in two-dimensional array(TDA).
Memory Representation or Sequential allocation of TDA
As there are two dimensions of two-dimensional array, it is stored in memory in sequential M*N cells where M and N are row and column size of TDA respectively. The sequential storage may be by ROW major or COLUMN major depending on the compiler.
In ROW major all the ROW element are stored sequentially, means first row elements are stored first then second rowed elements and so on. In COLUMN major all the COLUMN elements are stored sequentially, means first the column elements are stored first then second column elements and so on.
For example consider a matrix MAT (3*5), the element of which are as shown below:
4 5 6 8 9
7 9 1 5 3
6 5 4 3 2
In case of Row major the stored can be represented as follows:
11 mean first row’s first column element, similarly 12 and 13 represent second and third column elements first row respectively, so on the elements can be represented.
So, in case of row major all the 5.elements of first row are stored first, then second row’s 5 elements and then third row’s 5 elements are stored sequentially in memory. So depending on the word size M*N storage locations are required to store the TDA elements. Here in this example 3*5=15, fifteen storage (memory) locations are needed to store the TDA. As the word size is 2 (assuming integer) bytes, the total memory required is 30 bytes.
In case of column major the storage can be represented as follows:
11 means first row’s first column element, similarly 12 , 13 and so on.
So, in case of column major all the 3 elements of first column are stored first, then second column’s 3 elements, then third column’s 3elements, then fourth column’s 3 elements and fifth column’s 3 elements are stored sequentially in memory. So, depending on the word size M*N storage locations are required to store the TDA elements.
Here in this example 3*5=15, fifteen storage (memory) locations are needed to store the TDA. As the word size is 2 (assuming integer) bytes, the total memory required is 30 bytes (similar to row major).
Address Calculation
In case of two-dimensional array the address of the individual element is calculated depending on the storage major either row major or column major. The first element of the TDA is stored at location called Base Address and the location of the next coming elements depends on the word size, similar to one-dimensional arrays.
Row Major
In case of Row major as all the row elements are stored sequentially, by knowing the Base Address and Word Size, it is possible to calculate the location of any element. To reach to the element i.e. to find the location of the element, number of rows elements are skipped to reach to the element in the respective row and number of column elements are skipped to reach to the column element of that row.
For example in a TDA, MAT (5*6), in order to reach the fifth element of fourth row, three row are skipped and each row contains 6 elements plus four elements of fourth are also skipped. So total elements to skip is equal to 3*6+4=22, If word size is 4 then 22*4=88 plus Base Address is the address or location of fifth element of fourth row i.e. MAT(4,5).
For example consider a TDA, MAT (5 * 6), the element of which are as shown below:
The elements to be skipped are shown in bold face in order to reach to element 2.
Total number of elements skipped are 3*6+4=22.
If they are stored in memory starting from location 100, then the memory representation of the above TDA is as follows (assuming the word size 2 because of integer data):
So, the formula to find the address is as follows if TDA is given as MAT(M X N) (in which both RLB and CLB are 1):
Where
BA - Base Address, WS – Word Size
I – Row Number, J – column Number
N – Column Size
If TDA is given as MAT(RLB : RUB, CLB : CUB), then the formula changes to
Where
BA – Base Address, WS – Word Size, I – Row Number,
J – Column Number, CUB – Column Upper Bound, CLB – Column Lower Bound
In case of “C” language the two-dimensional array is declared by adding another size to one-dimensional array.
The syntax of the declaration of two-dimensional array looks like: data-type name-of_the_array[rsize][csize];
Where data_type may be any of the standard data types available in C like int, float, char, double etc. name_of_the_array is an identifier or user defined variable name to represent array name. [rsize] is an integer constant that specifies the row size of the array and it represents number rows that can be stored I two-dimensional array and [csize] is also integer constant that shows number elements for each row. For example, int matrix[5][5] is two-dimensional array of size 5*5 and of the type integer. Here matrix whereas matrix [4][4] represents last row’s last column element.
