Ce sunt structurile de date si de ce conteaza
Structurile de date sunt modalitati de organizare si stocare a datelor in memoria calculatorului. Gandeste-te la ele ca la diferite tipuri de recipiente: un pahar (variabila simpla) tine un singur lichid, dar un raft cu pahare (tablou) tine mai multe lichide organizate.
De ce sunt importante?
- Eficienta: Permit stocarea mai multor valori sub un singur nume, fara sa declaram sute de variabile separate
- Organizare: Faciliteaza operatiile asupra colectiilor de date (sortare, cautare, filtrare)
- Claritate: Fac programele mai usor de inteles si de intretinut
Tabloul (vectorul) este cea mai simpla si cea mai folosita structura de date:
note = [8, 9, 7, 10, 6]
// Index: 0 1 2 3 4
note[0] = 8 (primul element)
note[3] = 10 (al patrulea element)
note[4] = 6 (ultimul element)
Regula fundamentala: Indexarea incepe de la 0 ! Daca tabloul are n elemente, indexurile valide sunt de la 0 la n-1. Accesarea indexului n cauzeaza eroare!
💡 Analogie utila:
Gandeste-te la un bloc de apartamente: blocul e tabloul, fiecare apartament e un element, iar numarul apartamentului e indexul. Diferenta: in programare, primul apartament are numarul 0!
Operatii de baza cu tablouri
Tablourile suporta mai multe operatii fundamentale. Fiecare operatie are o sintaxa clara si un efect specific:
1. Accesare element (citire):
v = [5, 10, 15, 20]
x = v[0] // x devine 5
y = v[2] // y devine 15
2. Modificare element (scriere):
v[1] = 20 // tabloul devine [5, 20, 15, 20]
v[3] = v[0] + v[2] // v[3] = 5 + 15 = 20
3. Lungimea tabloului:
lungime(v)
sau
len(v)
returneaza numarul de elemente.
4. Parcurgere completa:
PENTRU i DE LA 0 LA lungime(v) - 1 EXECUTA
scrie v[i]
SFARSIT PENTRU
⚠ Eroare frecventa:
Daca tabloul are 4 elemente (indexuri 0,1,2,3), accesarea v[4] cauzeaza eroare "Index out of bounds"! Mereu verifica ca indexul < lungimea tabloului.
Citirea si afisarea tablourilor
In majoritatea problemelor, tabloul se citeste de la tastatura. Algoritmul tipic presupune citirea numarului de elemente, apoi citirea fiecarui element pe rand.
Citirea unui tablou:
scrie "Cate elemente are tabloul?"
citeste n
PENTRU i DE LA 0 LA n - 1 EXECUTA
scrie "Elementul ", i, ": "
citeste tablou[i]
SFARSIT PENTRU
Afisarea unui tablou:
PENTRU i DE LA 0 LA n - 1 EXECUTA
scrie tablou[i], " "
SFARSIT PENTRU
Afisare cu conditie: De multe ori vrem sa afisam doar elementele care indeplinesc o conditie. De exemplu, doar numerele pare:
PENTRU i DE LA 0 LA n - 1 EXECUTA
DACA tablou[i] MOD 2 = 0 ATUNCI
scrie tablou[i], " "
SFARSIT PENTRU
💡 Sfat:
La evaluare, cand ti se cere sa "afisezi elementele care...", mereu combini parcurgerea cu un DACA in interiorul buclei. Este un tipar foarte frecvent!
Cautarea secventiala (liniara)
Cautarea secventiala este cel mai simplu algoritm de cautare: parcurgem tabloul element cu element pana gasim ce cautam sau ajungem la sfarsit.
Algoritmul:
citeste valoare_cautata
gasit = false
pozitie = -1
PENTRU i DE LA 0 LA n - 1 EXECUTA
DACA tablou[i] = valoare_cautata ATUNCI
gasit = true
pozitie = i
SFARSIT PENTRU
DACA gasit = true ATUNCI
scrie "Gasit la pozitia ", pozitie
ALTFEL
scrie "Nu a fost gasit"
Caracteristici:
- Functioneaza pe orice tablou (sortat sau nesortat)
- In cel mai rau caz, parcurge toate elementele (O(n))
- In cel mai bun caz, gaseste la prima pozitie (O(1))
- Simplu de implementat, dar lent pentru tablouri foarte mari
Variante: Poti cauta prima aparitie (te opresti cand gasesti), ultima aparitie (continui pana la sfarsit), sau numarul de aparitii (contorizezi de cate ori apare).
⚠ Atentie:
Daca vrei doar prima aparitie, adauga un
break
sau o conditie suplimentara in bucla ca sa te opresti imediat ce gasesti. Altfel, variabila
pozitie
va retine ULTIMA aparitie.
Cautarea binara - cautare rapida in tablouri sortate
Cautarea binara este un algoritm mult mai rapid decat cautarea secventiala, dar functioneaza doar pe tablouri sortate . Ideea: la fiecare pas eliminam jumatate din elementele ramase.
Cum functioneaza (analogie): Gandeste-te ca ghicesti un numar intre 1 si 100. In loc sa intrebi "Este 1? Este 2? Este 3?...", intrebi "Este mai mare decat 50?" si elimini jumatate din posibilitati dintr-o singura intrebare!
Algoritmul:
stanga = 0
dreapta = n - 1
gasit = false
CAT TIMP stanga <= dreapta SI gasit = false EXECUTA
mijloc = (stanga + dreapta) DIV 2
DACA tablou[mijloc] = valoare_cautata ATUNCI
gasit = true
ALTFEL DACA valoare_cautata < tablou[mijloc] ATUNCI
dreapta = mijloc - 1
ALTFEL
stanga = mijloc + 1
Comparatie performanta:
| Criteriu | Secventiala | Binara |
|---|---|---|
| Necesita sortare? | Nu | Da |
| Pasi maximi (1000 elem.) | 1000 | 10 |
| Complexitate | O(n) | O(log n) |
Sortarea Bubble Sort (prin interschimbare)
Bubble Sort este cel mai simplu algoritm de sortare. Compara elemente vecine si le interschimba daca sunt in ordine gresita. Procesul se repeta pana cand tabloul e sortat.
Algoritmul complet:
REPETA
schimbat = false
PENTRU i DE LA 0 LA n - 2 EXECUTA
DACA tablou[i] > tablou[i + 1] ATUNCI
// Interschimbare
temp = tablou[i]
tablou[i] = tablou[i + 1]
tablou[i + 1] = temp
schimbat = true
PANA CAND schimbat = false
Exemplu pas cu pas: Sortam [5, 2, 8, 1] crescator:
| Trecere | Comparari si rezultat |
|---|---|
| 1 | [5,2]swap [2,5,8,1] | [5,8]ok | [8,1]swap = [2, 5, 1, 8] |
| 2 | [2,5]ok | [5,1]swap = [2, 1, 5, 8] |
| 3 | [2,1]swap = [1, 2, 5, 8] - SORTAT! |
💡 De ce "Bubble"?
Numele vine de la faptul ca elementele mari "plutesc" spre sfarsitul tabloului ca bulele de aer in apa, trecere dupa trecere.
Sortarea prin selectie (Selection Sort)
Selection Sort lucreaza diferit fata de Bubble Sort: la fiecare pas, gaseste minimul din partea nesortata a tabloului si il pune pe pozitia corecta.
Algoritmul:
PENTRU i DE LA 0 LA n - 2 EXECUTA
poz_min = i
PENTRU j DE LA i + 1 LA n - 1 EXECUTA
DACA tablou[j] < tablou[poz_min] ATUNCI
poz_min = j
// Interschimba tablou[i] cu tablou[poz_min]
temp = tablou[i]
tablou[i] = tablou[poz_min]
tablou[poz_min] = temp
SFARSIT PENTRU
Exemplu: Sortam [5, 2, 8, 1]:
- Pas 1: Minimul din [5,2,8,1] este 1 (pozitia 3). Interschimba cu pozitia 0: [1, 2, 8, 5]
- Pas 2: Minimul din [2,8,5] este 2 (pozitia 1). Deja pe loc: [1, 2, 8, 5]
- Pas 3: Minimul din [8,5] este 5 (pozitia 3). Interschimba cu pozitia 2: [1, 2, 5, 8]
Comparatie: Selection Sort face mereu acelasi numar de comparari (n*(n-1)/2), dar mai putine interschimbari decat Bubble Sort. Bubble Sort se poate opri mai devreme daca tabloul e deja sortat.
Interclasarea tablourilor sortate
Interclasarea (merge) combina doua tablouri deja sortate intr-un singur tablou sortat. Este un algoritm eficient care parcurge fiecare tablou o singura data.
Ideea: Comparam elementele curente din ambele tablouri si il copiem pe cel mai mic in tabloul rezultat. Apoi avansam in tabloul din care am copiat.
Algoritmul:
i = 0; j = 0; k = 0
CAT TIMP i < n SI j < m EXECUTA
DACA A[i] <= B[j] ATUNCI
C[k] = A[i]; i = i + 1
ALTFEL
C[k] = B[j]; j = j + 1
k = k + 1
// Copiaza elementele ramase
CAT TIMP i < n: C[k] = A[i]; i++; k++
CAT TIMP j < m: C[k] = B[j]; j++; k++
Exemplu vizual:
| Pas | Comparam | Rezultat C |
|---|---|---|
| 1 | A[0]=1 vs B[0]=2, 1<2 | [1] |
| 2 | A[1]=3 vs B[0]=2, 2<3 | [1, 2] |
| 3 | A[1]=3 vs B[1]=4, 3<4 | [1, 2, 3] |
| ... | continua... | [1, 2, 3, 4, 5, 6] |
Avantaj: Interclasarea este foarte eficienta - complexitate O(n+m), parcurge fiecare element exact o data.
Algoritmi frecventi pe tablouri - rezumat
Hai sa recapitulam cei mai importanti algoritmi pe tablouri, toti cu acelasi tipar: initializare + parcurgere + operatie .
| Algoritm | Initializare | Operatie in bucla |
|---|---|---|
| Suma | suma = 0 | suma = suma + v[i] |
| Maxim | max = v[0] | DACA v[i]>max: max=v[i] |
| Minim | min = v[0] | DACA v[i]<min: min=v[i] |
| Numarare | contor = 0 | DACA conditie: contor++ |
| Medie | suma = 0 | suma += v[i]; medie=suma/n |
| Inversare | i=0, j=n-1 | swap(v[i],v[j]); i++; j-- |
💡 Sfat pentru evaluare:
Daca vezi o problema cu tablou si nu stii cum sa incepi, gandeste-te: "Ce variabila de acumulare am nevoie?" (suma, contor, max). Apoi scrie bucla PENTRU si pune conditia inauntru. Acest tipar rezolva peste 80% din probleme!
Recapitulare - Cum alegi structura potrivita
In aceasta lectie ai recapitulat cele mai importante concepte despre structurile de date. Hai sa punem totul cap la cap:
🏆 Ghid rapid pentru evaluare:
- Trebuie sa stochezi mai multe valori? Foloseste un tablou (vector)
- Trebuie sa gasesti un element? Cautare secventiala (nesortat) sau binara (sortat)
- Trebuie sa ordonezi? Bubble Sort sau Selection Sort
- Trebuie sa combini doua tablouri sortate? Interclasare (merge)
- Trebuie sa calculezi ceva pe elemente? Parcurgere cu FOR + variabila de acumulare
Interschimbarea a doua valori (swap): Acest mini-algoritm apare in sortare si in multe alte locuri. Retine tiparul cu variabila temporara:
// Interschimba a si b
temp = a
a = b
b = temp
Greseli frecvente la evaluare:
- Uitarea variabilei temp la interschimbare (a=b; b=a NU functioneaza!)
- Indexare gresita: v[n] in loc de v[n-1] pentru ultimul element
- Initializarea max cu 0 in loc de v[0] (gresit daca toate numerele sunt negative)
- Confundarea cautarii secventiale cu cea binara (binara necesita tablou sortat!)
Exercitii practice
Exercitiul 1 (Nivel minim) - Analiza structuri de date
Raspunde la urmatoarele intrebari despre structuri de date:
- Avem tabloul v = [3, 7, 1, 9, 2]. Traseaza algoritmul Bubble Sort pas cu pas pana la sortarea completa. Cate treceri sunt necesare?
- Scrie algoritmul care gaseste al doilea cel mai mare element dintr-un tablou (fara sortare). Ce variabile de acumulare ai nevoie?
- Avem doua tablouri sortate A = [1, 4, 7, 10] si B = [2, 5, 8]. Traseaza algoritmul de interclasare pas cu pas.
- De ce cautarea binara nu functioneaza pe un tablou nesortat? Da un contraexemplu cu tabloul [8, 2, 5, 1, 9] si cautarea valorii 2.
- Cum ai modifica algoritmul de gasire a maximului ca sa gasesti si POZITIA maximului (nu doar valoarea)?
Raspunde numerotat: 1. ... 2. ... 3. ... 4. ... 5. ...
Exercitiul 2 (Nivel standard) - Mini-proiect: Catalog de note cu algoritmi
Creeaza un document Word care simuleaza un catalog de note folosind algoritmi pe tablouri.
Cerinte obligatorii:
⭐ Bonus (pentru nota maxima):
- Adauga un algoritm care calculeaza mediana notelor (elementul din mijloc dupa sortare)
- Implementeaza Selection Sort si compara numarul de interschimbari cu Bubble Sort
- Interclaseaza notele de la doua materii (doua tablouri sortate)
- Scrie codul in C++ sau Python pentru cel putin 3 algoritmi
Exercitiul 3 (Nivel performanta) - Compunere - Structuri de date in viata reala
Cerinta: Scrie o compunere de 15-20 randuri cu titlul "Unde gasim structuri de date in viata de zi cu zi" in care explici cum conceptele invatate (tablouri, sortare, cautare) se regasesc in aplicatii reale.
Indicii pentru structura:
- Incepe cu exemple din viata reala (lista de contacte = tablou, sortare = ordine alfabetica)
- Explica cum cautarea binara e folosita in dictionare si enciclopedii
- Mentioneaza cum sortarea apare in cataloage, clasamente sportive, topuri muzicale
- Discuta de ce eficienta conteaza (cautare pe Google = miliarde de pagini)
- Incheie cu importanta structurilor de date in programare
Cuvinte cheie de folosit: tablou, vector, index, sortare, cautare secventiala, cautare binara, Bubble Sort, interclasare, eficienta, complexitate