Strona główna » Algorytmy » Artykuły » Macierze cz. 1
1011
 

Macierze cz. 1

· część 1 · część 2 · część 3 · Wyznacznik ·

Macierze

Macierze najczęściej zapisuje się w postaci prostokątnej tablicy. Możliwe jest również zapisanie ich w postaci wektora długość równej ilości wierszy macierzy pomnożonej przez ilość kolumn macierzy. Najbardziej popularną metodą jest przechowywanie macierzy w tablicach podwójnie indeksowanych czyli prościej mówiąc dwuwymiarowych. Jednak prócz samej tabeli musimy przechowywać wielkość tabeli: ilość wierszy i kolumn. W celu uproszczenia zapisu użyjemy struktury.

Implementacja

Struktura

W strukturze będziemy przechowywać 2D listę zawierającą liczby w zmiennej data, ilość wierszy w n oraz ilość kolumn w m.

C++
C#
  1. struct Matrix{
  2.   double** data;
  3.   int n;
  4.   int m;
  5. };

Nowo utworzona macierz będzie miała zadaną wielkość przez argumenty n i m. Zwrócimy wskaźnik na nowo utworzoną macierz, a wszystkie jej liczby ustawimy na 0.

C++
C#
  1. Matrix* createMatrix(int n, int m){
  2.   Matrix* matrix = new Matrix();
  3.   matrix->n = n;
  4.   matrix->m = m;
  5.   double** table = new double*[n];
  6.   for(int i = 0; i < n; i++){
  7.     double* row = new double[m];
  8.     for(int j = 0; j < m; j++){
  9.       row[j] = 0;
  10.     }
  11.     table[i] = row;
  12.   }
  13.   matrix->data = table;
  14.   return matrix;
  15. }

(2.) Przy tworzeniu uzyskujemy wskaźnik na macierz, więc aby zmodyfikować pola danych nowo utworzonej macierzy to będziemy używać "->" zamiast "."(, którą używamy dla typ, a nie typ*). (3. - 4.) Następnie przypisujemy wielkość naszej zmiennej macierzy. (5.) Zmienna table to nasza 2D tablica, którą na sam koniec przekażemy do matrix. (7.) Następnie dla każdego wiersza tworzymy listę double i (9.) każdy element ustawiamy na 0. Na koniec iteracji (11.) przekazujemy wskaźnik do zmiennej table i (12.) zwracamy macierz.

Bardzo często przy macierzach omawia się macierze kwadratowe, dlatego warto uwzględnić szybki i prosty sposób na tworzenie macierzy kwadratowych.

C++
C#
  1. Matrix* createSquareMatrix(int n){
  2.   return createMatrix(n,n);
  3. }

Napiszmy jeszcze funkcję utworzMacierzJednostkowa(), która stworzy macierz jednostkową, która na swojej głównej diagonali ma same jedynki. Prościej mówiąc każda liczba o współrzędnych x i y, gdzie x = y ma wartość 1.

C++
C#
  1. Matrix* createIdentityMatrix(int n){
  2.   Matrix* m = createSquareMatrix(n);
  3.   for(int i = 0; i < n; i++)
  4.     m->data[i][i] = 1;
  5.   return m;
  6. }

Modyfikowanie macierzy

Załóżmy, że chcemy napisać funkcję, która usunie i-ty wiersz macierzy. Oznacza to, że musimy utworzyć nową tablicę wielkości n - 1 × m. Następnie przepisać każdy wiersz po kolei pomijając wiersz, który chcemy usunąć.

C++
C#
  1. void deleteRow(Matrix* m, int v){
  2.   double** table = new double*[m->n-1];
  3.   for(int i = 0; i < v-1; i++)
  4.     table[i] = m->data[i];
  5.   for(int i = v; i < m->n; i++)
  6.     table[i-1] = m->data[i];
  7.  
  8.   delete m->data;
  9.   m->data = table;
  10.   m->n--;
  11. }

Należy pamiętać, że nieużywaną pamięć należy zwolnić, dlatego przed (9.) przypisaniem nowej listy liczb (8.) usuwamy starą po przepisaniu. Linijki (3. - 6.) można przepisać jako jedną pętle for z dodatkowym warunkiem if. Jest to jednak bardziej skomplikowane i mniej efektywne. Na koniec należy pamiętać, że rozmiar macierzy się zmienił co oznacza, że (10.) ilość wierszy macierzy należy zmniejszyć.

Usuwanie kolumny macierzy jest trochę bardziej skomplikowane, ale opiera się na identycznym schemacie:

C++
C#
  1. void deleteColumn(Matrix* m, int v){
  2.   for(int i = 0; i < m->n; i++){
  3.     double* row = new double[m->m-1];
  4.     for(int j = 0; j < v-1; j++)
  5.       row[j] = m->data[i][j];
  6.     for(int j = v; j < m->m; j++)
  7.       row[j - 1] = m->data[i][j];
  8.     delete m->data[i];
  9.     m->data[i] = row;
  10.   }
  11.   m->m--;
  12. }

Mnożenie macierzy

Mnożenie macierzy przez skalar oznacza pomnożenie każdej liczby w macierzy przez skalar:

C++
C#
  1. void multiplyByNumber(Matrix* m, double a){
  2.   for(int i = 0; i < m->n; i++)
  3.     for(int j = 0; j < m->m; j++)
  4.       m->data[i][j] *= a;
  5. }

Wypisywanie macierzy

Struktura Matrix jest naszym wytworem i standardowe biblioteki nie potrafią wypisać jej na konsole. Jednak możemy napisać specjalną funkcje, która nam to umożliwi:

C++
C#
  1. void writeMatrix(Matrix* matrix){
  2.   for(int i = 0; i < matrix->n; i++){
  3.     for(int j = 0; j < matrix->m; j++){
  4.       cout << matrix->data[i][j] << "\t";
  5.     }
  6.     cout << endl;
  7.   }
  8. }

Funkcja używa tu specjalnego znaku "\t", który wypisuje tabulator, aby macierz była wyrównana w kolumnach.

Testowanie funkcji

Poniższy fragment kodu prezentuje użycie niektórych napisanych funkcji:

C++
C#
  1. int main () {
  2.   setlocale(LC_ALL,"");
  3.   Matrix* matrix = createIdentityMatrix(4);
  4.   cout << "Nowa macierz: \n";
  5.   writeMatrix(matrix);
  6.   cout << "\n\nUsuwamy drugi wiersz macierzy: \n";
  7.   deleteRow(matrix, 2);
  8.   writeMatrix(matrix);
  9.   cout << "\n\nUsuwamy drugą kolumnę macierzy: \n";
  10.   deleteColumn(matrix, 2);
  11.   writeMatrix(matrix);
  12.   cout << "\n\nMnożymy macierz przez skalar 3: \n";
  13.   multiplyByNumber(matrix, 3);
  14.   writeMatrix(matrix);
  15.   system("pause");
  16.   return 0;
  17. }

Zadania

Zadanie 1

Napisz funkcję sumujWszystko(), która zsumuje wszystkie liczby w macierzy i zwróci wynik jako liczbę rzeczywistą.

Zadanie 2

Napisz funkcję lub konstruktor, który pozwoli użytkownikowi wprowadzić macierz czyli: