ПРЕДИСЛОВИЕ
Программирование для электронных вычислительных машин давно перестало быть только совокупностью приемов переложения математических алгоритмов на язык машинных команд. В программировании широко и разнообразно применяются различные формальные методы точных наук (например, математической логики — для оптимизации программ, математической лингвистики — для создания трансляторов и т. д.).
С другой стороны, появились специфические методы, разработанные специально для нужд программирования и нашедшие применение не только в нем. Например, алгоритмический язык АЛГОЛ применяется специалистами различных профессий как средство полной и недвусмысленной записи алгоритмов независимо от того, будут эти алгоритмы решаться на ЭВМ или нет.
Все это вместе взятое дает право говорить, что программирование развивается в прикладную науку со своим кругом задач и методов.
В предлагаемой читателям книге А. Т. Берзтисса «Структуры данных» изложен один сравнительно новый раздел программирования. Рассмотрим вкратце, чем вызвано его появление.
Издавна (по крайней мере с времен Шумера) люди обрабатывают числовые данные о своей деятельности и об окружающем их мире, вовлеченном в эту деятельность. Каждый, кто этим занимался, знал, какие конкретные данные он обрабатывает, и ему не было нужды задумываться над понятием «данные» и над их общими структурами. Так зачастую осталось и до нашего времени. Теперешние экономист и плановик, бухгалтер и статистик также имеют на руках конкретные формы, только не на глиняных табличках. Это кажется совершенно естественным.
Однако при постановке задачи для решения ее на ЭВМ существенно возрастают требования к обобщению представления данных. Общеизвестно, что алгоритм, реализованный в виде программы, хорош только тогда, когда им можно пользоваться многократно для данных, значения и структура которых изменяются.
Процессы обработки и структуры данных инженерных и научных задач уже к моменту появления ЭВМ были достаточно хорошо приспособлены для реализации на ней. С иным положением столкнулись специалисты по обработке данных при программировании задач учета, статистики и планирования. Возникла необходимость обобщить структуры данных, представленных в бесчисленном множестве форм, таб-
5
ОГЛАВЛЕНИЕ
Предисловие ............................. 5
Введение............................... 8
ЧАСТЬ I ДИСКРЕТНЫЕ СТРУКТУРЫ В МАТЕМАТИКЕ
Глава 1 Теория множеств
.1. Основные определения...................... 10
.2. Индексированные множества.................. 14
.3. Дополнение множества..................... 17
.4. Алгебра множеств........................ 20
.5. Алгебра множеств как аксиоматическая теория.......... 23
.6. Диаграммы Венна (Venn).................... 30
1.7. Упорядоченные пары....................... 31
1.8. Размещения и сочетания..................... 35
Глава 2 Функции и отношения
2.1. Функции............................ 48
2.2. Булевы функции и формы..................... 52
2.3. Применение булевых функций.................. 62
2.4. Отношения........................... 74
2.5. Отношение эквивалентности................... 78
2.6. Отношения порядка...................... 81
2.7. Структуры........................... 88
2.8. Абстрактные алгебры...................... 92
Глава 3 Теория графов
3.1. Схемы и графы.........................106
3.2. Основные определения теории ориентированных графов......108
3.3. Орографы, матрицы и отношения.................115
3.4. Связность в орографе......................122
3.5. Линейные формулы орографов..................125
3.6. Деревья............................131
3.7. Изоморфизм орографов......................132
3.8. Плоские графы.........................136
Глава 4 Строки
4.1. Алгебраические структуры-....................144
4.2. Алгебра строк..........................149
4.3. Алгоритмы Маркова......................151
4.4. Языки и грамматики.......................157
4.5. Языки и автоматы........................163
ЧАСТЬ II ПРАКТИЧЕСКИЕ ПРИЛОЖЕНИЯ СТРУКТУР
Глава 5 Деревья
5.1. Деревья как грамматические маркеры...............170
5.2. Изображение префиксных формул................175
407
5.3. Деревья сортировки (упорядочения) и словари..........179
5.4. Деревья решений и решающие таблицы..............186
Глава 6 Путк и циклы в орографах
6.1. Задача о нахождении кратчайшего пути.............197
6.2. Циклы.............................206
6.3. Задача сетевого планирования и управления...........214
6.4'. Нахождение критического пути..................216
Глава 7 Орографы программ
7.1. Орографы и блок-схемы.....................225
7.2. Обнаружение ошибок в программе................228
7.3. Сегментация программ......................230
7.4. Автоматическое составление блок-схемы.............232
Глава 8 Другие приложения теории графов
8.1. Задачи о потоках в сетях.....................237
8.2. Графы в химии.........................244
8.3. Графы в информационном поиске.................248
ЧАСТЬ III МАШИННОЕ ПРЕДСТАВЛЕНИЕ СТРУКТУР
Глава 9 Массивы
9.1. Устройства памяти и их свойства.................254
9.2. Хранение массивов.......................257
9.3. Разреженные матрицы.....................260
9.4. Распределение памяти во время выполнения программы.......263
Глава 10 Стэковая память, списки и списковые структуры
10.1. Стэковая память .......................272
10.2. Префиксные, постфиксные и инфиксные формулы........275
10.3. Уровни памяти для стэков...................278
10.4. Списки — основные представления...............279
10.5. Форматы элементов списка ...................284
10.6. Списковые структуры......................287
10.7. Замкнутые и симметричные списки................291
10.8. Представление орографов в виде списковых структур ......295
10.9. Многословные элементы списков................297
10.10. Управление списковой памятью................298
10.11. Структуры данных типа ПЛ/1................301
Глава 11 Организация массивов
11.1. Записи и массивы........................308
11.2. Индексные массивы.......................311
11.3. Метод случайного рассеивания.................314
11.4. Сортировка..........................319
11.5. Массивы и внешняя память...................327
Глава 12 Языки программирования для информационных структур
12.1. Языки обработки списков....................331
12.2. Языки обработки строк.....................342
12.3. Расширение (надстройка) языков широкого назначения .....353
Решения к некоторым упражнениям..................362
Литература.............................389
Именной указатель.........................402
Предметный указатель.........................402
Цена: 150руб.
