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:
Reprezentacja lub definicja typu i operacji są zawarte w pojedynczej jednostce syntaktycznej.
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ć:
Definicja typu, która pozwala jednostkom programu deklarować zmienne typu, ale ukrywa reprezentację tych zmiennych.
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:
Zawiera elementy danych składowych, które mogą być atomowymi lub inną strukturą danych (wciąż domeną).
Zestaw operacji na jednym lub kilku elementach składowych.
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.