Tablouri bidimensionale
Am arătat că tablourile unidimensionale ne permit să grupăm mai multe variabile de același tip în una compusă și avem acces la variabilele componente prin numele variabilei compuse și printr-un singur indice care reprezintă poziția în cadrul tabloului. Tablourile bidimensionale (pe care le mai numim matrice) nu sunt altceva decât extinderea cu încă o dimensiune a conceptului prezentat.
Astfel, o declarație de forma:
tip nume [ dimensiune1 ][ dimensiune2 ];
este cea prin care anunțăm că vrem să se aloce memorie pentru o matrice numită nume, cu elemente de tipul tip și care are dimensiunile indicate între parantezele drepte. Ca și la vectori, cele două dimensiuni trebuie să fie constante sau expresii constante (care se pot evalua încă de la compilare pentru a se cunoaște de la început necesarul de memorie de alocat).
Fie o declarație de forma
int a [ 20 ][ 30 ];
Prin aceasta anunțăm că dorim alocarea unui tablou bidimensional cu dimensiunile 20 și 30. Dar câte elemente de tip int are structura declarată ? Cum ne-o imaginăm atunci când lucrăm cu ea ?
Ne amintim de la vectori că ne imaginam de obicei structura ca pe un șir cu indicii crescători de la stânga la dreapta. Acest lucru se datorează modului în care elementele apar pe ecran la o afișare obișnuită cu spații între ele (sau, dacă vreți, se datorează modului în care le vedem atunci când le scriem pe o foaie, unul după altul). Dar noi, în funcție de situație, ne putem imagina elementele vectorului dispuse și de la dreapta la stânga, și de sus în jos, și de jos în sus.
În cazul matricelor ne imaginăm variabilele dispuse pe o suprafață dreptunghiulară cu dimensiune1 linii și dimensiune2 coloane. Deducem deci că numărul de elemente este dimensiune1 ∙ dimensiune2.
Așadar, în exemplul de mai sus avem 20∙30 = 600 variabile de tip int. Pe acestea ni le imaginăm de obicei ca pe o zonă dreptunghiulară formată din 20 de linii și 30 de coloane. Acest mod de a lucra cu ele vom vedea că se datorează tot felului în care le vedem la o afișare standard pe ecran. Dar și aici, în funcție de situația reală pe care o modelăm, putem să ne imaginăm și altfel suprafața.
Așadar, de exemplu pentru matricea a declarată mai sus, avem:
Alternate
| Coloana 0 | Coloana 1 | Coloana 2 | Coloana 3 | ...... | Coloana 29 | |
|---|---|---|---|---|---|---|
| Linia 0 | a [ 0 ] [ 0 ] | a [ 0 ] [ 1 ] | a [ 0 ] [ 2 ] | a [ 0 ] [ 3 ] | ... | a [ 0 ] [ 29 ] |
| Linia 1 | a [ 1 ] [ 0 ] | a [ 1 ] [ 1 ] | a [ 1 ] [ 2 ] | a [ 1 ] [ 3 ] | ... | a [ 1 ] [ 29 ] |
| Linia 2 | a [ 2 ] [ 0 ] | a [ 2 ] [ 1 ] | a [ 2 ] [ 2 ] | a [ 2 ] [ 3 ] | ... | a [ 2 ] [ 29 ] |
| Linia 3 | a [ 3 ] [ 0 ] | a [ 3 ] [ 1 ] | a [ 3 ] [ 2 ] | a [ 3 ] [ 3 ] | ... | a [ 3 ] [ 29 ] |
| .... | .... | .... | .... | |||
| Linia 19 | a [ 19 ] [ 0 ] | a [ 19 ] [ 1 ] | a [ 19 ] [ 2 ] | a [ 19 ] [ 3 ] | ... | a [ 19 ] [ 29 ] |
Observații
- Pe principiul de la vectori, accesarea unui element se face cu o construcție de forma a [ indice1 ][ indice2 ]. Cei doi indici sunt expresii (nu neapărat constante) care la executare indică spre un singur element din matrice, acesta fiind o variabilă simplă de tip int în exemplul de față.
- La modul descris mai sus de a ne imagina lucrurile, primul indice înseamnă linie și al doilea reprezintă coloana.
- Ca și la vectori, și după cum se observă din tabelul de mai sus, indexarea se face de la 0 pentru ambele dimensiuni. Deci matricea declarată mai sus are indici de la 0 la 19 pentru linii și de la 0 la 29 pentru coloane.
- Ca și în cazul vectorilor, nu se folosește la fiecare rulare a programului în mod obligatoriu toată zona declarată (și alocată), ci se folosesc dimensiuni logice care se citesc în program (să le spunem noi n și m). De asemenea, cel puțin pentru început, vom folosi elementele începând cu poziția 1.
- Declararea de mai sus, din punct de vedere al spațiului de memorie alocat este echivalentă cu int b[600]. Posibilitatea de a declara tablouri bidimensionale trebuie privită ca o facilitate pe care limbajul o pune la dispoziția noastră pentru a ne fi mai ușor să organizăm datele când modelăm suprafețe. .
Se pune problema cum parcurgem un tablou bidimensional, altfel spus, cum avem acces la elementele sale pe rând. În cazul vectorilor parcurgerea se realizează cu o repetiție (for de obicei).
La matrice ne gândim că fiecare linie este un vector, deci pentru a-l parcurge avem nevoie de un for. Totodată avem mai multe linii, adică mai mulți vectori și îi vom vizita pe fiecare dintre ei. Așadar ajungem la faptul că parcurgerea unei matrice o realizăm cu două foruri
for (line = 1; line <= numberLines; line++)
for (column = 1; column <= numberColumns; column++)
"use" a[line][column];Am încercat să scriem codul de mai sus cât mai general, inclusiv ca denumiri ale identificatorilor. Totuși, cel puțin pentru început se folosesc prescurtări ale variabilelor, cel mai des întâlnim denumiri ca: n – pentru numărul de linii, m – pentru numărul de coloane, i – pentru indicele de linie, j – pentru indicele de coloană
Astfel, secvența de mai jos este una des folosită atunci când citim datele unei matrice:
cin>>n>>m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin>> a[i][j];Afișarea pe ecran a datelor dintr-o matrice are următorul efect: câte o linie a matricei pe câte o linie a ecranului și elementele aceleiași linii separate prin spații. Tipărirea se face pe schema parcurgerii prezentate mai sus, cu două foruri. Acolo este foloseste a[ linie ][ coloana ] este cout << a [ line ][ column ];
Lăsând exact așa codul nu se obține efectul dorit de noi întrucât elementele se afișează absolut toate unul după altul, fără ca odată cu linie nouă în matrice să se treacă la linie nouă pe ecran. Unii începători se grăbesc și înlocuiesc caracterul spațiu cu un caracter rând nou, dar nici așa nu obținem ceea ce ne dorim, de data asta absolut toate elementele apărând unul sub altul, deci fiecare pe câte un rând.
Soluția, care este prezentată în codul de mai jos, este să păstrăm spațiu la tipărirea fiecărui element, dar când se schimbă linia să tipărim separat un caracter de rând nou. Astfel, la primul for vom avea acolade întrucât două lucruri sunt de făcut la linia pe care acesta o pune în evidență: tipărirea, cu spații între ele, a elementelor liniei și trecerea pe ecran la linia următoare.
cin>>n>>m;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++)
cout << a[i][j] << “ ”;
cout << “\n”;
}Odată ce vom avansa în tainele progrmării ne vom lovi de nevoia de a sincroniza datele din memorie de ceea ce dorim să apară pe ecran. Ceea ce este mai sus poate fi privit și în acest mod.
Probleme rezolvate:
Ca și la alte capitole, aceste probeme trebuie privite și ca elemente teoretice noi, fiind cerințe clasice legate de matrice.
1. Operații uzuale ce necesită parcurgerea oarecare a unei matrice. Se citesc n, m apoi cele n∙m elemente întregi ale unei matrice. Să se afișeze pe ecran:
- Suma elementelor matricei;
- Numărul de elemente pare ale matricei;
- Valorarea cea mai mare care se află pe o linie impară a matricei;
Exemplu:
| Date de intrare | Date de ieșire |
|---|---|
4 4 1 2 3 4 1 0 1 0 2 1 2 1 9 8 7 6 |
Suma elementelor: 48 Numărul de valori pare: 8 Cea mai mare valoare de pe o linie impară: 4 |
Rezolvare:
#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;
}Pentru cerința cu suma avem de realizat parcurgerea matricei și operația efectivă cu elementul curent este adunarea lui la sumă. La celelalte cerințe sunt de asemenea parcurgeri însoțite de operațiile specifice. Întrucât elementele care ne interesează sunt doar o parte din totalul din matrice, avem în fiecare caz câte un if. Observați diferența între testul de paritate e elementului (a[ i ][ j ] % 2) și cel de paritate a indicelui (i % 2).
La final, în comentarii, este o alternativă de rezolvare a ultimei cerințe. Mergând cu indicele de linie din doi în doi traversăm doar liniile care ne interesează (cele impare), nemaifiind necesar testul de paritate pentru linie. Aceasta este și o soluție mai bună ca timp întrucât se vizitează doar elementele care interesează din matrice
2. Parcurgerea matricei linie cu linie. Se citesc n, m apoi cele n∙m elemente întregi ale unei matrice cu n linii și m coloane. Să se afișeze suma elementelor de pe fiecare linie. Aceste valori se vor afișa pe o singură linie a ecranului, separate prin spațiu
Exemplu:
| Date de intrare | Date de ieșire |
|---|---|
3 4 5 5 10 5 3 9 1 2 4 10 1 2 |
25 15 17
|
Rezolvare:
Varianta 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;
}Varianta 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;
}La varianta 1 traversăm matricea linie cu linie și înainte de a analia o linie ne-o imaginăm ca pe un vector, calculându-i suma. Folosim de fiecare dată aceeași variabilă și este necesar ca înaintea fiecărei linii să o inițializăm și imediat după parcurgerea liniei să facem afișarea. La varianta 2 am folosit un vector auxiliar, astfel, s[ i ] este suma elementelor de pe linia i . În acest fel nu trebuie să ne facem griji de afișare în timpul parcurgerii matricei întrucât datele rămân în vector și ulterior putem realiza cu ele operațiile dorite.
Am numit această problemă parcurgerea matricei linie cu linie întrucât la traversarea elementelor matricei vizităm mai întâi linia 1 în întregime, apoi linia 2 în întregime ... Aceasta este de fapt parcurgerea clasică pe care am prezentat-o la început.