Рецензия на книгу: «Структуры данных и алгоритмы Java», Роберт Лафоре

Сила каждого программиста — в его знаниях. Да, способность хорошо гуглить тоже стоит не на последнем месте, но тем не менее, должен быть некоторый запас знаний, на основе которого и формируется способ мышления разработчика. Чем глубже эти знания, тем более интересные решения может придумать программист. Одной из частей такой “базы” и являются структуры данных и алгоритмы. Как же можно расширять свои знания в данном направлении? Как вариант — найти книгу, знания из которой станут несгораемым запасом и фундаментом для дальнейшего изучения. Для меня такой книгой и стала «Структуры данных и алгоритмы Java» Роберта Лафоре.

Для кого

Аудиторией для данной книги может послужить весьма широкий спектр людей, ведь она будет полезна и для тех, кто только постиг синтаксис языка Java, и для практикующих программистов, для более глубокого понимания особенностей структур данных и алгоритмов.

О чём

Данная книга посвящена изучению и использованию структур данных и алгоритмов в программировании. Она расскажет читателю, каким образом структуры данных определяют способ организации данных в памяти, а также как алгоритмы обеспечивают выполнение различных операций с этими структурами. Давайте копнем немного глубже и посмотрим, о чём именно рассказывает эта книга:

1. Массивы. Подробно рассматривается операции вставки, поиска и удаления в массивах и упорядоченных массивах. Демонстрируется работа линейного и двоичного поиска для упорядоченных и неупорядоченных массивов. Также вы узнаете что такое O-синтаксис.
2. Сортировки. Рассматриваются три простые метода сортировки — “пузырьковая сортировка”, “сортировка методом выбора”, “сортировка методом вставки”. Из книги вы узнаете, какая из них самая медленная, а какая самая простая.
3. Стеки и очереди. Рассматриваются такие структуры данных как стек, очередь и приоритетная очередь, их эффективность, реализация на Java.
4. Связные списки. Книга рассказывает о двусвязных и двусторонних списках, об их эффективности и том, каким образом выполняются операции вставки, поиска и удаления. Также рассматриваются итераторы и то, какие для них нужны методы.
5. Рекурсии. Рассматриваются рекурсии в различных ситуациях, таких как: вычисление треугольных чисел и факториалов, построение анаграмм, выполнение рекурсивного двоичного поиска, решение головоломки “Ханойская башня”, реализация сортировки слиянием, решение задачи о рюкзаке.
6. Нетривиальные сортировки. Рассматриваются более совершенные методы: сортировка Шелла, быстрая сортировка и поразрядная, их алгоритмы, эффективность.
7. Двоичные деревья. Рассматриваются сбалансированные деревья двоичного поиска, как они работают, их операции вставки, удаления, различные виды обхода, поиск минимума и максимума, поиск преемника. Также будет рассмотрен Код Хаффмана.
8. Красно-черные деревья. Рассматривается одна из самых эффективных разновидностей сбалансированных деревьев, их операции поворота и переключения цветов, необходимые для балансировки.
9. Деревья 2-3-4. Описываются деревья данного вида как пример многопутевых деревьев, рассматривается их работа, отношение с В-деревьями, которые используются для внешнего хранения данных.
10. Хеш-таблицы. Рассматривается хеширование и его различные методы, такие как линейное и квадратичное пробирование, двойное хеширование и метод цепочек. Также вы сможете узнать, как можно применить хеширование для организации внешнего хранения файлов.
11. Пирамиды. Это особый тип дерева, используемый для эффективной реализации приоритетных очередей. В книге рассматриваются механизмы работы операции вставки, удаления, перестановки. Также вы узнаете, что такое пирамидальная перестановка и как её можно реализовать в Java.
12. Графы. Приводятся взвешенные и невзвешенные графы, алгоритмы для поиска по ним, алгоритмы, применяемые для нахождения кратчайших путей обхода.

Для большей наглядности в каждой главе приводится собственная реализация рассматриваемой структуры данных. Например, если это односвязный список, будет приведен пример класса, реализующего описанный функционал. Последняя глава книги, отталкиваясь от знаний, полученных из предыдущих глав, начинает собирать все знания в единую картину. К примеру, вы сможете четко сформировать представление о том, какую структуру данных в какой ситуации использовать:Также в конце каждой главы есть небольшие упражнения. Некоторые из них связаны с выполнением операций с приложением Workshop, а другие дают вам небольшие задания непосредственно в коде.

Что такое приложения Workshop

Для демонстрации данных структур и алгоритмов используются приложения Workshop. Приложения оформлены в виде апплетов Java, которые можно запускать в браузере. Приложения Workshop строят графические схемы, которые показывают, как работает алгоритм или структура данных. К примеру, в одном из приложений, предназначенном для отображения сортировки столбцов по возрастанию, при каждом нажатии кнопки на гистограмме будет выполняться следующий шаг. При этом будут выводиться значения переменных, задействованных в данном алгоритме, чтобы было видно, как происходит выполнение кода (напоминает описание дебагера, не так ли?).

Как скачать и установить Workshop

1. Скачать апплеты можно вот тут.
2. Нажимаете на WorkshopApplets.ZIP и качаете архив с апплетами.
3. Чтобы разобраться с апплетами, можно почитать вот этот топик и комменты к нему.

Плюсы книги

• очень легко читается, многие примеры объясняются почти "на пальцах";
• открывает глаза на многие “классические” вещи, без применения сложных математических формул. Ну, почти без них :)
• несмотря на то, что примеры приведены на языке Java, действия, происходящие в коде, весьма подробно объясняются текстом после и комментариями в коде. Поэтому ее может читать пользователь любого языка программирования, так как примеры кода довольно просты: они читаются почти как псевдокод.

Минусы книги

• несмотря на объяснение "на пальцах", в нем бывают пробелы. Для объяснения сортировки массивов автор рисует футбольную команду, а сортировка Шелла там практически не описана: я не смог её понять и читал о ней в интернете;
• возможны опечатки, как правило в изображениях или таблицах;
• некоторый код весьма устаревший.

Аналоги

Аналогами этой книги или следующими за ней (для тех кто хочет продолжать изучение) я советую:

• “Алгоритмы на Java” Роберта Седжвика;
• “Алгоритмы: построение и анализ” Томаса Кормена.

Итог

Минусов у книги немного, так что она действительно стоит прочтения. В ней доступно объясняется множество базовых, основополагающих тем, таких как различные сортировки, массивы, деревья, коллекции, графы и так далее. Так как книга не сильно привязывается к Java, база знаний, полученных от ее изучения, будет полезна и в других языках программирования. Must have, must read — если вы разработчик.