cuprins - .pascal sau “structurã” în c a permis definirea unor noi tipuri de date de cãtre

Download CUPRINS - .Pascal sau “structurã” în C a permis definirea unor noi tipuri de date de cãtre

Post on 16-Jun-2018

223 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • Florian Moraru: Structuri de Date ------------------------------------------------------------------------- 1

    CUPRINS

    1. STRUCTURI DE DATE SI TIPURI DE DATE ABSTRACTE

    1.1 Structuri de date fundamentale ....................................................... 3 1.2 Clasificri ale structurilor de date ................................................... 3 1.3 Tipuri abstracte de date ..................................................................... 4 1.4 Eficienta structurilor de date ............................................................. 6

    2. STRUCTURI DE DATE N LIMBAJUL C

    2.1 Implementarea operatiilor cu structuri de date 9 2.2 Utilizarea de tipuri generice .. 11 2.3 Utilizarea de pointeri generici 13 2.4 Structuri si functii recursive 16

    3. VECTORI

    3.1 Vectori 24

    3.2 Vectori ordonati . 25

    3.3 Vectori alocati dinamic .. 27

    3.4 Aplicatie: Componente conexe .. 29

    3.5 Vectori multidimensionali 31

    3.6 Vectori de biti 32

    4. LISTE CU LEGTURI

    4.1 Liste nlntuite .. 35

    4.2 Colectii de liste . 39

    4.3 Liste nlntuite ordonate 42

    4.4 Variante de liste nlntuite . 44

    4.5 Liste dublu-nlntuite . 47

    4.6 Comparatie ntre vectori si liste 48

    4.7 Combinatii de liste si vectori . 51

    4.8 Tipul abstract list (secvent) .. . 54

    4.9 Liste Skip ... 56

    4.10 Liste neliniare .. 59

    5. MULTIMI SI DICTIONARE

    5.1 Tipul abstract Multime 62

    5.2 Aplicatie: Acoperire optim cu multimi . 63

    5.3 Tipul Colectie de multimi disjuncte 64

    5.4 Tipul abstract Dictionar .. 66

    5.5 Implementare dictionar prin tabel de dispersie .. 68

    5.6 Aplicatie: Compresia LZW 71

    6. STIVE SI COZI

    6.1 Liste stiv .. .75

    6.2 Aplicatie: Evaluare expresii . .. 77

    6.3 Eliminarea recursivittii folosind o stiv . .. 82

    6.4 Liste coad ..84

    6.5 Tipul Coad cu prioritti . . . 89

    6.6 Vectori heap . . 91

  • ------------------------------------------------------------------------- Florian Moraru: Structuri de Date 2

    7. ARBORI

    7.1 Structuri arborescente . . 96 7.2 Arbori binari neordonati .. . 97

    7.3 Traversarea arborilor binari 99

    7.4 Arbori binari pentru expresii 104

    7.5 Arbori Huffman .. 106

    7.6 Arbori multici 110

    7.7 Alte structuri de arbore .. 115

    8. ARBORI DE CAUTARE

    8.1 Arbori binari de cutare .. 121

    8.2 Arbori binari echilibrati .. 124

    8.3 Arbori Splay si Treap . 127

    8.4 Arbori AVL 131

    8.5 Arbori RB si AA 136

    8.6 Arbori 2-3 ... 138

    9. STRUCTURI DE GRAF

    9.1 Grafuri ca structuri de date . 142

    9.2 Reprezentarea grafurilor prin alte structuri 143

    9.3 Metode de explorare a grafurilor 147

    9.4 Sortare topologic .. 150

    9.5 Aplicatii ale explorrii n adncime .. 152

    9.6 Drumuri minime n grafuri 157

    9.7 Arbori de acoperire de cost minim. 160

    9.8 Grafuri virtuale .. 164

    10. STRUCTURI DE DATE EXTERNE

    10.1 Specificul datelor pe suport extern .. 170

    10.2 Sortare extern 171

    10.3 Indexarea datelor 172

    10.4 Arbori B . 173

    11. STRUCTURI DE DATE N LIMBAJUL C++

    11.1 Avantajele utilizrii limbajului C++ .. 179

    11.2 Clase si obiecte n C++ .. 180

    11.3 Clase sablon (template) n C++ .. 186

    11.4 Clase container din biblioteca STL 189

    11.5 Utilizarea claselor STL n aplicatii . 192

    11.6 Definirea de noi clase container .. 194

  • Florian Moraru: Structuri de Date ------------------------------------------------------------------------- 3

    Capitolul 1

    STRUCTURI DE DATE SI TIPURI DE DATE ABSTRACTE

    1.1 STRUCTURI DE DATE FUNDAMENTALE

    Gruparea unor date sub un singur nume a fost necesar nc de la nceputurile programrii

    calculatoarelor. Prima structur de date folosit a fost structura de vector (tabel), utilizat n operatiile

    de sortare (de ordonare) a colectiilor si prezent n primele limbaje de programare pentru aplicatii

    numerice (Fortran si Basic).

    Un vector este o colectie de date de acelasi tip, n care elementele colectiei sunt identificate prin

    indici ce reprezint pozitia relativ a fiecrui element n vector.

    La nceput se puteau declara si utiliza numai vectori cu dimensiuni fixe, stabilite la scrierea

    programului si care nu mai puteau fi modificate la executie.

    Introducerea tipurilor pointer si alocrii dinamice de memorie n limbajele Pascal si C a permis

    utilizarea de vectori cu dimensiuni stabilite si/sau modificate n cursul executiei programelor.

    Gruparea mai multor date, de tipuri diferite, ntr-o singur entitate, numit articol (record) n

    Pascal sau structur n C a permis definirea unor noi tipuri de date de ctre programatori si

    utilizarea unor date dispersate n memorie, dar legate prin pointeri : liste nlntuite, arbori si altele.

    Astfel de colectii se pot extinde dinamic pe msura necesittilor si permit un timp mai scurt pentru

    anumite operatii, cum ar fi operatia de eliminare a unei valori dintr-o colectie.

    Limbajul C asigur structurile de date fundamentale (vectori, pointeri, structuri ) si posibilitatea

    combinrii acestora n noi tipuri de date, care pot primi si nume sugestive prin declaratia typedef .

    Dintr-o perspectiv independent de limbajele de programare se pot considera ca structuri de date

    fundamentale vectorii, listele nlntuite si arborii, fiecare cu diferite variante de implementare. Alte

    structuri de date se pot reprezenta prin combinatii de vectori, liste nlntuite si arbori. De exemplu, un

    tabel de dispersie (Hash table) este realizat de obicei ca un vector de pointeri la liste nlntuite (liste

    de elemente sinonime). Un graf se reprezint deseori printr-un vector de pointeri la liste nlntuite

    (liste de adiacente), sau printr-o matrice (un vector de vectori n C).

    1.2 CLASIFICRI ALE STRUCTURILOR DE DATE

    O structur de date este caracterizat prin relatiile dintre elementele colectiei si prin operatiile

    posibile cu aceast colectie. Literatura de specialitate actual identific mai multe feluri de colectii

    (structuri de date), care pot fi clasificate dup cteva criterii.

    Un criteriu de clasificare foloseste relatiile dintre elementele colectiei:

    - Colectii liniare (secvente, liste), n care fiecare element are un singur succesor si un singur

    predecesor;

    - Colectii arborescente (ierarhice), n care un element poate avea mai multi succesori (fii), dar un

    singur predecesor (printe);

    - Colectii neliniare generale, n care relatiile dintre elemente au forma unui graf general (un element

    poate avea mai multi succesori si mai multi predecesori).

    Un alt criteriu grupeaz diferitele colectii dup rolul pe care l au n aplicatii si dup operatiile

    asociate colectiei, indiferent de reprezentarea n memorie, folosind notiunea de tip abstract de date:

    - Structuri de cutare (multimi si dictionare abstracte);

    - Structuri de pstrare temporar a datelor (containere, liste, stive, cozi s.a.)

    Un alt criteriu poate fi modul de reprezentare a relatiilor dintre elementele colectiei:

    - Implicit, prin dispunerea lor n memorie (vectori de valori, vectori de biti, heap);

    - Explicit, prin adrese de legtur (pointeri).

    Dup numrul de aplicatii n care se folosesc putem distinge ntre:

    - Structuri de date de uz general ;

    - Structuri de date specializate pentru anumite aplicatii (geometrice, cu imagini).

  • ------------------------------------------------------------------------- Florian Moraru: Structuri de Date 4

    Organizarea datelor pe suport extern ( a fisierelor si bazelor de date) prezint asemnri dar si

    diferente fat de organizarea datelor n memoria intern, datorit particularittilor de acces la discuri

    fat de accesul la memoria intern.

    Un fisier secvential corespunde oarecum unui vector, un fisier de proprietti este n fond un

    dictionar si astfel de paralele pot continua. Pe suport extern nu se folosesc pointeri, dar se pot folosi

    adrese relative n fisiere (ca numr de octeti fat de nceputul fisierului), ca n cazul fisierelor index.

    Ideea unor date dispersate dar legate prin pointeri, folosit la liste si arbori, se foloseste mai rar

    pentru fisiere disc pentru c ar necesita acces la articole neadiacente (dispersate n fisier), operatii care

    consum timp pe suport extern. Totusi, anumite structuri arborescente se folosesc si pe disc, dar ele

    tin seama de specificul suportului: arborii B sunt arbori echilibrati cu un numr mic de noduri si cu

    numr mare de date n fiecare nod, astfel ca s se fac ct mai putine citiri de pe disc.

    Salvarea unor structuri de date interne cu pointeri ntr-un fisier disc se numeste serializare, pentru

    c n fisier se scriu numai date (ntr-o ordine prestabilit), nu si pointeri (care au valabilitate numai pe

    durata executiei unui program). La ncrcarea n memorie a datelor din fisier se poate reconstrui o

    structur cu pointeri (n general alti pointeri la o alt executie a unui program ce foloseste aceste date).

    Tot pe suport extern se practic si memorarea unor colectii de date fr o structur intern (date

    nestructurate), cum ar fi unele fisiere multimedia, mesaje transmise prin e-mail, documente, rapoarte

    s.a. Astfel de fisiere se citesc integral si secvential, fr a necesita operatii