Recapitulare Structuri de Date

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 locurile dintr-un sir de scaune numerotate de la 0: scaunul 0 este primul, scaunul 1 este al doilea s.a.m.d. Tabloul este sirul de scaune, fiecare element ocupa un scaun, iar numarul scaunului este indexul. In programare numerotarea incepe intotdeauna de la 0 — primul loc poarta intotdeauna numarul 0.

Care este indexul primului element dintr-un tablou (vector)?

A 0

B 1

C -1

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.

Avem tabloul v = [5, 10, 15]. Dupa v[1] = 20, ce contine tabloul?

A [20, 10, 15]

B [5, 20, 15]

C [5, 10, 20]

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!

De ce citim mai intai numarul de elemente (n) inainte de a citi elementele tabloului?

A Pentru ca asa e frumos

B Ca sa stim cate elemente trebuie sa citim (cat e de mare tabloul)

C Nu e necesar, putem citi fara n

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 (de la primul pana la ultimul)
In cel mai bun caz, gaseste chiar la prima pozitie
Simplu de implementat si usor de urmarit pas cu pas

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 secventiala parcurge elementele:

A De la sfarsit spre inceput

B Unul cate unul, de la inceput la sfarsit

C Aleatoriu

Verificarea unei proprietati a sirului

Verificarea unei proprietati este unul dintre algoritmii de baza ceruti de programa: se parcurge sirul si se verifica daca toate elementele (sau cel putin un element) indeplinesc o conditie data.

Tiparul general:

        // Verificare: TOATE elementele sunt pozitive?
       
        ok = true
       
        PENTRU i DE LA 0 LA n - 1 EXECUTA
       
        DACA tablou[i] <= 0 ATUNCI
       
        ok = false
       
        SFARSIT DACA
       
        SFARSIT PENTRU
       
        DACA ok = true ATUNCI scrie "Toate positive"
       
        ALTFEL scrie "Exista element nepozitiv"

Varianta cu oprire rapida (eficienta): Daca gasim un element care nu indeplineste proprietatea, nu mai are rost sa continuam.

        ok = true
       
        i = 0
       
        CAT TIMP i < n SI ok = true EXECUTA
       
        DACA tablou[i] <= 0 ATUNCI ok = false
       
        i = i + 1
       
        SFARSIT CAT TIMP

Alte proprietati verificabile:

Toate elementele sunt pare / impare
Toate elementele sunt mai mari decat o valoare data
Exista cel putin un element egal cu o valoare data (cautare simpla)
Sirul este sortat crescator

💡 Sfat pentru evaluare:

La verificare pornesti cu ok = true (presupui ca proprietatea e valida) si o schimbi pe false cand gasesti primul element care o incalca. Este tiparul clasic cerut la evaluare!

📚 Extensie optionala (dincolo de programa cls. VIII):

Cautarea binara — un algoritm mai rapid de cautare care functioneaza doar pe tablouri sortate. Ideea: intrebi "Este mai mare decat elementul din mijloc?" si elimini jumatate din posibilitati la fiecare pas. Acest algoritm nu este cerut de programa OMEN 3393/2017 pentru cls. VIII, dar il poti studia la cerinta de bonus sau in cls. IX.

Algoritmul de verificare a proprietatii "toate elementele sunt pozitive" se opreste:

A Mereu dupa ce parcurge tot tabloul

B Imediat ce gaseste un element care NU indeplineste proprietatea

C La jumatatea tabloului

Sortarea Bubble Sort (prin interschimbare) — Extensie optionala

📚 Extensie optionala — Sortarea (Bubble Sort) nu este ceruta explicit de programa OMEN 3393/2017 pentru cls. VIII. Programa prevede doar: citire, afisare, parcurgere, numarare, suma/produs, minim/maxim, verificare proprietate. Bubble Sort este un algoritm util de stiut, dar nu va aparea ca cerinta obligatorie la evaluarea nationala. Studiaza-l ca bonus.

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 Bubble Sort compara:

A Primul element cu ultimul

B Elemente vecine (consecutive)

C Toate elementele simultan

Sortarea prin selectie (Selection Sort) — Extensie optionala

📚 Extensie optionala — Selection Sort nu este cerut explicit de programa OMEN 3393/2017 pentru cls. VIII. Studiaza-l daca ai inteles Bubble Sort si vrei sa mergi mai departe. Nu va aparea la evaluarea nationala.

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.

In sortarea prin selectie, la fiecare pas:

A Interschimbam elemente vecine

B Gasim minimul din portiunea nesortata si il punem pe pozitia corecta

C Inseram elementul in pozitia corecta

Interclasarea tablourilor sortate — Extensie optionala

📚 Extensie optionala — Interclasarea (merge) nu este ceruta de programa OMEN 3393/2017 pentru cls. VIII. Este utila pentru a intelege cum functioneaza sortarea eficienta, dar nu va aparea la evaluarea nationala. Studiaza-o dupa ce stapanesti algoritmii de baza.

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 (pseudocod):

        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
       
        SFARSIT CAT TIMP
       
        // Copiaza elementele ramase din A (daca exista)
       
        CAT TIMP i < n EXECUTA C[k] = A[i]; i = i + 1; k = k + 1 SFARSIT CAT TIMP
       
        // Copiaza elementele ramase din B (daca exista)
       
        CAT TIMP j < m EXECUTA C[k] = B[j]; j = j + 1; k = k + 1 SFARSIT CAT TIMP

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 - parcurge fiecare element exact o data (n+m pasi in total), indiferent de valori.

Interclasarea a doua tablouri sortate [1,3,5] si [2,4,6] produce:

A [1,2,3,4,5,6]

B [1,3,5,2,4,6]

C [2,4,6,1,3,5]

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!

Pentru a gasi cel mai mare element dintr-un tablou, trebuie sa:

A Sortam tabloul si luam ultimul element

B Parcurgem tabloul si comparam fiecare element cu maximul curent

C Ambele variante sunt corecte

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 (parcurge element cu element)
Trebuie sa calculezi ceva pe elemente? Parcurgere cu PENTRU + variabila de acumulare (suma, produs, contor)
Trebuie sa gasesti cel mai mare/mic element? Parcurgere cu variabila max/min initializata cu primul element
Trebuie sa verifici o proprietate a sirului? Parcurgere cu variabila fanion (ok = true/false)

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:

Initializarea produsului cu 0 (rezultatul va fi mereu 0 — produsul porneste de la 1!)
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)
Uitarea SFARSIT DACA dupa un bloc conditionat in interiorul buclei

La initializarea variabilei de acumulare, care afirmatie este corecta?

A Suma se initializeaza cu 0, produsul cu 1, maximul cu v[0]

B Toate variabilele de acumulare se initializeaza cu 0

C Maximul se initializeaza cu 0, produsul cu 0, suma cu 1

Exercitii practice

Exercitiul 1 (Nivel minim) - Analiza structuri de date

Raspunde la urmatoarele intrebari despre structuri de date:

Avem sirul v = [3, 7, 1, 9, 2]. Traseaza algoritmul de gasire a maximului pas cu pas. Care este valoarea maxima si la ce pozitie (index) se afla?
Scrie algoritmul care numara cate elemente dintr-un sir sunt mai mari decat media aritmetica a sirului. Ce variabile de acumulare ai nevoie si in ce ordine le calculezi?
Avem sirul [5, 12, 3, 8, 6]. Traseaza algoritmul de calcul al sumei elementelor de pe pozitii pare (indexurile 0, 2, 4). Arata valoarea sumei dupa fiecare pas.
Scrie algoritmul care verifica daca sirul [4, 8, 2, 6, 10] contine numai numere pare. Foloseste o variabila fanion. Ce valoare are fanionul la final?
Cum ai modifica algoritmul de gasire a maximului ca sa gasesti si POZITIA maximului (nu doar valoarea)? Arata algoritmul modificat.

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:

Declara un tablou de 10 note (numere intregi intre 1 si 10)
Scrie algoritmul care calculeaza media aritmetica a notelor
Scrie algoritmul care gaseste nota maxima si nota minima
Scrie algoritmul care numara cate note sunt >= 5 (promovat)
Cauta daca exista nota 10 in tablou (cautare secventiala)
Fiecare algoritm include pseudocod si trasare cu valorile alese

⭐ Bonus (pentru nota maxima):

(Extensie optionala — nu este ceruta de programa OMEN 3393/2017 pentru cls. VIII) Sorteaza notele crescator folosind Bubble Sort (cu trasare)
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 note = tablou de valori, lista de preturi, clasament sportiv)
Explica cum gasim maximul sau minimul in situatii reale (cel mai scump produs, cel mai bun sportiv)
Mentioneaza cum suma si media apar in contexte practice (medie scolara, buget lunar, temperatura medie)
Discuta de ce cautarea secventiala este utila (gasirea unui contact in agenda, a unui produs intr-o lista)
Incheie cu importanta algoritmilor pe siruri de valori in programare si in viata cotidiana

Cuvinte cheie de folosit: tablou, vector, index, parcurgere, cautare secventiala, suma, produs, minim, maxim, numarare, verificare proprietate

Obiectivul lectiei

Dupa aceasta lectie vei putea: