Arrays and matrices
For some reason, in portuguese, the word "vetor" (vector in english) means both vector, the mathematical object, and array, the computing object. In C a matrix is a matrix for the user and the programmer who is not dealing with pointer arithmetic, but when pointer arithmetic is exposed, a matrix turns out be an "array of array".
In the beginning of the introduction to computing discipline we learn what's the use of arrays and how to use one. The mathematical side of matrices is not studied, that is left to be studied in depth in a linear algebra course. In the beginning you can see arrays and matrices as a type of variable that stores sets of values, but do not call and define arrays and matrices as variables. The definition of arrays and matrices will be much clearer when you learn pointers, until then we can use arrays and matrices without going in the pointer's details.
All problems are "solvable" with arrays or matrices of fixed size. Dynamic size requires dynamic allocation of memory and that is not part of this introduction.
The basic logic is: you need a loop and a counter. Every array has an index, the positions of that set's elements. We write a loop with a counter to "go over" each of the array's elements.
Errors of logic:
- The main one is with the index. If the counter goes off the array's maximum or minimum range, "run to the hills";
- Another, not so severe, is to count wrongly. That causes some value to be overwritten or the wrong position to be read;
- In the beginning it's common to confuse the index, the position, with the element itself stored in that position.
- Fill an array / matrix with lots of numbers:
int array[max], i;
/* all array's indexes, 0 ... max - 1, are assigned the value 1 */
for (i = 0; i < max; i++) { array[i] = 1; }
With matrices the logic is the same:
int matrix[imax][jmax], i, j;
/* fill all the matrix's indexes with the number 7. Row by row, column by column */
For n dimensions, there are going to be n loops in cascade, which is extremely slow if you think about it. The innermost loop is going to count the rightmost matrix's index, while the outermost loop is going to count the leftmost index.
Go through rows or columns first? Just for readability matters, it's better to stick to the standard, the outer loop counts rows, the inner loop counts columns. Although it's not forbidden to do it the other way around.
- Union of sets, union of two arrays:
int a[max], b[max], c[max];int i, j, k = 0;
/* k counts the index and how many elements c[] has, to not copy any element from b[] where an element of a[] has already been copied */
/* copy all elements from a[] in c[] */
for (i = 0; i < max; i++) c[k++] = a[i];
/* Compare all b[]'s elements with all c[]'s elements Interrupt the comparison in the first b[]'s element that is equal to one of c[]. If the comparison hasn't been interrupted, then copy the current b[]'s element to c[] */
for (j = 0; j < k; j++) if (c[j] == b[i]) break;
if (j == k) c[k++] = b[i];
}
The algorithm only works if both 'a' and 'b' doesn't contain any duplicated elements. As an exercise, try to solve this problem when there are duplicated elements. Try to do the difference of sets.
- Linear algebra, multiply a matrix by a vector
int i, j, rows, columns;
int c[imax], a[imax][jmax], b[jmax];
/* multiply matrix 'a' by vector 'b' element by element
c[i] = 0 is mandatory, else the product from the previous row is accumulated in the next */
c[i] = 0;
}
Side note: a vector in mathematics is represented with a one column matrix and with a number of rows that matches the number of columns of the matrix. But in here we represented the vector using an array, which has just one index, not two like a matrix.
If you don't remember how to multiply a matrix by a vector, check a textbook or mathematics site that explains how to multiply matrix by matrix. Remember that when we multiply a matrix by a vector, the result is always a vector.
