Istnieją różne rodzaje mieszanin. Masz struktury danych, które nie są powiązane z algorytmami, algorytmy, które nie wymagają (rzeczywistych) struktur danych, ale najczęściej oba są w jednym pakiecie.
Edycja: jak słusznie wskazano @Doval, struktury danych same w sobie nie są powiązane z żadnymi operacjami. Akt łączenia struktury danych i algorytmu tworzy abstrakcyjny typ danych.
Struktury danych bez algorytmów
Rozważmy na przykład strukturę danych do przechowywania współrzędnych dwuwymiarowych, odpowiednio nazwaną Point. Algorytmy nie mają wiele do zrobienia dla punktu, a tak naprawdę to tylko kontener dla wartości xi y. Oczywiście, nadając tę strukturę danych, możesz teraz dodawać do niej wszelkiego rodzaju algorytmy (obliczanie odległości, wypukłe kadłuby, co masz).
Możesz pomyśleć o wielu strukturach danych, które są po prostu nagromadzeniem pojedynczych danych. Chociaż występują one często w praktyce, nie stanowią dobrego materiału dydaktycznego, ponieważ nie można się z nich niczego nauczyć, po zrozumieniu, że pojedyncze elementy danych można akumulować w nową strukturę danych (np. Czego się uczysz po powyższym Pointprzykładzie, jeśli dostarczę ci tę niesamowitą strukturę danych Point3D, która może zrobić to samo w przypadku przestrzeni trójwymiarowej?)
Algorytmy bez (rzeczywistych) struktur danych
„Rzeczywisty”, ponieważ oczywiście każdy interesujący algorytm potrzebuje prymitywnych typów danych, takich jak liczby całkowite lub logiczne, i nie chcemy uwzględniać ich jako struktur danych w tym kontekście. Podobnie jak powyżej, algorytmy te są zazwyczaj dość proste. W szczególności nie mają one żadnego skomplikowanego stanu, ponieważ zwykle wchodzi w strukturę danych (patrz następny rozdział).
Przykładem takiego algorytmu może być obliczenie największego wspólnego dzielnika dwóch liczb. Algorytmy Euklid dla gcd naprawdę potrzebują tylko dwóch liczb całkowitych i manipulują nimi.
Gdy sprawy stają się coraz bardziej interesujące, bardzo szybko wkraczasz w świat abstrakcyjnych typów danych. Na przykład sito Eratostenesa opiera się na tablicy. Moglibyśmy teraz porozmawiać, czy tablica nadal jest prymitywna, czy w rzeczywistości możesz porozmawiać, jeśli liczba całkowita nie jest już strukturą danych. Tak czy inaczej, algorytmy, które istnieją całkowicie bez struktur danych, są nudne, nawet jeśli zaakceptujesz ich izolowane istnienie.
Algorytmy połączone ze strukturami danych, czyli abstrakcyjne typy danych
Teraz są to interesujące, ale z dwóch bardzo różnych powodów. Zazwyczaj można do nich podejść z dwóch kierunków: najpierw struktury danych lub najpierw algorytmu.
Podczas gdy abstrakcyjny typ danych jest definiowany przez kombinację struktury danych + algorytmy / operacje, często oglądamy je, koncentrując się na jednym z nich, i uważamy drugi za czynnik umożliwiający.
Struktura danych, a następnie algorytm
Spotkasz abstrakcyjne typy danych, które są raczej proste w użyciu, ale wymagają mniej lub bardziej skomplikowanych algorytmów, aby działały wewnętrznie. Na przykład, a HashMapjest trywialny w użyciu, ale wymaga sprytnej funkcji skrótu i radzenia sobie z kolizjami skrótu wewnątrz. Jednak z twojego punktu widzenia jako użytkownika zależy Ci na tym, że jest to coś, co przechowuje dane dla Ciebie, a nie coś, co coś dla Ciebie robi.
W przeciwieństwie do ostatniej grupy poniżej, te struktury danych nie narażają użytkowników na te algorytmy. Nie musisz wiedzieć ani przejmować się HashMapwewnętrzną funkcją skrótu, aby móc z niej korzystać. (Aby jednak efektywnie z niego korzystać, możesz chcieć poznać te rzeczy;)
Algorytm, a następnie struktura danych
Drugi kierunek oznacza, że masz algorytm, którego chcesz po prostu użyć, ale który potrzebuje wewnętrznych struktur danych, aby działał zgodnie z przeznaczeniem. Przykładem może być algorytm partycjonowania przestrzeni binarnej (BSP), który można po prostu poprosić o dwuwymiarowy Pointz dużego zestawu punktów najbliższego danemu punktowi zapytania. Jednak potrzebujesz struktury drzewa (a nawet dodatkowych algorytmów, takich jak obliczanie odległości) od wewnątrz, aby faktycznie napisać algorytm.
Ogólnie można powiedzieć, że algorytmy w tej grupie wykorzystują struktury danych do reprezentacji ich stanu wewnętrznego. Twierdziłbym, że ta grupa algorytmów jest najbardziej różnorodna i znajdziesz wiele różnych, które pasują do tego ogólnego schematu. Jeśli chodzi o punkt widzenia, uważamy je za interesujące, ponieważ robią dla nas coś (np. Sortowanie) i nie dbają tak bardzo o część przechowującą dane.
Ściśle powiązane struktury danych i algorytmy
Wreszcie, masz struktury danych, które są bardzo blisko związane z algorytmami, które bezpośrednio z nimi odpowiadają. Typowym przykładem jest drzewo binarne, które, gdy chcesz zrobić z nim coś sensownego, wymusza na tobie temat algorytmów chodzenia po drzewie (najpierw głębokość, najpierw szerokość, cokolwiek).
W takich przypadkach co jakiś czas zmieniamy skupienie naszego widoku na wynikowe abstrakcyjne typy danych. Czasami zależy Ci na strukturze drzewa, kilka minut później zależy Ci na możliwości uruchomienia operacji wyszukiwania, potem zastanawiasz się nad usunięciem węzła i od razu widać, jak potem wygląda struktura. Chociaż wszystko to obowiązuje również w innych sekcjach powyżej, nie jest to coś, na czym koncentruje się twój umysł, na przykład, gdy przechowujesz / odzyskujesz dane do / z Maplub sortujesz połączoną listę.