Colectii de date

In dezvoltarea aplicatiilor de programare pot fi puse in evidenta un numar limitat de entitati (liste, stive, cozi, cozi cu prioritati, arbori binari, tabele de dispersie, grafuri), caracterizate printr-o stare si un comportament specific. Acestea sunt cunoscute sub numele de tipuri de date abstracte sau colectii de date si contin un numar finit de elemente, de orice tip. Lucrarea isi propune sa evidentieze principalele colectii, care apar in aplicatii, sa specifice si sa implementeze operatiile caracteristice acestora si structurile de date corespunzatoare, utilizand in acest scop un limbaj de programare structurata, fara facilitati de programare orientata pe obiecte, constituind o baza pentru proiectarea unei biblioteci de tipuri de date abstracte. Lecturarea lucrarii incurajeaza utilizatorii sa-si scrie propriile aplicatii cu colectii de date, folosind serviciile oferite de o interfata, care ascunde detaliile structurilor de date folosite si operatiile specifice diferitelor colectii de date. Ne adresam atat studentilor facultatilor cu profil informatic, profesorilor care predau discipline informatice si elevilor acestora, dar si tuturor celor interesati sa-si dezvolte propriile aplicatii cu structuri de date.





1.  Colectii de date

1. 1. Operatii specifice colectiilor

1. 2. Exemple de colectii de date

1. 3. Parcurgerea colectiilor

1. 4. Criterii de clasificare a colectiilor

1. 5. Criterii de alegere a colectiilor

1. 6. Tipuri abstracte de date

1. 6. 1. Specificarea Tipurilor Abstracte de Date

1. 6. 2. Implementarea Tipurilor Abstracte de Date

1. 6. 3. Contractul client – furnizor

1. 6. 4. Criterii de proiectare ale interfetelor TAD

1. 6. 5. Eficienta utilizarii structurilor de date

1. 7. Compilare separata

1. 7. 1. Utilitarul make

1. 8. Complexitatea algoritmilor

1. 8. 1. Notatii asimptotice

 

2.  Stive

2. 1. Specificarea TAD Stiva

2. 2. Interfata TAD Stiva

2. 3. Aplicatii cu stive

2. 4. Implementarea stivelor

2. 4. 1. Implementare cu tablouri

2. 4. 2. Implementare cu liste inlantuite

2. 5. Probleme propuse

 

3.  Cozi

3. 1. Specificarea TAD Coada

3. 2. Operatii cu cozi

3. 3. Interfata TAD Coada

3. 4. Aplicatii cu cozi

3. 5. Implementarea cozilor

3. 5. 1. Implementare cu tablou circular

3. 5. 2. Implementare cu liste inlantuite

3. 6. Probleme propuse

4.  Liste

4. 1. Generalitati

4. 2. Operatii specifice listelor

4. 3. Specificarea TAD Lista

4. 4. Interfata TAD Lista

4. 5. Aplicatii cu liste

4. 6. Implementarea listelor

4. 6. 1. Implementare cu tablouri

4. 6. 2. Implementare cu liste dublu inlantuite

4. 7. Probleme propuse

 

5.  Arbori binari

5. 1. Definitii si generalitati

5. 2. Operatii specifice TAD Arbore Binar

5. 3. Traversarea arborilor binari si aplicatii ale traversarilor

5. 3. 1. Traversarea in preordine

5. 3. 2. Traversarea in postordine

5. 3. 3. Traversarea in inordine

5. 3. 4. Traversarea in latime

5. 4. Implementarea arborilor binari

5. 5. Probleme propuse

 

6.  Arbori generali (multicai)

6. 1. Interfata TAD Arbore General

6. 2. Transformarea unui arbore general intr-un arbore binar

6. 3. Implementarea arborilor generali

6. 3. 1. Prin tabel de cursori la predecesori

6. 3. 2. Cu tablouri, prin liste de adiacente

6. 3. 3. Prin tablourile PrimFiu si UrmatorFrate

6. 3. 4. Cu pointeri, cu lista de succesori si pointer la predecesor

6. 4. Traversarea arborilor generali

 

7.  Arbori de cautare

7. 1. Arbori binari de cautare

7. 1. 1. Definitii si generalitati

7. 1. 2. Operatii specifice TAD Arbore Binar de Cautare

7. 1. 2. 1. Cautarea unei chei

7. 1. 2. 2. Inserarea unui nod

7. 1. 2. 3. Cheia maxima dintr-un arbore binar de cautare

7. 1. 2. 4. Succesorul si predecesorul unui nod

7. 1. 2. 5. Stergerea unui nod

7. 2. Arbori echilibrati

7. 2. 1. Rotatii in arbori binari de cautare

7. 2. 2. Arbori AVL

7. 2. 2. 1. Definitii si generalitati

7. 2. 2. 2. Calculul factorului de echilibrare pentru o rotatie simpla

7. 2. 2. 3. Inserarea unui nod intr-un arbore AVL

7. 2. 3. Arbori bicolori (rosii-negri)

7. 2. 3. 1. Definitii si generalitati

7. 2. 3. 2. Functii suplimentare pentru arbori bicolori

7. 2. 3. 3. Inserarea unui nod intr-un arbore bicolor

7. 2. 3. 4. Stergerea unui nod dintr-un arbore bicolor

7. 2. 4. Structuri de date pentru memoria externa

7. 2. 4. 1. Arbori 2-3

7. 2. 4. 1. 1. Inserarea unei chei intr-un arbore 2-3

7. 2. 4. 2. 2. Stergerea unei chei dintr-un arbore 2-3

7. 2. 4. 2. Arbori B

7. 2. 4. 2. 1. Creerea unui arbore B

7. 2. 4. 2. 2. Cautarea unei chei intr-un arbore B

7. 2. 4. 2. 3. Inserarea unei chei intr-un arbore B

7. 2. 4. 2. 4. Variante de arbori B

7. 3. Probleme propuse

 

8.  Cozi prioritare

8. 1. Specificarea TAD Coada Prioritara

8. 2. Interfata TAD Coada Prioritara

8. 3. Exemple

8. 4. Arbori partial ordonati (heapuri binare)

8. 4. 1. Definitii si terminologie

8. 4. 2. Transformarea unui tablou intr-un heap

8. 4. 3. Sortare prin metoda heapurilor (heapsort)

8. 4. 4. Implementarea cozilor cu prioritati folosind heapuri binare

8. 4. 5.  Aplicatii ale cozilor prioritare

8. 5. Probleme propuse

 

9.  Tabele de dispersie

9. 1. Definitii si terminologie

9. 2. Functii de dispersie

9. 3. Strategii de rezolvare a coliziunilor

9. 3. 1. Dispersie deschisa

9. 3. 1. 1. Interfata dispersie deschisa

9. 3. 1. 2. Implementare dispersie deschisa

9. 3. 2. Dispersie inchisa

9. 3. 2. 1. Verificare liniara

9. 3. 2. 2. Verificare patratica

9. 3. 2. 3. Dispersie dubla

9. 3. 2. 4. Interfata dispersie inchisa

9. 3. 2. 5. Implementare dispersie inchisa

9. 3. 2. 6. Redispersare

9. 4. Eficienta operatiilor in tabelele de dispersie

9. 5. Probleme propuse

 

10.  Grafuri

10. 1. Elemente de teoria grafurilor: definitii si terminologie

10. 2. Operatii asociate varfurilor

10. 3. Operatii asociate arcelor

10. 4. TAD Graf

10. 5. Iterarea varfurilor si arcelor grafului

10. 6. Implementarea operatiilor independente de reprezentarea grafului

10. 7. Implementarea grafurilor cu matrice de adiacente

10. 8. Reprezentarea grafurilor prin liste de adiacente

10. 9. Implementarea iteratorilor

10. 10. Metode de explorare a grafurilor

10. 10. 1. Traversarea in adancime a unui graf

10. 10. 2. Traversarea in latime a unui graf

10. 11. Sortare topologica

10. 12. Determinarea componentelor tare conexe

10. 13. Colectii de multimi disjuncte

10. 14. Determinarea arborelui de acoperire de cost minim

10. 14. 1. Algoritmul Kruskal

10. 14. 2. Algoritmul Prim

10. 15. Algoritmi pentru drumuri minime in grafuri

10. 15. 1. Algoritmul Dijkstra

10. 15. 2. Algoritmul Bellman-Ford

10. 15. 3. Drumuri minime intre toate perechile de varfuri

10. 16. Probleme propuse



Anul aparitiei: 2012
Nr. pagini: 244