Эта программа принимает входные данные в виде обычного (инфиксного) выражения, преобразует это выражение в постфиксную форму и оценивает его применительно к заданным значениям переменных. <...> Скопируем прямоугольный массив newmap в прямоугольный массив map. <...> Выведем прямоугольный массив map на экран пользователя. <...> Включение спецификаций настолько полезно, что мы выделяем это действие в качестве нашего первого программистского принципа: В каждую написанную вами программу, процедуру и функцию включайте точные пред- и постусловия Программистский принцип Третья часть спецификаций для нашей программы представляет соподпрограммы бой список подпрограмм, которые она будет использовать (Uses). <...> Для программы Life нам еще надо написать процедуры и функции: • процедура Initialize(map,newmap) инициализирует решетку и вводит исходную конфигурацию; • процедура WriteMap(map) выполняет вывод; Глава 1. <...> Наконец, после выполнения вложенных циклов и предложения case, которые заполняют значениями прямоугольный массив newmap, предложение присваивания map := newmap копирует его в прямоугольный массив map, и процедура WriteMap(map) выводит результат. <...> Найти разумные имена не всегда просто, однако это достаточно важная задача, чтобы выделить ее в качестве второго программистского принципа: Программистский принцип Всегда именуйте свои переменные и подпрограммы с максимальным тщанием и детально объясняйте их назначение Язык Pascal даже навязывает нам выполнение этого принципа, требуя, чтобы в программе содержалась секция с объявлениями переменных. <...> Отсюда следует третий программистский принцип: Старайтесь, чтобы ваша документация была краткой, но содержательной Программистский принцип Стиль документации, как и вообще стиль любого письменного документа, зависит от личности автора, и самые разные стили могут оказаться вполне удовлетворительными. <...> В прямоугольном массиве map установлена начальная конфигурация живых ячеек.} var инициализация row, col: integer; begin <...>
Структуры_данных_и проектирование_программ_.pdf
Р. Круз Кру
СТРУКТУРЫ ДАННЫХ
И ПРОЕКТИРОВАНИЕ
ПРОГРАММ
Перевод 3-го английского издания
К. Г. Финогенова
4-е издание, электронное
Лаборатория знаний
2021
Москва
Стр.4
УДК 004.7
ББК 32.973.202
К84
С е р и я о с н о в а н а в 2005 г.
Круз Р. Л.
К84 Структуры данных и проектирование программ / Р. Л. Круз ;
пер. с англ. — 4-е изд., электрон. — М. : Лаборатория знаний,
2021. — 768 с. — (Программисту). — Систем. требования: Adobe
Reader XI ; экран 10". — Загл. с титул. экрана. — Текст :
электронный.
ISBN 978-5-93208-560-8
В качестве фундаментальных средств разработки программ рассматриваются
такие вопросы, как структурное решение задач, абстракция данных,
принципы программной инженерии и сравнительный анализ алгоритмов.
Дано полное освещение большинства модулей знаний, касающихся структур
данных и алгоритмов.
Б´ольшая часть глав начинается основной темой и сопровождается
примерами, приложениями и практическими исследованиями.
Это учебное пособие дает основательные знания, которые позволяют
студентам по ходу своей дальнейшей работы использовать ее также
в качестве справочного пособия.
УДК 004.7
ББК 32.973.202
Деривативное издание на основе печатного аналога: Структуры данных
и проектирование программ / Р. Л. Круз ; пер. с англ. — М. : БИНОМ.
Лаборатория знаний, 2008. — 765 с. : ил. — (Программисту).
ISBN 978-5-94774-879-6.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных
техническими средствами защиты авторских прав, правообладатель вправе требовать от
нарушителя возмещения убытков или выплаты компенсации
Authorized Translation from the English language edition, entitled DATA
STRUCTURES AND PROGRAM DESIGN, 3rd Edition; by ROBERT KRUSE; and
by BILL ZOBRIST; published by Pearson Education, Inc, publishing as Prentice
Hall. Copyright © 1994 by Prentice Hall, Inc. All rights reserved. No part
of this book may be reproduced or transmitted in any form or by any means,
electronic or mechanical, including photocopying, recording or by any information
storage retrieval system, without permission from Pearson Education, Inc. Electronic
RUSSIAN language edition published by BKL PUBLISHERS. Copyright © 2014.
ISBN 978-5-93208-560-8
Авторизованный перевод издания на английском языке, озаглавленного DATA
STRUCTURES AND PROGRAM DESIGN, авторы ROBERT KRUSE и BILL
ZOBRIST, опубликованного Pearson Education, Inc, осуществляющим издательскую
деятельность под торговой маркой Prentice Hall. Copyright © 1994
by Prentice Hall, Inc. Все права защищены. Воспроизведение или распространение
какой-либо части/частей данной книги в какой-либо форме, какими-либо
способами, электронными или механическими, включая фотокопирование,
запись и любые поисковые системы хранения информации, без разрешения
Pearson Education, Inc запрещены. Электронная русскоязычная версия издана
BKL Publishers. Copyright © 2014.
© Перевод, оформление. Лаборатория знаний, 2015
Стр.5
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Краткий обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Изменения в третьем издании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Структура курса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Разработка книги . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Глава 1. Принципы программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2. Игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2.1. Правила игры «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.2.2. Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.2.3. Решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.2.4. Life: главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.3. Стиль программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3.1. Имена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.3.2. Документация и форматы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.3.3. Детализация программы и модульность . . . . . . . . . . . . . . . . . . 33
1.4. Кодирование, тестирование и дальнейшая детализация . . . . . . . . . . 39
1.4.1. Заглушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.4.2. Подсчет соседей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.4.3. Ввод и вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
1.4.4. Драйверы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.4.5. Трассировка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
1.4.6. Принципы тестирования программы . . . . . . . . . . . . . . . . . . . . . 48
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Программистские принципы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Глава 2. Введение в программную инженерию . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.1. Поддержка программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.1.1. Обзор программы Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.1.2. Новый старт и новый метод для программы Life . . . . . . . . . . 60
2.2. Разработка алгоритма: второй вариант программы Life . . . . . . . . . . 63
2.2.1. Списки: спецификации для структуры данных . . . . . . . . . . . . 63
Стр.6
6
Оглавление
2.2.2. Программа Main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.2.3. Сокрытие информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.2.4. Детализация: разработка подпрограмм . . . . . . . . . . . . . . . . . . . 71
2.2.5. Верификация и алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.3. Кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.3.1. Пакет обработки списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
2.3.2. Обработка ошибок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.3.3. Демонстрация и тестирование . . . . . . . . . . . . . . . . . . . . . . . . . . 81
2.4. Кодирование процедур программы Life . . . . . . . . . . . . . . . . . . . . . . . . 85
2.5. Анализ и сравнение программ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
2.6. Заключение и предварительный просмотр . . . . . . . . . . . . . . . . . . . . . . 91
2.6.1. Игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
2.6.2. Разработка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
2.6.3. Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Глава 3. Стеки и рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.1. Стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.1.2. Первый пример: реверсирование строки . . . . . . . . . . . . . . . . . 102
3.1.3. Сокрытие информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.1.4. Спецификации для стека . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.1.5. Реализация стеков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
3.1.6. Связные стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
3.2. Введение в рекурсию . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.2.1. Кадры стека для подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.2.2. Дерево вызовов подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.2.3. Факториалы: рекурсивное определение . . . . . . . . . . . . . . . . . . 119
3.2.4. Метод разбиения: башни Ханоя . . . . . . . . . . . . . . . . . . . . . . . . . 121
3.3. Принципы рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
3.3.1. Разработка рекурсивных алгоритмов . . . . . . . . . . . . . . . . . . . . . 128
3.3.2. Как работает рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
3.3.3. Хвостовая рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.3.4. Когда не следует использовать рекурсию . . . . . . . . . . . . . . . . . 136
3.3.5. Рекомендации и заключения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Глава 4. Примеры рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4.1. Алгоритмы с отходом: откладывание работы . . . . . . . . . . . . . . . . . . . 145
4.1.1. Решение задачи о восьми ферзях . . . . . . . . . . . . . . . . . . . . . . . . 146
4.1.2. Пример: четыре ферзя . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
4.1.3. Алгоритм с отходом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.1.4. Детализация: выбор структур данных . . . . . . . . . . . . . . . . . . . . 148
4.1.5. Анализ алгоритма с отходом . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Стр.7
Оглавление
7
4.2. Древовидные программы: прогнозирование в играх . . . . . . . . . . . . . 154
4.2.1. Деревья игр . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.2.2. Метод минимакса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.2.3. Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.2.4. Детализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.3. Компиляция методом рекурсивного спуска . . . . . . . . . . . . . . . . . . . . . 161
4.3.1. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.3.2. Объявления типов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.3.3. Синтаксический анализ предложений . . . . . . . . . . . . . . . . . . . . 164
4.3.4. Синтаксический анализатор предложений языка Pascal . . . . 168
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Глава 5. Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.1. Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.2. Реализация очередей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.3. Кольцевые очереди в языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
5.4. Приложения очередей: Моделирование . . . . . . . . . . . . . . . . . . . . . . . . 195
5.4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.4.2. Моделирование работы аэропорта . . . . . . . . . . . . . . . . . . . . . . . 195
5.4.3. Случайные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.4.4. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.4.5. Шаги моделирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5.4.6. Пример результатов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
5.5. Связные очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.6. Приложения: полиномиальная арифметика . . . . . . . . . . . . . . . . . . . . . 210
5.6.1. Цель проекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
5.6.2. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.6.3. Структуры данных и их реализация . . . . . . . . . . . . . . . . . . . . . 214
5.6.4. Чтение и вывод полиномов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
5.6.5. Сложение полиномов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
5.6.6. Завершение проекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
5.7. Абстрактные типы данных и их реализации . . . . . . . . . . . . . . . . . . . . 222
5.7.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
5.7.2. Общие определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
5.7.3. Детализация спецификации данных . . . . . . . . . . . . . . . . . . . . . 227
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Глава 6. Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.1. Спецификации списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.2. Реализация списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.2.1. Непрерывная реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
6.2.2. Реализация простого связывания . . . . . . . . . . . . . . . . . . . . . . . . 235
6.2.3. Вариация: сохранение текущей позиции . . . . . . . . . . . . . . . . . 239
6.2.4. Дважды связные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.2.5. Сравнение реализаций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
Стр.8
8
Оглавление
6.3. Цепочки символов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
6.3.1. Операции над цепочками символов . . . . . . . . . . . . . . . . . . . . . . 246
6.3.2. Реализация цепочек символов . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
6.4. Приложение: текстовый редактор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
6.4.1. Спецификации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
6.4.2. Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
6.5. Связные списки в массивах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
6.6. Генерирование перестановок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
Глава 7. Поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
7.1. Введение и обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
7.2. Последовательный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.3. Гардеробы: проект . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
7.3.1. Введение и спецификации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
7.3.2. Демонстрационная и тестирующая программы . . . . . . . . . . . 291
7.4. Двоичный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
7.4.1. Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
7.4.2. Вариант с забыванием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
7.4.3. Распознавание равенства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
7.5. Деревья сравнений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
7.5.1. Анализ для n=10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
7.5.2. Обобщение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
7.5.3. Методы сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
7.5.4. Общее отношение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
7.6. Нижние границы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
7.7. Асимптотика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
7.7.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
7.7.2. О большое . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
7.7.3. Неточность определения O большого . . . . . . . . . . . . . . . . . . . . 322
7.7.4. Порядки распространенных функций . . . . . . . . . . . . . . . . . . . . 323
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
Глава 8. Сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
8.1. Введение и обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
8.2. Сортировка включением . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
8.2.1. Упорядоченные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
8.2.2. Сортировка методом включения . . . . . . . . . . . . . . . . . . . . . . . . . 330
8.2.3. Связный вариант . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
8.2.4. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
8.3. Сортировка методом выбора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
8.3.1. Алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
8.3.2. Непрерывная реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
8.3.3. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
8.3.4. Сравнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
Стр.9
Оглавление
9
8.4. Cортировка методом Шелла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
8.5. Нижние границы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
8.6. Сортировка методом разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
8.6.1. Базовые идеи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
8.6.2. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
8.7. Сортировка слиянием для связных списков . . . . . . . . . . . . . . . . . . . . . 357
8.7.1. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
8.7.2. Анализ метода сортировки слиянием . . . . . . . . . . . . . . . . . . . . 359
8.8. Метод быстрой сортировки для непрерывных списков . . . . . . . . . . . 365
8.8.1. Главная процедура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
8.8.2. Разделение списка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
8.8.3. Анализ метода быстрой сортировки . . . . . . . . . . . . . . . . . . . . . 368
8.8.4. Анализ метода быстрой сортировки для среднего случая . . 371
8.8.5. Сравнение с методом слияния . . . . . . . . . . . . . . . . . . . . . . . . . . 373
8.9. Пирамиды и пирамидальная сортировка . . . . . . . . . . . . . . . . . . . . . . . 377
8.9.1. Двухвариантные деревья как списки . . . . . . . . . . . . . . . . . . . . . 377
8.9.2. Пирамидальная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
8.9.3. Анализ пирамидальной сортировки . . . . . . . . . . . . . . . . . . . . . . 382
8.9.4. Очереди с приоритетами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
8.10. Обзор: сравнение методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
Глава 9. Таблицы и извлечение информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
9.1. Введение: переход через барьер lg n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
9.2. Прямоугольные массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
9.3. Таблицы различных форм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
9.3.1. Треугольные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
9.3.2. Рваные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
9.3.3. Инвертированные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
9.4. Таблицы: новый абстрактный тип данных . . . . . . . . . . . . . . . . . . . . . . . 404
9.5. Приложение: поразрядная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . 407
9.5.1. Идея метода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
9.5.2. Реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
9.5.3. Анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
9.6. Хеширование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
9.6.1. Разреженные таблицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
9.6.2. Выбор хеш-функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
9.6.3. Разрешение конфликтов с помощью открытой адресации . . 417
9.6.4. Разрешение столкновений посредством связных цепочек . . 422
9.7. Анализ хеширования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
9.8. Заключение: сравнение методов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
9.9. Приложение: снова игра «Жизнь» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
9.9.1. Выбор алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
9.9.2. Спецификация структур данных . . . . . . . . . . . . . . . . . . . . . . . . . 435
9.9.3. Главная программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
9.9.4. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
Стр.10
10
Оглавление
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
Глава 10. Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.1. Двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.1.1. Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.1.2. Просмотр двоичных деревьев . . . . . . . . . . . . . . . . . . . . . . . . . 448
10.1.3. Связная реализация двоичных деревьев . . . . . . . . . . . . . . . . 453
10.2. Деревья двоичного поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
10.2.1. Упорядоченные списки и реализации . . . . . . . . . . . . . . . . . . . 459
10.2.2. Поиск по дереву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
10.2.3. Включение в двоичное дерево поиска . . . . . . . . . . . . . . . . . . . 464
10.2.4. Древовидная сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
10.2.5. Удаление из двоичного дерева поиска . . . . . . . . . . . . . . . . . . . 469
10.3.2. Объявления и главная процедура . . . . . . . . . . . . . . . . . . . . . . 479
10.3.3. Включение узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
10.3.4. Завершение задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
10.3.5. Оценка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
10.3.6. Случайные деревья поиска и оптимизация . . . . . . . . . . . . . . 483
10.3. Построение двоичного дерева поиска. . . . . . . . . . . . . . . . . . . . . . . . . . . 477
10.3.1. Начинаем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
10.4. Балансирование по высоте: AVL-деревья . . . . . . . . . . . . . . . . . . . . . 486
10.4.1. Определение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
10.4.2. Включение узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
10.4.3. Удаление узла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494
10.4.4. Высота AVL-дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
10.5. Скошенные деревья: самонастраивающиеся структуры данных . 501
10.5.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
10.5.2. Шаги скашивания дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
10.5.3. Алгоритм скашивания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
10.5.4. Амортизационный анализ алгоритмов: введение . . . . . . . . . 509
10.5.5. Амортизационный анализ скашивания . . . . . . . . . . . . . . . . . . 514
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
Глава 11. Многовариантные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
11.1. Сады, деревья и двоичные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
11.1.1. Классификация видов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524
11.1.2. Упорядоченные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
11.1.3. Леса и сады . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
11.1.4. Формальное соответствие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529
11.1.5. Повороты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
11.1.6. Резюме . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
11.2. Деревья лексикографического поиска: трай-деревья . . . . . . . . . . . . 533
11.2.1. Трай-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
11.2.2. Поиск ключа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
11.2.3. Алгоритм на языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
11.2.4. Включение в трай-дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
Стр.11
Оглавление
11
11.2.5. Удаление из трай-дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
11.2.6. Оценка трай-деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
11.3. Внешний поиск: B-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
11.3.1. Время доступа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
11.3.2. Многовариантные деревья поиска . . . . . . . . . . . . . . . . . . . . . . 539
11.3.3. Сбалансированные многовариантные деревья . . . . . . . . . . . 539
11.3.4. Включение в B-дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
11.3.5. Алгоритмы на языке Pascal: поиск и включение . . . . . . . . . 542
11.3.6. Удаление из B-дерева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
11.4. Красно-черные деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
11.4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
11.4.2. Определения и анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
11.4.3. Включение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
11.4.4. Включение на языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
Глава 12. Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
12.1. Математические основы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
12.1.1. Определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
12.1.2. Неориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 570
12.1.3. Ориентированные графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
12.2. Компьютерное представление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572
12.3. Просмотр графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
12.3.1. Методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
12.3.2. Алгоритм просмотра в глубину . . . . . . . . . . . . . . . . . . . . . . . . 577
12.3.3. Алгоритм просмотра в ширину . . . . . . . . . . . . . . . . . . . . . . . . 578
12.4. Топологическая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
12.4.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
12.4.2. Алгоритм упорядочения в глубину . . . . . . . . . . . . . . . . . . . . . 581
12.4.3. Алгоритм упорядочения в ширину . . . . . . . . . . . . . . . . . . . . . 582
12.5. Алгоритм экономного продвижения: кратчайшие маршруты . . . . 584
12.6. Графы как структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
Подсказки и ловушки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
Обзорные вопросы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
Глава 13. Конкретный пример: польская нотация . . . . . . . . . . . . . . . . . . . . . . . . . 593
13.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
13.1.1. Формула корней квадратного уравнения . . . . . . . . . . . . . . . . 593
13.2. Идея . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
13.2.1. Дерево выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595
13.2.2. Польская нотация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597
13.2.3. Метод для языка Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
13.3. Оценка выражений в польской нотации . . . . . . . . . . . . . . . . . . . . . . . 599
13.3.1. Оценка выражений в префиксной форме . . . . . . . . . . . . . . . . 599
13.3.2. Соглашения языка Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
13.3.3. Pascal-процедура для префиксной оценки . . . . . . . . . . . . . . . 601
Стр.12
12
Оглавление
13.3.4. Оценка постфиксных выражений . . . . . . . . . . . . . . . . . . . . . . 602
13.3.5. Доказательство правильности программы: подсчет элементов
в стеке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
13.3.6. Рекурсивная оценка постфиксных выражений . . . . . . . . . . . 607
13.4. Преобразование из инфиксной формы в польскую . . . . . . . . . . . . . 611
13.5. Интерактивная программа оценки выражений . . . . . . . . . . . . . . . . . 617
13.5.1. Общая структура . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
13.5.2. Представление данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 619
13.5.3. Инициализация и вспомогательные задачи . . . . . . . . . . . . . . 623
13.5.4. Преобразование выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
13.5.5. Оценка выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
13.5.6. Графическое отображение выражения . . . . . . . . . . . . . . . . . . 639
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
Приложение A. Математические методы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
A.1. Суммы степеней целых чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
A.2. Логарифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
A.2.1. Определение логарифмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
A.2.2. Простые свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
A.2.3. Выбор основания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
A.2.4. Натуральные логарифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
A.2.5. Обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649
A.2.6. Изменение основания логарифмов . . . . . . . . . . . . . . . . . . . . . . 649
A.2.7. Логарифмические графики . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
A.2.8. Гармонические числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
A.3. Перестановки, сочетания, факториалы . . . . . . . . . . . . . . . . . . . . . . . . 652
A.3.1. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652
A.3.2. Сочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
A.3.3. Факториалы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
A.4. Числа Фибоначчи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655
A.5. Числа Каталана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
A.5.1. Основной результат . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
A.5.2. Доказательство посредством однозначного соответствия . . 657
A.5.3. История вопроса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
A.5.4. Численные результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
Приложение B. Случайные числа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663
B.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663
B.2. Метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
B.3. Разработка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
Литература для дальнейшего изучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
Приложение С. Модули, включаемые файлы и утилиты . . . . . . . . . . . . . . . . . . . . . 671
C.1. Модули Turbo Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
C.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
C.1.2. Синтаксис модулей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
C.2. Включаемые файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674
C.2.1. Замена модулей включаемыми файлами . . . . . . . . . . . . . . . . . 674
C.2.2. Родовые средства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
Стр.13
Оглавление
13
C.3. Модули, используемые в тексте . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
C.3.1. Структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
C.3.2. Модуль утилит Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
C.3.3. Модуль анализа процессорного времени . . . . . . . . . . . . . . . . . 680
C.3.4. Модуль для обслуживания файлов . . . . . . . . . . . . . . . . . . . . . . 682
C.3.5. Модуль случайных чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
C.4. Программы поиска и сортировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
C.4.1. Демонстрационная программа . . . . . . . . . . . . . . . . . . . . . . . . . . 685
C.4.2. Создание файлов данных для тестирования программ . . . . . 686
Приложение D. Свойства языка Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
D.1. Записи в языке Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
D.2. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
D.2.1. Процедуры в качестве параметров . . . . . . . . . . . . . . . . . . . . . . 700
D.2.2. Упреждающие объявления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
D.3. Указатели и связные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
D.3.1. Введение и обзор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
D.3.2. Указатели и динамическая память в языке Pascal . . . . . . . . . 707
D.3.3. Основы связных списков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
D.3.4. Связная реализация простых списков . . . . . . . . . . . . . . . . . . . 715
D.3.5. Советы для программистов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718
D.4. Синтаксические диаграммы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
D.5. Общие правила . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
D.5.1. Идентификаторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
D.5.2. Правила использования пробелов . . . . . . . . . . . . . . . . . . . . . . . 731
D.5.3. Указания по формату программы . . . . . . . . . . . . . . . . . . . . . . . 732
D.5.4. Пунктуация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
D.5.5. Альтернативные знаки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
D.6. Стандартные объявления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
D.6.1. Константы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
D.6.2. Типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735
D.6.3. Переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735
D.6.4. Процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736
D.6.5. Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 736
D.7. Операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738
Стр.14