Podstawy ADT
WPROWADZENIE
Abstrakcyjny typ danych
(ang. abstract data type, ADT) jest typem danych, który jest dostępny
tylko za pośrednictwem odpowiedniego interfejsu.
Program korzystający z abstrakcyjnego typu danych nazywamy
klientem,
a program określający typ danych - implementacją.
Dzięki abstrakcyjnym typom danych możemy oddzielić wykonywane
przez programy pojęciowe przekształcenia danych od wszelkich
konkretnych reprezentacji struktur danych i implementacji algorytmów.
Przy analizie wydajności programów musimy być świadomi kosztów operacji
podstawowych.
Dla zbiorów obiektów abstrakcyjnych zwykle potrzebujemy
następujących operacji:
- inicjalizacja zbioru obiektów (konstruktor)
- umieszczenie nowego obiektu w zbiorze (insert, push, put)
- usuwanie obiektu ze zbioru (remove, pop, get)
- niszczenie zbioru obiektów (destruktor, zwolnienie zasobów)
- kopiowanie zbioru obiektów (konstruktor kopiujący, podstawienie kopiujące)
Najważniejsze abstrakcyjne typy danych:
- lista (list)
- stos (LIFO, stack)
- kolejka (FIFO, queue)
- double-ended queue (deque)
- kolejka z priorytetami (priority queue)
- sterta/kopiec (heap)
- graf (graph)
- struktura zbiorów rozłącznych (disjoint-set data structure)
- zbiór (set)
- tablica asocjacyjna (associative array, dictionary)
ZALETY UŻYWANIA ADT
- Enkapsulacja.
Użytkownik nie musi znać szczegółów implementacji.
- Lokalizacja zmian.
Nie trzeba zmieniać kodu użytkownika po zmianie implementacji ADT.
- Elastyczność.
Różne implementacje danego ADT o tych samych właściwościach
mogą być używane zamiennie.
Daje to możliwość poprawienia ogólnej wydajności w szczególnych sytuacjach.
WIKIPEDIA
- https://en.wikipedia.org/wiki/Abstract_data_type
- https://en.wikipedia.org/wiki/List_(abstract_data_type)
- https://en.wikipedia.org/wiki/Collection_(abstract_data_type)
- https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
- https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
- https://en.wikipedia.org/wiki/Double-ended_queue
- https://en.wikipedia.org/wiki/Priority_queue
- https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
- https://en.wikipedia.org/wiki/Set_(abstract_data_type)
- https://en.wikipedia.org/wiki/Associative_array