Книга: Хусаинов Б. С. «Структуры и алгоритмы обработки данных»

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

Содержание:

ПРЕДИСЛОВИЕ...... 8 Глава 1. СТРУКТУРЫ ДАННЫХ И СТРУКТУРЫ ХРАНЕНИЯ...... 11 1. 1. Алгоритмы и данные...... 11 1. 2. Типы данных...... 21 1. 3. Структуры хранения данных...... 24 1. 3. 1. Вектор...... 28 1. 3. 2. Список...... 31 1. 3. 3. Сеть...... 34 1. 4. Массивы...... 35 1. 4. 1. Структуры данных массивов...... 35 1. 4. 2. Структуры хранения массивов...... 36 1. 4. 3. Свободные массивы...... 37 1. 4. 4. Треугольные и разреженные матрицы...... 39 1. 4. 5. Особенности использования массивов в языке Си...... 42 1. 5. Строки и операции над ними...... 62 1. 6. Записи и операции над ними...... 79 1. 7. Множества...... 85 1. 7. 1. Множества в математике...... 85 1. 7. 2. Множества в языках программирования...... 86 1. 7. 3. Множество как обобщенное понятие структур данных...... 86 Упражнения...... 87 Глава 2. ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ...... 89 2. 1. Стеки...... 89 2. 1. 1. Структуры стека...... 89 2. 1. 2. Операции над стеками...... 91 2. 1. 3. Применение стеков при разработке приложений...... 97 2. 2. Очереди...... 115 2. 3. Деки...... 122 2. 4. Операции над линейными списками...... 123 2. 5. Программа для работы со списками 130 Упражнения...... 143 Глава 3. НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ...... 144 3. 1. Рекурсии...... 144 3. 2. Общие сведения о деревьях...... 149 3. 3. Представление m-арного дерева бинарным деревом...... 152 3. 4. Леса...... 153 3. 5. Представление деревьев в памяти ЭВМ...... 153 3. 6. Идеально сбалансированное бинарное дерево...... 155 3. 7. Бинарные (двоичные) деревья поиска...... 159 3. 8. Сбалансированные деревья поиска...... 160 3. 8. 1. Сбалансированные АВЛ-деревья поиска...... 161 3. 8. 2. Рандомизированные деревья поиска...... 162 3. 9. Оптимальные деревья поиска...... 162 3. 10. Операции над деревьями...... 163 3. 11. Программа для работы с бинарными деревьями...... 177 3. 12. Особенности крупномасштабных деревьев...... 197 3. 13. 5-деревья...... 198 3. 14. Особенности операций над Д-деревьями...... 199 3. 15. Разновидности Д-дерева...... 201 3. 16. Программа для работы с Д-деревом 203 Упражнения...... 210 Глава 4. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ ВЫБОРА...... 211 4. 1. Способы решения задач...... 211 4. 2. Применение рекурсий...... 213 4. 3. Дерево решений...... 214 4. 4. Переборные задачи...... 216 4. 5. Алгоритмы с возвратом...... 221 4. 6. Метод ветвей и границ...... 228 4. 7. Метод проб и ошибок...... 231 4. 8. Динамическое программирование...... 236 4. 9. Алгоритмы сжатия данных...... 237 Упражнения...... 245 Глава 5. СОРТИРОВКА ДАННЫХ...... 246 5. 1. Общие понятия...... 246 5. 2. Внутренняя сортировка...... 247 5. 2. 1. Сортировка методом прямого включения...... 247 5. 2. 2. Сортировка методом прямого выбора...... 251 5. 2. 3. Сортировка методом прямого обмена (сортировка методом пузырька)...... 253 5. 2. 4. Шейкерная сортировка...... 254 5. 3. Быстрые (улучшенные) методы сортировки...... 256 5. 3. 1. Метод Шелла...... 256 5. 3. 2. Сортировка с помощью дерева (пирамиды)...... 259 5. 3. 3. Быстрая сортировка Хоара (сортировка разделением)...... 268 5. 4. Поразрядная («карманная») сортировка...... 273 5. 5. Порядковые статистики...... 274 5. 6. Внешняя сортировка (сортировка последовательностей)...... 276 5. 6. 1. Особенности внешней сортировки...... 276 5. 6. 2. Прямое слияние...... 277 5. 6. 3. Естественное слияние...... 291 5. 6. 4. Сбалансированное многопутевое слияние...... 297 5. 6. 5. Многофазная сортировка...... 299 5. 6. 6. Формирование и распределение начальных серий...... 301 Упражнения...... 303 Глава 6. ТАБЛИЧНЫЕ СТРУКТУРЫ...... 304 6. 1. Виды таблиц...... 304 6. 2. Условия поиска...... 305 6. 3. Линейные таблицы...... 307 6. 3. 1. Поиск в неупорядоченных таблицах...... 307 6. 3. 2. Поиск в упорядоченных таблицах...... 309 6. 3. 3. Некоторые рекомендации по работе с линейными таблицами...... 312 6. 4. Логически связанные таблицы...... 319 6. 5. Древовидные таблицы...... 326 6. 5. 1. Сравнение табличной и древовидной структур...... 326 6. 5. 2. Представление древовидной таблицы...... 327 6. 5. 3. Основные операции и возможная структура древовидной таблицы...... 328 6. 5. 4. Пример программы для работы с древовидной таблицей...... 334 6. 6. Таблицы с вычисляемыми входами...... 344 6. 6. 1. Понятие таблицы с вычисляемыми входами...... 344 6. 6. 1. Выбор функции расстановки...... 346 6. 6. 3. Разрешение коллизий методом цепочек...... 349 6. 6. 4. Методы открытой адресации...... 363 6. 6. 5. Особенности алгоритмов удаления записей из таблицы...... 365 6. 6. 6. Переразмещение (рехеширование) таблицы...... 366 Упражнения...... 366 Глава 7. ФАЙЛЫ...... 368 7. 1. Общие сведения...... 368 7. 2. Последовательные файлы...... 371 7. 3. Библиотечные файлы...... 372 7. 4. Файлы прямого доступа...... 372 7. 5. Индексно-последовательные файлы...... 372 7. 6. Файлы VSAM...... 378 7. 7. Файлы в MS DOS...... 381 7. 8. Файлы NTFS...... 384 7. 9. Работа с файлами в Си...... 390 7. 9. 1. Ввод-вывод потока...... 390 7. 9. 2. Ввод-вывод нижнего уровня...... 392 7. 9. 3. Пример программы работы с файлом...... 392 Упражнение...... 399 Глава 8. АЛГОРИТМЫ НА ГРАФАХ...... 400 8. 1. Основные определения...... 400 8. 2. Представление графов...... 402 8. 2. 1. Матрица смежности...... 403 8. 2. 2. Векторы смежности...... 406 8. 2. 3. Списки смежности...... 408 8. 2. 4. Матрица инцидентности...... 412 8. 3. Пути в графе...... 414 8. 4. Путевая матрица (матрица достижимости)...... 415 8. 5. Минимальная путевая матрица...... 417 8. 6. Кратчайшие пути...... 420 8. 6. 1. Алгоритм Дейкстры...... 421 8. 6. 2. Алгоритм Флойда...... 426 8. 7. Остовные деревья графа...... 430 8. 8. Обходы графов. Поиск в глубину и поиск в ширину...... 431 8. 9. Остовное дерево наименьшей стоимости (минимального веса)...... 441 8. 9. 1. Алгоритм Прима...... 441 8. 9. 2. Алгоритм Крускала...... 445 8. 10. Упорядочение графа (топологическая сортировка)...... 499 Упражнения...... 453 ПРИЛОЖЕНИЕ...... 454 ЛИТЕРАТУРА...... 462

Издательство: "Финансы и статистика" (2004)

ISBN: 5279027758