Articole

Generalități

Supraîncărcarea funcțiilor (eng. functions overloading) se referă la posibilitatea ca în același program să fie declarate și definite mai multe funcții cu același nume, care să difere prin parametri. La apelul unei funcții supraîncărcate, compilatorul stabilește care dintre declarații se potrivește cu apelul respectiv, comparând numărul și tipul parametrilor actuali cu cel al parametrilor formali.

Metodele unei clase, fiind funcții, pot fi supraîncărcate. Totodată, în interiorul unei clase pot fi definiți și supraîncărcați operatori (+, -, *, etc.), care permit utilizarea naturală a obiectelor, în raport cu înțelesul lor.

De exemplu, fracțiile pot fi adunate, scăzute, etc. O clasa care implementează fracții poate fi îmbogățită cu operațiile naturale de adunare, scădere, înmulțire, împărțire, dar și cu comparații, incrementări/decrementări, citire, afișare, etc.

În acest fel lucrul cu obiecte devine natural, evitând apelul explicit al unor metode care poate părea forțat, în anumite situații.

Supraîncărcarea metodelor

De știut:

• în definiția unei clase putem avea mai multe metode cu același nume;
• ele trebuie să difere prin numărul și tipul parametrilor, nu prin tipul rezultatului;
• nu se pot supraîncărca funcții care diferă numai prin tipul rezultatului!

Exemplu

În exemplul următor, definim pentru clasa Fracție două metode creste():

• una fără parametri, care va mări valoarea fracției încapsulate în obiect cu 1;
• una cu un parametru întreg n, care va mări valoarea fracției încapsulate în obiect cu n.

#include <iostream>

using namespace std;

class Fractie{
    private:
        int numarator, numitor;
    public:
		void afiseaza() /// metodă pentru afișarea fractiei
		{
			cout << numarator << "/" << numitor << endl;
		}
		Fractie(int a , int b) /// constructor
		{
			if(b < 0)
				a = -a, b = -b;
			numarator = a, numitor = b;
		}
		Fractie & creste()
		{
			numarator += numitor;
			return *this;
		}
		Fractie & creste(int n)
		{
			numarator += n * numitor;
			return *this;
		}
};

int main(){
	Fractie x(1 , 4);
	x.afiseaza();
	x.creste();
	x.afiseaza();
	x.creste(3);
	x.afiseaza();
	return 0;
}

Programul de mai sus va afișa:

1/4
5/4
17/4

Supraîncărcarea operatorilor

Putem supraîncărca aproape toți operatorii C++ predefiniți. În acest mod putem folosi operatorii și pentru tipurile definite de noi, nu doar pentru cele predefinite.

Nu putem supraîncărca operatori pentru tipurile de bază: int, double, etc.

Nu putem supraîncărca operatori care nu există. De exemplu, nu putem adăuga operatorul #.

Nu putem schimba prioritatea operatorilor.

Operatorii sunt funcții cu un nume special: cuvântul rezervat operator, urmat de simbolul operatorului pe care îl definim. La fel ca orice altă funcție, și operatorii au tip al rezultatului și listă de parametri.

Operatorii care pot fi supraîncărcați sunt:

• +, -, *, /, %
• ^, &, |, ~,
• ,
• =
• <, >, <=, >=, ==, !=,
• !, &&, ||
• ++, --
• <<, >>,
• +=, -=, /=, %=, ^=, &=, |=, *=, <<=, >>=,
• [], ()
• ->, ->*
• new, new [], delete, delete []

Următorii operatori nu pot fi supraîncărcați:

• ::, .*, ., ?:

Sunt două modalități de defini operatori pentru o clasă:

• prin intermediul metodelor;
• prin intermediul funcțiilor prietene.

Putem folosi metodele când operatorul este unar, sau când este binar și primul operand este obiect al clasei pentru care definim operatorul. Dacă operatorul este binar și primul operator nu este obiect al clasei, vom defini operatorul prin intermediul funcțiilor prietene.

Exemplu

În programul de mai jos definim o clasă Fractie în care vom defini și supraîncărca operatorul + pentru a implementa adunarea fracțiilor și adunarea fracțiilor cu întreg. Distingem următoarele cazuri:

• operația F + G, unde F și G sunt fracții, poate fi implementată atât printr-o metodă cât și ca funcție prietenă;
• operația F + n, unde F este fracție și n este număr întreg, poate fi implementată atât printr-o metodă cât și ca funcție prietenă;
• operația n + F, unde F este fracție și n este număr întreg, va fi implementată printr-o funcție prietenă.

Situația de mai sus se datorează faptului că, la implementarea operatorului ca metodă, obiectul curent, pentru care se implementează metoda, este primul operand.

#include <iostream>

using namespace std;

class Fractie{
    private:
        int numarator, numitor;
    public:
		void afiseaza() /// metodă pentru afișarea fractiei
		{
			cout << numarator << "/" << numitor << endl;
		}
		Fractie(int a = 0, int b = 1) /// constructor
		{
			if(b < 0)
				a = -a, b = -b;
			numarator = a, numitor = b;
		}
		Fractie operator+ (Fractie F)
		{
			Fractie R;
			R.numarator = numarator * F.numitor + numitor * F.numarator;
			R.numitor = numitor * F.numitor;
			return R;
		}
		Fractie operator+ (int n)
		{
			Fractie R;
			R.numarator = numarator + n * numitor;
			R.numitor = numitor;
			return R;
		}
		friend Fractie operator + (int n, Fractie F)
		{
			Fractie R;
			R.numarator = F.numarator + n * F.numitor;
			R.numitor = F.numitor;
			return R;
		}
};

int main(){
	Fractie X(1 , 4), Y(2, 3);
	Fractie R = X + Y;
	R.afiseaza();
	R = X + 2;
	R.afiseaza();
	R = 2 + X;
	R.afiseaza();
	return 0;
}

Programul de mai sus va afișa:

11/12
9/4
9/4

Înmulțirea a la russe

Considerăm următorul algoritm, aplicat pentru două numere naturale a și b:

R ← 0
┌ cattimp a ≠ 0 executa
│   ┌ daca a este impar atunci
│   │   R ← R + b
│   └■
│   a ← [a / 2]
│   b ← b * 2
└■
scrie R

Dacă îl vom aplica pentru a = 18 și b = 12 vom constata că:

Observăm că rezultatul R = 216 este de fapt chiar 18 * 12. Aceasta nu este o coincidență!

Algoritmul determină rezultatul înmulțirii dintre a și b și se numește înmulțirea a la russe (înmulțirea rusească). În ciuda numelui, se pare că metoda era cunoscută în Egiptul Antic și poate fi descrisă astfel:

• înmulțim numerele a și b:
  1. dacă a este impar, il adunăm pe b la rezultat, care inițial este 0;
  2. a se înjumătățește, iar b se dublează;
  3. continuăm pași 1 și 2 până când a devine 0.

Aparent ciudată, metoda se bazează de fapt pe scrierea unui număr ca sumă de puteri ale lui 2 ( sau reprezentarea numerelor în baza 2) – știm că orice număr natural are o unică reprezentare în baza 2, poate fi scris în mod unic ca sumă de puteri ale lui 2.

Să-l scrie pe \(a = 18\) ca sumă de puteri ale lui 2: \(18 = 2 + 16 = 0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4\). 0 1 0 0 1 sunt cifrele reprezentării lui 18 în baza 2, în ordine inversă (ordinea în care sunt determinate, prin metoda cunoscută ca resturi ale împărțirii la 2).

Atunci:
$$\begin{align} 18 \cdot 12 & = \left(0 \cdot 2^0 + 1 \cdot 2^1 + 0 \cdot 2^2 + 0 \cdot 2^3 + 1 \cdot 2^4 \right) \cdot 12 \\ & = \left(0 \cdot 1 + 1 \cdot 2 + 0 \cdot 4 + 0 \cdot 8 + 1 \cdot 16 \right) \cdot 12 \\ & = 0 \cdot 12 + 1 \cdot 24 + 0 \cdot 48 + 0 \cdot 96 + 1 \cdot 192 \\ & = 24 + 192 \\ & = 216 \\
\end{align}$$

Observăm deci că valorile care se adună pentru a obține rezultatul sunt tocmai acele valori obținute prin dublările succesive ale lui b când a este impar – ceea ce corespunde cifrei binare 1!!

Acest modalitate de înmulțire este interesantă, dar nu este neapărat utilă în practică. Mult mai interesant este următorul algoritm pentru ridicarea la putere, care poate fi utilizat în rezolvarea de probleme de informatică.

Ridicarea la putere rapidă

Să considerăm \(A^{25}\). Îl vom scrie pe \(25\) ca sumă de puteri ale lui \(2\): \(25 = 1 + 8 + 16\).

Atunci \( A^{25} = A^{1 + 8 + 16} = A^1 \cdot A^8 \cdot A^{16} = \underbrace{{(A^1)}^1}_{=A^1} \cdot \underbrace{{(A^2)}^0}_{=1} \cdot \underbrace{{(A^4)}^0}_{=1} \cdot \underbrace{{(A^8)}^1}_{=A^8} \cdot \underbrace{{(A^{16})}^1}_{=A^{16}}\). Observăm, desigur, că exponenții \(0\) și \(1\) sunt cifrele reprezentării în baza \(2\) a lui \(25\).

Pentru a determina An procedăm astfel:

• vom determina un produs P, format din factori de forma A1, A2, A4, A8, …
• determinăm cifrele reprezentării în baza 2 a lui n, începând cu cea mai nesemnificativă:
  • dacă cifra curentă este 1, înmulțim pe A la P, P ← P * A;
  • înmulțim pe A cu el însuși, A ← A * A;, obținând următoarea putere din șirul de mai sus

Următorul program pseudocod descrie algoritmul de mai sus:

citeste A,n (baza, exponent)
P ← 1
┌ cattimp n ≠ 0 executa
│   c ← n % 2
│   ┌ daca c = 1 atunci
│   │   P ← P * A
│   └■
│   n ← [n / 2]
│   A ← A * A
└■
scrie P

Observăm că algoritmul este foarte eficient! Numărul de iterații este egal cu numărul de cifre din reprezentarea în baza 2 a lui n – mult mai mic decât n!

Definiție

Definiție: Se numește arbore binar de cautare un arbore binar în care fiecare nod are o cheie unică de identificare care respectă următoarele condiții:

• pentru orice subarbore, cheile nodurilor din subarborele stâng sunt mai mici decât cheia rădăcinii;
• pentru orice subarbore, cheile nodurilor din subarborele drept sunt mai mari decât cheia rădăcinii.

Exemplu

Observații:

• Conform definiției, cheile asociate nodurilor dintr-un arbore binar de căutare nu se pot repeta. Dacă se dorește repetarea lor, definiția trebuie modificată încât în subarborele drept (sau stâng) cheile să poată fi și egale cu cheia rădăcinii.
• În practică informația utilă din nodurile arborelui poate fi de orice tip, cu condiția să conțină și cheia. Pentru simplitate, în cele ce urmează informatia utilă va consta exclusiv în cheia de identificare.
• În cele ce urmează vom folosi reprezentarea dinamică a arborilor binari, prin referințe descendente. Structura C++ folosită pentru nodurile arborelui este cea uzuală:
  

  struct nod{
  	int info;
      nod * st, * dr;
  
  };
  
  

Proprietăți

• Parcurgerea în inordine a nodurilor unui arbore binar de căutare se face în ordinea crescătoare a cheilor.
• Operațiile uzuale cu un arbore binar de căutare sunt:
  • inserarea unui nod nou
  • căutarea unui nod
  • ștergerea unui nod
  • parcurgerea nodurilor din arbore
• Căutarea unui nod care are o cheie precizată se realizează destul de repede, deoarece, dacă rădăcina nu corespunde cheii date, căutarea va continua doar în unul dintre subarbori – stâng sau drept, în funcție de relația dintre cheia dată și cheia corespunzătoare rădăcinii.

Operații cu arborii binari de căutare

Așa cum ma văzut mai sus, principalele operații sunt:

• inserarea unui nod nou;
• căutarea unei valori;
• ștergerea unui nod;
• parcurgerea nodurilor din arbore (traversarea arborelui).

În implementarea acestor operații vom folosi metoda divide-et-impera. Principiul este:

• prelucrăm rădăcina;
• parcurgem subarborele stâng și/sau subarborele drept.

Inserarea

Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL dacă arborele este vid) și o valoare. Se cere să se insereze în arbore un nod care are drept cheie de identificare valoarea dată.

Inserarea trebuie realizată astfel încât să se păstreze proprietatea specifică arborilor binari de căutare!

Procedăm astfel:

• dacă arborele este nevid:
  • dacă valoarea dată este identică cu cheia rădăcinii se renunță la inserare;
  • dacă valoarea dată este mai mică decât cheia rădăcinii, se continuă cu subarborele stâng;
  • dacă valoarea dată este mai mare decât cheia rădăcinii, se continuă cu subarborele drept;
• dacă arborele este vid:
  • se creează un nod nou care având cheia egală cu valoarea dată și descendenți stâng și drept NULL. Legarea nodului la subarbore se face automat, datorită transmiterii prin referință a parametrului care reprezintă adresa rădăcinii.

Pentru a creea un arbore binar de căutare vom porni de la un arbore vid și vom aplica în mod repetat operația de inserare.

Funcție C++

void Inserare(nod * & R, int x)
{
	if(R != NULL)
    {
    	if(R->info == x)
        	return;
        else
        	if(R->info > x)
            	Inserare(R->st , x);
            else
            	Inserare(R->dr , x);
    }
    else
    {
    	R = new nod;
        R->info = x;
        R->st = NULL;
        R->dr = NULL;
    }	
}

Căutarea

Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL dacă arborele este vid) și o valoare. Se cere să se stabilească dacă există în arbore un nod care are cheia de identificare egală cu valoarea dată.

Procedăm astfel:

• dacă arborele este nevid:
  • dacă valoarea dată este identică cu cheia rădăcinii atunci am găsit nodul căutat;
  • dacă valoarea dată este mai mică decât cheia rădăcinii, se continuă căutarea în subarborele stâng;
  • dacă valoarea dată este mai mare decât cheia rădăcinii, se continuă căutarea în subarborele drept;
• dacă arborele este vid:
  • valoarea căutată nu există în arbore.

Funcție C++

Funcția de mai jos caută valoarea x în arborele pentru care adresa rădăcinii este memorată în pointerul R. Funcția returnează adresa nodului care are cheia egală cu x sau NULL dacă nu există un asemenea nod.

nod * Cautare(nod * R , int x)
{
	if(R == NULL)
		return NULL;
	if(R->info == x)
		return R;
	if(R->info > x)
		return Cautare(R->st , x);
	else
		return Cautare(R->dr , x);
}

Ștergerea unui nod

Se cunoaște adresa rădăcinii unui arbore binar de căutare (sau NULL dacă arborele este vid) și o valoare. Se cere să se șteargă din arbore nodul care are cheia de identificare egală cu valoarea dată.

Ștergerea trebuie realizată astfel încât să se păstreze proprietatea specifică arborilor binari de căutare!

Procedăm astfel:

• dacă arborele este nevid:
  • dacă valoarea dată este identică cu cheia rădăcinii atunci am găsit nodul căutat. Procedăm astfel:
    • dacă nodul este terminal (subarborele stâng și subarborele drept sunt vizi) se va șterge acest nod, iar adresa reținută de părinte pentru el devine NULL;
    • dacă numai subarborele stâng este nevid nodul se va șterge, iar adresa reținută de părinte pentru el devine adresa subarborelui stâng;
    • dacă numai subarborele drept este nevid nodul se va șterge, iar adresa reținută de părinte pentru el devine adresa subarborelui drept;
    • dacă ambii subarbori sunt nevizi:
      • se identifică cel mai mare nod din subarborele stâng (cel mai din dreapta nod al subarborelui stâng). Acest nod nu poate avea subarbore drept!
      • se copiază informația din acest nod în nodul analizat;
      • nodul identificat este șters. Ștergerea se realizează ca în cazul în care nodul este terminal sau ca în cazul în care nodul are numai subarbore stâng;
  • dacă valoarea dată este mai mică decât cheia rădăcinii, se continuă căutarea în subarborele stâng;
  • dacă valoarea dată este mai mare decât cheia rădăcinii, se continuă căutarea în subarborele drept;
• dacă arborele este vid:
  • valoarea căutată nu există în arbore.

Secvența C++

Mai jos sunt prezentate două funcții: Stergere și StAux. Funcția StAux tratează cazul când nodul curent trebuie șters și are ambii subarbori.

void StergAux(nod * & p, nod * & R)
{
	// R - nodul care trebuie sters
	// p - pointer cu care identificăm nodul cel mai din dreapta
	if(p->dr)
		StergAux(p -> dr , R);
	else
	{
		R->info = p->info;
		nod * aux = p;
		p = p->st;
		delete aux;
	}
}

void Stergere(nod * & R , int x)
{
	if(R != NULL)
	{
		if(R->info == x)
		{
			// nodul trebuie șters
			if(R->st == NULL && R->dr == NULL)
			{
				delete R;
				R = NULL;
			}
			else
				if(R->dr == NULL)
				{
					nod * aux = R;
					R = R->st;
					delete aux;
				}
				else
					if(R->st == NULL)
					{
						nod * aux = R;
						R = R->dr;
						delete aux;
					}
					else
						StergAux(R->st, R);
		}
		else
			if(R->info > x)
				Stergere(R->st , x);
			else
				Stergere(R->dr , x);
	}
	else
		return; // valoarea x nu apare în arbore
}

Parcurgerea

Arborii binari de căutare pot fi parcurși în orice mod: inordine, preordine, postordine. Datorită structurii interne a arborilor (pentru orice subarbore, cheia asociată rădăcinii este mai mare decât orice cheie din subarborele stâng și mai mică decât orice cheie din subarborele drept), parcurgerea în inordine (Stâng-Rădăcină-Drept)se face în ordinea crescătoare a cheilor!

Pentru a realiza o parcurgere în ordinea descrescătoare a cheilor, folosim tot o parcurgere în inordine, dar de tip Drept-Rădăcină-Stâng!

Secvență C++

void Afisare(nod * r)
{
    if(r != NULL)
    {
		Afisare(r->st);
		cout << r->info << " ";
		Afisare(r->dr);
	}
}

Concluzii

• Căutarea rapidă a informațiilor este foarte importantă în practică, arborii binari de căutare fiind utilizați ca suport pentru diverse structuri de date eficiente.
• Eficiența operațiilor depinde de ordinea în care se realizează inserarea nodurilor în arbore. De exemplu, dacă nodurile sunt create în ordinea crescătoare a cheilor, arborele devine degenerat, fiecare nod având numai descendent drept. Operațiile nu mai sunt eficiente, complexitatea lor devenind \(O(n)\), unde \(n\) este numărul nodurilor din arbore.
• Pentru a evita această situație, arborii binari de căutare primesc proprietăți suplimentare astfel încât să devină arbori echilibrați – să aibă înălțimea mică în raport cu numărul \(n\) de noduri: aproximativ \(\log_2n\).
  • operațiile de inserare, ștergere și căutare aplicate pe arborii binari de căutare echilibrați au complexitatea \(O(\log n)\);
  • exemple de arbori echilibrați: arborii AVL (Adelson-Velskii și Landis au fost doi cercetători sovietici care au folosit prima dată arborii echilibrați), arborii roșu-negru.
• Containerele STL map și set sunt implementate cu ajutorul arborilor binari de căutare echilibrați – de regulă arbori roșu-negru.

Acest articol conține o listă cu probleme propuse pentru examenul de bacalaureat la care se cer soluții eficiente din punct de vedere a memoriei utilizate și/sau a timpului de execuție (punctul III.3).
Problemele pot fi filtrate folosind butoanele din stânga!

10 40
65 9 20 25 12 14 7 3 11 15 12 8 19 50 21

3 6 71
13 15 90

16 19
15 18
17 21
19 21
18 20
12 13

6 10 6
7 24 25
7 25 24
25 14 13
8 6 10
15 20 25
4 5 3

10 11
497 125 521 497 513 258 491 55 551 16
21 259 943 77 945 57 52 552 16 17 71

1925
31885 21925 8931925 31925 121900 11925 31925 151925 61950 201925 121880

8 9
1 0 4 1 5 3 5 5
1 1 1 7 5 3 5 3 0 

342 1684 2134 5434 111 98 98 3405 3412 7016 8634 1010 102 310

2 9
1 1 1 2 2 3 5 5 5 5 6 6 7 8 10 10 12 15 21 21

9 7 
112 20 42 112 5013 824 10012 55 155 
402 1024 321 521 57 6542 255 

13 

210
3445 210 893210 1245 1210 3210 15210 67120 20210 12

263
39628
79
887308

9988887766333220

12
4 6 3 7 8 1 6 2 7 9 10 8

4 6 6 7 8 8 8 8 8 9 10 10

4  1 10
1 16  1
4  2  8
2  1  5
1  5  2

5
2 10 5 20 21 0 10 60 15 3 9 20 20 5 45

Definiție și proprietăți

Definiție. Se numește arbore binar un arbore cu rădăcină în care fiecare nod are cel mult doi descendenți direcți: descendentul stâng și descendentul drept.

Exemplu.

În arborele de mai sus:

• nodul 1 este rădăcina;
• rădăcina are doi descendenți direcți (fii): 2 este descendent stâng a lui 1, iar 3 este descendent drept;
• nodul 2 are un singur descendent, pe 4. Acesta este descendent stâng al lui 2;
• similar, 7 este descendent drept al lui 4;
• nodurile 5, 6 și 7 sunt noduri terminale (frunze).

Observație. Dacă un nod are un singur descendent acesta va fi descendent stâng sau drept – acest lucru trebuie să fie precizat. Cei doi arbori de mai jos sunt considerați distincți.

O altă definiție, recursivă, a arborelui binar este următoarea: Un arbore binar este o mulțime finită de noduri, astfel:

• există un nod special, numit rădăcina arborelui;
• celelalte noduri sunt grupate în două submulțimi disjuncte \(A_1\) și \(A_2\), fiecare dintre ele fiind la rândul lor arbori binari. Arborii \(A_1\) și \(A_2\) reprezintă subarborele stâng, respectiv subarborele drept, al rădăcinii.

Această definiție recursivă este utilă deoarece foarte multe probleme cu arbori binari constau în prelucrarea nodurilor din arbore: a rădăcinii și a celor doi subarbori, în mod recursiv, prin metoda Divide et Impera.

Proprietății ale arborilor binari

1. Fiecare nivel i=0,1,2,... dintr-un arbore binar conține cel mult 2i noduri.
2. Un arbore binar de înălțime h conține cel mult 2h+1-1 noduri. Demonstrația se bazează pe afirmația anterioară.
3. Într-un arbore cu n noduri și înâlțime h avem relația \( h \geq \log_{2}{(n+1)} -1 \).
4. Dacă într-un arbore binar numărul nodurilor terminale este a, iar c este numărul nodurilor care au exact 2 fii, atunci a = c + 1.

Tipuri speciale de arbori binari

Arbore binar strict

Definiție: Se numește arbore binar strict un arbore binar în care fiecare nod, cu excepția celor terminale, are exact doi descendenți.

Exemplu:

Proprietăți:

• Un arbore binar strict cu \(k\) noduri terminale are \(n = 2 \cdot k – 1\) noduri.
• Un arbore binar strict are număr impar de noduri.

Arbore binar plin

Definiție: Se numește arbore binar plin un arbore binar în care fiecare nivel \( k \in \left\{ 0 , 1, 2, \cdots, h \right\} \), unde \(h\) este înălțimea arborelui, conține \(2^k\) noduri.

Exemplu:

Proprietăți:

• Arborele binar plin este un caz particular de arbore binar strict, în care toate nodurile terminale sunt situate pe același nivel.
• Un arbore binar plin cu \(k\) noduri terminale are \(n = 2 \cdot k – 1\) noduri.
• Un arbore binar plin cu înălțimea \(h\) are \(2^h-1\) noduri.

Arbore binar complet

Definiție: Se numește arbore binar complet un arbore binar în care fiecare nivel \( k \in \left\{ 0 , 1, 2, \cdots, h – 1 \right\} \), unde \(h\) este înălțimea arborelui, conține \(2^k\) noduri, iar nivelul \(k\) conține eventual mai puțin de \(2^h\) noduri, acestea fiind grupate de regulă în partea stângă.

Exemplu:

Observație: Arborele binar plin este și arbore binar complet.

Reprezentarea arborilor binari

Arborii binari se pot reprezenta fie prin referințe ascendente, fie prin referințe descendente, fie combinând cele două variante.

Reprezentarea prin referințe ascendente

În cazul reprezentării prin referințe ascendente, pentru fiecare nod din arbore trebuie să se cunoască:

• nodul părinte
• ce fel de descendent este (stâng sau drept).

Pentru memorarea informațiilor, considerând nodurile numerotate începând cu 1, putem folosi două tablouri: Tata[] și Tip[], unde Tata[k] reprezintă nodul părinte al lui k sau 0 dacă k este chiar rădăcina arborelui, iat Tip[k] este 0, dacă k este rădăcina arborului (caz în care nu are părinte), respectiv -1 dacă k este descendent stâng al lui Tata[k] sau 1 dacă k este descendent drept al lui Tata[k].

Exemplu.

Pentru arborele de mai sus, cele doua tablouri sunt:

Reprezentarea prin referințe descendente

În cazul reprezentării prin referințe descendente, trebuie să fie cunoscută rădăcina arborelui binar, iar pentru celelalte noduri din arbore, trebuie să se cunoască fiul stâng și fiul drept.

Această reprezentare se poate face cu ajutorul tablourilor sau prin intermediul alocării dinamice.

Reprezentarea cu tablouri

Dacă folosim tablouri, vom avea nevoie de două tablouri, st[] (de la stânga) și dr[] (de la dreapta). Considerând nodurile numerotate de la 1 la n:

• st[k] reprezintă numărul de ordine al nodului care este descendent stâng al lui k, sau 0 dacă k nu are descendent stâng;
• dr[k] reprezintă numărul de ordine al nodului care este descendent drept al lui k, sau 0 dacă k nu are descendent drept.

Exemplu.

Pentru arborele de mai sus, cele doua tablouri sunt:

Cunoscând valorile din cele două tablouri putem identifica rădăcina ca nodul care nu apare nici în st[], nici în dr[]. În exemplul de mai sus acesta este 1.

Reprezentarea folosind alocarea dinamică

Pentru fiecare nod al arborelui se crează o variabilă dinamică de tip structură, în care se vor memora următoarele câmpuri:

• numărul nodului, sau orice informație utilă despre nod
• două câmpuri de legătură, de tip pointer, reprezentând adresa nodului care este descendent stâng, respectiv adresa nodului care este descendent drept, sau NULL dacă nodul nu are descendent stâng (sau drept).

Următoarea secvență C/C++ definește structura:

struct nod{
	int info;
    nod * st, * dr;
};

Pentru operațiile cu arborele reprezentat astfel este necesar să cunoaștem adresa nodului rădăcină:

nod * R;

Pornind de la nodul rădăcină pot fi parcurse toate nodurile din arbore, pentru a efectua diverse operații cu acestea.

Crearea arborilor binari

Pentru a crea un arbore binar trebuie cunoscute pentru fiecare nod:

• informația utilă memorată în acel nod
• nodurile descendenților stâng și drept, dacă există

În funcție de reprezentarea folosită, mecanismul creării poate avea mai multe forme.

Crearea arborilor binari folosind reprezentarea statică

În cazul reprezentării statice pot fi citite numărul de noduri n și elementele tablourilor st[] și dr[], ca în exemplul următor:

// variabilele n, st[] si dr[] sunt considerate globale

void Citire()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> st[i];
    for(int i = 1 ; i <= n ; i ++)
        cin >> dr[i];
}

În numeroase probleme este necesară identificarea nodului rădăcină, folosind informațiile din cele două tablouri.

Determinarea rădăcinii se poate face ținând cont de faptul că ea nu este descendent al niciunui nod din arbore, deci nu va apărea în cele două tablouri:

int Radacina()
{
    int v[101] = {0};
    for(int i = 1 ; i <= n ; i ++)
    {
        if(st[i] != 0)
            v[st[i]] = 1;
        if(dr[i] != 0)
            v[dr[i]] = 1;
    }
    for(int i = 1 ; i <= n ; i ++)
        if(v[i] == 0)
            return i;
    return 0;
}

Crearea arborilor binari folosind reprezentarea dinamică

Reprezentarea dinamică unui arbore impune ca operațiile cu nodurile arborelui, inclusiv crearea, să se realizeze pornind de la rădăcină și continuând pe rând cu cei doi subarbori. Tehnica folosită este recursivitatea: pentru toți arborii (arborele initial și subarborii) realizăm aceleași operații – prelucrăm rădăcina și continuăm cu cei doi subarbori.

Schema folosită în funcția Creare din programul de mai jos este următoarea:

• funcția primește ca parametru un pointer, inițial NULL. Crează arborele (subarborele) și îl întoarce având ca valoare adresa rădăcinii;
• pentru fiecare apel (autoapel):
  • citim informația utilă din nodul curent – rădăcina arborelui (subarborelui);
  • dacă nodul curent are descendent stâng, continuăm cu acesta
  • dacă nodul curent are descendent drept, continuăm cu acesta

Pentru afișarea arborelui folosim funcția Afisare care procedează similar:

• are ca parametru adresa rădăcinii sau NULL
• afișează rădăcina (informația utilă din rădăcină)
• continuă recursiv cu subarborele stâng
• continuă recursiv cu subarborele drept

#include <iostream>

using namespace std;

int n , st[101], dr[101];

struct nod {
	int info;
	nod * st, * dr;
};

void Creare(nod * & r, int x)
{
    if(x != 0)
    {
		r = new nod;
		r->info = x;
		r->st = r->dr = NULL;
		int y;
		cout << "st[" << x << "]="; cin >> y;
		Creare(r -> st , y);
		cout << "dr[" << x << "]="; cin >> y;
		Creare(r -> dr , y);;
	}
}

void Afisare(nod * r)
{
    if(r != NULL)
    {
		cout << r->info << " ";
		Afisare(r->st);
		Afisare(r->dr);
	}
}

int main()
{
	nod * R = NULL;
	int x;
	cout << "Eticheta radacinii: "; cin >> x;
    Creare(R , x);
    Afisare(R);
    return 0;
}

Parcurgerea arborilor binari

Pentru a prelucra un arbore este necesar ca nodurile sale să fie vizitate. La fel ca în cazul grafurilor (ceea ce și sunt de fapt arborii binari), ei pot fi parcurși în lățime sau în adâncime, a doua metodă fiind de regulă folosită.

Parcurgerea începe din rădăcină.

În funcție de ordinea în care se vizitează nodurile avem următoarele parcurgeri:

1. parcurgerea în inordine – SRD – se parcurge mai întâi subarborele stâng (S), apoi rădăcina (R), apoi subarborele drept (D);
2. parcurgerea în preordine – RSD – se parcurge mai întâi rădăcina (R), apoi subarborele stâng (S), apoi subarborele drept (D);
3. parcurgerea în postordine – SDR – se parcurge mai întâi subarborele stâng (S), apoi subarborele drept (D), apoi rădăcina (R).

Observație: În programul de mai sus, crearea și afișarea arborelui se fac cu ajutorul parcurgerii, mai precis a parcurgerii în preordine.

Exemplu

Pentru arborele de mai sus, ordinea de parcurgere este:

• Inordine – SRD: 4 7 2 1 5 3 6
• Preordine: RSD 1 2 4 7 3 5 6
• Postordine: SDR 7 4 2 5 6 3 1

Deoarece parcurgerea începe din rădăcină și continuă cu nodurile descendent (cu subarborii stâng și drept), reprezentarea folosită este cea cu referințe descendente.

Programul C++ următor conține subprograme care implementează cele trei modalități de parcurgere pentru afisarea nodurilor din arbore. Reprezentarea arborelui este prin tablourile st[] și dr[]. Datele de intrare se citesc de la tastatură: mai întâi se citește numărul de noduri, n, apoi elementele vectorului st[], apoi elementele vectorului dr[].

#include <iostream>

using namespace std;

int n , st[101], dr[101];

void Citire()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        cin >> st[i];
    for(int i = 1 ; i <= n ; i ++)
        cin >> dr[i];
}

int Radacina()
{
    // radacina este un nod intre 1 și n care nu apare în tablourile st[] și dr[]
    int v[101] = {0};
    for(int i = 1 ; i <= n ; i ++)
    {
        if(st[i] != 0)
            v[st[i]] = 1;
        if(dr[i] != 0)
            v[dr[i]] = 1;
    }
    for(int i = 1 ; i <= n ; i ++)
        if(v[i] == 0)
            return i;
    return 0;
}

void Inordine(int x)
{
    if(x != 0)
    {
        Inordine(st[x]);
        cout << x << " ";
        Inordine(dr[x]);
    }
}

void Preordine(int x)
{
    if(x != 0)
    {
        cout << x << " ";
        Preordine(st[x]);
        Preordine(dr[x]);
    }
}

void Postordine(int x)
{
    if(x != 0)
    {
        Postordine(st[x]);
        Postordine(dr[x]);
        cout << x << " ";
    }
}

int main()
{
    Citire();
    int R = Radacina();
    Inordine(R); 
    cout << endl;
    Preordine(R); 
    cout << endl;
    Postordine(R); 
    cout << endl;
    return 0;
}

Programul C++ următor conține subprograme care implementează cele trei modalități de parcurgere pentru afisarea nodurilor din arbore, reprezentarea acestuia fiind cea dinamică.

#include <iostream>

using namespace std;

int n , st[101], dr[101];

struct nod {
	int info;
	nod * st, * dr;
};

void Creare(nod * & r, int x)
{
    if(x != 0)
    {
		r = new nod;
		r->info = x;
		r->st = r->dr = NULL;
		int y;
		cout << "st[" << x << "]="; cin >> y;
		Creare(r -> st , y);
		cout << "dr[" << x << "]="; cin >> y;
		Creare(r -> dr , y);;
	}
}


void Preordine(nod * r)
{
    if(r != NULL)
    {
		cout << r->info << " ";
		Preordine(r->st);
		Preordine(r->dr);
	}
}

void Inordine(nod * r)
{
    if(r != NULL)
    {
		Inordine(r->st);
		cout << r->info << " ";
		Inordine(r->dr);
	}
}

void Postordine(nod * r)
{
    if(r != NULL)
    {
		Postordine(r->st);
		Postordine(r->dr);
		cout << r->info << " ";
	}
}

int main()
{
	nod * R = NULL;
	int x;
	cout << "Eticheta radacinii: "; cin >> x;
    Creare(R , x);
    Preordine(R); cout << endl;
    Inordine(R);  cout << endl;
    Postordine(R); cout << endl;
    return 0;
}

Ștergerea arborilor binari

Ștergerea arborilor binari este necesară cu precădere în cazul reprezentării dinamice a acestora.

Ștergerea se va face nod cu nod, folosind parcurgerea în postordine: parcurgem subarbore stâng, apoi subarborele drept, apoi prelucrăm rădăcina. În acest fel la ștergerea nodului rădăcină cei doi subarbori sunt deja șterși.

Funcția C++ de mai jos șterge arborele binar pentru care adresa rădăcinii este transmisă ca parametru. Acesta parametru este de intrare-ieșire: intră cu adresa rădăcinii și iese cu valoarea NULL – arborele a fost șters.

void Stergere(nod * & R)
{
	if(R != NULL)
    {
    	Stergere(R->st);
        Stergere(R->dr);
        delete R;
        R = NULL;
    }
}

Funcția de mai sus poate fi utilizată și pentru ștergerea unui subarbore dintr-un arbore dat. Este însă important ca parametrul să fie câmpul st sau dr din nodul părinte, nu un pointer oarecare care să memoreze adresa rădăcinii subarborelui.

Exemplu: Considerăm un arbore binar pentru care adresa rădăcinii este memorată în pointerul R. Dorim să ștergem subarborele stâng al rădăcinii, care are adresa în R->st.

Următoarea secvență este corectă.

Stergere(R->st);

Următoarea secvență este greșită. De ce?

nod * p = R->st;
Stergere(p);

Stars and bars (Stele și bare) este o metodă de rezolvare a unor probleme de combinatorică. Se poate folosi când trebuie să determinăm numărul de modalități de a grupa un număr dat de obiecte identice.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii este egal cu: \( C_{n+k-1}^{k-1} \).

Demonstrația implică separarea celor n obiecte (stele) în k cutii prin k-1 bare – de unde și numele. De exemplu, configurația următoare are n=7 stele și k=4 cutii: \( \star \vert \star \star \vert \vert \star \star \star \star \) și corespunde următoarei situații:

• prima cutie conține un obiect
• a doua cutie conține două obiecte
• a treia cutie nu conține niciun obiect
• a patra cutie conține patru obiecte

Configurația este echivalentă cu următoarea configurație de biți: 0100110000, în care bitul 1 corespunde obiectului, \( \star \), iar 1 corespunde barei, \( \vert \). Toate configurațiile convenabile au n-k+1 biți, dintre care n au valoarea 0 și k-1 au valoarea 1 și corespund submulțimilor cu k-1 elemente ale unei mulțimi cu n+k-1 elemente.

Astfel, numărul lor este \( C_{n+k-1}^{k-1} \).

Consecință Ecuația \(x_1 + x_2 + x_3 + \cdots + x_k = n\) are \( C_{n+k-1}^{k-1} \) soluții întregi nenegative (mai mari sau egale cu 0).

Afirmația este echivalentă cu teorema de mai sus, în care \(x_i\) fiind egal cu numărul de obiecte din cutia i.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii astfel încât fiecare cutie conține cel puțin un obiect este egal cu: \( C_{n-1}^{k-1} \).

Demonstrația 1: Fixăm în fiecare cutie câte un obiect. Rămân \(n – k\) obiecte care trebuie plasate în \(k\) cutii, în condițiile teoremei de mai sus. Astfel, numărul de variante este \( C_{n-k+k-1}^{k-1} = C_{n-1}^{k-1} \).

Demonstrația 2: Folosim metoda Stars and bars. Separarea obiectelor în cutii se face plasând \(k\) bare în golurile dintre obiecte. Sunt \(n-1\) goluri în care putem plasa \(k\) bare în \( C_{n-1}^{k-1} \) moduri.

Introducere

Pseudocod este un limbaj prin care sunt descriși pașii dintr-un algoritm. Limbajul pseudocod conține structurile specifice unui limbaj de programare obișnuit (precum Pascal, C/C++, Basic, etc) dar este destinat a fi citit de către oameni, nu de către calculatoare.

De obicei sunt omise detaliile vitale într-un limbaj de programare, precum declararea variabilelor sau secvențe specifice limbajului. Algoritmii pseudocod pot conține secvențe descrise în limbaj natural, precum și expresii matematice compacte, care lipsesc din limbajele de programare reale.

Conceptele care intervin in algoritmii pseudocod sunt similare cu cele din limbajele de programare:

• instrucțiuni
• variabile
• constante
• operații
• expresii

Există mai multe variante ale limbajului pseudocod. Acest articol se referă la varianta folosită în subiectele pentru examenul de bacalaureat la informatică. Limba folosită este limba română.

Variabile și constante

În pseudocod variabilele nu se declară, iar numele lor respectă regula uzuală a identificatorilor – litere, cifre, caracterul de subliniere și să nu înceapă cu cifră.

Constantele care apar de regulă în algoritmii pseudocod sunt constante literale (valori numerice, întregi sau reale, caractere – delimitate prin apostrof ‘, șiruri de caractere – delimitate prin apostroafe (‘) sau ghilimele (“). De asemenea, pot să apară constante matematice, de exemplu \( \pi \).

Operații

Sunt prezente toate operațiile aritmetice uzuale:

• adunarea a două numere: a+b. În funcție de context, rezultatul este întreg sau real.
• scăderea a două numere: a-b. În funcție de context, rezultatul este întreg sau real.
• înmulțirea a două numere: a*b. În funcție de context, rezultatul este întreg sau real.
• împărțirea a două numere: a/b. Rezultatul se consideră real. Dacă se dorește determinarea câtului împărțirii a două numere naturale, se va folosi partea întreagă a rezultatului împărțirii: [a/b].
• restul împărțirii a două numere întregi: a%b. Se aplică numai pentru date întregi, iar rezultatul este număr întreg.

Notă: Unele variante pseudocod propun operațiile DIV și MOD pentru determinarea câtului și restului împărțirii a două numere întregi. De asemenea, pot să apară operații de ridicare la putere, în forma \( a ^ n\), sau de extragere a rădăcinii pătrate – \(\sqrt{x}\).

Operațiile relaționale sunt:

• = – egalitatea
• ≠ – neegalitatea
• < – mai mic
• ≤ – mai mic sau egal
• > – mai mare
• ≥ – mai mare sau egal

Operanzii sunt de regulă numere, iar rezultatul este valoare de adevăr (adevărat sau fals).

Operațiile logice sunt NOT, ȘI, SAU – cu semnificațiile cunoscute. O descriere a operațiilor logice poate fi găsită aici: www.pbinfo.ro/articole/21315/operatii-logice.

Instrucțiuni

Instrucțiunile sunt componentele algoritmului care au efect, atunci când se execută. Ele modifică valorile unor variabile, citesc sau afișează date, repetă anumite acțiuni, etc.

De regulă fiecare instrucțiune se scrie pe o linie (sau mai multe în cazul celor complexe), dar există situații când, pentru a economisi spațiu, două sau mai multe instrucțiuni simple se scriu pe același rând, separate prin ;.

Orice algoritm poate fi reprezentat prin intermediul a trei tipuri de structuri:

• structura liniară
• structura alternativă
• structura repetitivă
  • structura repetitivă cu număr necunoscut de pași
    • structura repetitivă cu număr necunoscut de pași și test inițial
    • structura repetitivă cu număr necunoscut de pași și test final
  • structura repetitivă cu număr cunoscut de pași

Citirea

Pentru citirea datelor se folosește instrucțiunea citește <listă variabile>, unde <listă variabile> reprezintă un șir de variabile separate prin caracterul ,. Se preiau valori succesive de la tastatură și se memorează în variabilele din listă.

Exemplu

citeste a , b , c

Citirea datelor este frecvent însoțită de precizări privind datele citite (tip, valori posibile. etc.).

Afișarea

Pentru afișarea datelor se folosește instrucțiunea scrie <listă expresii>, unde <listă expresii> reprezintă un șir de expresii separate prin caracterul ,. Se evaluează în ordine expresiile din listă și se afisează pe ecran rezultatele lor.

Exemplu

scrie 'a + b = ' , a + b

Dacă a = 3 și b = 4 se va afișa:

a + b = 7

Atribuirea

Pentru atribuire se folosește instructiunea <variabilă> ← <expresie>. Se evaluază expresia, iar valoarea obținută se memorează in variabilă.

Exemple

a ← 0
S ← a + b
i ← i + 1

Structura alternativă

În pseudocod există instrucțiunea daca, cu următoarea sintaxă:

┌ daca <conditie> atunci
│    <instructiuni1>
│ altfel
│    <instructiuni2>
└■

sau

┌ daca <conditie> atunci
│    <instructiuni1>
└■

Modul de execuție este următorul:

• se evaluează <conditie>
• dacă este adevărată, se executa grupul de instrucțiuni <instructiuni1>, apoi se trece la următoarea instrucțiune
• dacă este falsă, se executa grupul de instrucțiuni <instructiuni2>, dacă există secțiunea altfel, apoi se trece la următoarea instrucțiune.

Structuri repetive

Structura repetitivă cu număr cunoscut de pași

Instrucțiunea PENTRU

Sintaxă

┌ pentru <variabila> ← <expresie initiala>, <expresie finala> , <pas> executa
│    <instructiuni>
└■

unde expresie initiala, expresie finala și pas sunt expresii cu rezultat (de regulă) întreg, iar pas poate fi 1 sau -1 și poate lipsi, caz în care se consideră că este 1.

variabila primește pe rând valori crescătoare (dacă pas = 1) sau descrescătoare (dacă pas = -1) începând de la expresie initiala până la expresie finala, și pentru fiecare valoare se execută secvența instructiuni.

Dacă pas = 1 și expresie initiala > expresie finala>, secvența instructiuni nu se va executa deloc. La fel se întâmplă când <pas = -1 și expresie initiala < expresie finala. În caz contrar numărul de pași este expresie initială - expresie finala + 1, dacă <pas = 1, respectiv expresie finală - expresie initiala + 1, dacă pas=-1.

Exemplu

Determinarea sumei și produsului primelor n numere naturale:

S ← 0; P ← 1
┌ pentru i←1,n executa
│    S ← S + i
│    P ← P * i
└■
scrie S, ' ' , P

Structura repetitivă cu număr necunoscut de pasi și test inițial

Instrucțiunea CÂT TIMP … EXECUTĂ

Sintaxă

┌ cat timp <conditie> executa
│    <instructiuni>
└■

Mod de execuție

1. se evalueză condiția
2. dacă este adevărată se executa instrucțiunile și se revine la pasul 1
3. dacă este falsă se trece la următoarea instrucțiune din algoritm

Important: Dacă condiția este de la început falsă, instrucțiunile nu se vor executa deloc!

Exemplu

Determinarea sumei cifrelor unui număr natural:

citeste n
S ← 0
┌ cat timp n ≠ 0 executa
│    S ← S + n % 10
│    n ← [n/10]
└■
scrie S

Structura repetitivă cu număr necunoscut de pasi și test final

┌ executa
│    <instructiuni>
└ cat timp <conditie>

citeste n
cnt ← 0
┌ executa
│    cnt ← cnt + 1
│    n ← [n/10]
└ cat timp n ≠ 0
scrie cnt

┌ repeta
│    <instructiuni>
└ pana cand <conditie>

citeste n
cnt ← 0
┌ repeta
│    cnt ← cnt + 1
│    n ← [n/10]
└ pana cand n = 0
scrie cnt

Echivalența structurilor repetitive

Numeroase exerciții propun un algoritm și se cere scrierea unui algoritm echivalent care să folosească o structură repetitivă de alt tip. Doi algoritmi sunt echivalenți dacă pentru orice set de date de intrare (conforme cu restricțiile problemei) ei obțin aceleași rezultate.

Această secțiune descrie câteva reguli de transformare a structurilor repetitive din algoritmii pseudocod.

PENTRU → CÂTTIMP

┌ pentru i←a,b executa
│     <instructiuni>
└■

i ← a
┌ cattimp i ≤ b executa
│     <instructiuni>
│     i ← i + 1
└■

PENTRU → EXECUTĂ … CÂTTIMP

┌ pentru i←a,b executa
│     <instructiuni>
└■

i ← a
┌ daca i ≤ b atunci
│┌ executa
││     <instructiuni>
││     i ← i + 1
│└ cattimp i ≤ b
└■

PENTRU → REPETĂ … PÂNÂCÂND

┌ pentru i←a,b executa
│     <instructiuni>
└■

i ← a
┌ daca i ≤ b atunci
│┌ repeta
││     <instructiuni>
││     i ← i + 1
│└ panacand i > b
└■

CÂTTIMP → EXECUTĂ … CÂTTIMP

┌ cattimp <conditie> executa
│     <instructiuni>
└■

┌ daca <conditie> atunci
│┌ executa
││     <instructiuni>
│└ cattimp <conditie>
└■

CÂTTIMP → REPETĂ … PÂNÂCÂND

┌ cattimp <conditie> executa
│     <instructiuni>
└■

┌ daca <conditie> atunci
│┌ repeta
││     <instructiuni>
│└ panacand NOT <conditie>
└■

REPETĂ … PÂNĂCÂND → CÂTTIMP

┌ repeta
│     <instructiuni>
└ panacand <conditie>

<instructiuni>
┌ cattimp NOT <conditie> executa
│     <instructiuni>
└■

Coada de priorități este o structură de date de tip coadă, în care se fac operații de inserare și eliminare, dar ordinea nu este cea a cozii obișnuite. Fiecare element are asociată o anumită prioritate (de exemplu chiar valoarea sa), iar elementul de la începutul cozii este cel cu prioritate maximă, el fiind și cel care va fi eliminat din coadă în cazul operației de eliminare a unui element.

Cozile de priorități pot fi implementate sub formă de heap-uri, iar STL contine containerul adaptor priority_queue. Tehnic priority_queue implementează în mod implicit un max-heap.

Operația de determinare a elementului maxim are complexitate constantă, in timp ce operațiile de inserare și eliminare au complexități logaritmice în raport cu numărul de elemente.

Declarare

Clasa priority_queue este o clasă template definită în headerul queue:

#include <queue>

O putem declara ca în exemplul următor:

priority_queue<int> H;

Implicit, priority_queue-ul este un max-heap (elementul maxim are prioritate maximă) și se implementează pe baza operației < (less<int>)). Dacă dorim să gestionăm un min-heap (elementul minim să aibă prioritate maximă) vom folosi următoarea declarație:

priority_queue<int , vector<int> , greater<int> > H;

Similar, putem crea cozi de priorităti cu elemente de tipuri oarecare T. Condiția este să fie definit pentru tipul T operatorul < (functorul less<T>), sau să construim un functor de comparare.

struct fcmp
{	bool operator()(const T & a , const T & b)
	{
		//returneaza true daca si numai daca a este strict in fata lui b in ordinea dorita
	}
};
priority_queue<T , vector<T> , fcmp > H;

Operații de bază

Fie următoarea coadă de priorități:

priority_queue<T> H;
T v;

Adăugarea unui element

priority_queue<T> H;
T v;
H.push(v);

Se adaugă în coadă elementul v. Elementele se reorganizează pentru se păstra proprietate de heap (elementul maxim să fie la început).

Ștergerea unui element

priority_queue<T> H;
H.pop();

Se șterge din coadă elementul de la început. Elementele se reorganizează pentru se păstra proprietate de heap.

Determinarea elementului din vârf

priority_queue<T> H;
T v;
v = H.top();

Returnează o referință la elementul de la începutul cozii. Elementul se va elimina numai la apelul metodei pop().

Stabilirea faptului că este coada vidă

priority_queue<T> H;
H.empty()

Returnează true dacă H este o coadă vidă și false în caz contrar.

Dimeniunea cozii

priority_queue<T> H;
H.size()

Returnează numărul de elemente din coada de priorități H.

Atribuirea

Conținutul unei cozi de priorități poate fi copiat în altă coadă de același tip prin operatorul de atribuire =.

priority_queue<T> A , B;
...
A = B;

Exemple

Considerăm următoarea problemă;

Se dau coordonatele întregi ale unor puncte în plan. Să se afișeze coordonatele în ordinea crescătoare a absciselor, iar la abscise egale în ordinea crescătoare a ordonatelor.

Următoarele soluții se bazează pe o coadă de priorități în care adăugăm toate punctele, apoi le extragem și le afișăm.

Soluția 1

Pentru memorarea unui punct folosim o structură (clasă) definită în mod adecvat. Pentru stabilirea ordinii între puncte folosim un functor, iar pentru afișarea coordonatelor folosim o funcție prietenă.

#include <iostream>
#include <queue>

using namespace std;

struct Punct{
	int x , y;
	Punct(int a = 0, int b = 0){ x  = a , y = b;}
	friend ostream & operator<<(ostream & os , Punct A)
	{
		os << "(" << A.x << "," << A.y << ")";
		return os;
	}
};

struct fcmp
{	bool operator()(const Punct & a , const Punct & b)
	{
		if(a.x > b.x)
			return true;
		if(a.x < b.x)
			return false;
		if(a.y > b.y)
			return true;
		return false;
	}
};

int main()
{
	priority_queue<Punct, vector<Punct>, fcmp> H;
	H.push(Punct(6,1));
	H.push(Punct(2,7));
	H.push(Punct(2,4));
	H.push(Punct(4,10));
	H.push(Punct(7,4));
	while(! H.empty())
		cout << H.top() << '\n', H.pop();
	return 0;
}

Soluția 2

În acestă soluție nu folosim un functor pentru comparare, ci supraîncărcăm operatorul < printr-o functie prietenă.

#include <iostream>
#include <queue>

using namespace std;

struct Punct{
	int x , y;
	Punct(int a = 0, int b = 0){ x  = a , y = b;}
	friend ostream & operator<<(ostream & os , const Punct & A)
	{
		os << "(" << A.x << "," << A.y << ")";
		return os;
	}
	friend bool operator<(const Punct & A , const Punct & B)
	{
		if(A.x > B.x)
			return true;
		if(A.x < B.x)
			return false;
		if(A.y > B.y)
			return true;
		return false;
	}
};

int main()
{
	priority_queue<Punct> H;
	H.push(Punct(6,1));
	H.push(Punct(2,7));
	H.push(Punct(2,4));
	H.push(Punct(4,10));
	H.push(Punct(7,4));
	while(! H.empty())
		cout << H.top() << '\n', H.pop();
	return 0;
}

Soluția 3

Pentru memorare punctelor folosim clasa pair. Clasa pair are definit operatorul mai mic, acesta verificând ordinea lexicografică pentru membrii first și second.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue <
		pair<int,int>,
		vector<pair<int,int>>,
		greater<pair<int,int>>
		> H;
	H.push({6,1});
	H.push({2,7});
	H.push({2,4});
	H.push({4,10});
	H.push({7,4});
	while(! H.empty())
		cout << "(" << H.top().first << "," << H.top().second << ")" << '\n', H.pop();
	return 0;
}

Declararea de mai sus trebuie făcută în acest mod, pentru a obține un min-heap. Dacă am fi folosit declararea:

priority_queue <pair<int,int> > H;

s-ar fi implementat (pe baza functorului less<pair<int,int>>) un max-heap, în care elementele de prioritate maximă ar fi fost acela care au câmpul first mai mare.

Standard Template Library – STL

bitset este un container special din STL care permite lucrul cu șiruri de biți. Aceștia sunt memorați eficient, pentru un bit din șir folosindu-se un bit în memorie. Astfel, spațiul de memorie ocupat de un bitset cu M biți este mai mic decât un tablou bool V[M]; sau un vector cu elemente de tip bool, dar numărul de biți M din bitset trebuie să fie cunoscut în momentul compilării, deci trebuie să fie o contantă.

Pot fi folosiți de exemplu pe post de vectori caracteristici, dar suportă și operațiile pe biți cunoscute pentru tipurile întregi.

Declararea

Pentru a folosi containerul bitset trebuie inclus headerul bitset:

#include <bitset>

Declararea se face astfel:

const int M = 16;
bitset<M> B = 30;

Operații elementare

Afișarea

const int M = 16;
bitset<M> B = 30;
cout << B << endl;

Observații:

• M este constantă. Lipsa modificatorului const duce la o eroare de compilare.
• Când afișăm bitsetul, se afișează toți cei M biți.

Indexarea

Biții din bitset sunt indexați de la 0 și pot fi accesați prin operatorul []. Bitul cel mai nesemnificativ (cel mai din dreapta) este B[0], iar bitul cel mai semnificativ este B[M-1], unde M este dimensiunea bitsetului.

const int M = 16;
bitset<M> B = 30; // 0000000000011110
B[6] = 1;
cout << B;        // 0000000001011110

Compararea

Două containere bitset de aceeași dimensiune pot fi comparate cu operatorii == și !=.

Notă: operația != este eliminată în C++20.

Atribuirea

Putem să-i atribuim unui bitset valoarea unui întreg sau valoarea unui alt bitset. Prin atribuirea unui întreg, biții din bitsetul B devin identici cu biții din reprezentarea în memorie a valorii întregi care se atribuie:

const int M = 16;
bitset<M> B, A;
B = -30;
cout << B << endl; // 1111111111100010
B = 5;
cout << B << endl; // 0000000000000101
A = B;
cout << A << endl; // 0000000000000101

Manipularea biților

Numărarea bitilor setați, numărul total de biți

Pentru a afle câți biți din bitset sunt setați (au valoarea 1), folosim metoda count(). Pentru a determina numărul total de biți, folosim metoda size(). Numărul biților nesetați (cu valoarea 0), facem diferența celor două.

const int M = 16;
bitset<M> B = 63;
cout << B.count() << endl; // 6
cout << B.size() << endl; // 16

Determinarea valorii unui bit

Se face cu metoda test(k), unde k reprezintă numărul de ordine al bitului dorit (de la dreapta spre stânga, incepând de la 0), iar rezultatul este 1 sau 0.

const int M = 16;
bitset<M> B = 63;
cout << B << endl; // 0000000000111111
cout << B.test(5) << endl; // 1
cout << B.test(6) << endl; // 0

Set, reset, flip

Bitsetul oferă metode pentru:

• setarea unui bit precizat:
  • B.set(k) dă valoarea 1 pentru B[k]
  • B.set(k , r) dă valoarea r pentru B[k]
  • B.set() dă valoarea 1 pentru toți biții din B
• resetarea unui bit precizat:
  • B.reset(k) dă valoarea 0 pentru B[k]
  • B.reset() dă valoarea 0 pentru toți biții din B
• schimbarea valoare biților (din 1 devine 0, iar din 0 devine 1):
  • B.flip(k) schimbă valoarea lui B[k]
  • B.flip() schimbă valorile pentru toți biții din B

bitset<M> B;
B = 63;
cout << B << endl; // 0000000000111111
//bitii se numeroteaza de la dreapta, incepand cu 0
B.reset(5);
B.set(10);
B.set(9 , 1);
B.set(3 , 0);
B.flip(2);
cout << B << endl; // 0000011000010011
B.flip();
cout << B << endl; // 1111100111101100
B.set();
cout << B << endl; // 1111111111111111
B.reset();
cout << B << endl; // 0000000000000000

Operații pe biți

Operatii logice pe biți

Clasa bitset suportă operatorii logici pe biți (~, &, |, ^).

bitset<M> B, A;
B = -60; A = 5;
cout << "A     = " << A << endl;		// 0000000000000101
cout << "B     = " << B << endl;		// 1111111111000100
cout << "~B    = " << ~B << endl;		// 0000000000111011
cout << "A & B = " << (A & B) << endl;	// 0000000000000100
cout << "A | B = " << (A | B) << endl;	// 1111111111000101
cout << "A ^ B = " << (A ^ B) << endl;	// 1111111111000001

Operatorii de deplasare

Clasa bitset suportă operatorii de deplasare a biților (<<, >>).

bitset<M> B;
int n = 4;
B = 7;
cout << "B      = " << B << endl;				// 0000000000000111
cout << "B << n = " << (B << n) << endl;		// 0000000001110000

Atribuiri

Clasa bitset suportă atriburile scurte: &=, |=, ^=, precum și <<=, >>=.

Fie A , B două containere bitset de aceași dimensiune și n un întreg. Atunci:

• A &= B este echivalent cu A = A & B;
• A |= B este echivalent cu A = A | B;
• A ^= B este echivalent cu A = A ^ B;
• A <<= n este echivalent cu A = A << n;
• A >>= n este echivalent cu A = A >> n;

Conversii

Bitset-ul poate fi convertit la

• string – to_string
  • B.to_string() – returnează un string conținând reprezentarea binară a lui B, formată formată din caractere 0 și 1;
  • B.to_string(c0) – returnează un string conținând reprezentarea binară a lui B, caracterele 0 fiind înlocuite cu caracterul c0;
  • B.to_string(c0 , c1) – returnează un string conținând reprezentarea binară a lui B, caracterele 0 și 1 fiind înlocuite cu caracterul c0, respectiv c1;
• întreg fără semn- to_ulong(), to_uulong()
  • B.to_ulong() – retunează un întreg fără semn pe 32 de biți (unsingned int, unsigned long) cu reprezentarea binară echivalentă cu configurația bitsetului B;
  • B.to_uulong() – retunează un întreg fără semn pe 64 de biți (unsigned long long) cu reprezentarea binară echivalentă cu configurația bitsetului B;
  • dacă valoarea întreagă corespunzătoare bitsetului nu poate fi reprezentată pe 32, respectiv 64 de biți, se va ridica o excepție de tip overflow_error.

Standard Template Library – STL

Containerul C++ vector este, probabil, cel mai folosit container STL. Vectorii sunt tablouri dinamice cu elemente omogene care au proprietatea de a se redimensiona automat când se adaugă sau se șterge un element, gestionarea memoriei fiind realizată automat de către container.

Vectorii sunt stocați într-o zonă contiguă de memorie și pot fi traversați cu ajutorul iteratorilor. Elementele se adaugă, de regulă la sfârșit. Operația de adăugare ia, de regulă, timp constant, cu excepția cazului când spatiul de memorie alocat trebuie redimensionat (mărit). Ștergerea unui element ia întotdeauna timp constant. Inserarea și ștergerea la începutul sau în interiorul vectorului iau timp liniar.

Declararea unui vector

Trebuie inclus header-ul vector:

#include <vector>;

Declararea se face astfel:

vector<T> V;

unde T este un tip de date. Acesta va fi tipul elementelor vectorului. Vectorul declarat mai sus este vid – are 0 elemente.

Alternativ, putem declara vectorul astfel:

vector<T> V(n);

n este un întreg. Se va crea un crea un vector V cu n elemente. Valorile acestora sunt valorile implicite pentru datele de tip T. Pentru tipurile numerice, valoarea elementelor este 0.

vector<T> V(n, vT);

n este un întreg, iar vT este o dată de tip T. Se va crea un crea un vector V cu n elemente. Valorile acestora sunt copii ale lui vT.

De exemplu:

vector<int> A; // se crează un vector A cu zero elemente
cin >> n;
vector<int> B(n); // se crează un vector B cu n elemente, egale cu 0
cin >> x;
vector<int> C(n , x); // se crează un vector B cu n elemente, egale cu x

Atribuirea

Spre deosebire de tablourile standard C, vectorilor li se pot atribui valori în orice moment. Exemplu:

vector<int> A , B = {2 , 4, 6 , 8};
A = B;
A = {1 , 2 , 3 , 4 , 5};

Dimensiunea și capacitatea

Numărul de elemente din vector poate fi determinat cu funcția size():

vector<int> A = {2 , 4 , 6 , 8};
cout << A.size(); // 4

De regulă, memoria alocată pentru un vector este mai mare decât memoria folosită. Acest lucru se întâmplă pentru a se evita realocarea memoriei (operație costisitoare, care presupune copierea tuturor elementelor) de fiecare dată când se adaugă elemente.

Funcția capacity() returnează numărul de elemnte pe care le poate avea vectorul la momentul curent, fără a se realoca memoria. Are loc relația capacity() >= size(), iar numărul de elemente care pot fi adăugate fără realocare este capacity() - size().

Redimensionarea

Funcția resize() permite redimensionarea unui vector și are următoarele forme:

• V.resize(n); (1)
• V.resize(n , x); (2)

Vectorul V se redimensionează încât să aibă n elemente:

• dacă n < V.size(), în vector vor rămâne primele n elemente, celelalte vor fi șterse.
• dacă n > V.size(), în vector se vor adăuga n - V.size() elemente egale cu x , în cazul (2) sau egale cu valoarea implicită pentru tipul elementelor din vector, în cazul (1). Această valoare este 0 pentru tipurile numerice.

Adăugarea unui element

Adăugarea unui nou element în vector se face la sfârșit, cu funcția push_back():

vector<int> A;
for(int i = 1 ; i <= 5 ; i ++)
	A.push_back(2 * i);
cout << A.size();

Accesarea unui element

Elementele vectorilor pot fi accesate prin intermediul indicilor, cu operatorul []. Acesta nu verifică existență elementului cu un anumit indice, iar dacă acesta nu există, comportamentul programului este impredictibil.

vector<int> A;
for(int i = 1 ; i <= 5 ; i ++)
	A.push_back(2 * i);
for(int i = 0 ; i < A.size() ; i ++)
	cout << A[i] << ' '; // 0 2 4 6 8

De asemenea, este posibilă accesarea elementelor prin intermediul funcției at(). Aceasta returnează o referință la elementul de la poziția dată, iar dacă acesta nu există ridică o excepție care poate fi capturată prin mecanismul try … catch.

vector<int> A = {2 , 4 , 6 , 8 , 10};
A.at(1) = 20; //A = {2 , 20 , 6 , 8 , 10}
for(auto x : A)
	cout << x << " ";

Primul și ultimul element poate fi accesat prin intemediul funcțiilor front() și back(). Ele returnează referințe la primul, respectiv ultimul element al vectorului. Comportamentul este impredictibil dacă vectorul este vid.

vector<int> A = {2 , 4 , 6 , 8 , 10};
A.at(1) = 20; //A = {2 , 20 , 6 , 8 , 10}
A.front() = 7; //A = {7 , 20 , 6 , 8 , 10}
A.back() = 5; //A = {7 , 20 , 6 , 8 , 5}
for(auto x : A)
	cout << x << " ";

Iteratori

Iteratorii sunt similari cu pointerii. Cu ajutorul lor putem identifica adresa elementelor din vector. Iteratorii pot fi dereferențiați (obtinând referințe la elemente), pot fi incrementați/decrementați și pot fi adunați cu scalari.

Vectorii oferă prin intermediul funcției begin() un iterator la primul element al funcției, iar prin end() un iterator la elementul de după ultimul element al vectorului.

vector<int> A = {2 , 4 , 6 , 8 , 10};
vector<int>::iterator I;
for(I = A.begin() ; I < A.end() ; I ++)
	cout << *I << " "; // 2 4 6 8 10

Observații:

• tipul variabilei iterator trebuie să fie în concordanță cu tipul elementelor vectorului;
• pentru a lucra cu elementul pentru care cunoaștem iteratorul, acesta trebuie să fie dereferențiat: *I;
• rezultatul funcției A.end() este un iterator, dar acestuia nu-i corespunde un element al vectorului. Valoarea sa este adresa de după ultimul element al vectorului.

Clasa vector conține și funcțiile rbegin() și rend(), care returnează iteratori de tip reverse iterator, care permit parcurgerea vectorului în ordien inversă:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(vector<int>::reverse_iterator I = A.rbegin() ; I < A.rend() ; I ++)
	cout << *I << " ";

Acești iteratori fac parte din categoria iteratorilor cu acces aleatoriu. Este cea mai puternică categorie de iteratori (cu cele mai multe operații definite). Aceste operații sunt:

Parcurgerea unui vector

O primă modalitate de parcurgere este folosind indicii, similar cu parcurgerea tablourilor standard C. Pentru determinarea numărului de elemnte există functia size():

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int i = 0 ; i < A.size(); i ++)
	cout << A[i] << " ";

De asemenea, putem folosi iteratorii:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(vector<int>::iterator I = A.begin() ; I < A.end() ; I ++)
	cout << *I << " ";

Pentru ușurință, putem folosi specificatorul de tip auto pentru a stabili tipul iteratorului:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(auto I = A.begin() ; I < A.end() ; I ++)
	cout << *I << " ";

Începând de la versiunea 2011 a standardului C++ există o formă specială a instrucțiunii for, care permite parcurgerea elementelor unui container:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int x : A)
	cout << x << " ";

Specificatorul de tip auto poate fi folosit și aici. În secvența de mai sus, x reprezintă pe rând câte o copie a elementelor din A. Eventualele modificări ale lui x nu vor modifica valorile elementelor din A. Dacă se dorește modificare elemenelor din A, atunci x trebuie să fie o referință:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int & x : A)
	x *= 2;
for(int x : A)
	cout << x << " ";

Parcurgerea inversă

Vectorii suportă iteratori reversibili, care permit parcurgerea containerului în ordine inversă. Clasa vector are metodele:

• rbegin() – returnează un iterator reversibil la ultimul element din container
• rend() – returnează un iterator reversibil la elementul din fața primului

Parcurgerea se poate face astfel:

for(vector<int>::reverse_iterator I  = V.rbegin() ; I < V.rend() ; I ++)
	cout << *I << " ";

Inserarea elementelor

Pentru adăugarea la sfârșit se folosește metoda push_back(). Pentru inserarea de noi elemente în interiorul containerului se folosește metoda insert(), care are mai multe forme:

• V.insert(pos , x) – inserează în vectorul V, în fața iteratorului pos un nou element cu valoarea x;
• V.insert(pos , cnt , x) inserează în vectorul V, în fața iteratorului pos, cnt noi elemente egale cu x;
• V.insert(pos , st , dr) inserează în vectorul V, în fața iteratorului pos, dr-st noi elemente, având valorile egale cu cele ale elementelor din secvența [st, dr) dintr-un container oarecare. Dacă vectorul V și secvența [st,dr) se suprapun rezultatul este impredictibil.

Rezultatul apelurilor de mai sus este un iterator la primul element inserat.

Apelurile de mai sus invalidează toți iteratorii și referințele la elemente din V, dacă în urma inserării se realocă memorie, respectiv se invalidează iteratorii și referințele din dreapta lui pos, în caz contrar.

Mai multe detalii despre insert() aici: https://en.cppreference.com/w/cpp/container/vector/insert.

Eliminarea elementelor

Pentru eliminarea tuturor elementelor intr-un vector există metoda clear().

V.clear();

În urma eliminării, rezultatul lui V.size() este 0.

Pentru eliminarea ultimului element al tabloului există metoda pop_back(). În urma apelului se invalidează iteratorii și referințele la ultimul element, precum și iteratorul end().

Pentru eliminarea unor elemente oarecare se folosește metoda erase(), cu următoarele forme:

• V.erase(pos) – elimină elementul indicat de iteratorul pos. pos nu poate fi egal cu end()
• V.erase(st , dr) – elimină elementele din intervalul [st,dr), unde st și dr sunt iteratori la elemente din V

Rezultatul funcției erase() este un iterator la elementul de după ultimul element eliminat.

Se invalidează iteratorii și iteratorii din dreapta lui posm inclusiv iteratorul end().

Mai multe detalii aici: https://en.cppreference.com/w/cpp/container/vector/erase.

Standard Template Library – STL