Vectori și algoritmi comuni

Citire

Există două cazuri principale în care putem să citim un vector. Atunci când se specifică numărul său de elemente, n, și atunci când nu se specifică.

Numărul de elemente este cunoscut

Atunci când numărul de elemente este cunoscut, n, vom citi n numere într-un tablou unidimensional.

Exemplu

int v[50];
int n;

int main() {
    ...

    cin >> n;

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

    ...
}

• este important de știut că declarând un vector global, în afara main-ului sau a unei funcții, acesta este inițializat cu valoarea 0 pe toate pozițiile.

Numărul de elemente NU este cunoscut

Atunci când nu cunoaștem exact numărul de elemente pe care trebuie să îl citim vom avea probleme ce ne vor cere să citim dintr-un fișier. În acest caz, vom citi cât de mult putem dintr-un fișier, până atingem caracterul \EOF, sau mai simplu spus, citim atât timp cât avem ceva de citit.

Exemplu

fisier.txt

1 55 2 6 24 223 6 7
3 4

main.cpp

ifstream fin("fisier.txt");

int v[50];

int main() {
    ...

    int x;
    int idx = 0;

    while (cin >> x) {
        v[idx] = x;
        idx++;
    }

    ...
}

În v se vor reține, în această ordine, numerele 1, 55, 2, 6, 24, 223, 6, 7, 3, 4.

Vectori caracteristici / de apariție

Vectorii caracteristici au rolul de a marca dacă un element apare sau nu într-un șir dat. Aceștia sunt de obicei de tip bool, deoarece nu necesită alte informații în plus.

• un vector caracteristic are dimensiune constantă
• un vector caracteristic trebuie inițializat cu valoarea 0 sau fals
• valorile posibile se află printre indicii vectorului caracteristic. Pentru un șir de numere cu valori cuprinse între 2 și 1000, vom declara un vector caracteristic de mărime cel puțin 1001, pentru a cuprinde toate valorile posibile.
  

Exemplu

fisier.txt

2 55 2 6 24 223 6 7 1000

main.cpp

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("fisier.txt");

bool car[1005];

int main() {
    int x;

    while (fin >> x) {
        car[x] = true;
    }

    return 0;
}

În vectorul de apariții, pozițiile care au valoarea de true sunt 2, 55, 2, 6, 24, 223, 6, 7, 1000.

Vectori de frecvență

Vectorii de frecvență au rolul de a număra de câte ori apare o valoare într-un șir dat. Este similar cu vectorul caracteristic, însă acum nu vom marca apariția, ci vom incrementa valoarea de pe poziția respectivă. Acesta este de obicei de tipul int.

• un vector caracteristic are dimensiune constantă
• un vector caracteristic trebuie inițializat cu valoarea 0
• valorile posibile se află printre indicii vectorului caracteristic. Pentru un șir de numere cu valori cuprinse între 2 și 1000, vom declara un vector caracteristic de mărime cel puțin 1001, pentru a cuprinde toate valorile posibile.
  

Exemplu

fisier.txt

2 55 2 6 6 7 6 1000

main.cpp

#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("fisier.txt");

bool frv[1005];

int main() {
    int x;

    while (fin >> x) {
        frv[x]++;
    }

    return 0;
}

În vectorul de frecvență, poziția 2 are valoare 2, poziția 6 are valoare 3, 7 are 1, 55 are 1 și 1000 are 1. Restul pozițiilor au valoarea 0.

Probleme cu secvențe

pbInfo