Структуры данных и алгоритмы, страница 2

Выделение памяти для объектов разного размераФрагментация и уплотнение пустых блоковВыбор свободных блоков12.5. Методы близнецовРаспределение блоковВыделение блоковВозврат блоков в свободное пространство12.6. Уплотнение памяти, -.-,Задача уплотнения памятиi^fre ;<Алгоритм Морриса- •Упражнения^.... . , : . . . , .Библиографические примечания-ЯРСписок литературы369Предметный указатель' - • г-..л":^..<СОДЕРЖАНИЕ. - - Ж*Г: " • • : , . • .

. "352353357359360361362363364365366^68iIM'lM.-.,.;.., ; >v,r c r . f-,•"'375! | . №11MJПредисловиеВ этой книге описаны структуры данных и алгоритмы, которые являются фундаментом современного компьютерного программирования. Основу данной книги составляют первые шесть глав нашей ранее изданной книги The Design and Analysis ofComputer Algorithms1. Мы расширили ее содержание, включив материал по алгоритмам внешнего хранения и управлению памятью.

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

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

В начале книги алгоритмы часто будут представлены как в абстрактной форме, так и на языке Pascal. Это сделано для того, чтобы показать весь спектр проблем при решении практических задач: от проблемы формализации задачи до проблем, возникающих во время выполнения законченной программы. Алгоритмы,которые мы представляем, можно реализовать на любых языках программирования высокого уровня.Содержание книгиВ главе 1 содержатся вводные замечания и обсуждаются реализации процесса исходная задача — готовая программа и роль абстрактных типов данных в этом процессе.

Здесь также можно познакомиться с математическим аппаратом, необходимым для оценивания времени выполнения алгоритмов.В главе 2 рассматриваются традиционные структуры списков, стеков и очередей,а также отображения, которые являются абстрактным типом данных, основанным наматематическом понятии функции. В главе 3 вводятся деревья и основные структуры данных, которые эффективно поддерживают различные операторы, выполняемыенад деревьями.В главах 4, 5 рассмотрено большое количество абстрактных типов данных,основанных на математической модели множеств. Достаточно глубоко исследованы словари и очереди с приоритетами. Рассмотрены стандартные реализацииэтих абстрактных типов данных, такие как хеш-таблицы, двоичные деревья по1Существует перевод этой книги на русский язык: Построение и анализ вычислительныхалгоритмов. — М., "Мир", 1979.

— Прим.. ред.12ПРЕДИСЛОВИЕиска, частично упорядоченные деревья, 2-3 деревья и др. Более сложный материал помещен в главу 5.Главы 6, 7 содержат материал, относящийся к графам; ориентированные графырассмотрены в главе 6, а неориентированные — в главе 7. Эти главы начинают раздел книги, который больше посвящен алгоритмам, чем структурам данных, хотя мыпродолжаем обсуждать основные структуры данных, подходящие для представленияграфов. В этих главах представлено большое количество алгоритмов для работы сграфами, включая алгоритмы поиска в глубину, нахождения минимального остовного дерева, кратчайших путей и максимальных паросочетаний.В главе 8 рассмотрены основные алгоритмы внутренней сортировки: быстрая сортировка, пирамидальная сортировка, "карманная" сортировка, а также более простые (и менее эффективные) методы, например метод сортировки вставками.

В концеглавы описаны алгоритмы с линейным временем выполнения для нахождения медиан и других порядковых статистик..-rsВ главе 9 обсуждаются асимптотические методы анализа рекурсивных программ.Здесь, конечно же, рассмотрены методы решения рекуррентных соотношении.В главе 10 сравнительно кратко (без глубокого анализа) рассмотрены методы разработки алгоритмов, включая методы декомпозиции, динамическое программирование,алгоритмы локального поиска, и различные формы организации деревьев поиска.Последние две главы посвящены организации внешнего хранения и управлениюпамятью. Глава 11 охватывает методы внешней сортировки и организацию внешнегохранения данных, включая В-деревья и индексные структуры.Материал по управлению памятью, содержащийся в главе 12, условно можно разбить на четыре части, в зависимости от того, являются ли блоки памяти фиксированной или переменной длины, а также от того, явно или неявно осуществляетсяочистка памяти.Материал этой книги авторы использовали в программе лекционных курсов поструктурам данным и алгоритмам в Колумбийском, Корнеллском и Станфордскомуниверситетах как для студентов, так и для аспирантов.

Например, предварительную версию этой книги использовали в Станфордском университете как основу 10недельного курса по структурам данных для студентов первого года обучения. Этоткурс включал материал глав 1-4, 9, 10, 12 и частично из глав 5-7.УпражненияВ конце каждой главы приведено много упражнений различной степени сложности.

С помощью многих из них можно просто проверить усвоение изложенного материала. Некоторые упражнения требуют дополнительных усилий и размышлений,они помечены одной звездочкой. Упражнения, помеченные двумя звездочками,рассчитаны на студентов старших курсов и аспирантов. Библиографические примечания в конце каждой главы предлагают ссылки на дополнительную литературу.ПРЕДИСЛОВИЕ13БлагодарностиМы хотим выразить благодарность компании Bell Laboratories за предоставлениепревосходных коммуникационных средств и средств подготовки текстов (основанныхна UNIX™), которые позволили легко подготовить рукопись географически разделенным авторам.

Многие наши коллеги, прочитав различные части рукописи, сделали ценные замечания. Особенно мы хотим поблагодарить за полезные предложенияЭда Бекхама (Ed Beckham), Джона Бентли (Jon Bentley), Кеннета Чу (Kenneth Chu),Джанет Кореи (Janet Coursey), Хенка Кокса (Hank Сох), Нейла Иммермана (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.:14ПРЕДИСЛОВИЕГЛАВА 1Построениеи анализалгоритмовПроцесс создания компьютерной программы для решения какой-либо практической задачи состоит из нескольких этапов: формализация и создание технического задания на исходную задачу; разработка алгоритма решения задачи; написание, тестирование, отладка и документирование программы; получение решения исходной задачи путем выполнения законченной программы, В данной главемы покажем подходы к реализации этих этапов, а в последующих рассмотрималгоритмы и структуры данных как строительные блоки создаваемых компьютерных программ.1.1.