Предисловие
Глава 1. Введение
1.1. Абстрактные типы данных
ADT - формат
1.2. Классы C++ и абстрактные типы
Инкапсуляция и скрытие информации
Передача сообщений
1.3. Объекты в приложениях C++
Приложение: класс Circle
1.4. Разработка объектов
Объекты и композиция
C++ геометрические классы
Объекты и наследование
Наследование в программировании
Упорядоченные списки и наследование
Повторное использование кода
Спецификации класса SeqList и
OrderedList
1.5. Приложения с наследованием классов
1.6. Разработка объектно-ориентированных
программ
Анализ задачи/определение программы
Разработка
Кодирование
Тестирование
Иллюстрация программной разработки: Dice
график
1.7. Тестирование и сопровождение программы
Объектное тестирование
Тестирование управляющего модуля
Программное сопровождение и
документирование
1.8. Язык программирования C++
1.9. Абстрактные базовые классы и
полиморфизм
Полиморфизм и динамическое связывание
Письменные упражнения
Глава 2. Базовые типы данных
2.1. Целочисленные типы
Компьютерное хранение целых чисел
Данные в памяти
Представление целых в языке C++
2.2. Символьные типы
Символы ASCII
2.3. Вещественные типы
Представление вещественных чисел
2.4. Типы перечисления
Реализация типов перечисления C++
2.5. Указатели
Указатели ADT
Значения указателя
2.6. Массив (array)
Встроенный тип массива C++
Сохранение одномерных массивов
Границы массива
Двумерные массивы
Сохранение двумерных массивов
2.7. Строковые константы и переменные
Строки C++
Приложение: перестановка имен
2.8. Записи
Структуры C++
2.9. Файлы
Иерархия потоков C++
2.10. Приложения массива и записи
Последовательный поиск
Обменная сортировка
Подсчет зарезервированных слов C++
Письменные упражнения
Упражнения по программированию
Глава 3. Абстрактные типы данных и классы
3.1. Пользовательский тип - КЛАСС
Объявление класса
Конструктор
Объявление объекта
Реализация класса
Реализация конструктора
Создание объектов
3.2. Примеры классов
Класс Temperature
Класс случайных чисел
3.3. Объекты и передача информации
Объект как возвращаемое значение
Объект как параметр функции
3.4. Массивы объектов
Конструктор умолчания
3.5. Множественные конструкторы
3.6. Практическое применение: Треугольные
матрицы
Свойства верхней треугольной матрицы
Класс TriMat
Письменные упражнения
Упражнения по программированию
Глава 4. Классы коллекций
4.1. Описание линейных коллекций
Коллекции с прямым доступом
Коллекции с последовательным доступом
Универсальная индексация
4.2. Описание нелинейных коллекций
Коллекции групп
4.3. Анализ алгоритмов
Критерии эффективности
Общий порядок величин
4.4. Последовательный и бинарный поиск
Бинарный поиск
4.5. Базовый класс последовательного списка
Методы модификации списка
Письменные упражнения
Упражнения по программированию
Глава 5. Стеки и очереди
5.1. Стеки
5.2. Класс Stack
5.3. Оценка выражений
Постфиксная оценка
Применение: постфиксный калькулятор
5.4. Очереди
5.5. Класс Queue
5.6. Очереди приоритетов
Класс PQueue
Приложение: службы поддержки компании
5.7. Практическое применение:
Управляемое событиями моделирование
Разработка приложения
Информация моделирования
Установка параметров моделирования
Выполнение задачи моделирования
Письменные упражнения
Упражнения по программированию
Глава 6. Абстрактные операторы
6.1. Описание перегрузки операторов
Определяемые пользователем внешние
функции
Члены класса
Дружественные функции
6.2. Система рациональных чисел
Представление рациональных чисел
Арифметика рациональных чисел
Преобразование рациональных чисел
6.3. Класс Rational
6.4. Операторы класса Rational как
функции-члены
Реализация операторов класса Rational
6.5. Операторы потока класса Rational как
дружественные функции
Реализация операторов потока класса
Rational
6.6. Преобразование рациональных чисел
Преобразование в объектный тип
Преобразование из объектного типа
6.7. Использование рациональных чисел
Письменные упражнения
Упражнения по программированию
Глава 7. Параметризованные типы данных
7.1. Шаблонные функции
Сортировка на базе шаблона
7.2. Шаблонные классы
Определение шаблонного класса
Объявление объектов шаблонного класса
Определение методов шаблонного класса
7.3. Шаблонные списковые классы
7.4. Вычисление инфиксного выражения
Письменные упражнения
Упражнения по программированию
Глава 8. Классы и динамическая память
8.1. Указатели и динамические структуры
данных
Оператор new для выделения памяти
Динамическое выделение массива
Оператор delete освобождения памяти
8.2. Динамически создаваемые объекты
Освобождение данных объекта: деструктор
8.3. Присваивание и инициализация
Проблемы присваивания
Перегруженный оператор присваивания
Указатель this
Проблемы инициализации
Создание конструктора копирования
8.4. Надежные массивы
Класс Array
Выделение памяти для класса Array
Проверка границ массива и перегруженный
оператор []
Преобразование объекта в указатель
Использование класса Array
8.5. Класс String
Реализация класса String
8.6. Сопоставление с образцом
Процесс Find
Алгоритм сопоставления с образцом
Анализ алгоритма сопоставления с
образцом
8.7. Целочисленные множества
Множества целочисленных типов
Побитовые операторы C++
Представление элементов множества
Решето Эратосфена
Письменные упражнения
Упражнения по программированию
Глава 9. Связанные списки
Описание связанного списка
Обзор главы
9.1. Класс Node
Объявление типа Node
Реализация класса Node
9.2. Создание связанных списков
Создание узла
Вставка узла: InsertFront
Прохождение по связанному списку
Вставка узла: InsertRear
Приложение: Список выпускников
Создание упорядоченного списка
Приложение: сортировка со связанными
списками
9.3. Разработка класса связанного списка
Данные-члены связанных списков
Операции связанных списков
9.4. Класс LinkedList
Конкатенация двух списков
Сортировка списка
9.5. Реализация класса LinkedList
9.6. Реализация коллекций со связанными
списками
Связанные очереди
Реализация методов Queue
Использование объекта LinkedList с
классом SeqList
Реализация методов доступа к данным
класса SeqList
Приложение: Сравнение реализации SeqList
9.7. Исследовательская задача: Буферизация
печати
Анализ проблемы
Разработка программы
Реализация метода UPDATE для класса
Spooler
Методы оценки системы буферизации печати
9.8. Циклические списки
Реализация класса CNode
Приложение: Решение задачи Джозефуса
9.9. Двусвязные списки
Приложение: Сортировка двусвязного
списка
Реализация класса DNode
9.10. Практическая задача: Управление
окнами
Список окон
Реализация класса WindowLjst
Письменные упражнения
Упражнения по программированию
Глава 10. Рекурсия
10.1. Понятие рекурсии
Рекурсивные определения
Рекурсивные задачи
10.2. Построение рекурсивных функций
10.3. Рекурсивный код и стек времени
исполнения
Стек времени исполнения
10.4. Решение задач с помощью рекурсии
Бинарный поиск
Комбинаторика: задача о комитетах
Комбинаторика: перестановки главы
Прохождение лабиринта
Реализация класса Maze
10.5. Оценка рекурсии
Письменные упражнения
Упражнения по программированию
Глава 11. Деревья
Терминология деревьев
Бинарные деревья
11.1. Структура бинарного дерева
Проектирование класса TreeNode
Построение бинарного дерева
11.2. Разработка функций класса TreeNode
Рекурсивные методы прохождения деревьев
Симметричный метод прохождения дерева
11.3. Использование, алгоритмов прохождения
деревьев
Приложение: посещение узлов дерева
Приложение: печать дерева
Приложение: копирование и удаление
деревьев
Приложение: вертикальная печать дерева
11.4. Бинарные деревья поиска
Ключ в узле бинарного дерева поиска
Операции на бинарном дереве поиска
Объявление абстрактного типа деревьев
11.5. Использование бинарных деревьев
поиска
Дублированные узлы
11.6. Реализация класса BinSTree
Операции обработки списков
11.7. Практическая задача: конкорданс
Письменные упражнения
Упражнения по программированию
Глава 12. Наследование и абстрактные классы
12.1. Понятие о наследовании
Терминология наследования
12.2. Наследование в С++
Конструкторы и производные классы
Что нельзя наследовать
12.3. Полиморфизм и виртуальные функции
Демонстрация полиморфизма
Приложение: геометрические фигуры и
виртуальные методы
Виртуальные методы и деструктор
12.4. Абстрактные базовые классы
Абстрактный базовый класс List
Образование класса SeqList из
абстрактного базового класса List
12.5. Итераторы
Абстрактный базовый класс Iterator
Образование итераторов для списка
Построение итератора SeqList
Итератор массива
Приложение: слияние сортированных
последовательностей
Реализация класса ArrayIterator
12.6. Упорядоченные списки
12.7. Разнородные списки
Разнородные массивы
Разнородные связанные списки
Письменные упражнения
Упражнения по программированию
Глава 13. Более сложные нелинейные структуры
13.1. Бинарные деревья, представляемые
массивами
Приложение: турнирная сортировка
13.2. Пирамиды
Пирамида как список
Класс Heap
13.3. Реализация класса Heap
Приложение: пирамидальная сортировка
13.4. Очереди приоритетов
Приложение: длинные последовательности
13.5. AVL-деревья
Узлы AVL-дерева
13.6. Класс AVLTree
Распределение памяти для AVLTree
Оценка сбалансированных деревьев
13.7. Итераторы деревьев
Итератор симметричного метода
прохождения
Реализация класса Inorderlterator
Приложение: алгоритм TreeSort
13.8. Графы
Связанные компоненты
13.9. Класс Graph
Объявление абстрактного типа данных
Graph
Реализация класса Graph
Способы прохождения графов
Приложения
Достижимость и алгоритм Уоршалла
Письменные упражнения
Упражнения по программированию
Глава 14. Организация коллекций
14.1. Основные алгоритмы сортировки
массивов
Сортировка посредством выбора
Сортировка методом пузырька
Вычислительная сложность сортировки
методом пузырька
Сортировка вставками
14.2. "Быстрая сортировка"
Описание "быстрой сортировки"
Алгоритм Quicksort
Сравнение алгоритмов сортировки массивов
14.3. Хеширование
Ключи и хеш-функция
Хеш-функции
Другие методы хеширования
Разрешение коллизий
14.4. Класс хеш-таблиц
Приложение: частота символьных строк
Реализация класса HashTable
Реализация класса HashTableIterator
14.5. Производительность методов поиска
14.6. Бинарные файлы и операции с данными
на внешних носителях
Бинарные файлы
Класс BinFile
Внешний поиск
Внешняя сортировка
Сортировка естественным слиянием
14.7. Словари
Письменные упражнения
Упражнения по программированию
Приложение
Ответы на избранные письменные упражнения
Предметный указатель
Index