Structuri de Date

Imagine preview
(8/10 din 4 voturi)

Acest curs prezinta Structuri de Date.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier doc de 152 de pagini .

Iti recomandam sa te uiti bine pe extras, cuprins si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Calculatoare

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ă.

Fisiere in arhiva (1):

  • Structuri de Date.doc