|
|
|
Vectori alocati dinamic
Putem distinge doua situatii de alocare dinamica pentru vectori:
- Dimensiunea vectorului este cunoscuta de program inaintea valorilor ce trebuie memorate in vector si nu se mai modifica pe durata executiei programului; in acest caz este suficienta o alocare initiala de memorie pentru vector ("malloc").
- Dimensiunea vectorului nu este cunoscuta de la inceput sau numarul de elemente poate creste pe masura ce programul evolueaza; in acest caz este necesara extinderea dinamica a tabloului (se apeleaza repetat 'realloc').
In limbajul C nu exista nici o diferenta intre utilizarea unui vector alocat dinamic si utilizarea unui vector cu dimensiune constanta, iar functia 'realloc' simplifica extinderea (realocarea) unui vector dinamic cu pastrarea datelor memorate. Exemplu de ordonare a unui vector de numere folosind un vector alocat dinamic.
// comparatie de intregi - pentru qsort
int intcmp (const void * p1, const void * p2)
// citire - sortare - afisare
void main ()
In aplicatiile care prelucreaza cuvintele distincte dintr-un text, numarul acestor cuvinte nu este cunoscut si nu poate fi estimat, dar putem folosi un vector realocat dinamic care se extinde atunci cand este necesar. Exemplu:
// cauta cuvant in vector
int find ( char ** tab, int n, char * p)
#define INC 100
void main ()
tab[n++]=pc; // adauga la vector adresa cuvant
}
}
Functia 'realloc' primeste ca argumente adresa vectorului ce trebuie extins si noua sa dimensiune si are ca rezultat o alta adresa pentru vector, unde s-au copiat automat si datele de la vechea adresa. Aceasta functie este apelata atunci cand se cere adaugarea de noi elemente la un vector plin (in care nu mai exista pozitii libere).
Utilizarea functiei 'realloc' necesita memorarea urmatoarelor informatii despre vectorul ce va fi extins: adresa vector, dimensiunea alocata (maxima) si dimensiunea efectiva. Cand dimensiunea efectiva ajunge egala cu dimensiunea maxima, atunci devine necesara extinderea vectorului. Extinderea se poate face cu o valoare constanta sau prin dublarea dimensiunii curente sau dupa alta metoda.
Exemplul urmator arata cum se pot incapsula in cateva functii operatiile cu un vector alocat si apoi extins dinamic, fara ca alocarea si realocarea sa fie vizibile pentru programul care foloseste aceste subprograme.
#define INC 100 // increment de exindere vector
typedef int T; // tip componente vector
typedef struct Vector;
// initializare vector v
void initV (Vector & v)
// adaugare obiect x la vectorul v
void addV ( Vector & v, T x)
v.vec[v.dim]=x; v.dim ++;
Exemplu de program care genereaza si afiseaza un vector de numere:
void main()
Timpul necesar pentru cautarea intr-un vector neordonat este de ordinul O(n), deci proportional cu dimensiunea vectorului. Intr-un vector ordonat timpul de cautare este de ordinul O(lg n). Adaugarea la sfarsitul unui vector este imediata ( are ordinul O(1)) iar eliminarea dintr-un vector compact necesita mutarea in medie a n/2 elemente, deci este de ordinul O(n).
