Jakiś Abstrakcyjny typ danych (ADT) to model koncepcyjny, który definiuje zestaw operacji i zachowań dla struktury danych bez określenia sposobu realizacji tych operacji lub sposób organizacji danych w pamięci. Definicja ADT wspomina tylko co operacje mają być wykonane ale nie Jak operacje te zostaną zrealizowane. Nie określa, w jaki sposób dane będą zorganizowane w pamięci i jakie algorytmy zostaną użyte do realizacji operacji. Nazywa się to „abstrakcyjnym”, ponieważ zapewnia widok niezależny od implementacji.

Proces dostarczania tylko tego, co niezbędne i ukrywania szczegółów, nazywa się abstrakcja.

Cechy ADT

Abstrakcyjne typy danych (ADT) to sposób hermetyzacji danych i operacji na nich w jedną jednostkę. Niektóre z kluczowych cech ADT obejmują:

• Abstrakcja: Użytkownik nie musi znać implementacji struktury danych, dostarczane są jedynie podstawowe informacje.
• Lepsza konceptualizacja: ADT daje nam lepszą konceptualizację prawdziwego świata.
• Solidny: Program jest solidny i ma zdolność wychwytywania błędów.
• Hermetyzacja : ADT ukrywają wewnętrzne szczegóły danych i zapewniają publiczny interfejs umożliwiający użytkownikom interakcję z danymi. Pozwala to na łatwiejszą konserwację i modyfikację struktury danych.
• Abstrakcja danych : ADT zapewniają poziom abstrakcji od szczegółów implementacji danych. Użytkownicy muszą jedynie znać operacje, które można wykonać na danych, a nie sposób, w jaki te operacje są realizowane.
• Niezależność struktury danych : Zestawy ADT można implementować przy użyciu różnych struktur danych, takich jak tablice lub listy połączone, bez wpływu na funkcjonalność narzędzia ADT.
• Ukrywanie informacji: ADT mogą chronić integralność danych, umożliwiając dostęp tylko autoryzowanym użytkownikom i operacjom. Pomaga to zapobiegać błędom i niewłaściwemu wykorzystaniu danych.
• Modułowość : ADT można łączyć z innymi ADT, tworząc większe, bardziej złożone struktury danych. Pozwala to na większą elastyczność i modułowość w programowaniu.

Ogólnie rzecz biorąc, narzędzia ADT stanowią potężne narzędzie do organizowania danych i manipulowania nimi w ustrukturyzowany i wydajny sposób.

Ten obraz pokazuje, jak abstrakcyjny typ danych (ADT) ukrywa wewnętrzne struktury danych (takie jak tablice połączone listy) przy użyciu funkcji publicznych i prywatnych, udostępniając programowi aplikacyjnemu tylko zdefiniowany interfejs.

Dlaczego warto używać ADT?

Poniżej wymieniono najważniejsze powody, dla których warto używać narzędzi ADT w Javie:

• Hermetyzacja: Ukrywa złożone szczegóły implementacji za przejrzystym interfejsem.
• Możliwość ponownego użycia : Umożliwia różne implementacje wewnętrzne (np. tablicę lub listę połączoną) bez zmiany użycia zewnętrznego.
• Modułowość: Upraszcza konserwację i aktualizacje poprzez oddzielenie logiki.
• Bezpieczeństwo: Chroni dane, uniemożliwiając bezpośredni dostęp, minimalizując błędy i niezamierzone zmiany.

Przykład abstrakcji

Na przykład używamy prymitywnych wartości, takich jak int float i char, przy założeniu, że te typy danych mogą działać i być wykonywane bez znajomości szczegółów ich implementacji. ADT działają podobnie poprzez definiowanie jakie operacje są możliwe bez szczegółowego opisywania ich realizacji.

Różnica między ADT i UDT

Poniższa tabela pokazuje różnicę między ADT i UDT.

Różnica dat w Excelu

Przykłady ADT

Przyjrzyjmy się teraz trzem typowym narzędziom ADT: List ADT Stack ADT i Queue ADT.

1. Lista ADT

Lista ADT (Abstract Data Type) to sekwencyjny zbiór elementów obsługujący zestaw operacji bez określenia wewnętrznej implementacji . Zapewnia uporządkowany sposób przechowywania dostępu i modyfikacji danych.

formuła murarska

Operacje:

Lista ADT musi przechowywać wymagane dane w sekwencji i powinna zawierać następujące operacje :

• Dostawać(): Zwróć element z listy w dowolnej pozycji.
• wstawić(): Wstaw element w dowolnej pozycji na liście.
• usunąć(): Usuń pierwsze wystąpienie dowolnego elementu z niepustej listy.
• usuńAt(): Usuń element w określonej lokalizacji z niepustej listy.
• zastępować(): Zastąp element w dowolnej pozycji innym elementem.
• rozmiar(): Zwraca liczbę elementów na liście.
• jestPusty(): Zwróć wartość true, jeśli lista jest pusta; w przeciwnym razie zwróć wartość false.
• jest pełny(): Zwróć wartość true, jeśli lista jest pełna, w przeciwnym razie zwróć wartość false. Ma zastosowanie tylko w implementacjach o stałym rozmiarze (np. listach opartych na tablicach).

2. Stos ADT

Stack ADT to liniowa struktura danych zgodna z zasadą LIFO (Last In First Out). Umożliwia dodawanie i usuwanie elementów tylko z jednego końca zwanego szczytem stosu.

Operacje:

W Stack ADT kolejność wstawiania i usuwania powinna być zgodna z zasadą FILO lub LIFO. Elementy są wstawiane i usuwane z tego samego końca, zwanego wierzchołkiem stosu. Powinien także wspierać następujące operacje:

• naciskać(): Wstaw element na jednym końcu stosu, zwanym górą.
• muzyka pop(): Usuń i zwróć element na górze stosu, jeśli nie jest pusty.
• zerkać(): Zwróć element na szczycie stosu bez usuwania go, jeśli stos nie jest pusty.
• rozmiar(): Zwraca liczbę elementów na stosie.
• jestPusty(): Zwraca wartość true, jeśli stos jest pusty; w przeciwnym razie zwróć wartość false.
• jest pełny(): Zwraca wartość true, jeśli stos jest pełny; w przeciwnym razie zwróć wartość false. Dotyczy tylko stosów o stałej pojemności (np. opartych na macierzach).

3. Kolejka ADT

Queue ADT to liniowa struktura danych zgodna z zasadą FIFO (pierwsze weszło, pierwsze wyszło). Umożliwia wkładanie elementów jednym końcem (tył) i wyjmowanie elementów z drugiego końca (przód).

Operacje:

Kolejka ADT ma konstrukcję podobną do Stack ADT, ale kolejność wstawiania i usuwania zmienia się na FIFO. Elementy wkłada się na jednym końcu (zwanym tyłem) i usuwa na drugim końcu (zwanym przodem). Powinien obsługiwać następujące operacje:

dynamiczna tablica Java

• kolejka(): Wstaw element na końcu kolejki.
• odpowiednio(): Usuń i zwróć pierwszy element kolejki, jeśli kolejka nie jest pusta.
• zerkać(): Zwróć element kolejki bez usuwania go, jeśli kolejka nie jest pusta.
• rozmiar(): Zwraca liczbę elementów w kolejce.
• jestPusty(): Zwróć wartość true, jeśli kolejka jest pusta; w przeciwnym razie zwróć wartość false.

Zalety i wady ADT

Abstrakcyjne typy danych (ADT) mają kilka zalet i wad, które należy wziąć pod uwagę przy podejmowaniu decyzji o ich wykorzystaniu w tworzeniu oprogramowania. Oto niektóre z głównych zalet i wad korzystania z ADT:

Korzyść:

Poniżej wymieniono zalety:

• Hermetyzacja : ADT umożliwiają hermetyzację danych i operacji w jedną jednostkę, co ułatwia zarządzanie i modyfikowanie struktury danych.
• Abstrakcja : ADT pozwalają użytkownikom pracować ze strukturami danych bez konieczności znajomości szczegółów implementacji, co może uprościć programowanie i zmniejszyć liczbę błędów.
• Niezależność struktury danych : ADT można wdrożyć przy użyciu różnych struktur danych, co może ułatwić dostosowanie się do zmieniających się potrzeb i wymagań.
• Ukrywanie informacji : ADT mogą chronić integralność danych, kontrolując dostęp i zapobiegając nieautoryzowanym modyfikacjom.
• Modułowość : ADT można łączyć z innymi ADT, tworząc bardziej złożone struktury danych, które mogą zwiększyć elastyczność i modułowość programowania.

Wady:

Wady są wymienione poniżej:

• Nad głową : Implementacja narzędzi ADT może zwiększyć obciążenie w zakresie pamięci i przetwarzania, co może mieć wpływ na wydajność.
• Złożoność : Implementacja narzędzi ADT może być skomplikowana, szczególnie w przypadku dużych i złożonych struktur danych.
• Nauka Krzywa: Korzystanie z narzędzi ADT wymaga wiedzy na temat ich implementacji i użycia, a nauka może wymagać czasu i wysiłku.
• Ograniczona elastyczność: Niektóre narzędzia ADT mogą mieć ograniczoną funkcjonalność lub mogą nie być odpowiednie dla wszystkich typów struktur danych.
• Koszt : Wdrożenie ADT może wymagać dodatkowych zasobów i inwestycji, co może zwiększyć koszty rozwoju.