В качестве фундаментальных средств разработки программ рассматриваются такие вопросы, как структурное решение задач, абстракция данных, принципы программной инженерии и сравнительный анализ алгоритмов. Дано полное освещение большинства модулей знаний, касающихся структур данных и алгоритмов. Большая часть глав начинается основной темой и сопровождается примерами, приложениями и практическими исследованиями.Это учебное пособие дает основательные знания, которые позволяют студентам по ходу своей дальнейшей работы использовать ее также в качестве справочного пособия.

Предисловие......14Краткий обзор......15Изменения в третьем издании......17Структура курса......18Разработка книги......19Благодарности......20Глава 1. Принципы программирования......211.1. Введение......211.2. Игра «Жизнь»......241.2.1. Правила игры «Жизнь»......241.2.2. Примеры......251.2.3. Решение......261.2.4. Life: главная программа......271.3. Стиль программирования......291.3.1. Имена......291.3.2. Документация и форматы......321.3.3. Детализация программы и модульность......331.4. Кодирование
тестирование и дальнейшая детализация......391.4.1. Заглушки......391.4.2. Подсчет соседей......401.4.3. Ввод и вывод......421.4.4. Драйверы......461.4.5. Трассировка программы......471.4.6. Принципы тестирования программы......48Подсказки и ловушки......52Обзорные вопросы......54Литература для дальнейшего изучения......55Pascal......55Программистские принципы......55Игра «Жизнь»......56Глава 2. Введение в программную инженерию......572.1. Поддержка программ......572.1.1. Обзор программы Life......582.1.2. Новый старт и новый метод для программы Life......602.2. Разработка алгоритма: второй вариант программы Life......632.2.1. Списки: спецификации для структуры данных......632.2.2. Программа Main......682.2.3. Сокрытие информации......702.2.4. Детализация: разработка подпрограмм......712.2.5. Верификация и алгоритмы......752.3. Кодирование......782.3.1. Пакет обработки списков......792.3.2. Обработка ошибок......802.3.3. Демонстрация и тестирование......812.4. Кодирование процедур программы Life......852.5. Анализ и сравнение программ......892.6. Заключение и предварительный просмотр......912.6.1. Игра «Жизнь»......922.6.2. Разработка программы......932.6.3. Pascal......96Подсказки и ловушки......99Обзорные вопросы......99Литература для дальнейшего изучения......99Глава 3. Стеки и рекурсия......1013.1. Стеки......1013.1.1. Введение......1013.1.2. Первый пример: реверсирование строки......1023.1.3. Сокрытие информации......1043.1.4. Спецификации для стека......1053.1.5. Реализация стеков......1073.1.6. Связные стеки......1093.2. Введение в рекурсию......1163.2.1. Кадры стека для подпрограмм......1163.2.2. Дерево вызовов подпрограмм......1173.2.3. Факториалы: рекурсивное определение......1193.2.4. Метод разбиения: башни Ханоя......1213.3. Принципы рекурсии......1283.3.1. Разработка рекурсивных алгоритмов......1283.3.2. Как работает рекурсия......1293.3.3. Хвостовая рекурсия......1343.3.4. Когда не следует использовать рекурсию......1363.3.5. Рекомендации и заключения......140Подсказки и ловушки......142Обзорные вопросы......143Литература для дальнейшего изучения......143Глава 4. Примеры рекурсии......1454.1. Алгоритмы с отходом: откладывание работы......1454.1.1. Решение задачи о восьми ферзях......1464.1.2. Пример: четыре ферзя......1464.1.3. Алгоритм с отходом......1484.1.4. Детализация: выбор структур данных......1484.1.5. Анализ алгоритма с отходом......1524.2. Древовидные программы: прогнозирование в играх......1544.2.1. Деревья игр......1544.2.2. Метод минимакса......1564.2.3. Разработка алгоритма......1574.2.4. Детализация......1594.3. Компиляция методом рекурсивного спуска......1614.3.1. Главная программа......1624.3.2. Объявления типов......1634.3.3. Синтаксический анализ предложений......1644.3.4. Синтаксический анализатор предложений языка Pascal......168Подсказки и ловушки......179Обзорные вопросы......180Литература для дальнейшего изучения......180Глава 5. Очереди......1825.1. Определения......1825.2. Реализация очередей......1855.3. Кольцевые очереди в языке Pascal......1905.4. Приложения очередей: Моделирование......1955.4.1. Введение......1955.4.2. Моделирование работы аэропорта......1955.4.3. Случайные числа......1975.4.4. Главная программа......1985.4.5. Шаги моделирования......1995.4.6. Пример результатов......2025.5. Связные очереди......2055.6. Приложения: полиномиальная арифметика......2105.6.1. Цель проекта......2105.6.2. Главная программа......2115.6.3. Структуры данных и их реализация......2145.6.4. Чтение и вывод полиномов......2165.6.5. Сложение полиномов......2185.6.6. Завершение проекта......2205.7. Абстрактные типы данных и их реализации......2225.7.1. Введение......2225.7.2. Общие определения......2245.7.3. Детализация спецификации данных......227Подсказки и ловушки......228Обзорные вопросы......230Литература для дальнейшего изучения......230Глава 6. Списки......2316.1. Спецификации списков......2316.2. Реализация списков......2336.2.1. Непрерывная реализация......2346.2.2. Реализация простого связывания......2356.2.3. Вариация: сохранение текущей позиции......2396.2.4. Дважды связные списки......2406.2.5. Сравнение реализаций......2436.3. Цепочки символов......2466.3.1. Операции над цепочками символов......2466.3.2. Реализация цепочек символов......2486.4. Приложение: текстовый редактор......2536.4.1. Спецификации......2536.4.2. Реализация......2546.5. Связные списки в массивах......2616.6. Генерирование перестановок......271Подсказки и ловушки......276Обзорные вопросы......277Литература для дальнейшего изучения......278Глава 7. Поиск......2797.1. Введение и обозначения......2797.2. Последовательный поиск......2817.3. Гардеробы: проект......2877.3.1. Введение и спецификации......2877.3.2. Демонстрационная и тестирующая программы......2917.4. Двоичный поиск......2957.4.1. Разработка алгоритма......2967.4.2. Вариант с забыванием......2977.4.3. Распознавание равенства......2997.5. Деревья сравнений......3027.5.1. Анализ для n10......3037.5.2. Обобщение......3067.5.3. Методы сравнения......3097.5.4. Общее отношение......3107.6. Нижние границы......3137.7. Асимптотика......3187.7.1. Введение......3187.7.2. О большое......3197.7.3. Неточность определения O большого......3227.7.4. Порядки распространенных функций......323Подсказки и ловушки......324Обзорные вопросы......325Литература для дальнейшего изучения......326Глава 8. Сортировка......3278.1. Введение и обозначения......3278.2. Сортировка включением......3298.2.1. Упорядоченные списки......3298.2.2. Сортировка методом включения......3308.2.3. Связный вариант......3328.2.4. Анализ......3348.3. Сортировка методом выбора......3398.3.1. Алгоритм......3398.3.2. Непрерывная реализация......3408.3.3. Анализ......3428.3.4. Сравнения......3428.4. Упорядочение методом Шелла......3448.5. Нижние границы......3478.6. Сортировка методом разбиения......3508.6.1. Базовые идеи......3508.6.2. Пример......3518.7. Сортировка слиянием для связных списков......3578.7.1. Процедуры......3578.7.2. Анализ метода сортировки слиянием......3598.8. Метод быстрой сортировки для непрерывных списков......3658.8.1. Главная процедура......3658.8.2. Разделение списка......3668.8.3. Анализ метода быстрой сортировки......3688.8.4. Анализ метода быстрой сортировки для среднего случая......3718.8.5. Сравнение с методом слияния......3738.9. Пирамиды и пирамидальная сортировка......3778.9.1. Двухвариантные деревья как списки......3778.9.2. Пирамидальная сортировка......3798.9.3. Анализ пирамидальной сортировки......3828.9.4. Очереди с приоритетами......3838.10. Обзор: сравнение методов......386Подсказки и ловушки......390Обзорные вопросы......391Литература для дальнейшего изучения......392Глава 9. Таблицы и извлечение информации......3949.1. Введение: переход через барьер lgn......3949.2. Прямоугольные массивы......3959.3. Таблицы различных форм......3989.3.1. Треугольные таблицы......3989.3.2. Рваные таблицы......4009.3.3. Инвертированные таблицы......4019.4. Таблицы: новый абстрактный тип данных......4049.5. Приложение: поразрядная сортировка......4079.5.1. Идея метода......4079.5.2. Реализация......4089.5.3. Анализ......4119.6. Хеширование......4129.6.1. Разреженные таблицы......4129.6.2. Выбор хеш-функции......4149.6.3. Разрешение конфликтов с помощью открытой адресации......4179.6.4. Разрешение столкновений посредством связных цепочек......4229.7. Анализ хеширования......4289.8. Заключение: сравнение методов......4349.9. Приложение: снова игра «Жизнь»......4359.9.1. Выбор алгоритма......4359.9.2. Спецификация структур данных......4359.9.3. Главная программа......4379.9.4. Процедуры......438Подсказки и ловушки......442Обзорные вопросы......443Литература для дальнейшего изучения......444Глава 10. Двоичные деревья......44510.1. Двоичные деревья......44510.1.1. Определения......44510.1.2. Просмотр двоичных деревьев......44810.1.3. Связная реализация двоичных деревьев......45310.2. Деревья двоичного поиска......45710.2.1. Упорядоченные списки и реализации......45910.2.2. Поиск по дереву......46010.2.3. Включение в дерево двоичного поиска......46410.2.4. Древовидная сортировка......46710.2.5. Удаление из дерева двоичного поиска......46910.3. Построение дерева двоичного поиска......47710.3.1. Начинаем......47810.3.2. Объявления и главная процедура......47910.3.3. Включение узла......48010.3.4. Завершение задачи......48110.3.5. Оценка......48310.3.6. Случайные деревья поиска и оптимизация......48310.4. Балансирование по высоте: AVL-деревья......48610.4.1. Определение......48710.4.2. Включение узла......48810.4.3. Удаление узла......49410.4.4. Высота AVL-дерева......49810.5. Скошенные деревья: самонастраивающиеся структуры данных......50110.5.1. Введение......50110.5.2. Шаги скашивания дерева......50210.5.3. Алгоритм скашивания......50510.5.4. Амортизационный анализ алгоритмов: введение......50910.5.5. Амортизационный анализ скашивания......514Подсказки и ловушки......519Обзорные вопросы......520Литература для дальнейшего изучения......522Глава 11. Многовариантные деревья......52411.1. Сады
деревья и двоичные деревья......52411.1.1. Классификация видов......52411.1.2. Упорядоченные деревья......52511.1.3. Леса и сады......52811.1.4. Формальное соответствие......52911.1.5. Повороты......53011.1.6. Резюме......53111.2. Деревья лексикографического поиска: трай-деревья......53311.2.1. Трай-деревья......53311.2.2. Поиск ключа......53311.2.3. Алгоритм на языке Pascal......53411.2.4. Включение в трай-дерево......53511.2.5. Удаление из трай-дерева......53611.2.6. Оценка трай-деревьев......53711.3. Внешний поиск: B-деревья......53811.3.1. Время доступа......53811.3.2. Многовариантные деревья поиска......53911.3.3. Сбалансированные многовариантные деревья......53911.3.4. Включение в B-дерево......54011.3.5. Алгоритмы на языке Pascal: поиск и включение......54211.3.6. Удаление из B-дерева......54811.4. Красно-черные деревья......55711.4.1. Введение......55711.4.2. Определения и анализ......55811.4.3. Включение......56011.4.4. Включение на языке Pascal......563Подсказки и ловушки......566Обзорные вопросы......567Литература для дальнейшего изучения......568Глава 12. Графы......56912.1. Математические основы......56912.1.1. Определения и примеры......56912.1.2. Неориентированные графы......57012.1.3. Ориентированные графы......57112.2. Компьютерное представление......57212.3. Просмотр графа......57612.3.1. Методы......57612.3.2. Алгоритм просмотра в глубину......57712.3.3. Алгоритм просмотра в ширину......57812.4. Топологическая сортировка......57912.4.1. Постановка задачи......57912.4.2. Алгоритм упорядочения в глубину......58112.4.3. Алгоритм упорядочения в ширину......58212.5. Алгоритм экономного продвижения: кратчайшие маршруты......58412.6. Графы как структуры данных......589Подсказки и ловушки......591Обзорные вопросы......591Литература для дальнейшего изучения......592Глава 13. Конкретный пример: польская нотация......59313.1. Постановка задачи......59313.1.1. Формула корней квадратного уравнения......59313.2. Идея......59513.2.1. Дерево выражения......59513.2.2. Польская нотация......59713.2.3. Метод для языка Pascal......59913.3. Оценка выражений в польской нотации......59913.3.1. Оценка выражений в префиксной форме......59913.3.2. Соглашения языка Pascal......60013.3.3. Pascal-процедура для префиксной оценки......60113.3.4. Оценка постфиксных выражений......60213.3.5. Доказательство правильности программы: подсчет элементов в стеке......60313.3.6. Рекурсивная оценка постфиксных выражений......60713.4. Преобразование из инфиксной формы в польскую......61113.5. Интерактивная программа оценки выражений......61713.5.1. Общая структура......61813.5.2. Представление данных......61913.5.3. Инициализация и вспомогательные задачи......62313.5.4. Преобразование выражения......62713.5.5. Оценка выражения......63713.5.6. Графическое отображение выражения......639Литература для дальнейшего изучения......642Приложение A. Математические методы......643A.1. Суммы степеней целых чисел......643A.2. Логарифмы......645A.2.1. Определение логарифмов......646A.2.2. Простые свойства......646A.2.3. Выбор основания......647A.2.4. Натуральные логарифмы......648A.2.5. Обозначения......649A.2.6. Изменение основания логарифмов......649A.2.7. Логарифмические графики......650A.2.8. Гармонические числа......650A.3. Перестановки
сочетания
факториалы......652A.3.1. Перестановки......652A.3.2. Сочетания......653A.3.3. Факториалы......653A.4. Числа Фибоначчи......655A.5. Числа Каталана......656A.5.1. Основной результат......656A.5.2. Доказательство посредством однозначного соответствия......657A.5.3. История вопроса......659A.5.4. Численные результаты......659Литература для дальнейшего изучения......661Приложение B. Случайные числа......663B.1. Введение......663B.2. Метод......664B.3. Разработка программы......665Литература для дальнейшего изучения......670Приложение С. Модули
включаемые файлы и утилиты......671C.1. Модули Turbo Pascal......671C.1.1. Введение......671C.1.2. Синтаксис модулей......672C.2. Включаемые файлы......674C.2.1. Замена модулей включаемыми файлами......674C.2.2. Родовые средства......675C.3. Модули
используемые в тексте......677C.3.1. Структуры данных......677C.3.2. Модуль утилит Utility......678C.3.3. Модуль анализа процессорного времени......680C.3.4. Модуль для обслуживания файлов......682C.3.5. Модуль случайных чисел......685C.4. Программы поиска и сортировки......685C.4.1. Демонстрационная программа......685C.4.2. Создание файлов данных для тестирования программ......686Приложение D. Свойства языка Pascal......694D.1. Записи в языке Pascal......694D.2. Процедуры......700D.2.1. Процедуры в качестве параметров......700D.2.2. Упреждающие объявления......702D.3. Указатели и связные списки......703D.3.1. Введение и обзор......703D.3.2. Указатели и динамическая память в языке Pascal......707D.3.3. Основы связных списков......711D.3.4. Связная реализация простых списков......715D.3.5. Советы для программистов......718D.4. Синтаксические диаграммы......721D.5. Общие правила......730D.5.1. Идентификаторы......730D.5.2. Правила использования пробелов......731D.5.3. Указания по формату программы......732D.5.4. Пунктуация......733D.5.5. Альтернативные знаки......733D.6. Стандартные объявления......733D.6.1. Константы......733D.6.2. Типы......735D.6.3. Переменные......735D.6.4. Процедуры......736D.6.5. Функции......736D.7. Операторы......737Предметный указатель......738