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 (dequeue, 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