Chapter 2: Arrays
2.1 Array Definition
2.2 Representation
2.3 Analysis
2.4 Single and Multidimensional Arrays
2.5 Address calculation
2.6 Application of arrays
2.7 Character String in C
2.8 Character string operation
2.9 Array as Parameters
2.10 Ordered List
2.11 Sparse Matrices
2.12 Vectors.
Array definition:-Array is linear, homogeneous data structures whose elements are stored in contiguous memory locations.
Arrays are subscripted variables stored in contiguous memory locations.
Accessing Array elements: Elements of arrays are accessed by using index or subscripts.
Types of Arrays:
One-dimensional Array or linear array: requires only one index to access an element.
Two-Dimensional Array: requires two indices to access an element.
Multidimensional Array: requires two or more indices to access an element.
Size of linear array: size=ub-lb-1
Where ub represents upper bound or largest index of array,
lb represents lower bound or smallest index of array.
Indices of array are integer numbers.
In C/C++/Java index starts from 0,that is the smallest index of array is 0.
In C/C++/Java index are written in brackets [ ].
Representation of One-dimensional array in memory:-
Suppose name of linear array is arr and it has 5 elements. Then its elements are represented as:
arr
0 1 2 3 4
arr[0], arr[1], arr[2], arr[3], arr[4].
Address calculation in one-dimensional Array:-
Since array elements are stored in contiguous memory locations, the computer needs to not to know the address of every element but the address of only first element. The address of first element is called base address of array. Given the address of first element, address of any other element is calculated using the formula:-
Loc (arr [k]) =base (arr) + w * k (in C/C++/Java)
Where k is the index of array whose address we want to calculate and w is the number of bytes per storage location of for one element of array.
If not given explicitly, we take index set as 1,2,3,4,……n where n the upper bound of the array.
Example:- Suppose that array arr is declared as integers with size 20 and its first element is stored at address 1000. Calculate the address of 4th element of array when the index of the array starts from 0.
Here, base address=1000, k=3, w=2.
Thus, loc(arr[3])=1000 + 2*3=1006
Representation of two dimensional array in memory:
Suppose name of two-dimensional array is mat and it has 3 rows and 4 columns. Then its elements are represented as:
mat[0][0], mat[1][0], mat[2][0]
mat[0][1], mat[][1], mat[2][1]
mat[0][2], mat[1][2], mat[2][2]
mat
0 1 3
Elements of two-dimensional arrays are stored in two ways:-
(i) Column major order: Elements are stored column by column, i.e. all elements of first column are stored, and then all elements of second column stored and so on.
(ii) Row major order: Elements are stored row by row, i.e. all elements of first row are stored, and then all elements of second row stored and so on.
