Abstrakcyjny typ danych i struktura danych

Bardzo trudno jest mi zrozumieć te warunki. Szukałem w Google i czytałem trochę na Wikipedii, ale nadal nie jestem pewien. Do tej pory ustaliłem, że:

Abstrakcyjny typ danych to definicja nowego typu, opisująca jego właściwości i działanie.

Struktura danych jest implementacją ADT. Wiele ADT może być zaimplementowanych jako ta sama struktura danych.

Jeśli uważam, że słusznie, tablica jako ADT oznacza zbiór elementów i strukturę danych, w jaki sposób jest przechowywany w pamięci. Stos to ADT z operacjami wypychania i popu, ale czy możemy powiedzieć o strukturze danych stosu, jeśli mam na myśli, że stosowałem zaimplementowany jako tablica w moim algorytmie? A dlaczego kupa nie jest ADT? Może być zaimplementowany jako drzewo lub tablica.

Mówiąc najprościej, ADT (abstrakcyjny typ danych) jest bardziej logicznym opisem, podczas gdy struktura danych jest konkretna.

Pomyśl o narzędziu ADT jako obrazie danych i operacji służących do manipulowania nimi i ich zmiany.

Struktura danych to prawdziwa, konkretna rzecz . Może być zaimplementowany i używany w ramach algorytmu.

ADT jest dla interfejsu ( co robi ) czym jest struktura danych dla klasy ( jak to robi ).

Kilka przykładów:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Chyba rozumiesz.

Abstrakcyjny typ danych: ADT można zdefiniować jako zestaw wartości danych i powiązanych operacji, które są precyzyjnie określone niezależnie od konkretnej implementacji. Zatem abstrakcyjny typ danych to zorganizowany zbiór informacji i zestaw operacji służących do zarządzania tymi informacjami. Zestaw operacji określa interfejs narzędzia ADT. Dopóki ADT spełnia warunki interfejsu, tak naprawdę nie ma znaczenia, w jaki sposób ADT jest implementowany. Ponieważ w ADT wartości danych i operacje są definiowane z matematyczną precyzją, a nie jako implementacja w języku komputerowym, możemy rozumować o skutkach operacji, relacjach z innymi abstrakcyjnymi typami danych, czy program implementuje typ danych itp.

Podstawowa różnica między abstrakcyjnym typem danych (ADT) a konkretnym typem danych polega na tym, że ten drugi pozwala nam spojrzeć na konkretną reprezentację, podczas gdy ten pierwszy ukrywa przed nami reprezentację. ADT może być czystym ADT lub aktualizowanym ADT. Czysty ADT to taki, w którym wszystkie operacje są czystymi funkcjami. Oznacza to, że operacje nie powodują żadnych skutków ubocznych. W szczególności nie modyfikują ani nie aktualizują tam argumentów wejściowych. Po prostu używają tych argumentów do generowania danych wyjściowych, które są świeżymi wartościami ADT (lub innych typów). Większość rodzajów betonu jest czysta. Na przykład żadna operacja na liczbach całkowitych nie zmienia liczby całkowitej. Zamiast tego wszystkie operacje, takie jak „+”, dają nowe wyniki.

Aktualizowany ADT to taki, w którym niektóre operacje faktycznie zmieniają wartości ADT. Załóżmy na przykład, że mieliśmy operację o nazwie „pop”, która wzięła stos jako argument i zmodyfikowała go. („Na miejscu”, „destrukcyjnie”) poprzez usunięcie elementu o najwyższym priorytecie. Ta operacja byłaby uważana za nieczystą, a wówczas cały ADT byłby również nieczysty. ADT może być ADT zdefiniowanym przez użytkownika.

Wiemy, że abstrakcyjny typ danych to typ danych, który spełnia następujące dwa warunki:

1. Reprezentacja lub definicja typu i operacji są zawarte w pojedynczej jednostce syntaktycznej.

2. Reprezentacja obiektów tego typu jest ukryta przed jednostkami programu, które używają tego typu, więc możliwe są tylko bezpośrednie operacje na tych obiektach, które są podane w definicji typu.

Zdefiniowany przez użytkownika abstrakcyjny typ danych powinien zapewniać:

1. Definicja typu, która pozwala jednostkom programu deklarować zmienne typu, ale ukrywa reprezentację tych zmiennych.

2. Zestaw operacji do manipulowania obiektami tego typu.

Przykładem abstrakcyjnego typu danych zdefiniowanego przez użytkownika jest struktura. „C” zapewnia cztery podstawowe typy: int, char, float i double. Jednak „C” zapewnia również programiście możliwość definiowania własnych typów. Struktura jest jednym z takich przykładów. Struktura jest agregatem różnych części, z których każda jest jakiegoś typu.

struct abc

{int x;

float y;

};

Powyższa definicja struktury nie tworzy żadnych zmiennych, a raczej tworzy nowy typ. Zmienne tego typu można tworzyć w podobny sposób jak zmienne typu wbudowanego.

struct abc a;

Słowo kluczowe typedef pozwala nam tworzyć nowe nazwy typów dla naszych nowych typów.

Na przykład:

typedef struct abc AB;

gdzie AB to nazwa nowego typu, której można teraz używać do tworzenia nowych typów.

AB b;

Struktury danych: Poniżej przedstawiono charakterystyczne cechy struktur danych:

1. Zawiera elementy danych składowych, które mogą być atomowymi lub inną strukturą danych (wciąż domeną).

2. Zestaw operacji na jednym lub kilku elementach składowych.

3. Definiuje reguły dotyczące wzajemnego powiązania komponentów i struktury jako całości (twierdzenia).

Struktury danych:

Struktura danych może być statyczna lub dynamiczna. Statyczna struktura danych ma stały rozmiar. To znaczenie różni się od znaczenia modyfikatora statycznego. Tablice są statyczne; kiedy zdefiniujemy liczbę elementów, które może pomieścić, liczba się nie zmienia. Dynamiczna struktura danych rośnie i kurczy się w czasie wykonywania zgodnie z wymaganiami jej zawartości. Dynamiczna struktura danych jest implementowana za pomocą łączy.

Struktury danych można dalej podzielić na liniowe struktury danych i nieliniowe struktury danych. W liniowych strukturach danych każdy komponent ma unikatowego poprzednika i następcę, z wyjątkiem pierwszego i ostatniego elementu, natomiast w przypadku nieliniowych struktur danych nie ma takich ograniczeń, ponieważ elementy mogą być rozmieszczone w dowolny pożądany sposób ograniczony sposobem, w jaki wykorzystujemy reprezentują takie typy.

Po pierwsze, terminologie w strukturach danych mogą być bardzo mylące.

ADT przypomina teorię, model lub wytyczną itp., Która mówi, jak powinna zachowywać się struktura danych, jakie operacje powinna obsługiwać itp. Trzy podstawowe abstrakcyjne typy danych to kontenery, słowniki i kolejki priorytetowe. Na przykład słownik mówi nam, że każda struktura danych, która implementuje ten słownik ADT musi obsługiwać pary klucz-wartość, wyszukiwanie na podstawie kluczy, wstawianie elementów, znajdowanie następcy i poprzednika danego klucza itp.

Teraz wszystko, co implementuje powyższy ADT, to Struktura danych (DS) , Struktura danych to prawdziwe rzeczy, które implementujesz w swoich problemach i znajdujesz w bibliotekach. W przypadku słownika możesz go zaimplementować za pomocą Array lub Linked list.

Wydaje mi się, że prawdziwe zamieszanie powstaje, gdy ktoś nazywa swoje DS jako ADT, na przykład niektórzy nazywają go wspomnianym DS jako „Słownik” zamiast DictImplementation, co jest całkowicie legalne, powoduje tylko pewne zamieszanie.

Ref: Skiena: Podręcznik projektowania algorytmów