Tablouri unidimensionale (vectori)

Introducere în vectori

BIBLIOGRAFIE:

Un tablou cu o singură dimensiune este o succesiune de variabile având toate de acelaşi tip (tipul de bază al tabloului), care ocupă o zonă contiguă de memorie. Un tablou are:

  • o dimensiune (egală cu numărul de elemente al tabloului)
  • un nume (care identifică global tabloul)
  • o clasă de alocare
  • un tip comun tuturor elementelor tabloului

Dimensiunea tabloului precizează numărul de elemente printr-o constantă întreagă sau printr-o expresie constantă.

La declararea unui tablou se specifică: numele, tipul de bază, clasa de alocare şi dimensiunea:

tip nume[dimensiune]

//Exemple:

int x[10]; /* tablou de 10 intregi */
char litere[2*26]; /* tablou de 52 caractere */

Numele tabloului este adresa primului element din tablou (de exemplu x este adresa primului element, adică @x[0] ). Aceasta explică de ce nu este permisă o atribuire între două tablouri. Accesul la un element din tablou se face printr-o variabilă indexată, formată din numele tabloului şi un index - o expresie cuprinsă între 0 şi dimensiune-1. Primul element va fi desemnat aşadar prin x[0], al doilea element prin x[1], al N-lea prin x[N-1]

Prelucrările pe tablouri se implementează cu cicluri for.

Este important de remarcat faptul că elementele neiniţializate pot avea valori oarecare. La alocarea unui vector, compilatorul nu efectuează nici un fel de iniţializare şi nu furnizează nici un mesaj de eroare dacă un element este folosit înainte de a fi iniţializat. Un program corect va iniţializa, în orice caz, fiecare element înainte de a-l folosi.

La declararea unui tablou, acesta poate fi şi iniţializat, dacă declaraţia este urmată de semnul = şi de o listă de valori iniţiale, separate prin virgule şi incluse între acolade. Exemple:

int prime[5]={2,3,5,7,11};
char vocale[5]={'a','e','i','o','u'};

La declararea unui tablou iniţializat se poate omite dimensionarea, situaţie în care se ia ca dimensiune numărul de valori iniţiale:

char operator[]={'+','-','*','/'};
long x[]={1,10,100,1000,10000,100000};

Tablourile din exemplele de mai sus vor avea 4, respectiv 6 elemente.

O observație care merită menționată: Vectorul este o structură statică: dimensiunea acestuia trebuie să fie o constantă la compilare şi nu poate fi modificată în cursul execuţiei programului.

Limbajele C/C++ nu ne permit să declarăm o variabilă tablou cu număr variabil de componente (există şi limbaje care permit aceasta, de exemplu, Basic). De multe ori nu ştim câte componente vor fi necesare pentru o anumită rulare a programului. Orice problemă în care se lucrează cu variabile de tip tablou şi în care se cere prelucrarea unui număr (care nu se cunoaşte de la început) de componente, constituie un exemplu în acest sens. Atunci ce facem? Ideea este să rezervăm un număr maxim de componente - atât cât este necesar pentru rulare atunci când n este maxim. La fiecare rulare a programului se cere numărul de componente. De cele mai multe ori o parte dintre ele rămân neutilizate. Există tehnici precum folosirea pointerilor și a alocării dinamice, dar sunt în afara scopului lecției introductive la vectori, întrucât în C se fac într-un fel, în C++ în multe alte feluri.

Se poate face inițializarea întregului tablou cu o singură valoare astfel:

int x[10] = {0}

Erori pe care le puteți face:

  • Depăşirea limitelor indicilor (index out of bounds) este o eroare frecventă, ce poate duce la blocarea programului sau a sistemului şi poate fi evitată prin verificarea încadrării în intervalul valid.

  • Indici folosiţi greşit în bucle imbricate (index cross-talk). Sunt multe cazuri în care pe un nivel al buclei se foloseşte, de exemplu vect[i], şi pe nivelul imbricat vect[j], când de fapt se dorea folosirea lui i. Mare atenţie şi în astfel de cazuri!

Citire/scriere (întâlnit, în general, în probleme):

int main() 
{
  int a[100], n, i; /* vectorul a are maxim 100 de intregi */
 
  cin >> n; /* citeste nr de elemente vector */
 
  for (i = 0; i < n; i++) {
    cin >> a[i]; /* citire elemente vector */
  }
 
  for (i = 0; i < n; i++) {
    cout << a[i]; /* scrie elemente vector */
  }
 
  return 0;
}

Un exemplu de problemă: Să se determine poziţia elementului minim al unui tablou cu maxim 100 de elemente reale. Dimensiunea n a tabloului și tabloul se citesc de la tastatură:

#include <iostream>

using namespace std;

int main()
{
    int n, i, pm;
    double x[100];

    cin >> n;
    cin >> x[0]; pm = 0; //inițializăm minimul la primul element
    
    for(i = 1; i < n; i++) {
        cin >> x[i];
        if(x[i] < x[pm])
            pm = i;
    }
    
    cout << pm << endl;
}

O rulare ușor modificată a programului de sus o puteți urmări aici

Să se genereze un vector cu primele n numere din șirul lui Fibonacci:

#include <iostream>

using namespace std;

int main() 
{
  long fib[100] = {1, 1};
  int n, i;
 
  cin >> n;
 
  for (i = 2; i < n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  for (i = 0; i < n; i++) {
    cout << fib[i];
  }
 
  return 0;
}

O rulare ușor modificată a programului de sus o puteți urmări aici

Algoritmi de căutare secvențială și binară

BIBLIOGRAFIE:

Ce problemă dorim să rezolvăm: Se citesc n numere întregi sortate crescǎtor. De asemenea se citeşte un numǎr întreg nr. Sǎ se decidǎ dacǎ nr se gǎseşte în şirul celor n numere citite și la ce poziție se află acesta

Vizualizarea celor doi algoritmi se poate face la adresa https://info.mate10.ro/galles-dataviz/Search.html

Căutarea secvențială

Este o metodă elementară de rezolvare: Nu avem decât sǎ comparǎm, pe rând, nr cu toate numerele citite. Exemple:

sir = 1, 7, 3, 5, 2
x = 3
Rezultat: 2

sir = 1, 7, 3, 5, 2
x = 4
Rezultat: -1

Implementarea în C++ este:


#include <iostream>

using namespace std;

int main()
{
    int v[100], n, nr, i, pos;

    cin >> n;
    for (i = 0; i < n; i++)
        cin >> v[i];
    
    cin >> nr;

    for (i = 0; i < n; i++) {
        if (v[i] == nr)
            pos = i;
    }

    cout << pos;
}

Căutarea binară

Este explicat și aici https://www.pbinfo.ro/articole/3633/cautarea-binara

Existǎ un algoritm mai rapid. Acesta este algoritmul de cǎutare binarǎ şi ţine cont de faptul cǎ numerele citite sunt sortate crescǎtor. Ideea de la care se porneşte este simplǎ: cǎutarea se efectueazǎ între numerele reţinute de componente de indice reţinute de douǎ variabile li şi ls (iniţial li=1 şi ls=n).

Fiind date li şi ls procedǎm astfel:

  • se calculeazǎ indicele componentei din mijloc, în cazul în care n este impar, sau a uneia din cele douǎ plasate în mijloc, în cazul în care n este par (k=(li +ls) / 2);
  • apar trei posibilitǎţi:
    • valoarea reţinutǎ de componenta de indice calculat este egalǎ cu nr (caz în care cǎutarea se terminǎ cu succes);
    • valoarea reţinutǎ de componenta de indice calculat este mai micǎ decât nr (caz în care numǎrul va fi cǎutat între componentele de indice li=k+1 şi ls);
    • valoarea reţinutǎ de componenta de indice calculat este mai mare decât nr (caz în care numǎrul va fi cǎutat între componentele de indice li şi ls=k-1).

Cǎutarea se terminǎ când numǎrul a fost identificat sau când li>ls (cǎutare fǎrǎ succes)

Se citesc numerele de mai jos şi nr=12. Iniţial, li=1, ls=4. Avem k=(1+4) div 2=2.

cautbinexemplu

A[2]=5<12=nr

Deci li=k+1=3; ls=4, k=(li+ls) / 2=3

Cǎutarea se face între componentele de indice 3, 4, iar comparaţia se face între nr şi A[3]

#include<iostream>

using namespace std;

int main() 
{
    int a[100], n, i, li, ls, k, nr, gasit;

    cin >> n;
    for (i = 0; i < n; i++)
        cin >> a[i];

    cin >> nr;

    li = 0;
    ls = n - 1;
    gasit = 0;

    do {
        k = (li + ls) / 2;
        if (a[k] == nr) {
            cout << "gasit pe pozitia " << k + 1;
            gasit = 1;
        } else if (a[k] < nr) 
            li = k + 1;
        else
            ls = k - 1;
    } while (li <= ls && !gasit);

    if (li > ls) 
        cout << "negasit";
}

Mulțimi de numere cu vectori

Algoritmi de sortare

Sortare prin metoda bulelor (prin interschimbare)

Sortare prin inserție