Matrice în C++: citire, indici și transpunere

O matrice organizează valorile pe linii și coloane. Poți reprezenta astfel un tabel de note, o tablă de joc sau o hartă dreptunghiulară. Un element are doi indici: primul identifică linia, al doilea coloana.

Ai nevoie de vectori și indici. Vom folosi o matrice cu n linii și m coloane, numerotate de la zero. Elementul a[i][j] se află pe linia i, coloana j.

Citește întâi dimensiunile

Pentru o matrice cu două linii și trei coloane, indicii de linie sunt 0 și 1, iar cei de coloană sunt 0, 1, 2. Sunt n * m = 6 elemente, nu n + m.

Primul indice alege linia, al doilea alege coloana.

Cu un tablou clasic poți scrie int a[100][100]{}; și folosi doar primele n linii și m coloane. Capacitățile trebuie să fie constante în această declarație C++17 și suficiente pentru limitele problemei. Nu folosi int a[n][m]; cu dimensiuni citite la rulare.

Ca alternativă, în declarația std::vector<std::vector<int>> a(n, std::vector<int>(m));, vectorul exterior conține n linii, iar fiecare linie este un vector de m întregi. În exemplul nostru, toate liniile au aceeași lungime, chiar dacă acest tip poate reprezenta și linii de lungimi diferite.

Citirea și suma tuturor elementelor

Programul citește n și m, cu 1 <= n, m <= 100, apoi elementele linie cu linie. Valorile sunt întregi între -1000000 și 1000000. Afișează suma întregii matrice.

Varianta cu tablou clasic

int a[100][100]{}; rezervă o capacitate de 100 de linii și 100 de coloane. Folosim numai indicii din dimensiunile citite. Acoladele inițializează elementele cu zero.

#include <iostream>

int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    int a[100][100]{};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            suma += a[i][j];
        }
    }
    std::cout << suma << '\n';
    return 0;
}

Varianta cu std::vector

În varianta de mai jos, fiecare linie este un std::vector<int>, iar matricea conține exact numărul citit de linii și coloane. Accesul rămâne a[i][j]; condițiile de parcurgere și rezultatul sunt aceleași.

#include <iostream>
#include <vector>

int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            suma += a[i][j];
        }
    }
    std::cout << suma << '\n';
    return 0;
}

Pentru matricea din imagine, rezultatul este 21. La i = 0, bucla interioară trece prin coloanele 0, 1, 2. După încheierea ei, i devine 1, iar j pornește din nou de la zero. Fiecare pereche validă de indici este vizitată exact o dată.

Condițiile buclelor nu sunt interschimbabile: i < n limitează liniile, j < m limitează coloanele. Un program care folosește n la ambele condiții poate părea corect pe matrice pătratice și poate eșua pe cele dreptunghiulare. De aceea exemplul de bază are dimensiuni diferite.

Transpunerea schimbă rolurile indicilor

Transpusa unei matrice cu n linii și m coloane are m linii și n coloane. Elementul de pe poziția (i, j) ajunge pe (j, i). Nu este aceeași operație cu inversarea fiecărei linii.

Următorul program are aceleași limite de intrare. Afișează transpusa fără să construiască o a doua matrice: parcurge coloanele matricei inițiale și afișează fiecare coloană ca pe o linie nouă.

Varianta cu tablou clasic

int a[100][100]{}; rezervă o capacitate de 100 de linii și 100 de coloane. Folosim numai indicii din dimensiunile citite. Acoladele inițializează elementele cu zero.

#include <iostream>

int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    int a[100][100]{};
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            if (i > 0) {
                std::cout << ' ';
            }
            std::cout << a[i][j];
        }
        std::cout << '\n';
    }
    return 0;
}

Varianta cu std::vector

În varianta de mai jos, fiecare linie este un std::vector<int>, iar matricea conține exact numărul citit de linii și coloane. Accesul rămâne a[i][j]; condițiile de parcurgere și rezultatul sunt aceleași.

#include <iostream>
#include <vector>

int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    for (int j = 0; j < m; ++j) {
        for (int i = 0; i < n; ++i) {
            if (i > 0) {
                std::cout << ' ';
            }
            std::cout << a[i][j];
        }
        std::cout << '\n';
    }
    return 0;
}

Pentru exemplul 1 2 3 pe prima linie și 4 5 6 pe a doua, ieșirea este:

1 4
2 5
3 6

Datele din a rămân neschimbate. Dacă ai avea nevoie de transpusa memorată, ai crea o matrice b cu dimensiunile inversate și ai atribui b[j][i] = a[i][j].

Verificare și cost

Citirea și prelucrarea vizitează fiecare element de un număr constant de ori, deci au timp O(n * m). Varianta cu std::vector memorează n * m elemente, iar tabloul clasic rezervă întotdeauna 100 * 100 elemente. Variabila sumă este long long, deoarece adunarea multor valori poate depăși intervalul unui element individual.

Testează o singură linie, o singură coloană și o matrice cu un singur element. Limitele declarate exclud dimensiunile zero. Nu accesa a[n][j] sau a[i][m]: ultimii indici valizi sunt n - 1 și m - 1.

În variantele clasice, memoria rezervată este dată de capacitatea din declarație, nu de numărul de elemente folosite. În variantele cu std::vector, stocarea din aceste exemple este proporțională cu dimensiunile citite. Algoritmul și numărul de elemente prelucrate nu se schimbă între reprezentări. Inițializarea cu {} a tabloului clasic pune la zero întreaga capacitate, inclusiv pozițiile nefolosite; acest cost este separat de parcurgerea celor n elemente sau a celor n * m celule.

Exersează

1. Câte elemente are o matrice cu trei linii și patru coloane?
2. Ce dimensiuni are transpusa ei?
3. Ce valoare este a[0][2] în exemplul ilustrat?
4. Cum calculezi doar suma liniei k?

Răspunsuri: 12; patru linii și trei coloane; 3; păstrezi linia fixă și parcurgi coloanele j = 0, ..., m - 1, adunând a[k][j]. Verifică înainte că 0 <= k < n.

Continuă cu prelucrările pe matrice.