|
|
|
Vectori
Structura de vector ("array") este foarte folosita datorita avantajelor sale:
- Nu trebuie memorate decat datele necesare aplicatiei (nu si adrese de legatura);
- Este posibil accesul direct (aleator) la orice element dintr-un vector prin indici;
- Programarea operatiilor cu vectori este foarte simpla.
- Cautarea intr-un vector ordonat este foarte eficienta, prin cautare binara.
Dezavantajul unui vector cu dimensiune constanta rezulta din necesitatea unei estimari a dimensiunii sale la scrierea programului. Pentru un vector alocat si realocat dinamic poate apare o fragmentare a memoriei dinamice rezultate din realocari repetate pentru extinderea vectorului. De asemenea, eliminarea de elemente dintr-un vector compact poate necesita deplasarea elementelor din vector.
Prin vectori se reprezinta si anumite cazuri particulare de liste inlantuite sau de arbori pentru reducerea memoriei ocupate si timpului de prelucrare.
Ca tipuri de vectori putem mentiona:
- Vectori cu dimensiune fixa (constanta);
- Vectori extensibili ( realocabili dinamic);
- Vectori de biti (la care un element ocupa un bit);
- Vectori "heap" (care reprezinta compact un arbore binar particular);
- Vectori ca tabele de dispersie.
De obicei un vector este completat in ordinea crescatoare a indicilor, fie prin adaugare la sfarsit a noilor elemente, fie prin insertie intre alte elemente existente, pentru a mentine ordinea in vector.
Exista si exceptii de la cazul uzual al vectorilor cu elemente consecutive : vectori cu interval ("buffer gap") si tabele de dispersie ("hash tables").
Un "buffer gap" este folosit in procesoarele de texte; textul din memorie este impartit in doua siruri pastrate intr-un vector ("buffer" cu text) dar separate intre ele printr-un interval plasat in pozitia curenta de editare a textului. In felul acesta se evita mutarea unor siruri lungi de caractere in memorie la modificarea textului; insertia de noi caractere in pozitia curenta mareste secventa de la inceputul vectorului si reduce intervalul, iar stergerea de caractere din pozitia curenta mareste intervalul dintre caracterele aflate inainte si respectiv dupa pozitia curenta.
Mutarea cursorului necesita mutarea unor caractere dintr-un sir in celalalt, dar numai ca urmare a unei operatii de modificare in noua pozitie a cursorului.
Caracterele sterse sau inserate sunt de fapt memorate intr-un alt vector, pentru a se putea reconstitui un text modificat din greseala (operatia "undo" de anulare a unor operatii si de revenire la o stare anterioara).
Vectorii cu dimensiune constanta, fixata la scrierea programului, se folosesc in unele situatii particulare cand limita colectiei este cunoscuta si relativ mica sau cand se doreste simplificarea programelor, pentru a facilita intelegerea lor. Alte situatii pot fi cea a unui vector de constante sau de cuvinte cheie, cu numar cunoscut de valori.
Vectori cu dimensiune fixa se folosesc si ca zone tampon la citirea sau scrierea in fisiere text sau in alte fluxuri de date.
Vectorul folosit intr-un tabel de dispersie are o dimensiune constanta (preferabil, un numar prim) din cauza modului in care este folosit (se va vedea ulterior).
Un fisier binar cu articole de lungime fixa poate fi privit ca un vector, deoarece are aceleasi avantaje si dezavantaje, iar operatiile sunt similare: adaugare la sfarsit de fisier, cautare secventiala in fisier, acces direct la un articol prin indice (pozitie relativa in fisier), sortare fisier atunci cand este nevoie, s.a. La fel ca intr-un vector, operatiile de insertie si de stergere de articole consuma timp si trebuie evitate sau amanate pe cat posibil.
