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

Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман

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

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

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

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

Издательство: Вильямс, 2010 г.

ISBN 978-5-8459-1610-5, 0-201-00023-7

Количество страниц: 400.

Содержание книги «Структуры данных и алгоритмы»:

12 Предисловие
- 12 Представление алгоритмов
- 12 Содержание книги
- 13 Упражнения
- 14 Благодарности
15 ГЛАВА 1. Построение и анализ алгоритмов
- 15 1.1. От задачи к программе
  - 16 Алгоритмы
  - 20 Псевдоязык и пошаговая «кристаллизация» алгоритмов
  - 22 Резюме
- 23 1.2. Абстрактные типы данных
  - 23 Определение абстрактного типа данных
- 25 1.3. Типы данных, структуры данных и абстрактные типы данных
  - 26 Указатели и курсоры
- 28 1.4. Время выполнения программ
  - 28 Измерение времени выполнения программ
  - 29 Асимптотические соотношения
  - 30 Ограниченность показателя степени роста
  - 32 Немного соли
- 32 1.5. Вычисление времени выполнения программ
  - 35 Вызовы процедур
  - 36 Программы с операторами безусловного перехода
  - 37 Анализ программ на псевдоязыке
- 37 1.6. Практика программирования
- 39 1.7. Расширение языка Pascal
- 40 Упражнения
  - 44 Библиографические замечания
45 ГЛАВА 2. Основные абстрактные типы данных
- 45 2.1. Абстрактный тип данных «Список»
- 48 2.2. Реализация списков
  - 48 Реализация списков посредством массивов
  - 50 Реализация списков с помощью указателей
  - 54 Сравнение реализаций
  - 55 Реализация списков на основе курсоров
  - 58 Дважды связные списки
- 59 2.3. Стеки
  - 60 Реализация стеков с помощью массивов
- 62 2.4. Очереди
  - 63 Реализация очередей с помощью указателей
  - 65 Реализация очередей с помощью циклических массивов
- 68 2.5. Отображения
  - 68 Реализация отображений посредством массивов
  - 69 Реализация отображений посредством списков
- 70 2.6. Стеки и рекурсивные процедуры
  - 72 Исключение «концевых» рекурсий
  - 72 Полное исключение рекурсий
- 74 Упражнения
  - 78 Библиографические примечания
79 ГЛАВА 3. Деревья
- 79 3.1. Основная терминология
  - 80 Порядок узлов
  - 81 Прямой, обратный и симметричный обходы дерева
  - 83 Помеченные деревья и деревья выражений
  - 84 Вычисление «наследственных» данных
- 84 3.2. Абстрактный тип данных TREE
- 86 3.3. Реализация деревьев
  - 87 Представление деревьев с помощью массивов
  - 88 Представление деревьев с использованием списков сыновей
  - 90 Представление левых сыновей и правых братьев
- 93 3.4. Двоичные деревья
  - 94 Представление двоичных деревьев
  - 95 Пример: коды Хаффмана
  - 101 Реализация двоичных деревьев с помощью указателей
- 101 Упражнения
  - 104 Библиографические замечания
105 ГЛАВА 4. Основные операторы множеств
- 105 4.1. Введения в множества
  - 106 Система обозначений для множеств
  - 107 Операторы АТД, основанные на множествах
- 107 4.2. АТД с операторами множеств
- 111 4.3. Реализация множеств посредством двоичных векторов
- 113 4.4. Реализация множеств посредством связанных списков
- 116 4.5. Словари
- 118 4.6. Реализации словарей
- 119 4.7. Структуры данных, основанные на хеш-таблицах
  - 120 Открытое хеширование
  - 123 Закрытое хеширование
- 126 4.8. Оценка эффективности хеш-функций
  - 127 Анализ закрытого хеширования
  - 129 «Случайные» методики разрешения коллизий
  - 131 Реструктуризация хеш-таблиц
- 131 4.9. Реализация АТД для отображений
- 133 4.10. Очереди с приоритетами
- 135 4.11. Реализация очередей с приоритетами
  - 136 Реализация очереди с приоритетами посредством частично упорядоченных деревьев
  - 139 Реализация частично упорядоченных деревьев посредством массивов
- 141 4.12. Некоторые структуры сложных множеств
  - 142 Отношения «многие-ко-многим» и структура мультисписков
  - 143 Структуры мультисписков
  - 146 Эффективность двойных структур данных
- 148 Упражнения
  - 150 Библиографические примечания
151 ГЛАВА 5. Специальные методы представления множеств
- 151 5.1. Деревья двоичного поиска
- 155 5.2. Анализ времени выполнения операторов
  - 157 Эффективность деревьев двоичного поиска
- 157 5.3. Нагруженные деревья
  - 160 Узлы нагруженного дерева как АТД
  - 162 Представление узлов нагруженного дерева посредством списков
  - 162 Эффективность структуры данных нагруженных деревьев
- 163 5.4. Реализация множеств посредством сбалансированных деревьев
  - 165 Вставка элемента в 223 дерево
  - 166 Удаление элемента из 223 дерева
  - 167 Типы данных для 223 деревьев
  - 168 Реализация оператора INSERT
  - 172 Реализация оператора DELETE
- 174 5.5. Множества с операторами MERGE и FIND
  - 175 Простая реализация АТД MFSET
  - 176 Быстрая реализация АТД MFSET
  - 179 Реализация АТД MFSET посредством деревьев
  - 180 Сжатие путей
  - 181 Функция α(n)
- 182 5.6. АТД с операторами MERGE и SPLIT
  - 182 Задача наибольшей общей подпоследовательности
  - 184 Анализ времени выполнения алгоритма нахождения НОП
- 186 Упражнения
  - 188 Библиографические примечания
189 ГЛАВА 6. Ориентированные графы
- 189 6.1. Основные определения
- 190 6.2. Представления ориентированных графов
  - 192 АТД для ориентированных графов
- 193 6.3. Задача нахождения кратчайшего пути
  - 195 Обоснование алгоритма Дейкстры
  - 196 Время выполнения алгоритма Дейкстры
- 197 6.4. Нахождение кратчайших путей между парами вершин
  - 199 Сравнение алгоритмов Флойда и Дейкстры
  - 199 Вывод на печать кратчайших путей
  - 200 Транзитивное замыкание
  - 201 Нахождение центра ориентированного графа
- 203 6.5. Обход ориентированных графов
  - 204 Анализ процедуры поиска в глубину
  - 204 Глубинный остовный лес
- 206 6.6. Ориентированные ациклические графы
  - 208 Проверка ацикличности орграфа
  - 208 Топологическая сортировка
- 209 6.7. Сильная связность
- 211 Упражнения
  - 213 Библиографические примечания
214 ГЛАВА 7. Неориентированные графы
- 214 7.1. Основные определения
  - 216 Представление неориентированных графов
- 217 7.2. Остовные деревья минимальной стоимости
  - 217 Свойство остовных деревьев минимальной стоимости
  - 218 Алгоритм Прима
  - 220 Алгоритм Крускала
- 223 7.3. Обход неориентированных графов
  - 223 Поиск в глубину
  - 225 Поиск в ширину
- 226 7.4. Точки сочленения и двусвязные компоненты
- 228 7.5. Паросочетания графов
- 232 Упражнения
  - 233 Библиографические примечания
234 ГЛАВА 8. Сортировка
- 234 8.1. Модель внутренней сортировки
- 235 8.2. Простые схемы сортировки
  - 237 Сортировка вставками
  - 238 Сортировка посредством выбора
  - 239 Временная сложность методов сортировки
  - 239 Подсчет перестановок
  - 240 Ограниченность простых схем сортировки
- 241 8.3. Быстрая сортировка
  - 245 Временная сложность быстрой сортировки
  - 247 Время выполнения быстрой сортировки в среднем
  - 249 Реализация алгоритма быстрой сортировки
- 250 8.4. Пирамидальная сортировка
  - 253 Анализ пирамидальной сортировки
- 254 8.5. «Карманная» сортировка
  - 257 Анализ «карманной» сортировки
  - 257 Сортировка множеств с большими значениями ключей
  - 259 Общая поразрядная сортировка
  - 260 Анализ поразрядной сортировки
- 261 8.6. Время выполнения сортировок сравнениями
  - 262 Деревья решений
  - 263 Размер дерева решений
  - 264 Анализ времени выполнения в среднем
- 265 8.7. Порядковые статистики
  - 265 Вариант быстрой сортировки
  - 266 Линейный метод нахождения порядковых статистик
  - 268 Случай равенства некоторых значений ключей
- 269 Упражнения
  - 271 Библиографические примечания
272 ГЛАВА 9. Методы анализа алгоритмов
- 272 9.1. Эффективность алгоритмов
- 273 9.2. Анализ рекурсивных программ
- 274 9.3. Решение рекуррентных соотношений
  - 275 Оценка решений рекуррентных соотношений
  - 276 Оценка решения рекуррентного соотношения методом подстановки
- 277 9.4. Общее решение большого класса рекуррентных уравнений
  - 278 Однородные и частные решения
  - 279 Мультипликативные функции
  - 280 Другие управляющие функции
- 280 Упражнения
  - 282 Библиографические примечания
283 ГЛАВА 10. Методы разработки алгоритмов
- 283 10.1. Алгоритмы «разделяй и властвуй»
  - 284 Умножение длинных целочисленных значений
  - 286 Составление графика проведения теннисного турнира
  - 287 Баланс подзадач
- 287 10.2. Динамическое программирование
  - 288 Вероятность победы в спортивных турнирах
  - 290 Задача триангуляции
  - 295 Поиск решений на основе таблицы
- 295 10.3. «Жадные» алгоритмы
  - 296 «Жадные» алгоритмы как эвристики
- 298 10.4. Поиск с возвратом
  - 300 Функции выигрыша
  - 301 Реализация поиска с возвратом
  - 302 Альфа-бета отсечение
  - 304 Метод ветвей и границ
  - 304 Ограничения эвристических алгоритмов
- 309 10.5. Алгоритмы локального поиска
  - 310 Локальные и глобальные оптимальные решения
  - 310 Задача коммивояжера
  - 313 Размещение блоков
- 315 Упражнения
  - 317 Библиографические примечания
318 ГЛАВА 11. Структуры данных и алгоритмы для внешней памяти
- 318 11.1. Модель внешних вычислений
  - 319 Стоимость операций со вторичной памятью
- 320 11.2. Внешняя сортировка
  - 320 Сортировка слиянием
  - 323 Ускорение сортировки слиянием
  - 323 Минимизация полного времени выполнения
  - 324 Многоканальное слияние
  - 325 Многофазная сортировка
  - 326 Когда скорость ввода-вывода не является «узким местом»
  - 328 Схема с шестью входными буферами
  - 329 Схема с четырьмя буферами
- 331 11.3. Хранение данных в файлах
  - 332 Простая организация данных
  - 332 Ускорение операций с файлами
  - 333 Хешированные файлы
  - 334 Индексированные файлы
  - 336 Несортированные файлы с плотным индексом
  - 336 Вторичные индексы
- 337 11.4. Внешние деревья поиска
  - 337 Разветвленные деревья поиска
  - 338 B-деревья
  - 338 Поиск записей
  - 339 Вставка записей
  - 339 Удаление записей
  - 340 Время выполнения операций с B-деревом
  - 341 Сравнение методов
- 342 Упражнения
  - 345 Библиографические примечания
346 ГЛАВА 12. Управление памятью
- 346 12.1. Проблемы управления памятью
- 350 12.2. Управление блоками одинакового размера
  - 351 Контрольные счетчики
- 351 12.3. Алгоритмы чистки памяти для блоков одинакового размера
  - 353 Сборка на месте
  - 359 Алгоритм Дойча ¦ Шорра ¦ Уэйта без использования поля back
- 360 12.4. Выделение памяти для объектов разного размера
  - 361 Фрагментация и уплотнение пустых блоков
  - 365 Выбор свободных блоков
- 367 12.5. Методы близнецов
  - 368 Распределение блоков
  - 369 Выделение блоков
  - 369 Возврат блоков в свободное пространство
- 371 12.6. Уплотнение памяти
  - 371 Задача уплотнения памяти
  - 373 Алгоритм Морриса
- 374 Упражнения
  - 376 Библиографические примечания
377 Список литературы
383 Предметный указатель

Инструкция как скачать книгу Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман: Структуры данных и алгоритмы в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.