Lesson 07: Arrays
An array is a way to group together a number of variables of a single data type. Arrays are useful primarily because the individual variables stored in an array can be accessed using an index number. This makes it easy to cycle through the array, accessing one variable after another.
Arrays do have an important limitation: The variables stored in an array must all be of the same type. However, you can group variables of different types together in another storage mechanism called a structure, so I will talk about structures in Lesson 10.
7.1 Arrays
Arrays a kind of data structure that can store a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type.
Instead of declaring individual variables, such as number0, number1, ..., and number99, you declare one array variable such as numbers and use numbers[0], numbers[1], and ..., numbers[99] to represent individual variables. A specific element in an array is accessed by an index.
Defining an Array
Defining an Array
You may declare arrays of any data type, including classes. The general form of a singly dimensioned array is:
type variable [size];
type variable [size] = {initValue1, initValue2, … };
Where type specifies the data type of each element in the array and size specifies the number of elements in the array.
In C/C++, the name of an array always points to the first element of an array. Here, the address of the first element of an array is &age[0]. Also, age represents the address of the pointer where it is pointing. Hence, &age[0] is equivalent to age.
C arrays can be of any type. We define an array of ints, chars, doubles, etc. We can also define an array of pointers as follows. Here is the code to define an array of n char pointers or an array of strings.
char* A[n];
Array Elements
Array Elements
- Each variable stored in an array is called an element.
- The elements are numbered. These numbers are called index numbers or indexes.
- The index of the first array element is 0, the index of the second is 1, and so on. If the size of the array is n, the last element has the index n-1.
For example:
int num[20]; // An integer array of 20 elements
num[0] // first element of array num
num[19] // last (20th) element of array num
Initializing Array Elements
Initializing Array Elements
Arrays can be initialized by using a bracketed list of initializers. For example,
int coins[6] = { 1, 5, 10, 25, 50, 100};
The first element is initialized to 1, the second to 5, and so on.
The number of values between brackets ({}) can not be larger than the number of elements that we declare for the array between square brackets ([]).
You also can ignore the size of the array when you have a set of initialization values. The compiler will automatically calculate the size of the elements by counting the number of initial values.
int score[] = { 1, 5, 10, 25, 50, 100};
When setting the initial value of an array, if the number of set initial values is less than the number of elements of the array, the values of the rest of elements will be directly filled with 0.
int num[5] = { 5, 10}; // num[] = {5, 10, 0, 0, 0}
Initializing Array to Zero
The array will be initialized to 0 in case we provide an empty initializer list or just specify 0 in the initializer list.
int array[5] = {}; // initialize 5 ints to 0 -> array[5] = {0, 0, 0, 0, 0}
int array[5] = {0}; // initialize 5 ints to 0 -> array[5] = {0, 0, 0, 0, 0}
Designated Initializer (Supported by C++Builder)
This initializer is used when we want to initialize a range of the elements with the same value. (Not all compilers supoort this function)
int num[5] = {[1 ... 2] = 3}; // num[5] = {0, 3, 3, 0, 0}
int num[5] = {[0 ... 4] = 2}; // num[5] = {2, 2, 2, 2, 2}
You may also ignore the size of array.
int num[] = {[1 ... 2] = 3}; // num[3] = {0, 3, 3}
int num[] = {[0 ... 4] = 2}; // num[5] = {2, 2, 2, 2, 2}
You can assign different index elements with different initial values as follows:
int x = 1233;
int a[10] = { [9] = x + 1, [2] = 3, [1] = 2, [0] = 1 };
define a 10 elements array and initialize the last element to the value of x + 1 (or to 1234), and the first three elements to 1, 2, and 3, respectively.
Accessing Array Elements
Accessing Array Elements
All arrays consist of contiguous memory locations. The lowest address corresponds to the first element and the highest address to the last element. All the elements can be accessed by indexing the array name. This is done by placing the index of the element within square brackets ([]) after the name of the array. For example, we declare an integer array score with 6 elements and initialization values as shown below:
int score[6] = { 69, 71, 88, 74, 60, 83};
The array variable score points to the address of the first elements of the array, which is the same as the address of the score[0].
Suppose the starting address of the score[0] is $1000. Then, the address of the score[1] will be $1004. Similarly, the address of the score[2] will be $1008, and so on. This is because the size of an int is 4 bytes.
Each element in the array can be accessed using an index number. But you cannot directly use an assignment operator (=) to assign one array to another. You have to set each individual element.
int arr1[5];
int arr2[5] = { 3, 6, 4, 5, 8};
arr1 = arr2; // Error, you can not assign one array to another one
arr1[0] = arr2[0]; // correct
arr1[1] = 57; // set the index number 1 of element (the 2nd element) to 57
arr2[2] = 78; // set the index number 2 of element (the 3rd element) to 78
sum = arr1[1] + arr2[2]; // add arr1[1] with arr2[2] together, then assign the result to the sum
float temp[8]; // declare a float array with 8 elements
7.2 Multidimensional Arrays
C/C++ programming language allows multidimensional arrays. General form of declaring N-dimensional arrays:
type variable [size1][size2]… [sizeN];
Where type specifies the data type of each element in the array, and the size1, size2, …, sizeN are the sizes of each dimension.
Examples:
// Two dimensional array
int twoD[10][20];
// Three dimensional array
int threeD[10][20][30];
Two Dimensional Arrays
The two dimensional (2D) array is also known as matrix. A matrix can be represented as a table of rows and columns.
type variable[rows][cols];
For example:
float x[2][4];
Here, we declared a two-dimensional array, named x. The array can hold 8 elements. This array is the same as a table with 2 rows and each row has 4 elements as shown below:
Initialization of a 2-D array
// Different ways to declare a 2D array with initialization values
int a[2][3] = { { 1, 3, 0},
{-1, 5, 9}};
int b[][3] = { { 1, 3, 0},
{-1, 5, 9}};
int c[2][3] = { 1, 3, 0, -1, 5, 9}};
Here, x is a two-dimensional array. The array can hold 6 elements.
Three Dimensional Arrays
The three-dimensional (3D) array is also known as a matrix. A matrix can be represented as a table of rows and columns.
type variable[page][rows][cols];
For example:
float x[2][3][4];
Here, we declared a three-dimensional array named x. The array can hold 24 elements. This array is the same as a table with two pages, each page has three rows, and each row has four elements as shown below:
Initialization of a 3-D array
// Different ways to declare a 3D array with initialization values
int x[2][3][4] = {{{ 3, 4, 2, 3},
{ 0, -3, 9, 11},
{ 23, 12, 23, 2}},
{{ 13, 4, 56, 3},
{ 5, 5, 3, 5},
{ 3, 1, 4, 9}}};
int y[][3][4] = {{{ 3, 4, 2, 3},
{ 0, -3, 9, 11},
{ 23, 12, 23, 2}},
{{ 13, 4, 56, 3},
{ 5, 5, 3, 5},
{ 3, 1, 4, 9}}};
int z[2][3][4] = { 3, 4, 2, 3, 0, -3, 9, 11, 23, 12, 23, 2, 13, 4, 56, 3, 5, 5, 3, 5, 3, 1, 4, 9};
Multi-Dimensional Arrays
Declaration of a Multidimensional Array in C/C++:
type variable[size1][size2][size3] … [sizeN];
Where size1, size2, …, sizeN are the size of each dimension.
For example:
// Declare a 4-D array
int student[3][4][5][6];
// Declare a 5-D array
float score[5][6][5][6][5];
A 4-D array can be used to store a collection of data in Game design. For example, stores 3D coordinates and 1D time into 4D arrays for each car in the game,[x][y][z][time]; then, we can be used these arrays to check whether there is a collision that occurred between two vehicles or not.
7.4 Matrix Operations
A matrix is a two-dimensional array often used for linear algebra.
Square Matrix is a matrix for which column and row numbers are the same (i.e., an n×n matrix).
Matrix Addition
Matrix Addition — Both matrices should have the same size
Matrices of different sizes can not be added because the sum of two matrices is defined only when both matrices have the same number of rows and the same number of columns.
Algorithm to Add Two Matrices
- for i = 0 to (rows - 1)
- for j = 0 to (cols - 1)
- C[i][j] = A[i][j] + B[i][j]
Matrix Subtraction
Matrix Subtraction — Both matrices should have the same size.
Matrices of different sizes cannot be subtracted because the subtraction of two matrices is defined only when both matrices have the same number of rows and the same number of columns.
Algorithm to Add Two Matrices
- for i = 0 to (rows - 1)
- for j = 0 to (cols - 1)
- C[i][j] = A[i][j] - B[i][j]
Matrix Multiplication
Matrix Multiplication
The product of two matrices is not defined when the number of columns in the first matrix and the number of rows in the second matrix are not the same.
$ \Rightarrow {C_{i,j}} = {a_{i,0}} \cdot {b_{0,j}} + {a_{i,1}} \cdot {b_{1,j}} + \cdots + {a_{i,k}} \cdot {b_{k,j}}$
$ \Rightarrow {C_{i,j}} = \left[ {\sum\limits_{k = 0}^{p-1} {{a_{i ,k }} \cdot {b_{k ,j}}} } \right]$
$C = A \times B = \left[ {\matrix{
{{a_{00}} \times {b_{00}} + {a_{01}} \times {b_{10}} + {a_{02}} \times {b_{20}}} & {{a_{00}} \times {b_{01}} + {a_{01}} \times {b_{11}} + {a_{02}} \times {b_{21}}} \cr
{{a_{10}} \times {b_{00}} + {a_{11}} \times {b_{10}} + {a_{12}} \times {b_{20}}} & {{a_{10}} \times {b_{01}} + {a_{11}} \times {b_{11}} + {a_{12}} \times {b_{21}}} \cr
} } \right]$
Algorithm to Multiply Two Matrices
- for i = 0 to (m - 1)
- for j = 0 to (n - 1)
- for k = 0 to (p - 1)
- C[i][j] += A[i][k] * B[k][j]
Matrix Transpose
Matrix Transpose
Let A =[aij] be an m × n matrix. The transpose of A, denoted by AT, is the n × m matrix obtained by interchanging the rows and columns of A.
Algorithm for Matrix Transpose
- for i = 0 to (n - 1)
- for j = 0 to (m - 1)
- C[i][j] = A[j][i]
Determinant
The determinant of a matrix is the scalar value computed for a given square matrix. Linear algebra deals with the determinant computed using the elements of a square matrix. It can be considered the scaling factor for the transformation of a matrix. Useful in solving a system of linear equations, calculating the inverse of a matrix, and calculus operations.
The determinant of a matrix A,
$\left[ {\matrix{
{{a_{00}}} & {{a_{01}}} & \cdots & {{a_{0(n - 1)}}} \cr
{{a_{10}}} & {{a_{11}}} & \ldots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)1}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right]$
is commonly denoted $det(A)$.
If the $det(A)$ is 0, the matrix is singular, and if the $det(A)$ is 1, the matrix is unimodular.
A 2×2 determinant is defined to be
$\det \left( {\left[ {\matrix{{{a_{00}}} & {{a_{01}}} \cr
{{a_{10}}} & {{a_{11}}} \cr} } \right]} \right) = {a_{00}} \times {a_{11}} - {a_{01}} \times {a_{10}}$
An n×n matrix determinant can be expanded to obtain:
$\eqalign{
& \left[ {\matrix{
{{a_{00}}} & {{a_{01}}} & \cdots & {{a_{0(n - 1)}}} \cr
{{a_{10}}} & {{a_{11}}} & \ldots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)1}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right] = {a_{00}} \times \left[ {\matrix{
{{a_{11}}} & {{a_{12}}} & \cdots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)1}}} & {{a_{(n - 1)2}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right] - {a_{01}} \times \left[ {\matrix{
{{a_{10}}} & {{a_{12}}} & \cdots & {{a_{1(n - 1)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)2}}} & \cdots & {{a_{(n - 1)(n - 1)}}} \cr
} } \right] \cr
& + \cdots \pm {a_{0(n - 1)}} \times \left[ {\matrix{
{{a_{10}}} & {{a_{11}}} & \cdots & {{a_{1(n - 2)}}} \cr
\vdots & \vdots & \ddots & \vdots \cr
{{a_{(n - 1)0}}} & {{a_{(n - 1)1}}} & \cdots & {{a_{(n - 1)(n - 2)}}} \cr
} } \right] \cr} $
A general determinant for a matrix A has a value:
$\det (A) = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^n {{a_{ij}} \times {C_{ij}}} } = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^n {{a_{ij}} \times {{( - 1)}^{i + j}}{M_{ij}}} } $
Matrix Inverse
The inverse of a square matrix A, is called an invertible matrix. We write A-1 instead of ${1 \over A}$ because we do not divide by a matrix!
You can be obtained an inverse of a matrix using the following method:
- Calculate determinant of matrix, $det(A)$. If ($det(A) \ne 0$), then we can say the matrix A has an inverse.
- Calculate the adjoint of the given matrix, $adj(A)$. Adjoint can be obtained by taking the transpose of the cofactor matrix of the given square matrix.
- Finally, find the inverse of the matrix is given below:
${A^{ - 1}} = \frac{1}{{\det (A)}}\,adj(A)$