Colectii de date

Colectii de date - Valeriu Iorga ...in dezvoltarea aplicatiilor de programare pot fi puse în evidentã un numãr limitat de entitãti (liste, stive, cozi, cozi cu prioritãti, 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 numãr finit de elemente, de orice tip. ... cartea de fata îsi propune sã evidentieze principalele colectii, care apar în aplicatii, sã specifice si sã implementeze operatiile caracteristice acestora si structurile de date corespunzãtoare, utilizând în acest scop un limbaj de programare structuratã, fãrã facilitãti de programare orientatã pe obiecte, constituind o bazã pentru proiectarea unei biblioteci de tipuri de date abstracte. Lecturarea lucrãrii încurajeazã utilizatorii sã-si scrie propriile aplicatii cu colectii de date, folosind serviciile oferite de o interfatã, care ascunde detaliile structurilor de date folosite si operatiile specifice diferitelor colectii de date. Ne adresãm atât studentilor facultãtilor cu profil informatic, profesorilor care predau discipline informatice si elevilor acestora, dar si tuturor celor interesati sã-si dezvolte propriile aplicatii cu structuri de date. CUPRINS: 1. COLECŢII DE DATE 1.1. Operaţii specifice colecţiilor 1.2. Exemple de colecţii de date 1.3. Parcurgerea colecţiilor 1.4. Criterii de clasificare a colecţiilor 1.5. Criterii de alegere a colecţiilor 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 interfeţelor TAD 1.6.5. Eficienţa utilizării structurilor de date 1.7. Compilare separată 1.7.1. Utilitarul make 1.8. Complexitatea algoritmilor 1.8.1. Notaţii asimptotice 2. STIVE 2.1. Specificarea TAD Stivă 2.2. Interfaţa TAD Stivă 2.3. Aplicaţii cu stive 2.4. Implementarea stivelor 2.4.1. Implementare cu tablouri 2.4.2. Implementare cu liste înlănţuite 2.5. Probleme propuse 3. COZI 3.1. Specificarea TAD Coadă 3.2. Operaţii cu cozi 3.3. Interfaţa TAD Coadă 3.4. Aplicaţii cu cozi 3.5. Implementarea cozilor 3.5.1. Implementare cu tablou circular 3.5.2. Implementare cu liste înlănţuite 3.6. Probleme propuse 4. LISTE 4.1. Generalităţi 4.2. Operaţii specifice listelor 4.3. Specificarea TAD Listă 4.4. Interfaţa TAD Listă 4.5. Aplicaţii cu liste 4.6. Implementarea listelor 4.6.1. Implementare cu tablouri 4.6.2. Implementare cu liste dublu înlănţuite 4.7. Probleme propuse 5. ARBORI BINARI 5.1. Definiţii şi generalităţi 5.2. Operaţii specifice TAD Arbore Binar 5.3. Traversarea arborilor binari şi aplicaţii ale traversărilor 5.3.1. Traversarea în preordine 5.3.2. Traversarea în postordine 5.3.3. Traversarea în inordine 5.3.4. Traversarea în lăţime 5.4. Implementarea arborilor binari 5.5. Probleme propuse 6. ARBORI GENERALI (MULTICĂI) 6.1. Interfaţa TAD Arbore General 6.2. Transformarea unui arbore general într-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 adiacenţe 6.3.3. Prin tablourile PrimFiu şi UrmătorFrate 6.3.4. Cu pointeri, cu listă de succesori şi pointer la predecesor 6.4. Traversarea arborilor generali 7. ARBORI DE CĂUTARE 7.1. Arbori binari de căutare 7.1.1. Definiţii şi generalităţi 7.1.2. Operaţii specifice TAD Arbore Binar de Căutare 7.1.2.1. Căutarea unei chei 7.1.2.2. Inserarea unui nod 7.1.2.3. Cheia maximă dintr-un arbore binar de căutare 7.1.2.4. Succesorul şi predecesorul unui nod 7.1.2.5. Ştergerea unui nod 7.2. Arbori echilibraţi 7.2.1. Rotaţii în arbori binari de căutare 7.2.2. Arbori AVL 7.2.2.1. Definiţii şi generalităţi 7.2.2.2. Calculul factorului de echilibrare pentru o rotaţie simplă 7.2.2.3. Inserarea unui nod într-un arbore AVL 7.2.3. Arbori bicolori (roşii-negri) 7.2.3.1. Definiţii şi generalităţi 7.2.3.2. Funcţii suplimentare pentru arbori bicolori 7.2.3.3. Inserarea unui nod într-un arbore bicolor 7.2.3.4. Ştergerea unui nod dintr-un arbore bicolor 7.2.4. Structuri de date pentru memoria externă 7.2.4.1. Arbori 2-3 7.2.4.1.1. Inserarea unei chei într-un arbore 2-3 7.2.4.2.2. Ştergerea 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. Căutarea unei chei într-un arbore B 7.2.4.2.3. Inserarea unei chei într-un arbore B 7.2.4.2.4. Variante de arbori B 7.3. Probleme propuse 8. COZI PRIORITARE 8.1. Specificarea TAD Coadă Prioritară 8.2. Interfaţa TAD Coadă Prioritară 8.3. Exemple 8.4. Arbori parţial ordonaţi (heapuri binare) 8.4.1. Definiţii şi terminologie 8.4.2. Transformarea unui tablou într-un heap 8.4.3. Sortare prin metoda heapurilor (heapsort) 8.4.4. Implementarea cozilor cu priorităţi folosind heapuri binare 8.4.5. Aplicaţii ale cozilor prioritare 8.5. Probleme propuse 9. TABELE DE DISPERSIE 9.1. Definiţii şi terminologie 9.2. Funcţii de dispersie 9.3. Strategii de rezolvare a coliziunilor 9.3.1. Dispersie deschisă 9.3.1.1. Interfaţă dispersie deschisă 9.3.1.2. Implementare dispersie deschisă 9.3.2. Dispersie închisă 9.3.2.1. Verificare liniară 9.3.2.2. Verificare pătratică 9.3.2.3. Dispersie dublă 9.3.2.4. Interfaţă dispersie închisă 9.3.2.5. Implementare dispersie închisă 9.3.2.6. Redispersare 9.4. Eficienţa operaţiilor în tabelele de dispersie 9.5. Probleme propuse 10. GRAFURI 10.1. Elemente de teoria grafurilor: definiţii şi terminologie 10.2. Operaţii asociate vârfurilor 10.3. Operaţii asociate arcelor 10.4. TAD Graf 10.5. Iterarea vârfurilor şi arcelor grafului 10.6. Implementarea operaţiilor independente de reprezentarea grafului 10.7. Implementarea grafurilor cu matrice de adiacenţe 10.8. Reprezentarea grafurilor prin liste de adiacenţe 10.9. Implementarea iteratorilor 10.10. Metode de explorare a grafurilor 10.10.1. Traversarea în adâncime a unui graf 10.10.2. Traversarea în lăţime a unui graf 10.11. Sortare topologică 10.12. Determinarea componentelor tare conexe 10.13. Colecţii de mulţimi 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 în grafuri 10.15.1. Algoritmul Dijkstra 10.15.2. Algoritmul Bellman-Ford 10.15.3. Drumuri minime între toate perechile de vârfuri 10.16. Probleme propuse Autor: Valeriu Iorga

REVIEW-URI

Scrie un review și spune-ne opinia ta despre acest produs

scrie un review