superrinfo: Tablouri unidimensionale

DECLARAREA TABLOURILOR

Numim tablou o colectie (grup, multime ordonata) de date, de acelasi tip, situate intr-o zona de memorie continua (elementele tabloului se afla la adrese succesive). Tablourile sunt variabile compuse (structurate), deoarece grupeaza mai multe elemente. Variabilele tablou au nume, iar tipul tabloului este dat de tipul elementelor sale. Elementele tabloului pot fi referite prin numele tabloului si indicii (numere intregi) care reprezinta pozitia elementului in cadrul tabloului.

In functie de numarul indicilor utilizati pentru a referi elementele tabloului, putem intalni tablouri unidimensionale (vectorii) sau multidimensionale (matricile sunt tablouri bidimensionale).

Ca si variabilele simple, variabilele tablou trebuie declarate inainte de utilizare.

Modul de declarare:

tip nume_tablou[dim_1][dim_2]…[dim_n];

unde: tip reprezinta tipul elementelor tabloului; dim_1,dim_2,...,dim_n sunt numere intregi sau expresii constante intregi (a caror valoare este evaluata la compilare) care reprezinta limitele superioare ale indicilor tabloului.

TABLOURI UNIDIMENSIONALE

Tablourile unidimensionale sunt tablouri cu un singur indice (vectori).

Daca tabloul contine dim elemente, indicii elementelor au valori intregi din intervalul [0, dim-1].

Un element al unui tablou poate fi utilizat ca orice alta variabila. Adresarea unei componente se face proin indicele ei, trecut intre paranteze drepte. Se pot efectua operatii asupra fiecarui element al tabloului, nu asupra intregului tablou.

Exemple:

int vect[20]; /* declararea tabloului vect, de maximum 20 de elemente, de tipul int. Elementele tabloului vect sunt : vect[0], vect[1], …, vect[19] – date de tip int*/

double p,q,tab[10]; // declararea variabilelor simple p, q si a vectorului tab, de maximum 10 elemente, tip double

#define MAX 10

char tab[MAX]; /*declararea tabloului tab, de maximum MAX (10) elemente de tip char*/

Consideram declaratia tabloului v cu maxim 6 elemente de tip int

int v[6];

Elementele tabloului pot fi initializate prin atribuire:

v[0]=100;

v[1]=101;

v[2]=102;

v[3]=103;

v[4]=104;

v[5]=105;

100	101	102	103	104	105
v[0]	v[1]	v[2]	v[3]	v[4]	v[5]

Exemplu:

double alpha[5], beta[5], gama[5];

int i=2;

alpha[2*i-1] = 5.78;

alpha[0]=2*beta[i]+3.5;

gama[i]=aplha[i]+beta[i]; //permis

gama=alpha+beta; //nepermis

Variabilele tablou pot fi initializate in momentul declararii:

declaratie_tablou=lista_valori;

Valorile din lista de valori sunt separate prin virgula, iar intreaga lista este inclusa intre acolade:

Exemple:

int v[6]={100,101,102,103,104,105};

double x=9.8;

double a[5]={1.2, 3.5, x, x-1, 7.5};

La declararea unui vector cu initializarea elementelor sale, numarul maxim de elemente ale tabloului poate fi omis, caz in care compilatorul determina automat marimea tabloului, in functie de numarul elementelor initializate.

Exemplu:

char tab[]={ ’A’, ’C’, ’D’, ’C’};

[0] [3]

float data[5]={ 1.2, 2.3, 3.4 };

[0] [4]

Citirea elementelor unui vector:

double a[5];

int i;

for (i=0; i<5; i++)

{ cout<<”a["<<i<<”]=”; //afisarea unui mesaj prealabil citirii fiecarui element

cin>>a[i]; //citirea valorii elementului de indice i

}

Sau, pentru un vector cu n componente (n£20):

double a[20]; int i, n;

cout<<”Dim. Max. =”; cin>>n;

for (i=0; i<n; i++)

{ cout<<”a[“<<i<<”]=”;

cin>>a[i];

}

Pentru simplitate, se pot considera elementele vectorului incepand cu pozitia 1. In acest caz, primul element al tabloului ramane neutilizat, iar valoarea sa este cea alocata implicit la compilare.

double a[20]; int i, n;

cout<<”Dim. Max. =”; cin>>n;

for (i=1; i<=n; i++)

{ cout<<”a[“<<i<<”]=”;

cin>>a[i];

}

Afisarea elementelor unui vector:

cout<<”Vectorul introdus este:\n”;

for (i=0; i<n i++)

cout<<a[i]<<’ ’;

Căutări

Căutare secvenţială

Când avem de a face cu un vector nesortat (şi nu numai în acest caz), cea mai simplă abordare pentru a găsi o valoare, este căutarea secvenţială. Cu alte cuvinte, se compară, la rând, fiecare valoare din vector cu valoarea căutată. Dacă valoarea a fost găsită, căutarea se poate opri (nu mai are sens să parcugem vectorul până la capăt, dacă nu se cere acest lucru explicit).
Exemplu:

#define MAX 100
 
...
 
int v[MAX],x,i;
 
/*initializari*/
...
 
for(i=0;i<MAX;i++)
  if(x==v[i])
  {
    printf("Valoarea %d a fost gasita in vector\n",x);
    break;
  }
 
printf("Valoarea %d nu a fost gasita in vector\n",x);
...

Căutare binară iterativă

Dacă vectorul pe care se face căutarea este sortat, algoritmul mai eficient de folosit în acest caz este căutarea binară. Presupunem că vectorul este sortat crescător (pentru vectori sortaţi descrescător, raţionamentul este similar). Valoarea căutată, x, se compară cu valoarea cu indexul N/2 din vector, unde N este numărul de elemente. Dacă x este mai mic decât valoarea din vector, se caută în prima jumătate a vectorului, iar dacă este mai mare, în cea de-a doua jumătate.
Căutarea în una dintre cele două jumătăţi se face după acelaşi algoritm. Conceptual, căutarea binară este un algoritm recursiv, dar poate fi implementat la fel de bine într-un mod iterativ, folosind indecşii corespunzători bucăţii din vector în care se face căutarea. Aceşti indecşi se modifică pe parcursul algoritmului, într-o buclă, în funcţie de comparaţiile făcute.
Evoluţia algoritmului este ilustrată în imaginea de mai jos.

Pseudocodul pentru căutarea binară:

căutare_binară (v[0..N], x)
{
low = 0
high = N - 1
cât timp (low <= high) 
{
  mid = (low + high) / 2
    dacă v[mid] > value
      high = mid - 1
    altfel
      dacă v[mid] < value
        low = mid + 1
      altfel
        găsit x pe poziţia mid
 }     
 x nu a fost găsit
}

Sortări

Bubble Sort

Metoda bulelor este cea mai simplă modalitate de sortare a unui vector, dar şi cea mai ineficientă. Ea funcţionează pe principiul parcurgerii vectorului şi comparării elementului curent cu elementul următor. Dacă cele două nu respectă ordinea, sunt interschimbate. Această parcurgere este repetată de suficiente ori până când nu mai există nici o interschimbare în vector.

Sortarea prin selecţie

Sortarea prin selecţie oferă unele îmbunătăţiri în ceea ce priveşte complexitatea, însă este departe de a fi considerat un algoritm eficient. Presupunând că se doreşte sortarea crescătoare a vectorului, se caută minimul din vector, şi se interschimbă cu primul element – cel cu indexul 0. Apoi se reia acelaşi procedeu pentru restul vectorului.
Motivul pentru care algoritmul de sortare prin selecţie este mai eficient este acela că vectorul în care se caută minimul devine din ce în ce mai mic, şi, evident, căutarea se face mai repede la fiecare pas.

Cuvânt înainte.....

Tablouri unidimensionale