Pe scurt
Structurile de date liniare sunt colecții ordonate de elemente, fiecare având un predecesor și un succesor unic (cu excepția primului și ultimului). Vectorii oferă acces direct în timp O(1), iar listele permit inserări și ștergeri eficiente în O(1) dacă se cunoaște poziția, dar accesul aleator este O(n). Înțelegerea acestor structuri este esențială pentru rezolvarea problemelor de programare, inclusiv la bacalaureat.
Vectori (tablouri unidimensionale)
Vectorii sunt cele mai simple structuri liniare, caracterizate prin acces direct în timp O(1) la orice element prin index.
- Vector static:
tip nume[dimensiune]
- Vector dinamic: std::vector
- Operații de bază: inserare, ștergere, căutare, sortare, parcurgere
- Sortare:
- Bubble Sort (O(n²))
- Quick Sort (O(n log n) în medie)
- Exemplu: Se dă un vector cu n elemente întregi. Să se calculeze suma elementelor pare.
- Se citește n, se declară
int a[100], se citesc elementele într-un for
- Se inițializează s=0, apoi for(i=0;i<n;i++) if(a[i]%2==0) s+=a[i];
- Se afișează s. Complexitate O(n).
Matrice (tablouri bidimensionale)
Matricele extind conceptul la două dimensiuni, fiind reprezentate ca vectori de vectori.
- Acces la element:
matrice[i][j]
- Parcurgere: cu bucle imbricate (
for i, for j)
- Exemplu: Se dă o matrice pătrată de ordin n. Să se calculeze suma elementelor de pe diagonala principală.
- Se citesc n și elementele în
int a[100][100]
- Se parcurge cu for(i=0;i<n;i++) s+=a[i][i];
- Se afișează s. Complexitate O(n).
Liste simplu și dublu înlănțuite
Listele sunt structuri dinamice în care elementele (nodurile) conțin informația și adresa (adresele) următorului (și precedentului) nod.
- Avantaje: inserare și ștergere eficientă în O(1) dacă se cunoaște poziția
- Dezavantaje: accesul aleator este O(n)
- În C++:
std::list implementează o listă dublu înlănțuită
- Operații: inserare, ștergere, căutare, sortare, parcurgere (cu iteratori)
- Sortare: merge sort pe liste
- Exemplu: Se dă o listă simplu înlănțuită de numere întregi. Să se insereze un nod cu valoarea x după un nod care conține valoarea y (dacă există).
- Se parcurge lista cu un pointer
p
- Când p->info==y, se alocă un nou nod q=new nod; q->info=x; q->next=p->next; p->next=q;
- Complexitate O(n) la căutare, O(1) la inserare.
Aplicații practice
- Stive (LIFO) – implementabile cu vectori sau liste
- Cozile (FIFO) – implementabile cu vectori sau liste
- Probleme frecvente la bacalaureat:
- Determinarea elementelor unice
- Interclasarea a doi vectori sortați
- Rotirea unei matrice
- Simularea unei cozi cu ajutorul a doi vectori
Concepte cheie
- Acces direct în vectori (O(1)) vs. acces secvențial în liste (O(n))
- Inserare și ștergere în liste (O(1) dacă se cunoaște poziția) vs. vectori (O(n) prin deplasare)
- Parcurgerea matricei cu bucle imbricate (for i, for j)
- Alocarea dinamică a nodurilor într-o listă (new/delete)
- Sortarea eficientă a vectorilor (Quick Sort/merge sort) și a listelor (merge sort pe liste)
Verifică-te!
- Care este complexitatea accesului la un element într-un vector și într-o listă simplu înlănțuită?
- Cum se declară un vector static în C++ și cum se accesează un element dintr-o matrice?
- Ce operație este mai eficientă în liste decât în vectori și în ce condiție?