Jaka jest różnica między abstrakcyjnymi a konkretnymi strukturami danych?

Myślałem asocjacyjną (tj mapie lub słownika) i tabela mieszania były takie same pojęcia, dopóki nie zobaczyłem w Wikipedii tym

W przypadku słowników z bardzo małą liczbą powiązań sensowne może być zaimplementowanie słownika przy użyciu listy powiązań, połączonej listy powiązań. ...

Najczęściej stosowaną implementacją tablicy asocjacyjnej ogólnego przeznaczenia jest tablica skrótów: tablica powiązań wraz z funkcją skrótu, która odwzorowuje każdy możliwy klucz na indeks tablicy. ...

Słowniki mogą być również przechowywane w drzewach wyszukiwania binarnego lub w strukturach danych specjalizowanych dla określonego rodzaju kluczy, takich jak drzewa radix, try, tablice Judy lub drzewa van Emde Boas. ...

Myślę, że mój problem polega na tym, że nie wiem, że tablica asocjacyjna (tj. Mapa lub słownik) jest abstrakcyjnym typem danych, a tablica skrótów to konkretna struktura danych, a do implementacji można użyć różnych konkretnych struktur danych ten sam abstrakcyjny typ danych.

Moje pytania byłyby

• Jaka jest różnica i związek między abstrakcyjnymi strukturami danych a konkretnymi strukturami danych?

• Jakie są przykłady dla każdego z nich (abstrakcyjne i konkretne struktury danych)? Im więcej tym lepiej.

• Czy istnieje lista konkretnych struktur danych, które można zastosować do wdrożenia jakich struktur danych abstrakcyjnych? Byłoby miło mieć taki.

Abstrakcyjny typ danych (ADT) jest zasadniczo interfejsem API, a konkretna struktura danych zapewnia implementację tego interfejsu API. Dla danego narzędzia ADT często istnieje kilka różnych wyborów konkretnych struktur danych, które obsługują operacje zapytań i aktualizacji opisane przez narzędzie ADT. Każda konkretna struktura danych dla danego ADT musi obsługiwać wszystkie operacje opisane przez ADT (być może z pewnym prawdopodobieństwem powodzenia w przypadku struktur losowych), ale każda konkretna struktura może dawać różne gwarancje czasów działania każdej operacji. Wybór konkretnej struktury danych do wdrożenia dla danego ADT zwykle zależy od priorytetów wydajności każdej operacji (w tym inicjalizacji struktury) oraz złożoności wdrożenia i utrzymania różnych typów danych.

Istnieje o wiele za dużo ADT i odpowiednich struktur betonowych, aby wymienić je w jednej odpowiedzi, ale oto kilka przykładów:

• Find(x)$x$$x$Insert(x)Delete(x)

• Findsuccessor(x)$S$$x$$t \in S$$s < t$

• Kolejek priorytetów jest ADT wymagający inserti delete-minoperacje (a czasem innych operacji, a także, jak find-min increase-keyi delete-key). Struktury danych, które implementują kolejkę priorytetową ADT, obejmują:

  1. nieposortowana lista połączona, która jest szybka, insertale wolna delete-min.

  2. posortowana lista łączy, która jest szybka, delete-minale wolnainsert

  3. insertdelete-min$sort(n)$

  4. binarnym sterty który ma logarytmiczną inserti delete-minoraz liniowe inicjalizacji czasu.

  5. Istnieją również inne warianty implementacji sterty .

• stabbing(x)$x$

Abstrakcyjny typ danych opisuje, jakie operacje są dostępne i jakie prawa przestrzegają. Np. Słownik pozwala przechowywać wartość pod danym kluczem i pobrać wartość klucza, i obiecuje, że jeśli najpierw zapiszesz wartość, a następnie odzyskasz ją za pomocą tego samego klucza, odzyskasz wartość, którą zapisałeś. Stos zawiera operacje wypychania i wyskakiwania.

Konkretny typ danych mówi, jak te operacje są faktycznie realizowane.