Structuri de Date

Curs
9/10 (5 voturi)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 152 în total
Cuvinte : 32306
Mărime: 11.00MB (arhivat)
Cost: Gratis

Cuprins

CUPRINS 1

CAPITOLUL 1 Structuri elementare de date 3

1.1 Structuri liniare 3

1.2 Stive 3

1.3 Coada 5

Întrebări şi exerciţii la capitolul 1 8

CAPITOLUL 2. Structuri externe de date 9

Întrebări şi exerciţii la capitolul 2 14

CAPITOLUL 3 Modelul reţea 15

3. 1 Noţiuni de bază şi definiţii 16

3.2.1. Transformnarea unei relaţii n-are 20

3.2.2. Transformarea relaţiilor n la m 20

3.3. Limbajul de definire al datelor (DDL) 21

Întrebări şi exerciţii la capitolul 3 22

CAPITOLUL 4 Modelul ierarhic 23

Întrebări şi exerciţii la capitolul 4 27

CAPITOLUL 5 Modelul relaţional 28

2.1. Scurf istoric al modelului relaţional 28

2.2. Modelul relaţional al datelor 28

2.3 Structura relaţională a datelor 31

Întrebări şi exerciţii la capitolul 5 32

CAPITOLUL 6 Arbori binari 33

Întrebări şi exerciţii la capitolul 6 38

CAPITOLUL7 Cozi de prioritate (cu HEAP). 39

7.1 Operaţii asupra unei cozi de priorităţi 44

Întrebări şi exerciţii la capitolul 7 47

CAPITOLUL 8 Arbori binari de căutare 47

8.1.Ce este un arbore binar de cautare 47

8.2.Operaţii asupra unui arbore binar de căutare 48

Întrebări şi exerciţii la capitolul 8 55

CAPITULUL 9 HASH – TABLES 56

9.1. Tabele cu adresare directă 56

9.2. Tabele de repartizare (hash-tables) 58

9.3. Funcţii de repartizare (hash funcţii) 61

9.4.Adresarea deschisă 63

Întrebări şi exerciţii la capitolul 9 67

10. Arbori balansaţi (B-Trees) 68

10.1 Structura datelor în memoria pe disc 68

10.2. Definiţia arborilor balansaţi. 69

10.3 Operaţii în arbori balansaţi 71

Întrebări şi exerciţii la capitolul 10 77

CAPITOLUL 11. Arbori roşu-negri 78

11.1.Proprietăţle arborilor roşu-negri 78

11.2.Rotaţii 79

11.3.Inserarea 81

11.4 Ştergerea 83

Întrebări şi exerciţii la capitolul 11 85

CAPITOLUL 12 Îmbogăţirea structurilor de date 86

Întrebări şi exerciţii la capitolul 12 94

Capitolul 13 Heap-uri binomiale şi Fibonacci 95

13.1 Despre necesitatea unor altfel de structuri 95

13.2 Heap-uri binomiale 98

13.3 Arbori binomiali 99

13.4 Operaţii pe heap-uri binomiale 103

13.3 Heap-uri Fibonacci 113

13.4 Metoda de potenţial 115

13.5 Operaţii cu heap-uri interclasabile 117

13.6 Mărginirea gradului maxim 130

Rezolvarea unor probleme dintre cele propuse 133

BIBLIOGRAFIE 143

Extras din document

CAPITOLUL 1 Structuri elementare de date.

În capitolul 1, introductiv, recapitulăm câteva din noţiunile introduse la ‘algoritmică’ şi anume:

- structuri liniare vectori, matrici, stive, cozi

- alocarea stucturilor liniare

- secvenţială

- înlănţuită

Am folosit, până acum structuri foarte simple de date cum ar fi :

- variabile simple (dintre care unele aveau domeniul de valori formate doar din două valori).

- vectori cu componentele sortate sau nesortate (aşa cum sunt folosiţi în matematică).

- matrici considerate ca vectori de vectori sau ca masive biortogonale.

Vom studia acum alte structuri ceva mai complicate.

1.1 Structuri liniare.

O structură liniară este o mulţime de n  0 componente x(1),x(2),…,x(n) cu proprietăţile:

a) Cand n=0 spunem ca structura este vidă.

b) Daca n > 0 atunci x(1) este primul element iar x(n) este ultimul element.

c) Oricare ar fi x(k) unde k{2,…,n-1} există un predecesor x(k-1) şi un succesor x(k+1).

Ne va interesa să executăm cu aceste structuri urmatoarele operaţii:

-adăugarea unui element

-extragerea unui element

-accesarea unui element x(k) din structură

-combinarea a două sau mai multe structuri într-una singură

-“ ruperea “ unei structuri ăn mai multe structuri

-sortarea elementelor unei structuri

-căutarea unui element al structurii care are anumite proprietăţi etc…

1.2 Stive.

Una din cele mai folosite structuri liniare este stiva.O stivă este caracterizată de disciplina de intrare şi ieşire din stivă.

Să considerăm o mulţime de cărţi puse una peste alta ; există o primă carte care se poate lua foarte şor (TOP) şi o carte care se poate lua numai dacă deplasez toate celelalte carţi (BOTTOM).

Disciplina unei stive este “ ultimul intrat - primul ieşit “ (disciplină care nu v-ar place să fie respectată când staţi la rând la lapte ! ) ( Last in, first out - prescurtarea acestei reguli este LIFO).

Care ar fi diferenţele fată de un vector :

-un vector are o lungime fixă, non zero cunoscută aprioric

-o stivă poate fi vidă

-stiva are un numar variabil de elemente în timpul execuţiei unui algoritm

Se pune problema reprezentării concrete a unei stive în memoria unui calculator. Putem aloca o stivă în două moduri :

I ) Secvenţial

II ) Înlănţuit

I ) Alocarea secvenţială a stivei.

Folosim vectorul ca fiind structura cea mai apropiată de structura reală a memoriei. În vectorul (x (i) ) i=1,n

| x(1) | x(2) | x(3) | … | x(k) | … | x(n) |

Bottom Top

-din n componente ale unui vector doar ‘k’ elemente fac parte din stivă.

Algoritmul de intrare în stivă va fi :

a STIVA

Daca k = n atunci DEPASIRE

altfel

k = k + 1

x(k) = a

Sdaca

Return

Algoritmul de ieşire din stivă va fi :

aSTIVA

Daca k = 0 atunci STIVA VIDA

altfel

a = x( k )

- k = k – 1

Sdaca

Return

II ) Alocarea înlanţuită a stivei

În alocarea înlănţuită fiecare element al structurii este însoţit de adresa la care se afla precedentul element. Vom avea vârful pus în evidenţă (ancorat) în INC şi un semn special “” în loc de adresa bazei ca în figura următoare :

| INFO | LEG |

INC | || x(k) | ||x(k-1) | |…|x(2) | ||x(1) |  |

(Ordinea 1,2,…,k este ordinea intrării în stivă).

În acest caz intrarea în stivă va folosi stiva de locuri libere (această stivă se numeşte LIBERE) pentru a obţine locuri la introducerea în stivă.

Preview document

Structuri de Date - Pagina 1
Structuri de Date - Pagina 2
Structuri de Date - Pagina 3
Structuri de Date - Pagina 4
Structuri de Date - Pagina 5
Structuri de Date - Pagina 6
Structuri de Date - Pagina 7
Structuri de Date - Pagina 8
Structuri de Date - Pagina 9
Structuri de Date - Pagina 10
Structuri de Date - Pagina 11
Structuri de Date - Pagina 12
Structuri de Date - Pagina 13
Structuri de Date - Pagina 14
Structuri de Date - Pagina 15
Structuri de Date - Pagina 16
Structuri de Date - Pagina 17
Structuri de Date - Pagina 18
Structuri de Date - Pagina 19
Structuri de Date - Pagina 20
Structuri de Date - Pagina 21
Structuri de Date - Pagina 22
Structuri de Date - Pagina 23
Structuri de Date - Pagina 24
Structuri de Date - Pagina 25
Structuri de Date - Pagina 26
Structuri de Date - Pagina 27
Structuri de Date - Pagina 28
Structuri de Date - Pagina 29
Structuri de Date - Pagina 30
Structuri de Date - Pagina 31
Structuri de Date - Pagina 32
Structuri de Date - Pagina 33
Structuri de Date - Pagina 34
Structuri de Date - Pagina 35
Structuri de Date - Pagina 36
Structuri de Date - Pagina 37
Structuri de Date - Pagina 38
Structuri de Date - Pagina 39
Structuri de Date - Pagina 40
Structuri de Date - Pagina 41
Structuri de Date - Pagina 42
Structuri de Date - Pagina 43
Structuri de Date - Pagina 44
Structuri de Date - Pagina 45
Structuri de Date - Pagina 46
Structuri de Date - Pagina 47
Structuri de Date - Pagina 48
Structuri de Date - Pagina 49
Structuri de Date - Pagina 50
Structuri de Date - Pagina 51
Structuri de Date - Pagina 52
Structuri de Date - Pagina 53
Structuri de Date - Pagina 54
Structuri de Date - Pagina 55
Structuri de Date - Pagina 56
Structuri de Date - Pagina 57
Structuri de Date - Pagina 58
Structuri de Date - Pagina 59
Structuri de Date - Pagina 60
Structuri de Date - Pagina 61
Structuri de Date - Pagina 62
Structuri de Date - Pagina 63
Structuri de Date - Pagina 64
Structuri de Date - Pagina 65
Structuri de Date - Pagina 66
Structuri de Date - Pagina 67
Structuri de Date - Pagina 68
Structuri de Date - Pagina 69
Structuri de Date - Pagina 70
Structuri de Date - Pagina 71
Structuri de Date - Pagina 72
Structuri de Date - Pagina 73
Structuri de Date - Pagina 74
Structuri de Date - Pagina 75
Structuri de Date - Pagina 76
Structuri de Date - Pagina 77
Structuri de Date - Pagina 78
Structuri de Date - Pagina 79
Structuri de Date - Pagina 80
Structuri de Date - Pagina 81
Structuri de Date - Pagina 82
Structuri de Date - Pagina 83
Structuri de Date - Pagina 84
Structuri de Date - Pagina 85
Structuri de Date - Pagina 86
Structuri de Date - Pagina 87
Structuri de Date - Pagina 88
Structuri de Date - Pagina 89
Structuri de Date - Pagina 90
Structuri de Date - Pagina 91
Structuri de Date - Pagina 92
Structuri de Date - Pagina 93
Structuri de Date - Pagina 94
Structuri de Date - Pagina 95
Structuri de Date - Pagina 96
Structuri de Date - Pagina 97
Structuri de Date - Pagina 98
Structuri de Date - Pagina 99
Structuri de Date - Pagina 100
Structuri de Date - Pagina 101
Structuri de Date - Pagina 102
Structuri de Date - Pagina 103
Structuri de Date - Pagina 104
Structuri de Date - Pagina 105
Structuri de Date - Pagina 106
Structuri de Date - Pagina 107
Structuri de Date - Pagina 108
Structuri de Date - Pagina 109
Structuri de Date - Pagina 110
Structuri de Date - Pagina 111
Structuri de Date - Pagina 112
Structuri de Date - Pagina 113
Structuri de Date - Pagina 114
Structuri de Date - Pagina 115
Structuri de Date - Pagina 116
Structuri de Date - Pagina 117
Structuri de Date - Pagina 118
Structuri de Date - Pagina 119
Structuri de Date - Pagina 120
Structuri de Date - Pagina 121
Structuri de Date - Pagina 122
Structuri de Date - Pagina 123
Structuri de Date - Pagina 124
Structuri de Date - Pagina 125
Structuri de Date - Pagina 126
Structuri de Date - Pagina 127
Structuri de Date - Pagina 128
Structuri de Date - Pagina 129
Structuri de Date - Pagina 130
Structuri de Date - Pagina 131
Structuri de Date - Pagina 132
Structuri de Date - Pagina 133
Structuri de Date - Pagina 134
Structuri de Date - Pagina 135
Structuri de Date - Pagina 136
Structuri de Date - Pagina 137
Structuri de Date - Pagina 138
Structuri de Date - Pagina 139
Structuri de Date - Pagina 140
Structuri de Date - Pagina 141
Structuri de Date - Pagina 142
Structuri de Date - Pagina 143
Structuri de Date - Pagina 144
Structuri de Date - Pagina 145
Structuri de Date - Pagina 146
Structuri de Date - Pagina 147
Structuri de Date - Pagina 148
Structuri de Date - Pagina 149
Structuri de Date - Pagina 150
Structuri de Date - Pagina 151
Structuri de Date - Pagina 152

Conținut arhivă zip

  • Structuri de Date.doc

Alții au mai descărcat și

Proiectarea unei Solutii de Comert Electronic

Comertul electronic reprezinta multitudinea proceselor software si comerciale necesare proceselor business sa functioneze numai, sau în primul...

Tehnici de Programare

PREZENTARE GENERALE In proiectul urmator am creat o baza de date cu referire la un hotel (ANGELA). Baza de date este impartita in doua fisiere:...

Proiect Structuri de Date - Orar

1. INTRODUCERE 1.1 Obiectivul problemei : Aceasta aplicatie informatica are ca obiectiv gestionarea cat mai buna a orarului unei facultati pentru...

Sabloane de Proiectare a Interfetelor Utilizator pentru Aplicatii Web

Capitolul 1 Introducere Lucrarea prezinta sabloanele de proiectare , ce sunt acestea si cum ne ajuta ele in rezolvarea problemelor de proiectare...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Clasa Matrice si Principalele Functionalitati Necesare pentru Lucrul cu Matrici

Tema II - Problema I Cerinte minimale: Sa se implementeze o clasa Matrice si principalele functionalitati necesare pentru lucrul cu matrici. Sa...

Proiectarea Algoritmilor

1. INTRODUCERE ÎN PROIECTAREA ALGORITMILOR 1.1. Definiţii Un algoritm este o metodă de rezolvare pas cu pas a problemelor. O problemă este...

Ai nevoie de altceva?