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

СТРУКТУРЫ ДАННЫХИ АЛГОРИТМЫ.5•'DATA STRUCTURESAMD ALGORITHMSALFRED V. AHOBell LaboratoriesMurray Hill, New JerseyJOHN E. HOPKROFTCornell UniversityIthaca, New YorkJEFFREY D. ULLMANStanford UniversityStanford, CaliforniaVЛADDISON-WESLEY PUBLISHING COMPANYReading, Massachusetts » Menlo Park, CaliforniaLondon » Amsterdam » Don Mills, Ontario » SydneyСТРУКТУРЫ ДАННЫХИ АЛГОРИТМЫАЛЬФРЕД в. АХО.дBell LaboratoriesМуррей-Хилл, Нью-Джерси, .o{ТЧОЯЛЧСДЖОН Э. ХОПКРОФТКорнеллский университетИтака, Нью-ЙоркДЖЕФФРИ Д. УЛЬМАНСтанфордский университетСтамфорд, Калифорния, •....':Издательский дом "Вильяме"Москва» Санкт-Петербург»Киев2003<^ хББК 32.973.26-018.2я75А95УДК 681.3.07Издательский дом "Вильяме"Зав.

редакцией С. Н. Тригуб. ,,:-•.--•-.Перевод с английского и редакция канд. физ.-мат. наук А. А. Минъко• • - • . , - , ,По общим вопросам обращайтесь в Издательский дом "Вильяме"по адресу: info@williamspublishing.com, http://www.williamspublishing.com-','";s!t: *»„- . • , - . . - , - • , <:,...'• ..; _ -•"i.• - _ ,*i ' ' ' - ' • ' • - , ' • •i ••,.•tj 'i. .

. . . .Axo, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д.А95Структуры данных и алгоритмы. : Пер. с англ. : М. : Издательскийдом "Вильяме", 2003. — 384 с. : ил. — Парал. тит. англ.ISBN 5-8459-0122-7 (рус.)В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ.Показаны разнообразные реализации абстрактных типов данных, начиная отстандартных списков, стеков, очередей и заканчивая множествами и отображениями, которые используются для неформального описания и реализации алгоритмов. Две главы книги посвящены методам анализа и построения алгоритмов;приведено и исследовано множество различных алгоритмов для работы с графами, внутренней и внешней сортировки, управления памятью.Книга не требует от читателя специальной подготовки, только предполагаетего знакомство с какими-либо языками программирования высокого уровня, такими как Pascal. Вместе с тем она будет полезна специалистам по разработкепрограмм и алгоритмов и может быть использована как учебное пособие длястудентов и аспирантов, специализирующихся в области компьютерных наук.ББК 32.973.26-018.2Я75Все названия программных продуктов являются зарегистрированными торговыми марками соответствующих фирм.Никакая часть настоящего издания ни в каких целях не может быть воспроизведена вкакой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на это нетписьменного разрешения издательства Addison-Wesley Publishing Company, Inc.Rights to this book were obtained by arrangement with Addison-Wesley Longman, Inc.Russian language edition published by Williams Publishing House according to theAgreement with R&I Enterprises International, Copyright © 2000Издательство выражает признательность Дмитрию Владимировичу Виленскому за информационную поддержкуISBN 5-8459-0122-7 (рус.)ISBN 0-201-00023-7 (англ.)) Издательский дом "Вильяме", 2000) Addison-Wesley Publishing Company, Inc.ОглавлениеГЛАВА 1.

Построение и анализ алгоритмов15ГЛАВА 2. Основные абстрактные типы данных45ГЛАВА 3. Деревья> • •т то- (' •77ГЛАВА 4. Основные операторы множеств103ГЛАВА 5. Специальные методы представления множеств146ГЛАВА 6. Ориентированные графы183.ГЛАВА 7. Неориентированные графы208ГЛАВА 8. Сортировка228ГЛАВА 9. Методы анализа алгоритмов265ГЛАВА 10. Методы разработки алгоритмов276ГЛАВА 11.

Структуры данных и алгоритмы для внешнейпамяти311ГЛАВА 12. Управление памятью339Список литературы369СОДЕРЖАНИЕ7Содержание5.3. Нагруженные деревья 'Узлы нагруженного дерева как АТДПредставление узлов нагруженного дерева посредством списковЭффективность структуры данных нагруженных деревьев5.4. Реализация множеств посредством сбалансированных деревьевВставка элемента в 2-3 деревоУдаление элемента из 2-3 дереваТипы данных для 2-3 деревьевРеализация оператора INSERTРеализация оператора DELETE5.5. Множества с операторами MERGE и FINDПростая реализация АТД MFSETБыстрая реализация АТД MFSETРеализация АТД MFSET посредством деревьевСжатие путейФункция а(п),;',, 5.6. АТД с операторами MERGE и SPLITЗадача наибольшей общей подпоследовательностиАнализ времени выполнения алгоритма нахождения НОПУпражненияБиблиографические примечанияГЛАВА 6. Ориентированные графы'.6.1.

Основные определения6.2. Представления ориентированных графовАТД для ориентированных графов6.3. Задача нахождения кратчайшего путиОбоснование алгоритма ДейкстрыВремя выполнения алгоритма Дейкстры6.4. Нахождение кратчайших путей между парами вершинСравнение алгоритмов Флойда и ДейкстрыВывод на печать кратчайших путейТранзитивное замыканиеНахождение центра ориентированного графа6.5. Обход ориентированных графовАнализ процедуры поиска в глубинуГлубинный остовный лесОриентированные ациклические графыПроверка ацикличности орграфаТопологическая сортировкаСильная связностьУпражненияБиблиографические примечанияГЛАВА 7. Неориентированные графы^7.1.

Основные определенияПредставление неориентированных графов7.2. Остовные деревья минимальной стоимостиСвойство остовных деревьев минимальной стоимостиАлгоритм ПримаАлгоритм Крускала7.3. Обход неориентированных графовПоиск в глубинуПоиск в ширину7.4. Точки сочленения и двусвязные компоненты8,. '152154156157.158159161162162166167168169172173174175175177179181183183184186187189191191193193194195196197198200201202203205207208208210211211212214217217218220СОДЕРЖАНИЕ7.5. Паросочетания графовУпражненияБиблиографические примечанияГЛАВА 8. Сортировка8.1. Модель внутренней сортировки8.2.

Простые схемы сортировкиСортировка вставкамиСортировка посредством выбораВременная сложность методов сортировкиПодсчет перестановокОграниченность простых схем сортировки8.3. Быстрая сортировкаВременная сложность быстрой сортировкиВремя выполнения быстрой сортировки в среднемРеализация алгоритма быстрой сортировки8.4.

Пирамидальная сортировкаАнализ пирамидальной сортировки8.5. "Карманная" сортировкаАнализ "карманной" сортировкиСортировка множеств с большими значениями ключейОбщая поразрядная сортировкаАнализ поразрядной сортировки8.6. Время выполнения сортировок сравнениямиДеревья решенийРазмер дерева решенийАнализ времени выполнения в среднем8.7. Порядковые статистикиВариант быстрой сортировкиЛинейный метод нахождения порядковых статистикСлучай равенства некоторых значений ключейУпражненияБиблиографические примечанияГЛАВА 9.

Методы анализа алгоритмов9.1. Эффективность алгоритмов9.2. Анализ рекурсивных программ9.3. Решение рекуррентных соотношенийОценка решений рекуррентных соотношенийОценка решения рекуррентного соотношения методом подстановки9.4. Общее решение большого класса рекуррентных уравненийОднородные и частные решенияМультипликативные функцииДругие управляющие функцииУпражненияБиблиографические примечанияГЛАВА 10. Методы разработки алгоритмов10.1. Алгоритмы "разделяй и властвуй"Умножение длинных целочисленных значенийСоставление графика проведения теннисного турнираБаланс подзадач10.2. Динамическое программированиеВероятность победы в спортивных турнирахЗадача триангуляцииСОДЕРЖАНИЕ222225227228228229231232,233233234235238240243244246247249250252253254254256257258258259261261264265265266267268269270271271;273,.2752762762772792802802812839Поиск решений на основе таблицы10.3.

"Жадные" алгоритмы"Жадные" алгоритмы как эвристики10.4. Поиск с возвратомФункции выигрышаРеализация поиска с возвратомАльфа-бета отсечениеМетод ветвей и границОграничения эвристических алгоритмов10.5. Алгоритмы локального поискаЛокальные и глобальные оптимальные решенияЗадача коммивояжераРазмещение блоковУпражненияБиблиографические примечания.ГЛАВА 11. Структуры данных и алгоритмы для внешнейпамяти11.1. Модель внешних вычисленийСтоимость операций со вторичной памятью11.2. Внешняя сортировкаСортировка слияниемУскорение сортировки слияниемМинимизация полного времени выполненияМногоканальное слияниеМногофазная сортировкаКогда скорость ввода-вывода не является "узким местом"Схема с шестью входными буферамиСхема с четырьмя буферами11.3.

Хранение данных в файлахПростая организация данныхУскорение операций с файламиХешированные файлыИндексированные файлыНесортированные файлы с плотным индексомВторичные индексы11.4. Внешние деревья поискаРазветвленные деревья поискаВ-деревьяПоиск записейВставка записейУдаление записей,Время выполнения операций с В-деревомСравнение методовУпражненияБиблиографические примечания311311312313313316316317318319320321323324325325327328329330330330331331332333334335338ГЛАВА 12. Управление памятью33912.1.

Проблемы управления памятью12.2. Управление блоками одинакового размераКонтрольные счетчики12.3. Алгоритмы чистки памяти для блоков одинакового размераСборка на местеАлгоритм Дойча : Шорра : Уэйта без использования поля back10288288289291293294295296298302303303306308310339343344344346351СОДЕРЖАНИЕ12.4.