Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (Алгоритмы + структуры данных = программы)

Н.Вирт АЛГОРИТМЫ + СТРУКТУРЫ ДАННЫХ = ПРОГРАММЫ Монография известного швейцарского специалиста по системному программированию, знакомого советским читателям по переводу его книги «Систематическое программирование. Введение.» 1М.: Мир. 1977). Она содержит описание и анализ основных алгоритмов, методов построения программ. Книгу можно использовать и как руководство по применению языка Паскаль в задачах математического обеспечения ЭВМ. Для научных работников, преподавателей, аспирантов и студентов, специализирующихся по математическому обеспечению ЭВМ. Содержание Предисловие редактора перевода 5 Предисловие 7 1. Фундаментальные структуры дапиых 14 1.1.

Введение 14 1.2. Концепция типа для данных 17 1.3. Простые типы данных 20 1.4. Стандартные простые типы 22 1,5. Ограниченные тисы 25 1.6. Массивы 25 1.7. Записи 30 1.8. Записи с вариантами 35 1.9. Множество 38 1.10. Представление массивов, записей и множеств 44 1.11,Последовательный файл 50 Упражнения 71 Литература 73 2.

Сортировка 74 2.1. Введение 74 2.2. Сортировка массивов 77 2.3. Сортировка последовательных файлов 108 Упражнения 147 Литература 149 3. Рекурсивные алгоритмы 150 3.1. Введение 150 3.2. Когда не нужно использовать рекурсию 153 3.3, Два примера рекурсивных программ 156 3.4. Алгоритмы с возвратом 163 3.5. Задача о восьми ферзях 169 3.6 Задача об устойчивых браках 174 3.7. Задача оптимального выбора 182 Упражнения 186 Литература 188 4. Динамические информационные структуры 189 4.1. Рекурсивные типы данных 4.2.

Ссылки или указатели 4.3. Линейные списки 4.4. Древовидные структуры 4.5, Сильно ветвящиеся деревья 4.6. Преобразования ключа (расстановка) Упражнения Литература 5. Структура языков и.трансляторы 5.1. Определение и структура языка 5.2. Анализ предложений 5.3. Построение синтаксического графа 5.4. Построение программы грамматического разбора для заданного синтаксиса 5.5.Построение таблично-управляемой программы грамматического разбора 5.6.

Преобразование БНФ в структуру данных, управляющую грамматическим разбором 5,7. Язык программирования ПЛ~О 5.8. Программа грамматического разбора для ПЛ/О 5.9. Восстановление при синтаксических ошибках 5.10. Процессор ПЛ/О 5.11. Формирование команд Упражнения Литература Приложение А Множество символов АБСП Приложение В Синтаксические диаграммы Паскаля Указатель программ Указатель 189 193 198 219 278 303 314 318 319 319 322 322 332 336 340 346 352 361 373 376 390 392 393 393 394 394 400 401 Указатель программ 1.1. Вычисление степеней двойки ЗО 2.6.

Сортировка Шелла 89 1.2. Сканер 42 2.7. Просеивание 93 1.3. Чтение вещественного числа 63 2.8. Пирамидальная сортировка 95 1.4. Печать вещественного числа 65 2.9. Разделение 97 2.1. Сортировка простыми 2.10. Быстрая сортировка 99 включениями 79 2.11. Нерекурсивная версия быстрой бинарными 2.4. Сортировка методом пузырька 114 84 23 4. Сортировка естественным 2.5. Шейкер-сортировка 86 слиянием 121 22. Сортировка сортировки 100 включениями 80 2.12. Поиск Ьго элемента 105 2.3. Сортировка простым выбором 82 2.13. Сортировка простым слиянием 2.15. Сортировка сбалансированным слиянием 126 2.16. Многофазная сортировка 138 2.17.

Распределение начальных серий с помощью пирамиды 145 3.1. Кривые Гильберта 157 3.2. Кривые Серпинского 161 3.3. Ход коня 167 3.4. Восемь ферзей (одно решение) 172 3.5. Восемь ферзей (все решения) 174 3.6. Устойчивые браки 180 3.7. Оптимальная выборка 184 4.1.

Включение в список 204 4.2. Топологическая сортировка 218 4.3, Построение идеально сбалансированного дерева 227 4.4. Поиск с включениями 236 4.5. Построение таблицы перекрестных ссылок 240 4.6. Построение оптимального дерева поиска 274 4.7. Поиск, включение и удаление в Б-дереве 290 4.8. Построение таблицы перекрестных ссылок с использованием функций расстановки 308 5.1. Грамматический разбор для синтаксиса из примера 5 334 5.2. Грамматический разбор для языка (5.12) 343 5.3. Транслятор для языка (5.13) 345 5.4. Грамматический разбор для ПЛ/О 356 5.5. Грамматический разбор для ПЛ/О с восстановлением при ошибках 368 5.6.

ТранслятордляПЛ/О 380 Адельсон-Вельский 248 Адрес 44, 48 — абсолютный 374 — базовый 374 — возврата 374 — относительный 374 Алгол-60 17, 320 Алгоритм включения в Б-дерево 285 — — в ББ-дерево 296 — — в сбалансированное дерево 254 — — в список 200 — вычисления и-го факториального числа 153 — грамматического разбора 324 — линейного просмотра 203 — поискамедианы 103 — — по дереву с включением 233 — построения кустарников 300 — сортировки включениями бинарными 79 — — — простыми 78 — — — с убывающим приращением (сортировка 111елла) 87 Указатель — — выбором простым 81 — — обменом простым 83 — — пирамидальной 90 — — с разделением 96 — — слиянием естественным 115 — — слиянием многофазным 137 — — — простым 109 — — — сбалансированным Ф- путевым 122 — удаления из Б-дерева 288 — — из сбалансированногодерева 256 — шейкер-сортировки 85 Алгоритмы рекурсивные 9 — с возвратом 9, 168 Анализ алгоритмов сортировки 79, 80, 82, 85, 88, 94, 100, 113 Балансировка 288 Банки данных 58 Барабаны магнитные 57 Барьер 79, 203, 233 ББ-дерево см.

Б-дерево бинарное Б-дерево 282 Б-дерево бинарное 295 — — симметричное 293 Буквы латинские 24 Буфер 54 Бэйер 282, 289, 295, 293 Варианты в записях 35 Вес дерева 264 Ветвь 223 Возврат 9, 168, 325 Вольтер 13 Восстановление при ошибках 373 Время патентное 58 Выборочное изменение 28 Выравнивание 46 Выражение 17 — индексное 27 Высота дерева 220 Гаусс 169 Гьльберт 156 Глубина дерева 220 Горизонтальное распределение 134 Готлиб 267 Грамматический разбор 10, 328 — — нисходящий 323 — — целеориентированный 328 Граф распознавания 328 — синтаксический 328 — — детерминированный 332 Графы 19 Данные 11 Дейкстра 7, 12 Декартово произведение 31 Декартовы координаты 15, 36 Дерево 10, 19, 219 — — АВЛ-сбалансированное 248 — бинарное 223 — вырожденное 220 — идеально сбалансированное 226 — лексикографическое 238 — оптимальное 263 — поиска 231 — сильно ветвящееся 223 — сортировки 91 — упорядоченное 220 — Фибоначчи 249 2-3 дерево 295 Диаграмма зависимости 361 Дизъюнкция логическая 23 Диски магнитные 57 Дискриминант типа 36 Длинапути 220 — — взвешенная 261 — — внешнего 220 — — внугреннего 220 Доступ последовательный 53 — прямой 58 — случайный 25 Заглядывание вперед 55, 68 Заголовок списка 314 Задача об устойчивых браках 174 — о восьми ферзях 169 — о ходе коня 164 — оптимального выбора 182 — поиска медианы 103 — построения школьного расписания 41 Запись (гесогй) 8, 31, 48 — с вариантами 36 Запись бесскобочная 377 — инфиксная 230 — польская 377 — постфиксная 230 — префиксная 230 Инвариант цикла 28 Индекс 26, 44 Интерпретатор 373 Искусственный интеллект 163 Итерация 9, 99, 154 Карта (индексов) 123, 128 Квантиль 105 Ключ 76, 303 Ключей преобразование 303 Ключи переменной длины 318 Кнут 77, 86, 134, 144, 264 Кольца 19 Конкатенация 51, 52, 54 Константа 17 Конструктор 20 — записи 32 — массива 26 Контекстная зависимость 322 Конфликт 304 Конфликтов разрешение 304 Коньюнкция логическая 23 Координаты 15, 31, 36 — декартовы 15, 36 Корень дерева 220 Коэффициент заполнения 312 — использования памяти 46 Кривая Гипьберта 156 — Серлинского 158 Кустарники 299 Лаидис 248, 249 Лента 54 — магнитная 108 Лист дерева 220 Лорин 77 Лукасееич 377 Мак-Вити 179 Мак-Крейт 289 Мантисса 15 Массив 19, 25, 44 Матрица 29 Машина ПЛ/О 373 Медиана 101, 103 Метасимволы 320 Метод деления пополам 28 — пузырька 84 — рассеянных таблиц 307 Множеств объединение 40 — пересечение 40 — разность 40 — сложение 40 — умножение 40 Множество 15, 19, 38 Множество-степень 38 Множеству принадлежность 40 Моррис 306 Нотация 52 Областьпереполнения 306 Обход дерева 229 Оператор варианта 37 — присоединения 34, 286 — процедуры 190 — условный 190 — цикла 29 — — с параметром 190 — — с предисловием 190 Операции булевские 23 — над файлами 54 — отношений 40 — преобразования 20 И)-операции 62 Операция 17, 18, 19 Описание 17 Опробирование квадратичное 307 — линейное 306 Открытая адресация 306 Очередь 198 Ошибки наведенные 373 Память для программы 373 — оперативная 295 Паскаль 8, 11, 16, 19, 62 Переменная буферная 55 Переменные 17, 23 Переупорядочение списка 209 Пирамида 91 ПЛ/О 331, 349 ПЛП 20 Поддерево 223 Поиск бинарный 28 в списке 202 — медианы 103 — по дереву с включением 233 — по списку самоорганизующийся 209 Поле 48 Поле признака 36 Порядок Б-дерева 282 — частичный 211 — числа 15 Последовательность 16, 19, 52 Потомок 220 Поэтапное уточнение 11, 67, 344 Правила подстановки 320 — порождающие 320 — построения графа 329 Правило «не поднимай панику» 363 Предложения 319 Преобразование (типов) 24 — ключей 303 Приоритеты операций 40 Присваивание 19, 21, 189 Проблема пустой строки 326 Программа рабочая 373 — таблично-управляемая 328 Просеивание 92 Просмотр на один символ вперед без возврата 323 Проход 109 — по списку 201 Процедура 190 Путь внешний 222 — внутренний 220 Разряд 15, 44 Расписание школьное 41 Распознавание предложений 322 Распределение горизонтальное 134 — памяти динамическое 51, 193 Расстановка 303 †повторн 318 Реализация 47, 50 Регистр адреса команды 374 — команды 374 — вершины стека 374 Редактирование 67 Рекурсия 9, 99, 150 — косвенная 151 †прям 151 СББ-дерево 298 Связка динамическая 374 Сегмент 57 — логический 58 — физический 58 Сектор 58 Селектор 20, 37 — записи 32 — массива 26 Серии 115 — максимальные 115 — фиктивные 132 — фиктивные 132 Серлинский 158 Символ 23, 40, 319 — начальным 320 — пустой 24 Символы внешние 363 †возобновлен 363 — нетерминальные 320 — терминальные 320 — управляющие 393 Сканер 40, 341 Слияние 109 — двухфазное 115 — естественное 115 — каскадное 149 — многопутевое 122 — однофазное 110 — простое 109 — сбалансированное 110, 122 — трехленточное 109 Слова размер 44 Словарь частотный 203 Слово памяти 44 Случайный доступ 25 Смещение 48, 374 Сопрограммы 144 Сортировка 9, 74, 77 — быстрая 96 — включениями 77 — — бинарными 80 — — простыми 78 — внешняя 75 — внутренняя 75 — выбором 77 — — простым 81 — массивов 75 — методом пузырька 84 — обменом 83 — — простым 83 — пирамидальная 91 — слиянием 109 — — многофазная 128 — — простым 109 — с помощью дерева 89 — топологическая 211 †устойчив 79 — файлов 75 — Шелла 88 1-сортировка 88 Список 10, 198 †двунаправленн 315 †циклическ 314 Сравнение 19 — методов сортировки массивов 105 Ссылки 10, 19, 193 Стек 99, 374 Строка разрядов 49 — текущая 69 Структуры данных динамические 10 — — усложненные 8, 51 — — фундаментальные 8 — древовидные 219 Структурирования методы 19 Схемы программ 56 Таблица рассеянная 307 — расстановки 305 Таблично-управляемые программы 328 Таккер 266 Тексты 59 Тип базовый 18 — данных 17 — — регулярный 26 — — скалярный 19 — — составной 30 — — стандартный 19 — индексов 26 — рекурсивный 314 Транслятор 10, 17, 40, 319 Трансляция 40 Удаление из дерева 241 — из списка 200 Узел дерева внутренний 220 — — специальный 222 Уилсон 179 Уильямс 91 Указатели 10 Уолкер 263 Упаковка 47, 49 Уровень 220 Файл 14, 19, 53 — индексированный 58 — многоуровневый 57 — персональный 14 — с прямым доступом 58 Фиктивный элемент 79 Флойд 92 Фибоначчи деревья 249 — числа 131 Фиксация 378 Форма бэкус-наурова 320 — инфиксная 377 — постфиксная 377 Формула Эйлера 247 Функция 17 — Аккермана 188 — преобразования 24 — расстановки 304 — упорядочения 75 — факториал 150 — характеристическая 49 Ханойские башни 186 Хоор 7, 8, 12, 96, 103 Ху 266 Центроид 267 Цепочка 115 Цикл 16 Цифры арабские 15, 24 — двоичные ! 5 — римские 15 Числа вещественные 15 — комплексные 31 — натуральные 150 — с плавающей запятой 15 — факториальные 153 — цели с 15 Число гармоническое 83 — кардинальное 18, 20, 39, 49, 50 Читаемый вход 59 — выход 59 1Пенкер-сортировка 85 Эвристика 267 Эйлер ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Уже много лет говорят о кризисе в области программирования и создания программного обеспечения.