Algoritmi C++ cu aplicatii in structurile de date. Vol I+II

DESPRE CARTE

ALGORITMI C++. Algoritmi fundamentali si algoritmi evoluati. Vol. I

Acest prim volum introduce cititorul in gandirea algoritmica printr-o expunere riguroasa si unitara, care porneste de la conceptele elementare si conduce, firesc, catre metodele avansate de programare. Lucrarea imbina claritatea explicatiilor cu implementari clasice in C++, numeroase exemple comentate pas cu pas si o atentie constanta pentru mecanismele interne ale algoritmilor.

Volumul acopera principalii piloni ai proiectarii algoritmilor: structuri de control, vectori si matrici, siruri de caractere, subprograme, pointeri, recursivitate, divide et impera, cautare binara, metode Greedy, programare dinamica si backtracking. Fiecare capitol combina fundamentele teoretice cu programe C++ complete, diagrame explicative, aplicatii practice si observatii pedagogice menite sa previna confuziile frecvente.

Volumul se adreseaza tuturor cititorilor interesati de proiectarea algoritmilor si de modul lor de implementare in C++, oferind nu doar programe corecte, ci si instrumentele necesare pentru analiza, comparatie si constructia unor solutii algoritmice robuste.

STRUCTURI DE DATE SI BAZELE STL. Vol. II

Acest al doilea volum ofera o perspectiva ampla si coerenta asupra structurilor de date, punand accent pe organizarea lor interna, pe comportamentul in memorie si pe aplicarea practica in C++ clasic si modern. Lucrarea porneste de la structurile liniare — liste dublu inlantuite, liste simple, liste circulare, stive si cozi — si continua cu structurile neliniare: arbori, arbori AVL, arbori Red-Black, grafuri neorientate si orientate, matrici rare si polinoame rare.

Un element definitoriu al volumului il reprezinta legatura constanta dintre teorie si implementare. Fiecare structura este explicata prin programe C++ complete, comentate si testate, care ilustreaza comportamentul algoritmilor la nivelul memoriei: alocare, eliberare, inserare, stergere, parcurgere si analiza eficientei.

Ultimul capitol este dedicat bibliotecii STL (Standard Template Library), prezentata ca o continuare fireasca a abordarii clasice si ca un instrument modern care completeaza structurile implementate pas cu pas in lucrare.

Volumul poate fi folosit atat ca manual de studiu, cat si ca material de referinta, ajutand cititorul sa inteleaga nu doar cum se folosesc structurile de date, ci si cum sunt construite — si de ce alegerea lor influenteaza decisiv performanta algoritmilor.

CUVANT INAINTE

Recomand cu caldura lucrarea „Algoritmi C++ cu aplicatii in structurile de date”, autor Dan Stefan Gogoncea. Ea contine un bogat material despre algoritmi fundamentali si algoritmi evoluati, structuri de date si o prezentare sintetica a STL (Standard Template Library).

Prezentarea lucrarii este sustinuta de peste 160 de programe din aceste domenii, rulate si verificate, precum si un bogat material grafic. Aspectul interdisciplinar este sustinut de aplicatii pentru reprezentarea grafica, dinamica si interactiva, a rezultatelor unor programe C++ , prin JavaScript, HTML, Canvas si Google Maps App.

O idee centrala a lucrarii este unitatea dintre algoritmi si structurile de date, algoritmii fiind ganditi pentru a servi ca instrumente directe in implementarea structurilor de date, din partea a doua a lucrarii.

Lucrarea se poate citi fara dificultati, expunerea fiind clara si insotita de multe exemple. Ea este recomandata in contexte variate: cursuri universitare de algoritmi si structuri de date, laboratoare de programare in C/C++, pregatirea pentru concursuri sau interviuri tehnice, sau pentru studiul individual.

Acad. IOAN TOMESCU

CUPRINS Vol.I

PREFATA 19

1. ALGORITMI FUNDAMENTALI23
1.1 INTRODUCERE 24
1.2 PROGRAMAREA IN LIMBAJUL C++ 26
1.2.1 INTRODUCERE IN PROGRAMARE SI ALGORITMICA 26
1.2.1.1 COMPILATOARE SI INTERPRETOARE 26
1.2.1.2 COMPARATIE INTRE LIMBAJE C/C++ SI ALTE LIMBAJE MODERNE 28
1.2.2 LIMBAJELE C SI C++ – CARACTERISTICI ESENTIALE 28
1.2.3 ALGORITMI – DEFINITII, PROPRIETATI SI EXEMPLE 29
1.2.4 PSEUDOCOD SI REPREZENTARI GRAFICE (ORGANIGRAME) 30
1.2.5 NOTIUNI ELEMENTARE C/C++: VARIABILE, TIPURI, OPERATII 32
1.2.6 MEDIUL CODE::BLOCKS – UTILIZARE PRACTICA 33
1.2.7 RECOMANDARI SI BUNE PRACTICI IN PROGRAMARE C/C++ 37
1.3 BAZELE MATEMATICE 38
1.3.1 PREZENTARE GENERALA; DEFINITII 38
1.3.2 TRECEREA NUMERELOR NATURALE DIN BAZA 10 INTR-O BAZA B OARECARE 44
1.3.3 TRECEREA NUMERELOR NATURALE DINTR-O BAZA B IN BAZA 10 52
1.3.5 REPREZENTARE NUMERELOR FRACTIONARE INTR-O BAZA B 61
1.4 INTRARI IESIRI 65
1.4.1 INTRARI – IESIRI IN C++ 65
1.4.1.1 CITIREA DATELOR DE LA TASTATURA 65
1.4.1.2 CITIREA / SCRIEREA DATELOR DIN / IN FISIERE EXTERNE 67
1.4.2 INTRARI – IESIRI IN C 71
1.5 INSTRUCTIUNI CONDITIONALE 77
1.5.1 NOTIUNI GENERALE 77
1.5.2 INSTRUCTIUNEA IF 78
1.5.3 INSTRUCTIUNEA IF…ELSE 79
1.5.4 INSTRUCTIUNEA IF…ELSE IF…ELSE 80
1.5.5 INSTRUCTIUNEA SWITCH 80
1.5.6 OPERATORUL CONDITIONAL ?: 80
1.5.7 CONDITII COMPUSE 82
1.5.8 APLICATII ALGORITMICE 86
1.5.8.1 METODA CRAMER PENTRU REZOLVAREA SISTEMELOR LINIARE:86
1.5.8.2 REZOLVAREA ECUATIEI DE GRADUL 2 88
1.5.8.3 MENIU DE OPTIUNI PENTRU LISTE 94
1.5.9 CONCLUZII 94
1.5.10 PROBLEME PROPUSE 95
1.6 INSTRUCTIUNI REPETITIVE 95
1.6.1 INTRODUCERE 95
1.6.2 INSTRUCTIUNEA WHILE 96
1.6.3 INSTRUCTIUNEA DO…WHILE 99
1.6.4 INSTRUCTIUNILE BREAK SI CONTINUE 101
1.6.5 SCHEME UZUALE DE LUCRU 101
1.6.6 EXEMPLE ALGORITMICE 102
1.6.6.1 ALGORITMUL LUI EUCLID CU SCADERI REPETATE 102
1.6.6.2 ALGORITMUL LUI EUCLID CU IMPARTIRI REPETATE 104
1.6.6.3 CONSTRUCTIA UNUI NUMAR DIN CIFRELE CONSTITUENTE 106
1.6.6.4 VERIFICAREA DACA UN NUMAR ESTE PALINDROM 107
1.6.7 DIFERENTE INTRE WHILE SI DO…WHILE 108
1.6.8 PROBLEME PROPUSE 110
1.7 CICLUL FOR 110
1.7.1 INTRODUCERE 110
1.7.2 ECHIVALENTA FOR – WHILE 111
1.7.3 EXEMPLU DE PROBLEMA REZOLVATA CU FOR 114
1.7.4 INSTRUCTIUNILE BREAK SI CONTINUE 115
1.7.5 UTILIZAREA UNEI VARIABILE FANION (FLAG) 115
1.7.6 EXEMPLE DE ALGORITMI 116
1.7.6.1 VERIFICAREA PRIMALITATII UNUI NUMAR 116
1.7.6.2 CALCULUL UNOR SUME SI PRODUSE RECURENTE 117
1.7.6.3 SIRUL LUI FIBONACCI 119
1.7.6.4 CALCULUL MAXIMULUI SI MINIMULUI 121
1.7.7 EXERCITII PROPUSE 123
1.7.8 CONCLUZII 123
1.8 VECTORI 124
1.8.1 INTRODUCERE TEORETICA 124
1.8.2 INITIALIZAREA UNUI VECTOR 125
1.8.3 CITIREA VECTORILOR 126
1.8.3.1 CITIREA DE LA TASTATURA 126
1.8.3.2 CITIREA UNUI VECTOR DINTR-UN FISIER 128
1.8.4 ALGORITMI FUNDAMENTALI CU VECTORI 130
1.8.4.1 CAUTAREA UNEI VALORI INTR-UN VECTOR NEORDONAT 130
1.8.4.2 DETERMINAREA VALORILOR MAXIME SI MINIME 131
1.8.4.3 ORDONAREA VECTORILOR 133
1.8.4.4 DEPLASAREA ELEMENTELOR INTR-UN VECTOR 139
1.8.5 CREAREA DE VECTORI DERIVATI 143
1.8.5.1 PE BAZA VALORILOR (PARE VS. IMPARE) 143
1.8.5.2 PE BAZA POZITIEI (INDICI PARI VS. IMPARI) 145
1.8.6 VECTORI CU CARACTERISTICI SPECIALE 146
1.8.6.1 VERIFICAREA ELEMENTELOR DISTINCTE 146
1.8.6.2 VECTORI DE CONSISTENTA 148
1.8.6.3 VECTORI DE FRECVENTA 150
1.8.7 OPERATII IMPLICAND DOI VECTORI 151
1.8.7.1 DETERMINAREA ELEMENTELOR COMUNE 151
1.8.7.2 DESCOMPUNEREA IN FACTORI PRIMI 153
1.8.8. ASPECTE LEGATE DE ADRESE SI POINTERI LA VECTORI 154
1.8.9 VECTORI DINAMICI FOLOSIND STL CLASA STD::VECTOR 157
1.8.10 CONCLUZII 160
1.8.11 PROBLEME PROPUSE 160
1.9 MATRICE 161
1.9.1 INTRODUCERE TEORETICA 161
1.9.2 CITIREA SI AFISAREA MATRICELOR 162
1.9.2.1 CITIREA UNEI MATRICE DE LA TASTATURA 162
1.9.2.2 CITIREA UNEI MATRICE DIN FISIER 165
1.9.3 CONSTRUCTIA MATRICEI DE CONTROL 166
1.9.4 DRUMURI SI ZONE IN MATRICE 168
1.9.4.1 DRUMURI IN MATRICE 168
1.9.4.2 ZONE IN MATRICE 172
1.9.5 PROBLEME ELEMENTARE 180
1.9.5.1 SUMA A DOUA MATRICE 180
1.9.5.2 PRODUSUL A DOUA MATRICE 181
1.9.5.3 TRANSPUSA UNEI MATRICE 184
1.9.5.4 VECTORI ATASATI UNEI MATRICE 185
1.9.5.5 INTERSCHIMBARI DE LINII SI COLOANE 187
1.9.5.6 PUNCTELE SA ALE UNEI MATRICE 191
1.9.6 PROBLEME APLICATIVE 193
1.9.6.1 PARCURGEREA IN SPIRALA A UNEI MATRICE 193
1.9.6.2 DETERMINAREA CELEI MAI MARI SUBMATRICI PATRATICE 196
1.9.6.3 TRIANGULARIZAREA SUPERIOARA A UNEI MATRICE PATRATICE 199
1.9.6.4 GENERAREA UNEI MATRICE PATRATICE CU ELEMENTE ORDONATE 202
1.9.7 CONCLUZII 204
1.9.8 PROBLEME PROPUSE 205
1.10 SIRURI DE CARACTERE 205
1.10.1 TIPUL DE DATE CHAR 206
1.10.1.1 TABELUL ASCII 207
1.10.1.2 OPERATII ELEMENTARE PE CARACTERE 209
1.10.2 SIRURI DE CARACTERE 210
1.10.2.1 INTRODUCERE 210
1.10.2.2 DECLARATII SI INITIALIZARE DE SIRURI 212
1.10.2.3 CITIREA SI AFISAREA SIRURILOR 212
1.10.2.4 FUNCTII UTILE DIN BIBLIOTECILE STANDARD 217
1.10.2.5 APLICATII ALGORITMICE PE SIRURI 244
1.10.2.6 FUNCTII DE CONVERSIE 248
1.10.2.7 PROBLEME CU SIRURI DE CARACTERE 253
1.10.2.8 CONCLUZII 259
1.10.2.9 PROBLEME PROPUSE 260
1.11 TIPUL DE DATE STRUCT 261
1.11.1 INTRODUCERE 261
1.11.2 DE CE AVEM NEVOIE DE STRUCTURI? 261
1.11.3 OPERATII CU STRUCTURI 263
1.11.3.1 DECLARAREA UNEI VARIABILE DE TIP STRUCT 263
1.11.3.2 ACCESAREA SI MODIFICAREA CAMPURILOR 263
1.11.3.3 INITIALIZARE LA MOMENTUL DECLARARII 264
1.11.3.4 MAI MULTE VARIABILE SIMULTAN 264
1.11.3.5 COPIEREA VALORILOR INTRE STRUCTURI 264
1.11.4 STRUCTURI SIMPLE 264
1.11.4.1 EXEMPLUL 1: 266
1.11.4.2 EXEMPLUL 2: 270
1.11.5 STRUCTURI IMBRICATE 271
1.11.6 PROBLEME REZOLVATE 273
1.11.6.1 PROBLEMA DISTANTA PUNCTE 273
1.11.6.2 PROBLEMA FRACTII: 276
1.11.7 CONCLUZII 278
1.11.8 PROBLEME PROPUSE 279
1.12 SUBPROGRAME 281
1.12.1 INTRODUCERE 281
1.12.2 GENERALITATI 282
1.12.4 RETURNAREA VALORILOR 285
1.12.5 PROTOTIPUL FUNCTIEI 285
1.12.6 VARIABILE LOCALE SI DOMENIUL DE VIZIBILITATE 286
1.12.7 VARIABILE GLOBALE 287
1.12.8 CONFLICTE INTRE VARIABILE LOCALE SI GLOBALE 288
1.12.9 IERARHIE 288
1.12.10 DEFINIREA UNEI FUNCTII (SUBPROGRAM) 289
1.12.10.1 TIPURI DE SUBPROGRAME 289
1.12.10.2 EXEMPLUL 1 – FUNCTIE CU RETURN 289
1.12.10.3 EXEMPLUL 2 – FUNCTIE CU DETALII DE EXECUTIE 290
1.12.10.4 EXEMPLUL 3 FUNCTIE `void` CU PARAMETRI PRIN REFERINTA 292
1.12.11 FUNCTII CU VECTORI 296
1.12.11.1 MAXIMUMUL DINTR-UN VECTOR 296
1.12.11.2 ORDONARE PRIN INTERSCHIMBARE 297
1.12.11.3 ORDONARE PRIN METODA BULELOR 298
1.12.12 SUBPROGRAME – PRELUCRAREA NUMERELOR COMPLEXE (STRUCT + FUNCTII) 300
1.12.13 CONCLUZII 308
1.12.14 PROBLEME PROPUSE 308
1.13 POINTERI IN C++ 310
1.13.1 INTRODUCERE 310
1.13.2 ADRESE, VARIABILE SI OPERATORUL & 310
1.13.3 DECLARAREA SI UTILIZAREA POINTERILOR 314
1.13.4 MODIFICAREA VALORII PRIN DEREFERENTIERE 315
1.13.5 ARITMETICA POINTERILOR 315
1.13.6 POINTERI SI ALOCAREA DINAMICA A VECTORILOR 316
1.13.6.1 ALOCARE DINAMICA – EXEMPLU ELEMENTAR 316
1.13.6.2 ALOCARE DINAMICA – STUDIU DE CAZ 318
1.13.7 POINTERI CA PARAMETRI AI FUNCTIILOR 320
1.13.8 POINTERI NULI SI POINTERI GENERICI (void*) 320
1.13.8.1 POINTERI NULI SI SIGURANTA PROGRAMARII 320
1.13.8.2 POINTERI GENERICI (VOID*) SI AFISARE POLIMORFA 321
1.13.9 ALOCARE DINAMICA IN STIL C++ 323
1.13.10 ALOCARE DINAMICA IN STIL C 323
1.13.11 POINTERI LA POINTERI 324
1.13.12 MATRICE ALOCATE DINAMIC 325
1.13.13 DIFERENTA INTRE POINTERI SI APLICATII CU SIRURI 326
1.13.14 POINTERI LA FUNCTII 327
1.13.15 EXEMPLE AVANSATE: POINTERI + STRUCTURI 328
1.13.16 APLICATIE INTEGRATOARE 332
1.13.17 POINTERI LA FUNCTII – APLICATII AVANSATE 336
1.13.18 POINTERI SI MATRICI 338
1.13.19 CONCLUZII 340

2. ALGORITMI EVOLUATI 341
2.1 RECURSIVITATE 343
2.1.1 RECURSIVITATEA IN ALGORITMICA 343
2.1.2 DIFERENTE INTRE RECURSIVITATE SI ITERATIE 345
2.1.3 MECANISMUL STIVEI DE APELURI 346
2.1.4 ORDINEA EXECUTARII INSTRUCTIUNILOR IN RECURSIVITATE 348
2.1.5 EXEMPLE CLASICE DE RECURSIVITATE 353
2.1.5.1 ALGORITMUL LUI EUCLID CU SCADERI SUCCESIVE 353
2.1.5.2 ALGORITMUL LUI EUCLID CU IMPARTIRI SUCCESIVE 354
2.1.5.3 SIRUL LUI FIBONACCI – APLICATII SI ANALIZA 354
2.1.5.4 CONVERSIA NUMERELOR DIN BAZA 10 IN BAZA B 357
2.1.5.5 UMPLEREA UNEI ZONE INCHISE (FLOOD FILL) 358
2.1.5.6 LABIRINT RECURSIV 361
2.1.6 CONCLUZII 370
2.1.7 PROBLEME PROPUSE 370
2.2 DIVIDE ET IMPERA 371
2.2.1 INTRODUCERE SI PRINCIPII GENERALE 371
2.2.2 GASIREA MAXIMULUI DINTR-UN VECTOR 372
2.2.3 ALGORITMI CLASICI DE SORTARE PRIN DIVIDE ET IMPERA 374
2.2.3.1 ALGORITMUL MERGE SORT (SORTARE PRIN INTERCLASARE) 375
2.2.3.2 ALGORITMUL QUICK SORT (SORTARE RAPIDA) 377
2.2.4 ALTE APLICATII REPREZENTATIVE 379
2.2.4.1 TURNURILE DIN HANOI 379
2.2.4.2 PROBLEMA GRADINII JAPONEZE (ARIA MAXIMA) 382
2.2.4.3 METODA BISECTIEI – CALCULUL RADACINII UNEI ECUATII 385
2.2.5 CONCLUZII 386
2.2.6 PROBLEME PROPUSE 387
2.3 CAUTARE BINARA 388
2.3.1 INTRODUCERE 388
2.3.2 EXEMPLUL TIPIC DE PROBLEMA REZOLVATA PRIN CAUTARE BINARA 389
2.3.3 STUDIU DE CAZ 390
2.3.4 CAUTARE BINARA – REZUMAT SI ANALIZA COMPARATIVA 400
2.3.5 CONCLUZIE 400
2.3.6 EXERCITII PROPUSE 401
2.4 ALGORITMUL GREEDY 401
2.4.1 INTRODUCERE 401
2.4.2 PRINCIPIUL METODEI GREEDY 402
2.4.3 EXEMPLE CLASICE DE APLICARE A METODEI GREEDY 403
2.4.4 EXEMPLE PROBLEME REZOLVATE 405
2.4.4.1 PROBLEMA SELECTARII ACTIVITATILOR 405
2.4.4.2 PROBLEMA RUCSACULUI FRACTIONAR 406
2.4.4.3 PROBLEMA ACOPERIRII CU MONEDE 408
2.4.4.4 PROBLEMA ACOPERIRII INTERVALELOR 409
2.4.5 EXEMPLU DE ESEC AL METODEI GREEDY 410
2.4.6 CONCLUZII 411
2.5 PROGRAMARE DINAMICA 412
2.5.1 INTRODUCERE 412
2.5.2 EXEMPLE DE PROBLEME „CLASICE” 413
2.5.3 PROBLEME REZOLVATE 414
2.5.3.1 PROBLEMA PARTITIEI (PARTITION PROBLEM) 414
2.5.3.2 SUBSIRUL CRESCATOR MAXIMAL (LIS) 417
2.5.3.3 PROBLEMA RUCSACULUI (KNAPSACK PROBLEM) 420
2.5.3.4 PROBLEMA SUMEI DE MONEDE (COIN CHANGE) 423
2.5.4 CONCLUZII 425
2.5.5 PROBLEME PROPUSE 426
2.6 METODA BACKTRACKING 426
2.6.1 INTRODUCERE 426
2.6.2 EXEMPLE DE PROBLEME REZOLVATE PRIN BACKTRACKING 433
2.6.2.1 GENERAREA PRODUSULUI CARTEZIAN 433
2.6.2.2 GENERAREA PERMUTARILOR UNEI MULTIMI 436
2.6.2.3 GENERAREA ARANJAMENTELOR DE n LUATE CATE k 439
2.6.2.4 GENERAREA COMBINARILOR DE n LUATE CATE k 441
2.6.2.5 PROBLEMA ASEZARII TURNURILOR PE O TABLA DE SAH 443
2.6.2.6 PROBLEMA ASEZARII NEBUNILOR PE O TABLA DE SAH 446
2.6.2.7 PROBLEMA ASEZARII REGINELOR PE O TABLA DE SAH 451
2.6.2.8 PROBLEMA COMIS-VOIAJORULUI 453
2.6.3 CONCLUZII 463
2.6.4 PROBLEME PROPUSE 464

PREFATA

Lucrarea de fata, intitulata „Algoritmi C++ cu aplicatii in Structurile de Date”, este rezultatul unei activitati didactice si de cercetare desfasurate pe parcursul mai multor ani.

Ea se adreseaza in primul rand studentilor facultatilor de profil informatic si ingineresti, dar poate constitui un reper util si pentru elevii pasionati de algoritmica, precum si pentru toti cei care doresc sa aprofundeze arta programarii.

Lucrarea urmareste sa ofere nu doar implementari corecte in limbajele C si C++, ci si o viziune unitara asupra modului in care algoritmii fundamentali si cei evoluati se impletesc cu structurile de date clasice.

Constructia textului respecta principiile didactice: introducerea graduala a notiunilor, alternarea explicatiilor teoretice cu exemple concrete si includerea unor observatii menite sa previna confuziile frecvente.

In mod deliberat, am pastrat o abordare clasica a programarii – utilizand pointeri, alocare manuala si scheme algoritmice consacrate – pentru a sublinia mecanismele profunde ale limbajului, fara a ne lasa dominati de facilitatile bibliotecilor moderne.

Aceasta alegere didactica permite cititorului sa inteleaga mai bine „ce se afla sub capota” si sa-si formeze un mod de gandire algoritmic, independent de un anumit mediu de programare.

Totusi, pentru a oferi o imagine completa, la sfarsitul lucrarii este inclusa si o scurta prezentare a STL (Standard Template Library).

Aceasta are rolul de introducere in instrumentele moderne ale limbajului C++, dar se recomanda cu tarie aprofundarea mai intai a abordarii clasice, pentru a dobandi o baza solida si o intelegere reala a principiilor fundamentale.

Lucrarea este structurata in doua mari parti: Algoritmi si Structuri de Date, fiecare acoperind atat conceptele fundamentale, cat si aplicatiile mai avansate.

Partea de Algoritmi este, la randul ei, impartita in

– Algoritmi fundamentali

– Algoritmi evoluati (numiti uneori si „metode de programare”)

Aceasta impartire nu este doar formala, ci reflecta o progresie fireasca a gandirii algoritmice.

Algoritmii fundamentali pun bazele: de la operatii elementare si structuri simple de control, pana la primele modalitati de lucru cu date structurate.

Ei formeaza limbajul comun fara de care nu se pot construi solutii mai complexe.

Algoritmii evoluati, denumiti frecvent si metode de programare, deschid apoi orizontul catre strategii sofisticate – recursivitate, divide et impera, cautare binara, programare dinamica, tehnici Greedy sau Backtracking – capabile sa abordeze probleme de o dificultate mult sporita.

Prin alternarea explicatiilor teoretice cu aplicatii practice, cartea urmareste sa arate cum aceste metode nu sunt doar retete, ci adevarate instrumente de gandire, valabile dincolo de limbajul de programare folosit.

In mod complementar, Partea dedicata Structurilor de Date analizeaza modul in care informatia este organizata, stocata si accesata in memorie. Ea incepe cu structurile liniare – liste, stive si cozi – si continua cu structurile neliniare – grafuri, arbori si diverse structuri particulare (de la polinoame rare la matrici rare si arbori echilibrati).

Pentru fiecare categorie sunt prezentate atat conceptele teoretice, cat si implementari detaliate in C++, insotite de aplicatii practice si observatii privind avantajele si limitele fiecarei solutii. Aceasta abordare graduala ii ajuta pe cititori sa inteleaga cum alegerea unei structuri de date influenteaza performanta algoritmilor si, in final, eficienta programului.

Capitolele au fost concepute pentru a putea fi parcurse progresiv, dar si pentru a fi utilizate independent, ca material de referinta. Scopul acestei lucrari nu este doar acela de a furniza solutii, ci si de a stimula spiritul critic si creativitatea cititorului. Multe dintre problemele prezentate includ sugestii de extindere sau variante interdisciplinare, pentru a deschide orizonturi noi celor care indraznesc sa depaseasca tiparele.

Am inclus si exemple interdisciplinare care demonstreaza interconectarea fireasca a domeniilor tehnice:

• La capitolul Recursivitate – problema iesirii din labirint: rezultatul programului C++ este reprezentat grafic prin JavaScript si HTML – Canvas, vizualizand solutiile pas cu pas.

• La capitolul Liste dublu inlantuite – reprezentarea grafica dinamica a unei harti: datele generate in C++ sunt integrate intr-o aplicatie web interactiva (JavaScript, HTML Canvas, Google Maps API), pentru afisarea si explorarea vizuala a unei retele de orase.

Astfel de exemple arata ca informatica, matematica, grafica si tehnologiile web pot lucra impreuna, iar conceptele invatate aici au aplicabilitate directa in contexte variate.

Rolul figurilor si al ilustratiilor

Cartea acorda o atentie speciala figurilor si schemelor explicative.

Acestea nu au doar rol decorativ, ci sprijina intelegerea mecanismelor interne ale algoritmilor si structurilor de date. Sunt prezentate atat diagrame conceptuale – arbori, grafuri, fluxuri logice -, cat si rezultatele grafice obtinute direct din rularea programelor C/C++.

Fiecare imagine este conceputa sa insoteasca textul pas cu pas, pentru ca cititorul sa poata corela imediat teoria cu aplicatia practica. In plus, multe figuri sunt adaptate pentru versiunea alb-negru destinata tiparului, asigurand lizibilitatea indiferent de modul de publicare.

Imi exprim speranta ca aceasta lucrare sa fie, nu doar un instrument util de studiu, ci si o calatorie intelectuala prin universul fascinant al algoritmilor si structurilor de date.

Resurse suplimentare

Pe parcursul lucrarii, cititorul va intalni, alaturi de explicatiile si codurile prezentate, si o serie de linkuri catre materiale externe — fie clipuri video disponibile pe platforma YouTube, fie articole sau alte prezentari scrise. Acestea au fost realizate de autori diferiti si sunt puse la dispozitia publicului tocmai cu scopul de a fi vizionate si utilizate. Includerea lor in aceasta lucrare are un dublu rost: pe de o parte, ele ofera o perspectiva vizuala si ilustrativa, complementara textului; pe de alta parte, constituie un indemn de a explora si alte resurse, dincolo de lucrare, pentru a aprofunda temele discutate.

Perspective si utilizare

Lucrarea a fost gandita astfel incat sa raspunda atat nevoilor de formare academica, cat si celor de auto-instruire.

Fiecare capitol porneste de la notiunile de baza si avanseaza gradual catre aplicatii complexe, astfel incat cititorul sa poata reveni oricand asupra unui subiect, folosind cartea ca pe un manual de curs sau ca pe un ghid de referinta rapida.

Exemplele prezentate nu se limiteaza la ilustrarea unui algoritm, ci urmaresc sa dezvaluie conexiuni intre diferite domenii ale informaticii si matematicii.

Un accent deosebit este pus pe gandirea algoritmica: pe modul de analiza a unei probleme, pe structurarea solutiei si pe verificarea riguroasa a corectitudinii. Intr-o epoca in care mediile de programare evolueaza rapid, aceasta capacitate de a construi rationamente clare si de a evalua alternative ramane cea mai sigura investitie intelectuala.

Lucrarea poate fi utilizata in contexte variate: cursuri universitare de algoritmi si structuri de date, laboratoare de programare in C/C++, pregatirea pentru concursuri sau interviuri tehnice, ori pur si simplu pentru studiu individual.

Bibliografia selectiva de la final indica surse clasice si actuale, utile celor care doresc sa aprofundeze conceptele teoretice sau sa exploreze directii mai avansate.

In loc de incheiere

Multumesc studentilor mei, ale caror intrebari si observatii m-au ajutat sa clarific multe aspecte ale lucrarii si mi-au dat motivatia necesara pentru a duce la sfarsit aceasta lucrare.

Scrierea acestei carti a fost si o calatorie personala, o redescoperire a frumusetii algoritmilor si a bucuriei de a impartasi cunoastere.

Fie ca ea sa inspire cititorul sa abordeze problemele cu rabdare, rigoare si curiozitate, cultivand acea placere a descoperirii care sta la temelia progresului stiintific!

CUPRINS Vol.II

3. STRUCTURI DE DATE 13
3.1 LISTE DUBLU INLANTUITE 15
3.1.1 DEFINITIE SI STRUCTURA 15
3.1.2 AVANTAJE SI UTILIZARI 17
3.1.3 INSERAREA UNUI NOD INTR-O LISTA DUBLU INLANTUITA 17
3.1.4 STERGEREA UNUI NOD DINTR-O LISTA DUBLU INLANTUITA 20
3.1.5 CREAREA LISTEI – APLICATIE PRACTICA 21
3.1.6 INITIALIZAREA LISTEI 22
3.1.7 FUNCTII AUXILIARE 22
3.1.8 APLICATIE INTERDISCIPLINARA 36
3.1.9 CONCLUZII 38
3.2 LISTE SIMPLU INLANTUITE 39
3.2.1 INTRODUCERE 39
3.2.2 DEFINITIE SI STRUCTURA 39
3.2.3 OPERATII FUNDAMENTALE 40
3.2.3.1 CREAREA LISTEI 40
3.2.3.2 AFISAREA LISTEI 40
3.2.3.3 INSERAREA UNUI ELEMENT IN LISTA 41
3.2.3.4 STERGEREA UNUI NOD 42
3.2.3.5 CAUTAREA UNUI ELEMENT 42
3.2.4 APLICATIE PRACTICO-ALGORITMICA 43
3.2.5 CONCLUZII 48
3.3 LISTE CIRCULARE 49
3.3.1 INTRODUCERE SI CONCEPT 49
3.3.2 CREAREA UNEI LISTE CIRCULARE 50
3.3.3 AFISAREA LISTEI CIRCULARE 51
3.3.4 INSERAREA UNUI NOD DUPA UN ELEMENT DAT 51
3.3.5 STERGEREA UNUI NOD CU VALOARE DATA 52
3.3.6 CAUTAREA UNUI ELEMENT 53
3.3.7 PARCURGERE RECURSIVA 53
3.3.8 PROGRAM DEMONSTRATIV 59
3.3.9 RUTINE SUPLIMENTARE RECOMANDATE 66
3.3.10 CONCLUZII 67
3.4 STIVE 68
3.4.1 INTRODUCERE 68
3.4.2 OPERATII FUNDAMENTALE 69
3.4.2.1 ADAUGAREA UNUI ELEMENT (PUSH) 69
3.4.2.2 ELIMINAREA ELEMENTULUI DE LA VARF (POP) 70
3.4.2.3 CONSULTAREA ELEMENTULUI DE LA VARF (PEEK) 71
3.4.2.4 TESTAREA STIVEI GOALE 71
3.4.3 PROGRAM COMPLET PENTRU SIMULAREA OPERATIILOR 72
3.4.4 APLICATII FUNDAMENTALE ALE STIVEI 80
3.4.4.1 AFISAREA UNEI LISTE SIMPLU INLANTUITE IN ORDINE INVERSA FOLOSIND O STIVA 80
3.4.4.2 CONVERSIA INFIX POSTFIX 83
3.4.5 CONCLUZII 90
3.4.6 EXERCITII PROPUSE 91
3.5 COZI 91
3.5.1 INTRODUCERE 91
3.5.2 OPERATII FUNDAMENTALE 93
3.5.3 IMPLEMENTARE CU LISTA SIMPLU INLANTUITA 101
3.5.4 IMPLEMENTARE CU VECTOR (COADA CIRCULARA) 103
3.5.5 PROGRAM COMPLET CU MENIU 106
3.5.6 APLICATII ALGORITMICE PE COZI 112
3.5.7 OBSERVATII SI LEGATURI CU STL 115
3.5.8 CONCLUZII 117
3.5.9 EXERCITII PROPUSE 117
3.6 GRAFURI NEORIENTATE 118
3.6.1 INTRODUCERE 118
3.6.2 NOTIUNI FUNDAMENTALE 120
3.6.3 REPREZENTAREA GRAFURILOR NEORIENTATE 124
3.6.4 PARCURGEREA GRAFURILOR NEORIENTATE 132
3.6.5 EXEMPLE DE RULARE 148
3.6.6 GRAFURI EULERIENE 164
3.6.7 CICLURI HAMILTONIENE 173
3.6.8 APLICATIE – PROBLEMA COMIS-VOIAJORULUI 174
3.6.9 CONCLUZII FINALE – GRAFURI NEORIENTATE 180
3.6.10 PROBLEME PROPUSE 182
3.7 GRAFURI ORIENTATE 183
3.7.1 INTRODUCERE 183
3.7.2 NOTIUNI FUNDAMENTALE 184
3.7.3 PARCURGEREA GRAFURILOR ORIENTATE 187
3.7.3.1 PARCURGEREA IN LATIME (BFS) 187
3.7.3.2 PARCURGEREA IN ADANCIME (DFS) 188
3.7.4 ALGORITMUL ROY-FLOYD 189
3.7.5 ALGORITMUL DIJKSTRA 194
3.7.6 COMPARAREA ALGORITMILOR ROY-FLOYD SI DIJKSTRA 199
3.7.7 DIJKSTRA EXTINS: DRUMURI MINIME DE LA TOATE NODURILE 201
3.7.8 CONCLUZII ASUPRA GRAFURILOR ORIENTATE 205
3.7.9 PROBLEME PROPUSE 206
3.8 ARBORI IN GENERAL 207
3.8.1 INTRODUCERE 207
3.8.2 DEFINITII SI PROPRIETATI GENERALE ALE ARBORILOR 208
3.8.3 REPREZENTARI ALE ARBORILOR 210
3.8.3.1 REPREZENTAREA PRIN MATRICE DE ADIACENTA 210
3.8.3.2 REPREZENTAREA PRIN MATRICEA MUCHIILOR 210
3.8.3.3 REPREZENTAREA PRIN LISTA DE ADIACENTA 211
3.8.3.4 REPREZENTAREA PRIN VECTORUL DE TATI 212
3.8.4 PARCURGEREA ARBORILOR 212
3.8.5 EXEMPLE DE APLICATII PENTRU STRABATEREA ARBORILOR 212
3.8.6 CONCLUZII 223
3.9 ARBORI BINARI 223
3.9.1 INTRODUCERE 223
3.9.2 APLICATII ALE ARBORILOR BINARI 224
3.9.3 STRUCTURA CAPITOLULUI 225
3.9.4 DEFINITIA ARBORELUI BINAR SI EXEMPLE 225
3.9.5 REPREZENTAREA ARBORILOR BINARI 227
3.9.6 PARCURGEREA ARBORILOR BINARI 228
3.9.6.1 PARCURGEREA IN PREORDINE (RSD) 228
3.9.6.2 PARCURGEREA IN INORDINE (SRD) 229
3.9.6.3 PARCURGEREA IN POSTORDINE (SDR) 229
3.9.7 APLICATIE PENTRU STRABATEREA ARBORILOR 232
3.9.8 CONCLUZII 237
3.9.9 EXERCITII PROPUSE 237
3.10 ARBORI DE CAUTARE 237
3.10.1 DEFINITIE SI PROPRIETATI 237
3.10.2 CONSTRUCTIA ARBORILOR DE CAUTARE 240
3.10.3 INSERAREA UNUI ELEMENT 240
3.10.4 CAUTAREA UNUI ELEMENT 240
3.10.5 STERGEREA UNUI ELEMENT 241
3.10.6 PARCURGERILE CLASICE 241
3.10.7 EXEMPLU ILUSTRATIV 242
3.10.8 EXEMPLU APLICAT 250
3.10.9 CONCLUZII 254
3.10.10 PROBLEME PROPUSE 254
3.11 ARBORI AVL 254
3.11.1 DEFINITIE SI PROPRIETATI 254
3.11.2 FACTORUL DE ECHILIBRU 255
3.11.3. ROTATII PENTRU REECHILIBRARE 257
3.11.4 INSERAREA INTR-UN ARBORE AVL 260
3.11.5 STERGEREA INTR-UN ARBORE AVL 263
3.11.6. OBSERVATII, APLICATII SI COMPLEXITATE 266
3.11.7 EXEMPLU COMPLET 278
3.11.8 CONCLUZII 285
3.11.9 PROBLEME PROPUSE 287
3.12 POLINOAME RARE 288
3.12.1 INTRODUCERE 288
3.12.2 REPREZENTAREA UNUI POLINOM RAR PRIN LISTA INLANTUITA 289
3.12.3 ALGORITMUL DE ADUNARE A DOUA POLINOAME RARE 289
3.12.4 PROGRAM C++ COMPLET 290
3.12.5 INMULTIREA A DOUA POLINOAME RARE 295
3.12.6 DERIVAREA UNUI POLINOM RAR 296
3.12.7 EVALUAREA NUMERICA A UNUI POLINOM RAR 296
3.12.8 PROGRAM INTEGRAT 302
3.12.9 CONCLUZII 311
3.13 MATRICE RARE 312
3.13.1 INTRODUCERE 312
3.13.2 REPREZENTARI EFICIENTE 312
3.13.3 STRUCTURA DE DATE UTILIZATA 313
3.13.4 CITIREA DIN FISIERE 313
3.13.5 OPERATII FUNDAMENTALE 314
3.13.5.1 AFISAREA UNEI MATRICE RARE 314
3.13.5.2 TRANSPUNEREA UNEI MATRICE RARE 314
3.13.6 FUNCTII DE BAZA PENTRU MATRICE RARE 315
3.13.6.1 STRUCTURILE TRIPLET SI NOD 315
3.13.6.2 INSERAREA ORDONATA 315
3.13.6.3 AFISAREA SI ELIBERAREA 316
3.13.6.4 CREAREA INTERACTIVA A UNEI MATRICE RARE 316
3.13.7 OPERATII FUNDAMENTALE (REPREZENTARE DINAMICA) 316
3.13.7.1 ADUNAREA A DOUA MATRICE RARE 316
3.13.7.2 TRANSPUNEREA UNEI MATRICE RARE 317
3.13.7.3 STERGEREA UNUI ELEMENT 318
3.13.8 COD IMPLEMENTARE STATICA 318
3.13.9 COD IMPLEMENTARE DINAMICA 320
3.13.10 CONCLUZII SI DIRECTII DE EXTINDERE 329
3.14 ARBORI RED-BLACK 330
3.14.1 DEFINITIE SI CONTEXT 330
3.14.2 PROPRIETATI FUNDAMENTALE 331
3.14.3 INSERAREA INTR-UN ARBORE RED-BLACK 332
3.14.4 IMPLEMENTARE C++ – VERSIUNE DIDACTICA 335
3.14.5 OBSERVATII ASUPRA STERGERII 339
3.14.6 COMPARATIE INTRE ARBORII AVL SI RED-BLACK 340
3.14.7 APLICATII PRACTICE 341
3.14.8 CONCLUZII 343

4. PREZENTARE SINTETICA A STL 345
4.1 CE ESTE STL SI CUM ESTE ORGANIZAT 347
4.2 CONTAINERE SECVENTIALE 348
4.2.1 std::vector 348
4.2.2 std::array 349
4.2.3 std::deque 349
4.2.4 std::list 350
4.3 CONTAINERE ASSOCIATIVE 350
4.3.1 std::set 350
4.3.2 std::multiset 351
4.3.3 std::map 351
4.3.4 std::multimap 351
4.4 CONTAINERE ADAPTATE 352
4.4.1 std::stack – LIFO 352
4.4.2 std::queue – FIFO 352
4.4.3 std::priority_queue 352
4.5 ITERATORI 353
4.6 ALGORITMI STL 353
4.7 RECOMANDARI SI BUNE PRACTICE 354
4.8. CONCLUZII 354
4.9 EXEMPLE COMPARATIVE: REZOLVARI CLASICE VS. STL 354
4.9.1 ELIMINAREA DUPLICATELOR SI AFISAREA ORDONATA 354
4.9.2 FRECVENTA CUVINTELOR DINTR-UN TEXT 360

CONCLUZII GENERALE 369

MOTIVATIA LUCRARII 369

BIBLIOGRAFIE 375

ANEXA LISTA SELECTIVA DE FIGURI 377

ANEXA LISTA DE PROGRAME 381

DESPRE AUTOR

Dan-Stefan Gogoncea este lector universitar doctor inginer la Universitatea Hyperion din Bucuresti, in cadrul Facultatii de Stiinte Exacte si Ingineresti. Activitatea sa didactica si de cercetare este orientata catre domeniile algoritmilor, programarii si structurilor de date, cu accent pe dezvoltarea gandirii algoritmice si pe metode didactice moderne de predare a informaticii.

Cursuri predate in prezent:

– PCPL (Programarea Calculatoarelor si Limbaje de Programare)

– TW (Tehnologii Web)

– TS (Teoria Sistemelor)

– TO (Tehnici de Optimizare)

– SAE (Sisteme Automate cu Esantionare)

– SFRN (Sisteme Fuzzy si Retele Neuronale)

O buna parte din materialele necesare pentru aceste cursuri sunt accesibile pe site-ul https://gogopathfinder.org/, iar cele referitoare la prezenta lucrare la https://gogopathfinder.org/asd

Anterior, a desfasurat activitate de cercetare stiintifica in cadrul Institutul de Cercetari pentru Electrotehnica din Bucuresti (ICPE), unde a ocupat succesiv pozitiile de cercetator stiintific, cercetator stiintific principal si sef al laboratorului „Circuite Logice”. Experienta acumulata in cercetare a fost ulterior valorificata in activitatea universitara.

In mediul academic, a predat la mai multe universitati din Bucuresti si a ocupat, de asemenea, functia de prodecan al Facultatii de Stiinte Exacte si Ingineresti a Universitatea Hyperion din Bucuresti, unde a desfasurat activitati de coordonare academica si de asigurare a calitatii in invatamantul superior.

In paralel cu activitatea universitara, a fost implicat in programe educationale dedicate formarii tinerilor pasionati de informatica, la diverse Cercuri de Informatica.

Lucrarea „Algoritmi C/C++ cu aplicatii in structurile de date” reflecta experienta didactica acumulata in peste trei decenii de activitate universitara si isi propune sa ofere studentilor si celor interesati de programare o introducere clara si sistematica in gandirea algoritmica si in utilizarea limbajelor C si C++.