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 curs
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 :
aSTIVA
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
Conținut arhivă zip
- Structuri de Date.doc
Alții au mai descărcat și
Comertul electronic reprezinta multitudinea proceselor software si comerciale necesare proceselor business sa functioneze numai, sau în primul...
Capitolul 1 Introducere Lucrarea prezinta sabloanele de proiectare , ce sunt acestea si cum ne ajuta ele in rezolvarea problemelor de proiectare...
Tema II - Problema I Cerinte minimale: Sa se implementeze o clasa Matrice si principalele functionalitati necesare pentru lucrul cu matrici. Sa...
Arbori binari de cautare 1. Definiţii Un arbore este un graf orientat in care nu exista nici un ciclu(graf orientat aciclic) Un arbore binar...
Modulul 0. Alocare dinamica in limbajul C Capitolul 0. Pointeri si alocare dinamica. Tipul de date struct 0.1 Pointeri si alocare dinamica O...
1. Conceptul de dată În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine...
CURS 1. - STRUCTURI DE DATE Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii....
1.1 Scopul cursului Cursul se adreseaza angajatilor care au un nivel elementar de cunostinte Excel, pentru a ajunge la nivelul mediu pentru ca mai...
Te-ar putea interesa și
INTRODUCERE “Criza este cea mai binecuvântată situaţie care poate apăre pentru ţări şi persoane, pentru că ea atrage după sine progrese. Cine...
1. INTRODUCERE: • Obiectiv: Realizarea functiilor pentru diferite tipuri de transformari in structuri de date predefinite: vectori, matrici,...
Introducere În era pe care o trăim, era tehnologiilor informaţionale, informaţia este o componentă esenţială în desfăşurarea oricărei activităţi....
CONTROLUL COMPUTERIZAT AL CONTURILOR BANCARE 1. Introducere: Obiectivul proiectului este acela de a permite utilizatorului de a gestiona...
1. Introducere Proiectul constă în realizarea unui program care are ca scop gestiunea unui magazin de vinuri, în vederea regăsirii...
Capitolul I Sistem Informaţional – Sistem Informatic I.1. Sistemul Informaţional. Un sistem poate fi privit ca un ansamblu de elemente...
CAP. STRUCTURI DE DATE Structura de date este o notiune abstracta, caracterizata prin operatiile care se executa asupra ei, in timp ce tipul de...
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...