Введение

В этом разделе вы узнаете:

• Что нового появилось во втором издании книги.
• О чем эта книга.
• О чем эта книга.
• Чем она отличается от других книг.
• Кому она может пригодиться.
• Что необходимо знать перед чтением.
• Какие программы и оборудование могут понадобиться читателю.
• Как организован материал книги.

Второе издание

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

Дополнительные темы

В книге рассматривается целый ряд новых интересных тем, которые можно использоваться для создания программных проектов. Вот лишь несколько примеров:

• Обход в глубину и игровое программирование.
• Задача Иосифа Флавия.
• Коды Хаффмана и сжатие данных.
• Задача коммивояжера.Гамильтоновы циклы.
• Задача обхода доски ходом шахматного коня Алгоритм Флойда.
• Алгоритм Уоршелла.
• Деревья 2-3.
• Задача о рюкзаке.
• Генерирование перестановок K объектов из N.
• Применение свертки при хешировании.
• Поразрядная сортировка.

Вопросы

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

Упражнения

Мы также предлагаем несколько полезных упражнений для читателя. Одни упраж- нения связаны с выполнением каких-либо операций с приложениями Workshop или примерами программ для исследования особенностей алгоритмов, другие выполняются с карандашом и бумагой, а то и вовсе относятся к категории «умозрительных экспериментов».

Программные проекты

И самое важное: в конце каждой главы читателю предлагается несколько (обычно пять) программных проектов. Простейшие проекты представляют собой простые вариации на тему программ-примеров, а самые сложные — реализации тем, которые упоминались в тексте без приведения программного кода. Решения в книге не приводятся.

О чем эта книга

Книга посвящена использованию структур данных и алгоритмов в программировании. Структуры данных определяют способ организации данных в памяти компьютера (или на диске). Алгоритмы обеспечивают выполнение различных операций с этими структурами.

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

Массив в этом примере является структурой данных, а цикл for, обеспечивающий последовательный доступ к элементам, выполняет простой алгоритм. Для простых программ с небольшими объемами данных такого простого решения может оказаться достаточно. Но для программ, обрабатывающих хотя бы умеренные объемы данных или решающих хоть сколько-нибудь нетривиальные задачи, требуются более сложные методы. Простого знания синтаксиса языка программирования, будь то Java или C++, недостаточно.

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

Чем эта книга отличается от других

О структурах данных и алгоритмах написаны десятки книг. Чем эта книга отличается от них? Три основных отличия:

• Работая над книгой, мы прежде всего стремились к тому, чтобы материал излагался понятно и доступно.
• Демонстрационные приложения Workshop наглядно поясняют рассматрива- емые темы, шаг за шагом показывая, как работают структуры данных и алгоритмы
• Примеры кода написаны на языке Java, более понятном, чем C, C++ или �as- cal (языки, традиционно использовавшиеся для написания примеров в учебни- ках по программированию).Давайте рассмотрим каждое отличие более подробно.

Доступность
Типичный учебник по программированию содержит теорию, математические формулы и заумные примеры кода. В этой книге, напротив, основное внимание уделяется простому объяснению методов решения практических задач. Мы избегаем сложных обоснований и математических выкладок. Текст поясняется многочисленными иллюстрациями.Многие книги о структурах данных и алгоритмах включают материал, отно- сящийся к программотехнике — дисциплине, направленной на проектирование и реализацию крупных и сложных программных проектов. Однако мы полагаем, что структуры данных и алгоритмы сложны и без привлечения дополнительных дисциплин, поэтому мы намеренно отказались от рассмотрения программотехни- ческих вопросов в книге. (О связи структур данных и алгоритмов с программотехникой рассказано в главе 1, «Общие сведения»).Конечно, мы используем объектно-ориентированный подход и рассматриваем различные аспекты объектно-ориентированной архитектуры, включая мини-курс ООП в главе 1. И все же основное внимание уделяется самим структурам данных и алгоритмам.

Приложения Workshop

С сайтов издательств «Питер» можно загрузить демонстрационные приложения Workshop для обсуждаемых тем. Приложения оформлены в виде апплетов Java, работающих в большинстве современных браузеров. (За дополнительной информацией обращайтесь к приложению А.) Приложения Workshop строят графические схемы, которые показывают, как работает алгоритм в режиме «замедленной съемки». Например, в одном из приложений при каждом нажатии кнопки на гисто- грамме выполняется очередной шаг процесса сортировки столбцов по возрастанию. Также выводятся значения переменных, задействованных в алгоритме сортировки, чтобы при выполнении алгоритма было точно видно, как работает программный код. Текстовые сообщения поясняют, что происходит в данный момент.

Другое приложение моделирует двоичное дерево. При помощи стрелок, пере- мещающихся по дереву вверх-вниз, пользователь следит за тем, что происходит при вставке или удалении узла из дерева. В книге используется более 20 приложений Workshop — не менее одного для каждой из основных тем.

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

Приложения Workshop являются автономными графическими программами. Их можно использовать как обучающие средства, дополняющие материал книги. Не путайте приложения Workshop с примерами кода, приводимыми в тексте книги, — о них будет рассказано ниже.

Для кого написана эта книга

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

Что необходимо знать читателю

От читателя требуется только одно — владение каким-либо языком программирования.

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

Конечно, если читатель уже знаком с Java, это пойдет ему только на пользу. Также пригодится знание C++, так как синтаксис Java строился на базе C++. Для наших программ различия между этими языками несущественны (если не считать столь полезного исчезновения указателей); они будут кратко рассмотрены в главе 1.

Необходимые программы

Для запуска приложений Workshop вам понадобится браузер — например, Microsoft Internet explorer или netscape . Также может пригодиться программа для просмотра апплетов. Такие программы входят в комплект многих систем программирования на Java.

Для запуска примеров программ понадобится окно командной строки в Microsoft Windows или аналогичная консольная среда.

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

Как организован материал книги

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