Книга содержит систематическое изложение основ современных методов обработки данных. В ней подробно изучаются информационные структуры, характерные для нечислового применения ЭВМ, такие, как строки, таблицы и файлы. Описываются соответствующие им абстрактные структуры — графы, деревья, списки, стеки и методы их организации в машинной памяти. Специальная глава посвящена сортировке таблиц во внутренней и внешней памяти. Изложение хорошо продумано и богато иллюстрировано примерами. Каждая глава сопровождается упражнениями.
Книга принесет большую пользу как студентам, изучающим программирование, так и специалистам по АСУ, системному программированию, и другим применениям ЭВМ.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Предлагаемую книгу можно считать явной удачей издаваемой в Англии серии монографий по вычислительным машинам и программированию, которая довольно полце представлена в переводах, осуществляемых издательством «Мир». Она является руководством по структурам данных, характерным практически для любых нечисловых применений машин. Ни для кого не секрет, что нечисловые применения ЭВМ далеко превзошли по своему размаху их применение для числент ных расчетов в узком смысле этого слова — особенно в результате широкого развития автоматизированных, систем проектирования, управления, обработки информации, экономических расчетов. Да и в самих численных расчетах роль информационного обслуживания, обработки исходных данных и результатов, организации удобных для пользователя форм общения возросла настолько, что соответствующие программы уже только с большой натяжкой можно считать «числовыми».
Особенно приятно, что книга, посвященная структурам данных, сама имеет стройную и глубоко продуманную структуру. Ясность и систематичность изложения, четкая классификация излагаемых методов, не только облегчают усвоение довольно богатого материала, но и помогают читателю взглянуть на него с единой точки зрения, выявить характерные приемы, научиться применять их в различных контекстах.
Обрабатываемые на вычислительных машинах данные имеют три структуры: конкретную — отражающую их использование в конкретной задаче, абстрактную — отражающую связи, существующие между их отдельными компонентами, и машинную—отражающую представление этих данных в памяти вычислительной машины. Имечнно рассмотрение этих трех типов структур по отдельности, проведение между ними четкого разграничения и последующий анализ их взаимодействия: лозволили автору изложить большое разнообразие методов достаточно просто.
Книга, несомненно, будет полезна как программистам-лрактикам, так и студентам и преподавателям факультетов прикладной математики. . .
Э. 3. Любимский
ОГЛАВЛЕНИЕ
"Предисловие редактора перевода .............. . 5
*Предисловие . . . ...... ..... -. ........ в
-Введение ....... . ........... ..... Ю
I. Абстрактные структуры информации и алгоритмов .......
1.1. Некоторые важные обозначения .......... .... 14
1.2. Индексация и упорядоченность . . . ..... ..... 15
1.3. Строки . ....'.......... ....... 1б
1.4. Графы ............. ; ...... ... 17
1.5. Деревья .................. .... 23
1.6. Стеки и очереди . .................. 29
1.7. Структура алгоритмов ............. .... 30
1.8. Упражнения . . . ' ..... ........... .35
2. Машинные структуры: память и управление .......... 37
2.1. Структура памяти ............ ....... 37
2.1.1. Совокупности квантов памяти ........... 38
2.1.2. Основные отношения между квантами памяти, использующие адресную арифметику ....... ....... 40
2.1.3. Отношения в памяти, использующие сцепление . . . . .41
2.1.4. Распределение памяти и управление памятью ...... 49
2.1.4.1. Выделение памяти без возврата . . . . ." . . .52
2.1.4.2. Блоки фиксированной длины, выделение и возврат
в свободную область ............ 53J
2.1.4.2.1. Основные программы ........ .5$
2.1.4.2.2. Простое восстановление памяти .... 5В
2.1.4.2.3. Сложное восстановление памяти . . . . 6в ,
2.1.4.3. Звенья переменной длины, выделение и возврат в свободную память ...... ....... 58 ••:
2.1.5. Методы реализации работы со звеньями ....... 62
2.1.6. Представление абстрактных структур в памяти ..... 63
2.1.6.1. Представление множеств . ......... 64
2.1.6.2. Представление строк . . . ......... 65
2.1.6.3. Представление графов .......... . . 66
2.1.6.4. Представление деревьев ........... 66
2.1.6.5. Представление стеков .......... . . 66
2.2. Структуры управления ................ 68
2.2.1. Управление на машинном уровне _ , ..... • • • • 68
2.2.2. Управление в языках высокого уровня . . ...... 72
2.3. Упражнения
3. Обработка строк ................ .... 78
3.1. Методы представления строк в памяти ......... .80
3.1.1. Кодирование символов . ........ ...... 80
3.1.2. Представление отдельных строк в памяти,. . . . . . . 82-
3.1.3. Представление совокупностей строк в памяти ..... 85
3.2. Сопоставление строк
3.2.1. Точное сопоставление............... 89
3.2.2. Сопоставление подстрок..............91
3.2.3. Более сложные сопоставления...........92
3.3. Преобразование строк.................94
3.3.1. Объединение и разъединение............95
• 3.3.2. Исключение и включение.............97
3.4. Упражнения.................... 99
4. Файлы и таблицы....................105
4.1. Внутренние таблицы.................108
4.1.1. Последовательные таблицы............110
4.1.1.1. Несортированные последовательные таблицы . .111
4.1.1.2. Сортированные последовательные таблицы . . .118
4.1.1.3. Оценка.................121
4.1.2. Таблицы, организованные как деревья сравнений .... 124
4.1.2.1. Деревья сравнений в векторной памяти с логарифмическим поиском.............126
4.1.2.2. Деревья сравнений в сцепленной памяти . . . . 128
4.1.2.3. Сбалансированные деревья сравнений в сцепленной памяти.................. 136
4.1.3. Таблицы с вычисляемыми адресами.........137
4.1.3.1. Таблицы с непосредственным доступом.....137
4.1.3.2. Перемешанные таблицы...........138
4.1.4. Общие рассмотрения и итоговые оценки.......154
4.2. Внешние файлы............•......156
I 4.2.1. Пакетирование и слияние.............157
4.3. Сложные файлы...................}59
4.4. Упражнения . • • • •-...............lhii
5. Сортировка...............:......168
5.1. Внутренняя сортировка.......,.........170=
5.1.1. Стратегии внутренней сортировки ... . . . . . • .171
5.1.2. Сортировка выборкой...............172
5.1.3. Сортировка включением . . '. ........• . .182
5.1.4. Сортировка распределением............185-
5.1.5. Сортировка слиянием...............189
5.1.6. Оценка методов внутренней сортировки...... . 192
5.2. Внешняя сортировка.................193
5.2.1. Внутренняя сортировка с замещением........197
5.2.2. Сбалансированное многопоточное слияние.......199
5.2.3. Многофазное слияние...............202
5.3. Упражнения .................... 204
Список литературы....................207
Цена: 150руб.
