Structuri de date avansate
Se studiază structuri de date mai complexe utilizate în rezolvarea problemelor de informatică.
Evaluarea Națională
Șiruri de caractere
Un șir de caractere este o succesiune de caractere tratată ca o singură valoare: un nume, un cuvânt, o propoziție. În C++ îl memorăm fie ca vector de caractere terminat cu caracterul nul '\0' (șir în stil C), fie cu tipul modern string, mult mai comod.
Diferența esențială față de un număr: șirul „123” NU este numărul 123. Pe șir nu poți face adunări aritmetice — „12” + „3” cu tipul string înseamnă concatenare (lipire) și dă „123”, nu 15.
Operațiile de bază pe care le cere programa:
- Lungimea șirului: numărul de caractere (funcția length() sau strlen); un șir vid are lungimea 0.
- Accesarea unui caracter prin indice: s[0] este PRIMUL caracter — indexarea pornește de la 0, sursa clasică de rezultate „decalate cu 1”.
- Parcurgerea caracter cu caracter, pentru a număra vocale, litere mari, cifre etc.
- Concatenarea a două șiruri și compararea lor.
Compararea șirurilor se face lexicografic — ca în dicționar, caracter cu caracter după codurile lor: „ana” < „banana” pentru că 'a' vine înaintea lui 'b'. Atenție: lexicografic „abc” < „b”, chiar dacă primul șir e mai lung! Lungimea NU decide ordinea; contează primul caracter diferit. De asemenea literele mari și mici au coduri diferite: 'A' nu este egal cu 'a'.
Prelucrări utile pe șiruri
Subiectele de evaluare adoră câteva prelucrări-șablon pe șiruri; recunoaște-le și le rezolvi mecanic:
- Numărarea vocalelor: parcurgi șirul și verifici dacă s[i] este una dintre 'a', 'e', 'i', 'o', 'u'. Dacă enunțul cere și litere mari, nu uita 'A', 'E', 'I', 'O', 'U' — jumătate din punctaj se pierde aici.
- Transformarea literelor: între codul unei litere mici și cel al literei mari corespunzătoare există o distanță fixă (32 în codul ASCII), deci litera mare se obține scăzând 32 sau cu funcții dedicate (toupper/tolower).
- Verificarea palindromului: un șir citit identic de la stânga la dreapta și invers („cojoc”, „aerisirea”). Compari perechile s[0] cu s[n−1], s[1] cu s[n−2]... e suficient să mergi până la jumătate; dacă TOATE perechile coincid, e palindrom. Prima pereche diferită încheie verificarea cu răspuns negativ.
- Inversarea unui șir: interschimbi perechile simetrice sau construiești un șir nou parcurgând originalul de la coadă la cap.
- Numărarea cuvintelor dintr-o propoziție: numeri separatorii (spațiile) și adaugi 1 — dar numai dacă șirul nu are spații multiple sau la capete, caz pe care enunțurile atente îl precizează.
Un detaliu care se punctează: caracterul '0' (cifra scrisă) NU este numărul 0. Ca să transformi caracterul-cifră în valoare numerică, scazi codul lui '0': s[i] − '0'.
Matrice: prelucrări pe linii și coloane
La structurile avansate, matricea nu mai e doar de citit și afișat — se cer prelucrări direcționate:
- Suma fiecărei linii: pentru fiecare i fixat, aduni a[i][j] cu j de la 1 la m. Rezultatul natural e un vector de sume, câte una pe linie.
- Maximul fiecărei coloane: fixezi coloana j și parcurgi liniile. Atenție la inversarea rolurilor — la coloane, bucla EXTERIOARĂ e pe j.
- Zona de deasupra/dedesubtul diagonalei principale (la matrice pătratice): deasupra înseamnă i < j, dedesubt i > j. Diagonala însăși are i = j, iar diagonala secundară i + j = n + 1 la indexare de la 1.
- Interschimbarea a două linii între ele: se face element cu element, cu variabilă auxiliară, printr-o singură buclă pe coloane.
- Bordarea sau parcurgerea marginii: prima/ultima linie și prima/ultima coloană — elementele cu i = 1, i = n, j = 1 sau j = m.
Greșeala cea mai scumpă: încurcarea ordinii indicilor. a[i][j] înseamnă linia i, coloana j — mereu întâi linia. Când enunțul spune „coloana 3”, elementul generic este a[i][3], cu i variabil, nu a[3][i].
Un truc de verificare pe hârtie: desenează matricea mică (3×3 sau 4×4), pune valorile și execută algoritmul pas cu pas. La itemii de urmărire a execuției, tabelul cu valori intermediare face diferența dintre nota mare și una mediocră.
Căutare și sortare în tablouri
Căutarea secvențială verifică elementele unul câte unul, de la primul la ultimul, până găsește valoarea căutată sau epuizează tabloul. Merge pe ORICE vector, sortat sau nu, dar în cel mai rău caz face n comparații.
Căutarea binară e mult mai rapidă, dar are o condiție obligatorie, cerută explicit la examen: vectorul trebuie să fie SORTAT. Compari valoarea căutată cu elementul din mijloc: dacă e egală, gata; dacă e mai mică, arunci jumătatea dreaptă; dacă e mai mare, arunci jumătatea stângă. La fiecare pas intervalul se înjumătățește, deci într-un vector de 1000 de elemente ajung circa 10 comparații.
Sortarea înseamnă rearanjarea elementelor în ordine crescătoare sau descrescătoare. La acest nivel e suficient să înțelegi ideea sortării prin interschimbare: compari elemente vecine și le schimbi între ele când sunt în ordine greșită, repetând trecerile prin vector până când nu mai are loc nicio interschimbare.
De ce contează sortarea? Pentru că multe prelucrări devin banale pe un vector sortat: minimul e primul element, maximul e ultimul, dublurile stau una lângă alta, iar căutarea binară devine posibilă.
Legătura care se cere înțeleasă: căutarea binară e rapidă, dar cere sortare în prealabil; dacă vei căuta o singură dată, poate nu merită să sortezi tot vectorul — dar la multe căutări repetate, sortarea se amortizează. Acest tip de judecată despre eficiență apare în întrebările de comparare a metodelor.
Tipul înregistrare (record) – primii pași
Până acum toate structurile grupau valori de același tip. Dar un elev din catalog are nume (șir), medie (număr real) și clasă (șir) — tipuri diferite care descriu împreună UN singur obiect. Pentru asta există tipul înregistrare: în Pascal se numește record, în C++ struct.
În C++ definim: struct Elev { string nume; float medie; };. Am creat un tip nou, Elev, cu două câmpuri. Apoi declarăm variabile de acest tip: Elev e; și accesăm câmpurile cu operatorul punct: e.nume, e.medie.
Diferența de reținut, cerută la teorie:
- Tabloul grupează elemente de același tip, accesate prin indice (v[3]);
- Înregistrarea grupează câmpuri de tipuri posibil diferite, accesate prin nume de câmp (e.medie).
Cele două se combină natural: un vector de înregistrări — Elev clasa[30]; — modelează un catalog întreg. Elementul clasa[5] este un elev complet, iar clasa[5].medie este media acelui elev. Observă ordinea: întâi indicele vectorului, apoi punctul și câmpul.
Prelucrările tipice pe vectori de înregistrări sunt aceleași ca la vectori simpli, doar că se aplică pe un câmp: elevul cu media maximă (compari clasa[i].medie), numărarea elevilor cu media peste 9, afișarea numelui celui mai bun elev. Greșeala tipică e amestecarea nivelurilor: clasa.medie[5] e incorect — indicele aparține vectorului, nu câmpului.
De reținut
- șir de caractere
- succesiune de caractere tratată ca o singură valoare, memorată ca vector de caractere sau ca tip string, indexată de la 0
- concatenare
- operația de lipire a două șiruri de caractere, rezultatul fiind un șir care conține caracterele primului urmat de ale celui de-al doilea
- ordine lexicografică
- ordinea de dicționar a șirurilor: se compară caracter cu caracter după coduri, primul caracter diferit decide relația
- palindrom
- șir care se citește identic de la stânga la dreapta și de la dreapta la stânga, verificat prin compararea perechilor simetrice
- căutare secvențială
- metodă de căutare care verifică elementele tabloului pe rând, de la primul la ultimul, funcționând și pe tablouri nesortate
- căutare binară
- metodă de căutare aplicabilă doar pe tablouri sortate, care compară cu elementul din mijloc și înjumătățește intervalul la fiecare pas
- sortare
- rearanjarea elementelor unui tablou în ordine crescătoare sau descrescătoare a valorilor
- înregistrare (record/struct)
- structură de date care grupează câmpuri de tipuri posibil diferite ce descriu împreună același obiect, accesate prin numele câmpului
- câmp
- componentă a unei înregistrări, cu nume și tip propriu, accesată cu operatorul punct (de exemplu e.medie)
Greșeli frecvente
Greșit: Compararea șirurilor după lungime în loc de ordinea lexicografică
Corect: Ordinea lexicografică se decide la primul caracter diferit, ca în dicționar: „abc” este înaintea lui „b”, deși e mai lung
Greșit: Aplicarea căutării binare pe un vector nesortat
Corect: Căutarea binară funcționează NUMAI pe vectori sortați; pe un vector nesortat singura opțiune directă este căutarea secvențială
Greșit: Confundarea caracterului '0' cu numărul 0
Corect: Caracterul-cifră se transformă în valoare numerică scăzând codul lui '0': s[i] − '0'; caracterul '7' nu este numărul 7
Greșit: Numărarea vocalelor doar pentru litere mici când șirul conține și majuscule
Corect: Dacă enunțul nu garantează litere mici, se verifică ambele seturi de vocale sau se convertește întâi șirul la un singur registru
Greșit: Accesarea câmpului unei înregistrări dintr-un vector cu indicele pe câmp: clasa.medie[5]
Corect: Indicele aparține vectorului, apoi urmează câmpul: clasa[5].medie — al cincilea elev, câmpul medie
Test — 6 întrebări ca la examen
1. Șirul s = „informatica” este indexat de la 0. Ce caracter este s[3]?
- f
- o
- n
- r
Vezi răspunsul
o. Pozițiile sunt: s[0]='i', s[1]='n', s[2]='f', s[3]='o'. Varianta „f” e capcana celor care numără de la 1 — la indexare de la 1, al patrulea caracter ar fi într-adevăr altul, dar aici indexarea pornește de la 0.
2. Care dintre următoarele șiruri este palindrom?
- cartea
- aerisirea
- anagrama
- informatica
Vezi răspunsul
aerisirea. „aerisirea” citit invers dă tot „aerisirea” — perechile simetrice coincid toate. „anagrama” e distractorul tentant fiindcă începe și se termină cu „a”, dar deja a doua pereche (n cu m) diferă; primele caractere identice nu sunt suficiente.
3. În ordine lexicografică, care aranjare este corectă?
- mar < ana < banana
- ana < banana < mar
- banana < mar < ana
- ana < mar < banana
Vezi răspunsul
ana < banana < mar. Se compară primele caractere: 'a' < 'b' < 'm', deci ana < banana < mar. Varianta ana < mar < banana e capcana lungimii — banana pare „mai mare” doar dacă judeci greșit după numărul de litere, dar lexicografic decide primul caracter diferit.
4. Într-un vector sortat cu 1000 de elemente, căutarea binară găsește un element în cel mult aproximativ:
- 1000 de comparații
- 500 de comparații
- 10 comparații
- 3 comparații
Vezi răspunsul
10 comparații. Fiecare comparație înjumătățește intervalul: 1000 → 500 → 250 → ... → 1, cam 10 înjumătățiri. Varianta 500 e capcana „jumătate din vector” — dar nu parcurgem jumătate de vector, ci înjumătățim REPETAT intervalul de căutare.
5. Într-o matrice a cu 4 linii și 5 coloane, suma elementelor de pe coloana 2 se calculează cu:
- s = s + a[2][j], cu j de la 1 la 5
- s = s + a[i][2], cu i de la 1 la 4
- s = s + a[i][2], cu i de la 1 la 5
- s = s + a[2][i], cu i de la 1 la 4
Vezi răspunsul
s = s + a[i][2], cu i de la 1 la 4. Coloana 2 fixează al DOILEA indice: a[i][2], iar i parcurge liniile, de la 1 la 4. Prima variantă — capcana clasică — parcurge de fapt linia 2, pentru că fixează primul indice; a treia are indicele de linie mergând până la 5, dar matricea are doar 4 linii.
6. Se definește struct Carte { string titlu; int pagini; }; și vectorul Carte raft[50];. Numărul de pagini al celei de-a zecea cărți (indexare de la 1) se accesează prin:
- raft.pagini[10]
- raft[10].pagini
- pagini.raft[10]
- raft[10, pagini]
Vezi răspunsul
raft[10].pagini. Întâi selectăm elementul vectorului — raft[10] este o carte întreagă — apoi câmpul cu operatorul punct: raft[10].pagini. Varianta raft.pagini[10] amestecă nivelurile: indicele aparține vectorului de înregistrări, nu câmpului.