Vectori (tablouri unidimensionale)

Până acum, am prelucrat numere „din mers” - le citeam pe rând și le foloseam imediat, fără a le păstra pe toate.

Dar sunt probleme în care avem nevoie de toate valorile simultan:

• să afișăm numerele în ordine inversă;
• să căutăm o valoare după ce am citit tot șirul;
• să comparăm elemente aflate la distanță;
• să sortăm numerele.

Pentru aceste situații, folosim vectori.

Ce este un vector?

Un vector este o colecție de valori de același tip, stocate una lângă alta în memorie, fiecare având un indice (un număr de ordine).

Imaginează-ți un șir de cutii numerotate:

indice:    |  0  |  1  |  2  |  3  |  4  |
           +-----+-----+-----+-----+-----+
valoare:   |  3  |  7  |  2  |  9  |  4  |
           +-----+-----+-----+-----+-----+

Fiecare cutie are:

• un indice (poziția) - începe de la 0;
• o valoare - numărul stocat acolo.

Declararea unui vector

int v[100];

Aceasta creează un vector cu cel mult 100 de elemente de tip int.

Putem folosi oricâte din cele 100 de poziții - de obicei, folosim primele n.

Accesarea elementelor

Fiecare element se accesează prin indice, folosind paranteze pătrate []:

v[0] = 3;   // primul element
v[1] = 7;   // al doilea element
v[2] = 2;   // al treilea element

cout << v[1]; // afișează 7

Atenție la indici

În C++, indicii încep de la 0.

Un vector cu n elemente are indicii de la 0 la n - 1.

Citirea unui vector din fișier

De obicei, pe prima linie primim n (numărul de elemente), iar pe a doua linie cele n valori.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    return 0;
}

date.in:

5
3 7 2 9 4

După citire, vectorul arată așa (indexat de la 1):

v[1] = 3,  v[2] = 7,  v[3] = 2,  v[4] = 9,  v[5] = 4

Afișarea unui vector

for (int i = 1; i <= n; i++) {
    fout << v[i] << " ";
}

Output:
3 7 2 9 4

Afișarea în ordine inversă

Acesta este un exemplu clasic pentru care avem nevoie de vector - nu putem afișa invers dacă nu avem toate valorile stocate.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    for (int i = n; i >= 1; i--) {
        fout << v[i] << " ";
    }

    return 0;
}

date.in:

5
3 7 2 9 4

date.out:

4 9 2 7 3

Suma elementelor unui vector

int suma = 0;

for (int i = 1; i <= n; i++) {
    suma = suma + v[i];
}

fout << suma;

Maximul și minimul dintr-un vector

int maxim = v[1];
int minim = v[1];

for (int i = 2; i <= n; i++) {
    if (v[i] > maxim) {
        maxim = v[i];
    }
    if (v[i] < minim) {
        minim = v[i];
    }
}

fout << "Max: " << maxim << endl;
fout << "Min: " << minim << endl;

Căutarea unei valori în vector

Problema: avem un vector și un număr x. Vrem să aflăm dacă x există în vector.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int x;
    fin >> x;

    int gasit = 0;

    for (int i = 1; i <= n; i++) {
        if (v[i] == x) {
            gasit = 1;
        }
    }

    if (gasit == 1) {
        fout << "DA";
    } else {
        fout << "NU";
    }

    return 0;
}

date.in:

5
3 7 2 9 4
7

date.out:

DA

Numărarea aparițiilor unei valori

int x;
fin >> x;

int cnt = 0;

for (int i = 1; i <= n; i++) {
    if (v[i] == x) {
        cnt++;
    }
}

fout << cnt;

Modificarea elementelor unui vector

Putem modifica valorile direct:

// Dublăm fiecare element
for (int i = 1; i <= n; i++) {
    v[i] = v[i] * 2;
}

Sau putem înlocui o valoare specifică:

// Înlocuim toate aparițiile lui 0 cu 1
for (int i = 1; i <= n; i++) {
    if (v[i] == 0) {
        v[i] = 1;
    }
}

Inserarea unui element

Vrem să inserăm o valoare val pe poziția poz. Trebuie să mutăm toate elementele de la poz la n cu o poziție la dreapta.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int poz, val;
    fin >> poz >> val;

    // Mutăm elementele la dreapta
    for (int i = n; i >= poz; i--) {
        v[i + 1] = v[i];
    }

    v[poz] = val;
    n++;

    for (int i = 1; i <= n; i++) {
        fout << v[i] << " ";
    }

    return 0;
}

date.in:

5
3 7 2 9 4
3 5

date.out:

3 7 5 2 9 4

Pas cu pas (inserăm 5 pe poziția 3)

Înainte: 3 7 2 9 4

1. Mutăm v[5] → v[6]: 3 7 2 9 4 4
2. Mutăm v[4] → v[5]: 3 7 2 9 9 4
3. Mutăm v[3] → v[4]: 3 7 2 2 9 4
4. Punem v[3] = 5: 3 7 5 2 9 4
5. n devine 6

Ștergerea unui element

Vrem să ștergem elementul de pe poziția poz. Mutăm toate elementele de la poz + 1 la n cu o poziție la stânga.

int poz;
fin >> poz;

for (int i = poz; i < n; i++) {
    v[i] = v[i + 1];
}

n--;

Exemplu

Vector: 3 7 2 9 4, ștergem poziția 2.

1. v[2] = v[3]: 3 2 2 9 4
2. v[3] = v[4]: 3 2 9 9 4
3. v[4] = v[5]: 3 2 9 4 4
4. n devine 4

Rezultat: 3 2 9 4

Exemplu complet: elementele distincte

Afișăm fiecare valoare o singură dată (eliminăm duplicatele).

Ideea: pentru fiecare element, verificăm dacă a mai apărut înainte de el.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    for (int i = 1; i <= n; i++) {
        int aparut = 0;

        for (int j = 1; j < i; j++) {
            if (v[j] == v[i]) {
                aparut = 1;
            }
        }

        if (aparut == 0) {
            fout << v[i] << " ";
        }
    }

    return 0;
}

date.in:

8
3 7 2 7 4 3 9 2

date.out:

3 7 2 4 9

Declararea vectorului - unde și cum

La concursuri, vectorul se declară global (înainte de main), exact ca fin și fout:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[1001]; // global
int n;       // global

int main()
{
    // ...
}

De ce global?

• Vectorii mari (peste ~1000 de elemente) pot cauza probleme dacă sunt declarați în main (spațiu limitat pe stivă).
• Variabilele globale sunt inițializate automat cu 0.
• Este mai simplu - accesibile oriunde.

Greșeli frecvente

1. Depășirea limitelor vectorului

int v[100];
v[100] = 5; // GREȘIT! Indicii sunt de la 0 la 99

Dacă vectorul are 100 de poziții (indici 0 la 99), accesarea v[100] este în afara vectorului și poate cauza erori grave.

2. Uitarea citirii lui n

for (int i = 1; i <= n; i++) { // n nu a fost citit!
    fin >> v[i];
}

Variabila n trebuie citită înainte de buclă.

3. Confuzia între indice și valoare

• v[3] este valoarea de pe poziția 3
• 3 este indicele (poziția)

// Greșit: afișăm indicele în loc de valoare
cout << i;

// Corect: afișăm valoarea
cout << v[i];

4. Inserare/ștergere în direcția greșită

La inserare, mutăm de la dreapta la stânga. La ștergere, mutăm de la stânga la dreapta.

Dacă inversăm direcția, suprascriem valori înainte de a le salva.

5. Vectorul prea mic

Dacă n poate fi cel mult 1000, vectorul trebuie declarat v[1001] (cu o poziție în plus pentru indexarea de la 1).

Ce să reții

• Un vector stochează mai multe valori de același tip, accesibile prin indice.
• Indicii în C++ încep de la 0, dar la concursuri se folosește frecvent indexarea de la 1.
• Declarăm vectorul global, suficient de mare.
• Citirea: buclă for de la 1 la n, cu fin >> v[i].
• Cu vectori putem: afișa invers, căuta, număra, insera, șterge, elimina duplicate.
• Atenție la limitele vectorului - nu depăși indicele maxim.
• Inserarea se face de la dreapta la stânga, ștergerea de la stânga la dreapta.

Probleme

pbinfoParitate1→

pbinfoAfisare0→

pbinfoAfisare→

pbinfoPozminmax→

pbinfoConstr2→