Recenzja książki: „Struktury i algorytmy danych Java”, Robert Laforet

Siła każdego programisty tkwi w jego wiedzy. Tak, umiejętność dobrego googlowania też nie jest na ostatnim miejscu, niemniej jednak musi istnieć pewna wiedza, na podstawie której kształtuje się sposób myślenia programisty. Im głębsza ta wiedza, tym ciekawsze rozwiązania może wymyślić programista. Jedną z części takiej „bazy” są struktury danych i algorytmy. Jak możesz poszerzyć swoją wiedzę w tym kierunku? Opcjonalnie znajdź książkę, której wiedza stanie się ognioodporną rezerwą i podstawą do dalszych badań. Dla mnie taką książką były „Struktury i algorytmy danych Java” Roberta Laforeta .

Dla kogo

Odbiorcą tej książki może być bardzo szerokie grono osób, ponieważ będzie ona przydatna zarówno dla tych, którzy dopiero opanowali składnię języka Java , jak i dla praktykujących programistów, do głębszego zrozumienia cech struktur danych i algorytmów .

O czym

Książka ta poświęcona jest badaniu i wykorzystaniu struktur danych i algorytmów w programowaniu. Nauczy czytelnika, w jaki sposób struktury danych determinują sposób organizacji danych w pamięci, a także w jaki sposób algorytmy wykonują różne operacje na tych strukturach. Zagłębmy się nieco głębiej i zobaczmy, o czym dokładnie jest ta książka:

1. Tablice. Operacje wstawiania, wyszukiwania i usuwania tablic i uporządkowanych tablic są szczegółowo omówione. Demonstruje działanie wyszukiwania liniowego i binarnego tablic uporządkowanych i nieuporządkowanych. Dowiesz się także czym jest O-składnia.
2. Sortowanie. Rozważane są trzy proste metody sortowania: „sortowanie bąbelkowe”, „sortowanie przez wybór”, „sortowanie przez wstawianie”. Z książki dowiesz się, który z nich jest najwolniejszy, a który najprostszy.
3. Stosy i kolejki. Rozważane są struktury danych takie jak stos, kolejka i kolejka priorytetowa, ich efektywność oraz implementacja w Javie.
4. Połączone listy. Książka omawia listy podwójnie połączone i dwukierunkowe, ich wydajność oraz sposób wykonywania operacji wstawiania, wyszukiwania i usuwania. Omówiono także iteratory i wymagane przez nie metody.
5. Rekursje. Rekursje są uwzględniane w różnych sytuacjach, takich jak: obliczanie liczb trójkątnych i silni, konstruowanie anagramów, przeprowadzanie rekurencyjnego wyszukiwania binarnego, rozwiązywanie zagadki Wieży Hanoi, implementacja sortowania przez scalanie, rozwiązywanie problemu plecakowego.
6. Sortowanie nietrywialne. Rozważane są metody bardziej zaawansowane: sortowanie powłokowe, sortowanie szybkie i sortowanie radix, ich algorytmy, wydajność.
7. Drzewa binarne. Rozważane są zrównoważone drzewa wyszukiwania binarnego, sposób ich działania, operacje wstawiania i usuwania, różne rodzaje przechodzenia, poszukiwanie minimum i maksimum, poszukiwanie następcy. Omówiony zostanie także Kodeks Huffmana.
8. Czerwone i czarne drzewa. Uważamy, że jedna z najskuteczniejszych odmian zrównoważonych drzew, ich obrót i operacje przełączania kolorów są niezbędne do równoważenia.
9. Drzewa 2-3-4. Drzewa tego typu opisano jako przykład drzew wielościeżkowych, omówiono ich działanie i związek z drzewami B, które służą do zewnętrznego przechowywania danych.
10. Tabele mieszające. Omówiono haszowanie i jego różne metody, takie jak sondowanie liniowe i kwadratowe, podwójne mieszanie i metoda łańcuchowa. Możesz także dowiedzieć się, jak można wykorzystać haszowanie do organizacji zewnętrznego przechowywania plików.
11. Piramidy. Jest to specjalny typ drzewa służący do wydajnej implementacji kolejek priorytetowych. W książce omówiono mechanizmy działania wstawiania, usuwania i porządkowania. Dowiesz się także czym jest permutacja piramidalna i jak można ją zaimplementować w Javie.
12. Wykresy. Przedstawiono grafy ważone i nieważone, algorytmy ich przeszukiwania oraz algorytmy wykorzystywane do wyszukiwania najkrótszych ścieżek przejścia.

Dla większej przejrzystości każdy rozdział przedstawia własną implementację danej struktury danych. Przykładowo, jeśli jest to lista pojedynczo połączona, zostanie podany przykład klasy realizującej opisaną funkcjonalność. Ostatni rozdział książki, bazując na wiedzy zdobytej z poprzednich rozdziałów, zaczyna gromadzić całą wiedzę w jeden obraz. Na przykład będziesz w stanie jasno określić, jakiej struktury danych użyć w jakiej sytuacji: Na końcu każdego rozdziału znajdują się również małe ćwiczenia. Niektóre z nich polegają na wykonywaniu czynności za pomocą aplikacji Workshop , podczas gdy inne umożliwiają wykonanie drobnych zadań bezpośrednio w kodzie.

Czym są aplikacje warsztatowe

Do zademonstrowania tych struktur i algorytmów służą aplikacje warsztatowe . Aplikacje są zaprojektowane jako aplety Java, które można uruchomić w przeglądarce. Aplikacje warsztatowe tworzą diagramy graficzne, które pokazują, jak działa algorytm lub struktura danych. Przykładowo w jednej aplikacji przeznaczonej do wyświetlania kolumn posortowanych rosnąco, za każdym razem, gdy klikniesz przycisk na histogramie, zostanie wykonany kolejny krok. W tym przypadku zostaną wyświetlone wartości zmiennych biorących udział w tym algorytmie, dzięki czemu będzie można zobaczyć, jak wykonywany jest kod (przypomina opis debuggera , prawda?).

Jak pobrać i zainstalować Workshop

1. Tutaj możesz pobrać aplety .
2. Kliknij WorkshopApplets.ZIP i pobierz archiwum z apletami.
3. Aby zrozumieć aplety, możesz przeczytać ten temat i komentarze do niego.

Plusy książki

• bardzo łatwo się czyta, wiele przykładów wyjaśnionych niemal „na palcach”;
• otwiera oczy na wiele „klasycznych” rzeczy, bez stosowania skomplikowanych wzorów matematycznych. No prawie bez nich :)
• Chociaż przykłady są w Javie, działania występujące w kodzie są szczegółowo wyjaśnione w poniższym tekście i komentarzach w kodzie. Dlatego może go przeczytać użytkownik dowolnego języka programowania, ponieważ przykłady kodu są dość proste: czyta się je prawie jak pseudokod.

Minusy książki

• Pomimo wyjaśnienia „na palcach” są w nim luki. Aby wyjaśnić sortowanie tablic, autor rysuje drużynę piłkarską, ale sortowanie Shella praktycznie nie jest tam opisane: nie mogłem tego zrozumieć i przeczytać o tym w Internecie;
• Mogą występować literówki, zwykle w obrazach lub tabelach;
• niektóre kody są dość przestarzałe.

Analogi

Polecam analogi tej książki lub jej następców (dla tych, którzy chcą kontynuować naukę):

• „Algorytmy w Javie” Roberta Sedgwicka;
• „Algorytmy: konstrukcja i analiza” Thomasa Cormena.

Konkluzja

Książka ma kilka wad, dlatego naprawdę warto ją przeczytać. W jasny sposób wyjaśnia wiele podstawowych, fundamentalnych tematów, takich jak różne rodzaje, tablice, drzewa, kolekcje, wykresy i tak dalej. Ponieważ książka nie jest mocno powiązana z Javą , wiedza zdobyta podczas jej studiowania będzie przydatna w innych językach programowania. Musisz mieć, musisz przeczytać - jeśli jesteś programistą.