Разное

Лафоре алгоритмы и структуры данных java: Структуры данных и алгоритмы в Java. Р. Лафоре

Содержание

«Структуры данных и алгоритмы 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 — если вы разработчик.

AlexKorablev.ru – Структуры данных и алгоритмы в Java (2-е издание)

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

Почему эта книга?

Эта книга для занятых (или ленивых) студентов или программистов, кто решил повторить алгоритмы перед техническим интервью. Книгу можно просмотреть очень быстро: читаем список идей после каждой статьи, просматриваем примеры кода. Если что-то показалось непонятным, возвращаемся к основному тексту главы.

С другой стороны, если читать книгу от корки до корки делая все упражнения, можно добиться заметного прогресса в освоении материала. К тому же в книге есть не только текстовое описание алгоритмов и их программный код, но и Java приложение для демонстрации их работы.

Как я отмечал выше, еще одна причина читать эту книгу — простой язык. И оригинал, и перевод отличаются максимально ясными объяснениями работы каждого алгоритма. И если после прочтения пары страниц Кнута, вы засыпаете, эта книга для вас.

Можно что-нибудь улучшить?

Алгоритмы — очень консервативная тема. Не многое изменилось с того момента, как книга была опубликована. При этом Java изменилась значительно. В ней появились новые синтаксические конструкции. В ней появились новые подходы к написанию хорошего кода. Обновились правила оформления кода.

Поймите меня правильно. Все примеры из книги все еще работающий Java код. Тем не менее, это уже не современная Java. Я не хочу видеть подобный код в продакшене. Почему важно использовать самые свежие подходы в коде примеров? Из-за того, что книги, подобные этой, читают преимущественно студенты и начинающие программисты. Они будут копировать этот стиль в свои проекты.

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

Плюсы:

  • Очень простой язык
  • Хороший набор алгоритмов
  • Каждая статья заканчивается списком идей

Минусы:

  • Довольно старая
  • Странное форматирование примеров кода
  • Некоторые алгоритмы рассматриваются без примеров кода, только словесное объяснение

Структуры данных и алгоритмы JAVA

Загрузка…
Навазние: Структуры данных и алгоритмы JAVA

Автор: Роберт Лафоре
Издательство:
Год: 2013
Страниц: 704
Язык: Русский
Размер: 12
Формат: pdf
ISBN: 978-5-496-00740-5
PDF: 12 Мб

Второе издание одной из самых авторитетных книг по программированию посвящено использованию структур данных и алгоритмов. Алгоритмы — это основа программирования, определяющая, каким образом разрабатываемое программное обеспечение будет использовать структуры данных. На четких и простых программных примерах автор объясняет эту сложную тему, предлагая читателям написать собственные программы и на практике освоить полученные знания. Рассматриваемые примеры написаны на языке Java, хотя для усвоения материала читателю не обязательно хорошо знать его — достаточно владеть любым языком программирования, например C++. Первая часть книги представляет собой введение в алгоритмизацию и структуры данных, а также содержит изложение основ объектно-ориентированного программирования. Следующие части посвящены различным алгоритмам и структурам данных, рассматриваемым от простого к сложному: сортировка, абстрактные типы данных, связанные списки, рекурсия, древовидные структуры данных, хеширование, пирамиды, графы. Приводятся рекомендации по использованию алгоритмов и выбору той или иной структуры данных в зависимости от поставленной задачи.