Two Dimensional Arrays
We have found that one-dimensional arrays allow us to group several variables of a similar type into one compound and we have access to the variable components by the name of the compound variable and by a single index which is applied within the array. Two-dimensional arrays (which we also call matrices) are not nothing more than expanding the presented concept with another dimension.
Astfel, o declarație de forma:
type name [ size1 ][ size2 ];
is the one by which we announce that we want to allocate memory for an array called name, with elements of type type and having the dimensions shown in square brackets. As with vectors, the two dimensions must either constants or constant expressions (which can be evaluated at compile time to know from the start memory requirement to allocate).
Let's have this form:
int a [ 20 ][ 30 ];
We hereby announce that we want to allocate a two-dimensional array with dimensions 20 and 30. But how many elements of type int has the structure declared ? How do we imagine it when we work with it?
We remember from vectors that we usually imagined the structure as a string with indices increasing from left to right. This is due to the way elements appear on the screen on a regular spaced display between them (or, if you like, it's because of the way we see them when we write them on a sheet, one after another another). But we, depending on the situation, can imagine the elements of the vector also arranged from right to left, and from top to bottom, and from bottom to top.
In the case of matrices, we imagine the variables arranged on a rectangular surface with size 1 lines and size 2 columns. We therefore deduce that the number of elements is size1 ∙ size2.
So, in the above example we have 20∙30 = 600 int variables. We imagine these usually as a rectangular area consisting of 20 lines and 30 columns. This way of working with them we will see that it is all due to the way we see them on a standard screen display. But here too, depending on the real situation we model, we can also imagine the surface differently.
So, for example for the matrix a declared above, we have:
Alternate
| Column 0 | Column 1 | Column 2 | Column 3 | ...... | Column 29 | |
|---|---|---|---|---|---|---|
| Line 0 | a [ 0 ] [ 0 ] | a [ 0 ] [ 1 ] | a [ 0 ] [ 2 ] | a [ 0 ] [ 3 ] | ... | a [ 0 ] [ 29 ] |
| Line 1 | a [ 1 ] [ 0 ] | a [ 1 ] [ 1 ] | a [ 1 ] [ 2 ] | a [ 1 ] [ 3 ] | ... | a [ 1 ] [ 29 ] |
| Line 2 | a [ 2 ] [ 0 ] | a [ 2 ] [ 1 ] | a [ 2 ] [ 2 ] | a [ 2 ] [ 3 ] | ... | a [ 2 ] [ 29 ] |
| Line 3 | a [ 3 ] [ 0 ] | a [ 3 ] [ 1 ] | a [ 3 ] [ 2 ] | a [ 3 ] [ 3 ] | ... | a [ 3 ] [ 29 ] |
| .... | .... | .... | .... | |||
| Line 19 | a [ 19 ] [ 0 ] | a [ 19 ] [ 1 ] | a [ 19 ] [ 2 ] | a [ 19 ] [ 3 ] | ... | a [ 19 ] [ 29 ] |
Remarks
- On the principle of vectors, accessing an element is done with a form construction a[ index1 ][ index2 ] . The two indexes are expressions (not necessarily constants) that when executed points to a single element in the array, which is a simple variable of type int in the example.
- In the above described way of imagining things, the first index means line and the second represents column.
- As with vectors, and as seen from the table above, indexing is done from 0 for both sizes. So the array declared above has indices 0 to 19 for rows and 0 to 29 for columns.
- As in the case of vectors, the entire area is not necessarily used every time the program is run declared (and allocated), but logical dimensions are used that are read in the program (let's call them n and m). Also, at least to begin with, we'll use elements starting at position 1.
- The above declaration, in terms of allocated memory space, is equivalent to int b [ 600 ]. The ability to declare two-dimensional arrays should be viewed as a facility that the language makes it available to us to make it easier for us to organize data when we model surfaces.
The problem is how we go through a two-dimensional array, in other words how we have access to its elements on row. In the case of vectors, traversal is done with a repetition (usually).
In the matrix we think that each line is a vector, so to go through it we need a for. Simultaneously we have several lines, that is, several vectors, and we will visit each of them. So we come to the fact that traversing a matrix is done with two fors.
for (line = 1; line <= numberLines; line++)
for (column = 1; column <= numberColumns; column++)
"use" a[line][column];We tried to write the code above as general as possible, including the identifier names. However, the a little to begin with, abbreviations of the variables are used, most often we meet names like: n – for the number of lines, m – for the number of columns, i – for the line index, j – for the column index.
Thus, the sequence below is one often used when reading data from an matrix:
cin>>n>>m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin>> a[i][j];Displaying data from an matrix on the screen has the following effect: one line of the array on one line of a screen and elements of the same line separated by spaces. The printing is done according to the flow scheme presented above, with two fors. Where is use a [ line ][ column ]; is cout << a [ line ][ column ];
Leaving the code exactly like this does not achieve the effect we want because the elements are displayed absolutely all one after another, without switching to a new line on the screen with a new line in the matrix. Some beginners rush and replace the space character with a newline character, but we still don't get what we want this time absolutely all the elements appearing one below the other, so each one on a row.
The solution, which is shown in the code below, is to save space when printing each element, but when line breaks to print a newline character separately. Thus, at the first for we will have braces because two things need to be done on the line he highlights: printing, with spaces between, the elements line and move the screen to the next line.
cin>>n>>m;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++)
cout << a[i][j] << “ ”;
cout << “\n”;
}Once we advance into the mysteries of programming we will hit upon the need to synchronize data from memory with what what we want to appear on the screen. The above can also be viewed in this way.
Solved Problems:
As in other chapters, these problems must also be seen as new theoretical elements, being classic requirements related to matrix.
1. Usual operations that require some traversal of a matrix. Read n, m then the n∙m elements integers of a matrix. Output this:
- The sum of the elements of the matrix;
- The number of even elements of the matrix;
- The highest value that is on an odd row of the matrix;
Example:
| Input | Output |
|---|---|
4 4 1 2 3 4 1 0 1 0 2 1 2 1 9 8 7 6 |
Sum of elements: 48 Number of even values: 8 Cea mai mare valoare de pe o linie impară: 4 |
Solution:
#include <iostream>
using namespace std;
int a[1001][1001];
int n, m, i, j, suma, cnt, maxim;
int main () {
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin>>a[i][j];
/// cerinta a
suma = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
suma += a[i][j];
cout << suma << "\n";
/// cerinta b
cnt = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (a[i][j] % 2 == 0)
cnt ++;
cout << cnt << "\n";
/// cerinta c
maxim = -1;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
if (i%2 == 1)
if (a[i][j] > maxim)
maxim = a[i][j];
/**
for (i = 1; i <= n; i += 2)
for (j = 1;j <= m; j++)
if (a[i][j] > maxim)
maxim = a[i][j];
**/
cout << maxim << "\n";
return 0;
}For the sum requirement we have to traverse the matrix and the actual operation with the current element is adding it to the sum. The other requirements are also accompanied by specific operations. because the elements we are interested in are only part of the total in the matrix, we have an if in each case. Note the difference between the element parity test ( a [ i ][ j ] % 2 ) and the index parity test (i % 2).
Finally, in the comments, is an alternative solution to the last requirement. Going with the line index from two in two we cross only the lines we are interested in (the odd ones), making the parity test for the line no longer necessary. This is also a better solution in terms of time since only the elements of interest in the matrix are visited.
2. Going through the matrix line by line. Read n, m then the n∙m integer elements of a matrix with n lines and m columns. To display the sum of the elements on each line. These values will be displayed on a single line of the screen, separated by space
Example:
| Input | Output |
|---|---|
3 4 5 5 10 5 3 9 1 2 4 10 1 2 |
25 15 17
|
Solution:
Method 1:
#include <iostream>
using namespace std;
int a[101][101], s;
int n, m, i, j;
int main(){
cin >> n >> m;
for (i = 1;i <= n; i++)
for (j = 1; j <= m;j++)
cin >> a[i][j];
for (i = 1; i <= n; i++) {
s = 0;
for (j = 1; j <= m; j++)
s += a[i][j];
cout << s << " ";
}
return 0;
}Method 2:
#include <iostream>
using namespace std;
int a[101][101], s[101];
int n, m, i, j;
int main(){
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin >> a[i][j];
for (i = 1;i <= n; i++)
for (j = 1; j <= m; j++)
s[i] += a[i][j];
for (i = 1;i <= n;i++)
cout << s[i] << " ";
return 0;
}In method 1, we cross the matrix line by line and before analyzing a line we imagine it as a vector, calculating its amount. We use the same variable every time and it is necessary that before each line o initialize and immediately after traversing the line let's do the display. In version 2, I used an auxiliary vector, thus, s [ i ] is the sum of the elements on line i. This way we don't have to worry about display during traversing the matrix as the data remains in the vector and later we can perform the desired operations with them.
I called this problem line-by-line matrix traversal because when traversing the elements of the matrix we first visit line 1 in its entirety, then line 2 in its entirety ... This is actually the classic traversal on which I presented at the beginning.