Глава 8. Рекурсивные определения 148
8.1. Простейшие примеры 148
8.2. Рекурсивные подпрограммы 150
8.2.1. Выполнение рекурсивных вызовов 150
8.2.2. Задача "Ханойские башни" 151
8.2.3. Глубина рекурсии и общее число рекурсивных вызовов 152
8.2.4. Быстрый алгоритм возведения в степень 153
8.3. Рекурсия в синтаксических правилах 155
8.3.1. Синтаксические правила 155
8.3.2. Синтаксические правила и выводимые цепочки 157 8.3-3. Расширенные формы Бэкуса—Наура 158 8.3.4. Синтаксические диаграммы 161
Глава 9. Массивы, записи и множества 165
9.2. Одномерные массивы 167
9.2.1. Массивы и их элементы 167
9.3. Матрицы и многомерные массивы 175
9.4. Массивы как параметры 177
9.4.1. Значения, переменные, константы 177
9.5. Записи с вариантами и совмещение в памяти 178
9.6. Множества в языке Паскаль 180
Глава 10. Файлы 188
10.1. Основы работы с файлами 188
10.1.1. Физические файлы и файловые переменные 188
10.1.2. Последовательная запись в типизированные файлы 191
10.1.3. Последовательное чтение типизированных файлов 193
10.1.4. Знакомство с контроле м правильности ввода- вы вода 1 96
10.1.5. Прямой доступ в системе Турбо Паскаль 197
10.2. Простейшая работа с текстами 198
10.2.1. Особенности организации текстов 198
10.2.2. Запись втекст 199
10.2.3. Чтение числовых констант 200
10.2.4. Особенности чтения символов и строк 201
10.3. Буферизация ввода и вывода 203
10.3.1. Идея буферизации 203
10.3.2. Буферизация текстов 203
10.3.3. Буферизация экрана и клавиатуры 205
10 4 Ти п бести новых файлов 206
Резюме 209
Контрольные вопросы 210
Задачи 210
Глава 11. Структуры данных в свободной памяти 21 з
11.1. Указатели и свободная память 213
11.1.1. Адреса и указатели 213
11.1.2. Свободная память 214
11.2. Линейные связанные списки 216
11.2.1. Линейный связанный список в куче 216
11.2.2. Простейшие операции над списками 218
11.2.3. Ешс два представления линейных списков 220
11.3. Списки как рекурсивные объекты 221
11.4. Большие массивы в свободной памяти 222
11.5. Строки неопределенного размера 224
11.5.1. ASCIIZ-строки и тип Pchar 224
11.5.2. Несколько подпрограмм модуля Strings 225
11.5.3. Список строк неопределенной длины 226
Резюме 227
Контрольные вопросы 228
Задачи 228
Глава 12, Сортировка 230
12.1. Знакомство с поиском по ключу и сортировкой 230
12.1.1. Линейный поиск 230
12.1.2. Дихотомический поиск 231
12.1.3. Две простейшие сортировки 232
12.1.4. Что сорти руется в действ итсл ьн ости 234
12.2. Эффективные алгоритмы внутренней сортировки 234
12.2.1. Два алгоритма сортировки слиянием 234
12.2.2. Быстрая сортировка 236
12.2.3. Пирамида, или сортирующее дерево 237
12.2.4. Сложность задачи сортировки 240
12.3. Знакомство с сортировкой файлов 240
12.3.1. Сбалансированное слияние 240
12.3.2. Выбор с замещением 241
12.3.3. Индексные файлы 241
Резюме 241
Контрольные вопросы 242
Задачи 242
Задачи для любознательных 243
Глава 13. Знакомство с графами 245
13.1. Графы и способы их представления 245
13.1.1. Основные определения 245
13.1.2. Представления графа 247
13.2. Способы обхода графа 249
13.2.1. Обход в глубину 249
13.2.2. Ксрскурсивний вариант обхода в глубину 250
13.2.3. Обход в ширину 251
13.2.4. Гибридный алгоритм обхода 252
13.3. Алгоритмы на основе обходов графа 253
13.3.1. Построение остовного леса 253
13.3.2. Вычисление расстояний между вершинами 254 -
13.3.3. Топологическая сортировка ациклического орграфа 255
13.4. Построение остовного дерева минимального веса 256
13.4.1. Алгоритм При ма 257
13.4.2. Алгоритм Крас кала 258
13.5. Алгоритм Дейкстры для графов с неотрицательным весом ребер 259
Резюме 261
Контрольные вопросы 262
Задачи . 262
Глава 14. Перебор вариантов 264
14.1. Задача о размещении ферзей н исчерпывающий поиск 264
14.1.1. Рекурсивный алгоритм поиска размещений 264
14.1.2. Дерево поиска и его обход 266
14.1.3. Алгоритм обхода дерева с помощью стека 267
14.1.4. Задача о подмножестве 69
14.2. Метод ветвей и границ 270
14.2.1. Задача коммивояжера 270
14.2.2. Идея метода ветвей и границ 271
14.2.3. Пример применения метода ветвей и границ 271
14.3. Эвристические и "жадные" алгоритмы 272
14.4. Применение принципа оптимальности 274
Резюме 276
Контрольные вопросы 276
Задачи 277
Задачи для любознательных 278
Глава 15. Знакомство с объектами 280
15.1 Основы объектного подхода 281
15.1.1. Инкапсуляция, классы и объекты 281 15 ¡.2- Использование объектов 283
15.1.3. Объекты как компоненты других объектов 285
15.1.4. Создание и уничтожение объектов 286
15.1.5. Доступность объектов-серверов в клиентах 286
15 2 Наследование н полиморфизм 287
15.2. ], Понятие наследования 287
15.2.2. Виртуальные подпрограммы 289
15.2.3. Понятие полиморфизма 291
15.2.4. Динамическое связывание 291 15.2.5- Объекты в свободной памяти 292
15.3. Несколько приемов ООН 292
15.3.1. Абстрактный класс студентов и его потомки 292
15.3.2. Отделение внешнего представления 295
15.3.3. Массив ссылок на объекты различных классов 296
15.3.4. Знакомство с контейнерами и итераторами 299
15.3.5. Обозначение объекта в его собственных методах 302
15.3.6. Операция с элементами как параметр внутреннего итератора 303
Резюме 304
Контрольные вопросы 305
Задачи 305
Глава 16. Выделение лексем в текстах зо
16.1. Регулярные выражения и диаграммы состояний 308
16.1.1. Описание лексем с помощью регулярных выражений 308
16.1.2. Диаграммы состояний и конечные автоматы 309
16.1.3. Диаграмма состояний для лексического анализа 310
16.2. Реализация и использование сканера 313
16.2.1. Реализация сканера в виде класса 313
16.2.2. Процедура получения лексем 315
16.2.3. Сравнение двух потоков лексем 316
Резюме 317
Контрольные вопросы 317
Задачи 317
Глава 17, Элементы синтаксического анализа и интерпретации 319
17.1. КС- грамматики н синтаксический анализ 3 20
17. ]. 1. Задача принадлежности и синтаксический анализ 320
17.1.2. Грамматики Хомского 320
17.1.3. Контекстно-свободные грамматики 321
17.1.4. Две идеи синтаксического анализа 321
17.2.1_Л( 1)-грамматики и метод рекурсивного спуска 322
17.2.1. ЬА(1Ьграмматики 322
17.2.2. Леворекурсивные и расширенные продукции 324
17.2.3. Правила построения алгоритма 1А( ] )-анализа 324
17.3. Анализатор последовательности операторов присваивания 326
17.3.1. Грамматика для последовательности операторов присваивания 326
17.3.2. Процедуры синтаксического анализатора 328
17.3.3. Синтаксический анализатор как объект 329
17.4. Интерпретация с помощью семантического дерева 330
17.4.1. Семантическое дерево и его представление 331
17.4.2. Класс для построения дерева 333
17.4.3. Реализация построения дерева 333
17.4.4. Интерпретация семантического дерева 336
17.4.5. Программа с классом интерпретации 338
Резюме 339
Контрольные вопросы 339
Задачи 340
Приложение А. Некоторые возможности интегрированной среды
Турбо Паскаль 341
Приложение Б. Служебные слова языка Турбо Паскаль 347
Приложение В. Директивы компилятора системы Турбо Паскаль 349
Приложение Г. Кодировка символов 351
Приложение Д. Краткие ответы на контрольные вопросы -52
Приложение Е. Решение задач, отмеченных знаком 358
Список литературы 389
Предметный указатель 391