Книга содержит систематическое изложение основ современных методов обработки данных. В ней подробно изучаются информационные структуры, характерные для нечислового применения ЭВМ, такие, как строки, таблицы и файлы. Описываются соответствующие им абстрактные структуры - графы, деревья, списки, стеки и методы их организации в машинной памяти. Специальная глава посвящена сортировке таблиц во внутренней и внешней памяти. Изложение хорошо продумано и богато иллюстрировано примерами. Каждая глава сопровождается упражнениями. Книга принесет большую пользу как студентам, изучающим программирование, так и специалистам по АСУ, системному программированию и другим применениям ЭВМ.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Предлагаемую книгу можно считать явной удачей изда¬
ваемой в Англии серии монографий по вычислительным ма¬
шинам и программированию, которая довольно полно пред¬
ставлена в переводах, осуществляемых издательством «Мир».
Она является руководством по структурам данных, характер¬
ным практически для любых нечисловых применений машин.
Ни для кого не секрет, что нечисловые применения ЭВМ да¬
леко превзошли по своему размаху их применение для числен¬
ных расчетов в узком смысле этого слова — особенно в
результате широкого развития автоматизированных систем
проектирования, управления, обработки информации, эконо¬
мических расчетов. Да и в самих численных расчетах роль
информационного обслуживания, обработки исходных данных
и результатов, организации удобных для пользователя форм
общения возросла настолько, что соответствующие програм¬
мы уже только с большой натяжкой можно считать «число¬
выми».
Особенно приятно, что книга, посвященная структурам
данных, сама имеет стройную иглубоко продуманную структу¬
ру. Ясность и систематичность изложения, четкая классифи¬
кация излагаемых методов не только облегчают усвоение до¬
вольно богатого материала, но и помогают читателю взгля¬
нуть на него с единой точки зрения, выявить характерные
приемы, научиться применять их в различных контекстах.
Обрабатываемые на вычислительных машинах' данные
имеют три структуры: конкретную — отражающую их исполь¬
зование в конкретной задаче, абстрактную — отражающую
связи, существующие между их отдельными компонентами, и
машинную— отражающую представление этих данных в памя¬
ти вычислительной машины. Именно рассмотрение этих трех
типов структур по отдельности, проведение между ними чет¬
кого разграничения и последующий анализ их взаимодействия
позволили автору изложить большое разнообразие методов
достаточно просто.
Книга, несомненно, будет полезна как программистампрактикам,
так и студентам и преподавателям факультетов прикладной математики.
Э. 3. Любимский
Author(s): Холл П.
Series: Математическое обеспечение ЭВМ
Publisher: Мир
Year: 1978
Language: Russian
Pages: 218
City: Москва
Предисловие редактора перевода 5
Предисловие 6
Введение 10
1. Абстрактные структуры информации и алгоритмов
1.1. Некоторые важные обозначения 14
1.2. Индексация и упорядоченность 15
1.3. Строки 16
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. Блоки фиксированной длины, выделение и возврат в свободную область 53
2.1.4.2.1. Основные программы 55
2.1.4.2.2. Простое восстановление памяти . . . . 56
2.1.4.2.3. Сложное восстановление памяти . . . . 56
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. Упражнения . 75
3. Обработка строк - 78
3.1. Методы представления строк в памяти 80
3.1.1. Кодирование символов . 80
3.1.2. Представление отдельных строк в памяти 82
3.1.3. Представление совокупностей строк в памяти 85
3.2. Сопоставление строк 88
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. Последовательные таблицы ПО
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
4.2.1. Пакетирование и слияние - 157
4.3. Сложные файлы 159
4.4. Упражнения 163
5. Сортировка 16&
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
