Предисловие
Эта книга представляет собой описание структур данных и алгоритмов, которые являются фундаментом современного компьютерного программирования. Основу данной книги составляют первые шесть глав нашей ранее изданной книги The Design and Analysis of Computer Algorithms . Мы расширили ее содержание, включив материал по алгоритмам внешнего хранения и управлению памятью. Как и предыдущая, эта книга может составить основу учебного курса по структурам данным и алгоритмам. Мы не требуем от читателя специальной подготовки, только предполагаем его знакомство с какими-либо языками программирования высокого уровня, такими как Pascal.
Мы попытались осветить структуры данных и алгоритмы в более широком контексте решения задач с использованием вычислительной техники, а также использовали абстрактные типы данных для неформального описания и реализации алгоритмов. И хотя сегодня абстрактные типы данных только начинают применять в современных языках программирования, авторы считают, что они являются полезным инструментом при разработке программ независимо от применяемого языка программирования.
Мы также постоянно подчеркиваем и внедряем идею вычисления и оценки времени выполнения алгоритмов (временную сложность алгоритмов) как составную часть процесса компьютерного решения задач. В этом отражается наша надежда на то, что программисты осознают, что при решении задач прогрессирующе больших размеров особое значение имеет временная сложность выбранного алгоритма, а не возможности новых поколений аппаратных средств.
Представление алгоритмов
Мы используем язык Pascal для представления описываемых алгоритмов и структур данных просто потому, что это широко известный язык программирования. В начале книги алгоритмы часто будут представлены как в абстрактной форме, так и на языке Pascal. Это сделано для того, чтобы показать весь спектр проблем при решении практических задач: от проблемы формализации задачи до проблем, возникающих во время выполнения законченной программы. Алгоритмы, которые мы представляем, можно реализовать на любых языках программирования высокого уровня.
Содержание книги
В главе 1 содержатся вводные замечания и обсуждаются реализации процесса исходная задача — готовая программа и роль абстрактных типов данных в этом процессе. Здесь также можно познакомиться с математическим аппаратом, необходимым для оценивания времени выполнения алгоритмов.
В главе 2 рассматриваются традиционные структуры списков, стеков и очередей, а также отображения, которые являются абстрактным типом данных, основанным на математическом понятии функции. В главе 3 вводятся деревья и основные структуры данных, которые эффективно поддерживают различные операторы, выполняемые над деревьями.
В главах 4, 5 рассмотрено большое количество абстрактных типов данных, основанных на математической модели множеств. Достаточно глубоко исследованы словари и очереди с приоритетами. Рассмотрены стандартные реализации этих абстрактных типов данных, такие как хеш-таблицы, двоичные деревья поиска, частично упорядоченные деревья, 2-3 деревья и др. Более сложный материал помещен в главу 5.
Главы 6, 7 содержат материал, относящийся к графам; ориентированные графы рассмотрены в главе 6, а неориентированные — в главе 7. Эти главы начинают раздел книги, который больше посвящен алгоритмам, чем структурам данных, хотя мы продолжаем обсуждать основные структуры данных, подходящие для представления графов. В этих главах представлено большое количество алгоритмов для работы с графами, включая алгоритмы поиска в глубину, нахождения минимального остовного дерева, кратчайших путей и максимальных паросочетаний.
В главе 8 рассмотрены основные алгоритмы внутренней сортировки: быстрая сортировка, пирамидальная сортировка, "карманная" сортировка, а также более простые (и менее эффективные) методы, например метод сортировки вставками. В конце главы описаны алгоритмы с линейным временем выполнения для нахождения медиан и других порядковых статистик.
В главе 9 обсуждаются асимптотические методы анализа рекурсивных программ. Здесь, конечно же, рассмотрены методы решения рекуррентных соотношений.
В главе 10 сравнительно кратко (без глубокого анализа) рассмотрены методы разработки алгоритмов, включая методы декомпозиции, динамическое программирование, алгоритмы локального поиска и различные формы организации деревьев поиска.
Последние две главы посвящены организации внешнего хранения и управлению памятью. Глава 11 охватывает методы внешней сортировки и организацию внешнего хранения данных, включая В-деревья и индексные структуры.
Материал по управлению памятью, содержащийся в главе 12, условно можно разбить на четыре части, в зависимости от того, являются ли блоки памяти фиксированной или переменной длины, а также от того, явно или неявно осуществляется очистка памяти.
Материал этой книги авторы использовали в программе лекционных курсов по структурам данным и алгоритмам в Колумбийском, Корнельском и Станфордском университетах как для студентов, так и для аспирантов. Например, предварительную версию этой книги использовали в Станфордском университете как основу 10-недельного курса по структурам данных для студентов первого года обучения. Этот курс включал материал глав 1–4, 9, 10, 12 и частично из глав 5–7.
Упражнения
В конце каждой главы приведено много упражнений различной степени сложности. С помощью многих из них можно просто проверить усвоение изложенного материала. Некоторые упражнения требуют дополнительных усилий и размышлений, они помечены одной звездочкой. Упражнения, помеченные двумя звездочками, рассчитаны на студентов старших курсов и аспирантов. Библиографические примечания в конце каждой главы предлагают ссылки на дополнительную литературу.
Благодарности
Мы хотим выразить благодарность компании Bell Laboratories за предоставление превосходных коммуникационных средств и средств подготовки текстов (основанных на UNIX), которые позволили легко подготовить рукопись географически разделенным авторам. Многие наши коллеги, прочитав различные части рукописи, сделали ценные замечания. Особенно мы хотим поблагодарить за полезные предложения Эда Бекхама (Ed Beckham), Джона Бентли (Jon Bentley), Кеннета Чу (Kenneth Chu), Джанет Корси (Janet Coursey), Хенка Кокса (Hank Cox), Нейла Иммермана (Neil Immerman), Брайана Кернигана (Brian Kernighan), Стива Мехени (Steve Mahaney), Крейга Мак-Мюррей (Craig McMurray), Альберто Мендельзона (Alberto Mendelzon), Элистер Моффат (Alistair Moffat), Джеффа Нотона (Jeff Naughton), Керри Нимовичер (Kerry Nemovicher), Пола Ниэмки (Paul Niamkey), Ёшио Оно (Yoshio Ohno), Роба Пайка (Rob Pike), Криса Руэна (Chris Rouen), Мориса Шлумбергера (Maurice Schlumberger), Стенли Селкова (Stanley Selkow), Ченгай Ши (Chengya Shih), Боба Тарьяна (Bob Tarjan), В. Ван Снайдера (W. Van Snyder), Питера Вейнбергера (Peter Weinberger) и Энтони Ерекериса (Anthony Yeracaris). Наконец, мы хотим принести огромную благодарность г-же Клейр Мецгер (Claire Metzger) за профессиональную помощь при подготовке рукописи к печати.
A.V.A.
J.E.H.
J.D.U.
