2009г.
Эта книга представляет собой учебное пособие для двухсеместрового курса информатики (Computer Science, CS). Начинается она с изучения предмета, традиционно называемого "Структуры данных" (курс CS-2), после чего рассматриваются более изощренные структуры данных и анализ алгоритмов. В часть I описываются некоторые продвинутые средства С++, широко используемые в дальнейшем изложении. Часть II посвящена базовым алгоритмам и строительным блокам. В части III проводится несколько конкретных исследований, и каждая глава посвящена определенной общей теме. В части IV представлены реализации структур данных. Часть V содержит материал, предназначенный для использования в более продвинутом курсе, а также в качестве иллюстрации современных методов. Автор повсюду включает в книгу новейшие средства С++, используя, где это возможно, Стандартную библиотеку шаблонов (STL) с детальными пояснениями. Книга дополнена большим количеством упражнений, от простых до заданий повышенной сложности. Приложения содержат обширный дополнительный справочный материал по С++.
Для студентов и преподавателей.
Предисловие
Уникальный подход
Необходимые предварительные знания i
Обзор изменений, внесенных во второе издание книги С++
Организация книги
Содержание частей книги
Взаимосвязь частей книги
Отдельные разделы
Использование математического аппарата
Организация курса
Упражнения
Методические особенности
Как получить исходные тексты программ
Руководство для преподавателя
Благодарности
Часть I. Объекты и С++
Глава 1. Массивы, указатели и структуры
1.1. Что представляют собой массивы, указатели и структуры?
1.2. Массивы и строки
1.2.1. Объекты первого класса и объекты второго класса
1.2.2. Использование класса vector
1.2.3. Изменение размера объекта vector
1.2.4. Функция push_back: размер size и объем capacity
1.2.5. Механизм передачи параметров
1.2.6. Примитивные массивы констант
1.2.7. Многомерные массивы
1.2.8. Тип string Стандартной библиотеки
1.3. Синтаксис указателя в С++
1.4. Динамическое управление памятью
1.4.1. Оператор new
1.4.2. Сбор мусора и оператор delete
1.4.3. Устаревшие указатели, двойное удаление и другие вопросы
1.5. Ссылочные переменные
1.6. Структуры
1.6.1. Указатели на структуры
1.6.2. Выбор между внешними или внутренними данными и между поверхностным или глубоким копированием
1.6.3. Не непрерывные списки: связные списки
Итоги
Упражнения
Рекомендуемая литература
Глава 2. Объекты и классы
2.1. Что представляет собой объектно-ориентированное программирование?
2.2. Основы синтаксиса класса
2.2.1. Члены класса
2.2.2. Дополнительные детали синтаксиса конструктора и аксессоры
2.2.3. Разделение интерфейса и реализации
2.2.4. Большая троица: деструктор, конструктор копий и оператор =
2.2.5. Конструктор по умолчанию
2.3. Дополнительные средства С++ для классов
2.3.1. Еще раз об инициализации и присваивании в конструкторе
2.3.2. Преобразования типов
2.3.3. Перегрузка операторов
2.3.4. Ввод-вывод и друзья класса
2.4. Некоторые общеупотребительные приемы
2.4.1. Устранение дружественных функций
2.4.2. Статические члены класса
2.4.3. Трюк с ключевым словом enum для определения целочисленных констант класса
2.5. Исключения
2.6. Класс string
2.7. Повторение: что вызывается в разных случаях и каковы действия по умолчанию?
2.8. Включение
Итоги
Упражнения
Рекомендуемая литература
Глава 3. Шаблоны
3.1. Что такое шаблон?
3.2. Шаблонные функции
3.3. Шаблонная функция сортировки
3.4. Шаблонные классы
3.4.1. Шаблон MemoryCell
3.4.2. Реализация шаблонного класса vector
3.5. Шаблон шаблонов: класс matrix
3.5.1. Данные-члены, конструктор и основные аксессоры
3.5.2. Оператор operator[]
3.5.3. Деструктор, присваивание копированием и конструктор копий...
3.6. Причудливые шаблоны
3.6.1. Множественные параметры шаблона
3.6.2. Параметры шаблона по умолчанию
3.6.3. Зарезервированное слово typename
3.7. Ошибки при использовании шаблонов
3.7.1. Неправильные сообщения об ошибках и противоречивые правила
3.7.2. Алгоритмы поиска соответствия шаблонов
3.7.3. Вложенные классы в шаблоне
3.7.4. Статические члены в шаблонах классов
Итоги
Глава 4. Наследование
4.1. Что такое наследование?
4.2. Основы наследования
4.2.1. Правила видимости
4.2.2. Конструктор и инициализация базового класса
4.2.3. Добавление членов
4.2.4. Замещение метода
4.2.5. Статическое и динамическое связывание
4.2.6. Конструктор по умолчанию, конструктор копий, оператор присваивания копированием и деструктор
4.2.7. Конструкторы и деструкторы: виртуальные или невиртуальные?
4.2.8. Абстрактные методы и классы
4.3. Пример: развитие класса Shape
4.4. Хитрые детали С++
4.4.1. Статическое связывание параметров
4.4.2. Параметры по умолчанию
4.4.3. Методы производного класса скрывают методы базового класса
4.4.4. Совместимые типы возврата для замещенных методов
4.4.5. Закрытое наследование
4.4.6. Друзья класса
4.4.7. Вызов по значению и полиморфизм не сочетаются
4.5. Множественное наследование
Итоги
Упражнения
Рекомендуемая литература
Глава 5. Шаблоны разработки
5.1. Что такое шаблон?
5.2. Функторы (функциональные объекты)
5.3. Адаптеры и оболочки
5.3.1. Класс-оболочка для указателей
5.3.2. Класс-оболочка константной ссылки
5.3.3. Адаптеры: изменение интерфейса
5.4. Итераторы
5.4.1. Итератор. Разработка 1
5.4.2. Итератор. Разработка 2
5.4.3. Итераторы, основанные на наследовании, и фабрики
5.5. Объединение (класс pair)
5.6. Наблюдатель
Итоги
Упражнения
Рекомендуемая литература
Часть II. Алгоритмы и строительные блоки
Глава 6. Анализ алгоритмов
6.1. Что представляет собой анализ алгоритма?
6.2. Примеры времени выполнения алгоритмов
6.3. Задача определения максимальной суммы непрерывной подпоследовательности
6.3.1. Очевидный алгоритм сложности 0(N3)
6.3.2. Улучшенный алгоритм сложности 0(N2)
6.3.3. Линейный алгоритм
6.4. Общие правила использования О большого
6.5. Логарифм
6.6. Задача статического поиска
6.6.1. Последовательный поиск
6.6.2. Двоичный поиск
6.6.3. Интерполяционный поиск
6.7. Проверка анализа алгоритма
6.8. Ограничения анализа посредством О большого
Итоги
Упражнения
Рекомендуемая литература
Глава 7. Стандартная библиотека шаблонов STL
7.1. Введение
7.2. Стеки и очереди
7.2.1. Стеки
7.2.2. Стеки и компьютерные языки
7.2.3. Очереди
7.3. Контейнеры и итераторы
7.3.1. Контейнеры
7.3.2. Итератор iterator
7.4. Алгоритмы библиотеки STL
7.4.1. Функциональные объекты библиотеки STL
7.4.2. Двоичный поиск
7.4.3. Сортировка
7.5. Реализация класса vector с итератором
7.6. Последовательности и связные списки
7.6.1. Класс списка list
7.6.2. Стеки и очереди
7.7. Множества
7.8. Таблицы отображений
7.9. Очереди с приоритетами
Итоги
Упражнения
Рекомендуемая литература
Глава 8. Рекурсия
8.1. Что такое рекурсия?
8.2. Исходные данные: доказательства методом математической индукции
8.3. Основы рекурсии
8.3.1. Вывод чисел в любой системе счисления
8.3.2. Почему оно работает
8.3.3. Как оно работает
8.3.4. Слишком много рекурсии может представлять опасность
8.3.5. Введение в деревья
8.3.6. Дополнительные примеры
8.4. Численные применения
8.4.1. Вычисления по модулю
8.4.2. Возведение в степень по модулю
8.4.3. Наибольший общий делитель и мультипликативные инверсии
8.4.4. RSA-кодирование
8.5. Алгоритмы разбиения
8.5.1. Задача определения максимальной суммы непрерывной подпоследовательности
8.5.2. Анализ рекурсивного алгоритма в методе разбиения
8.5.3. Общий случай верхней границы времени выполнения для алгоритмов разбиения
8.6. Динамическое программирование
8.7. Алгоритмы с отходом
Итоги
Упражнения
Рекомендуемая литература
Глава 9. Алгоритмы сортировки
9.1. Почему сортировка имеет такое значение?
9.2. Предварительные замечания
9.3. Анализ сортировки включением и других простых алгоритмов сортировки
9.4. Сортировка Шелла
9.4.1. Производительность сортировки Шелла
9.5. Сортировка слиянием
9.5.1. Слияние упорядоченных массивов за линейное время
9.5.2. Алгоритм сортировки слиянием
9.6. Быстрая сортировка
9.6.1. Алгоритм быстрой сортировки
9.6.2. Анализ быстрой сортировки
9.6.3. Выбор опорного элемента
9.6.4. Стратегия разделения
9.6.5. Ключи, равные опорному
9.6.6. Разделение методом среднего из трех элементов
9.6.7. Небольшие массивы
9.6.8. Процедура быстрой сортировки на С++
9.7. Быстрый выбор
9.8. Нижняя граница процедуры сортировки
9.9. Косвенная сортировка
9.9.1. Использование указателей для уменьшения числа копий объектов Comparable до величины 2N
9.9.2. Устранение дополнительного массива
Итоги
Упражнения
Рекомендуемая литература
Глава 10. Рандомизация
10.1. Зачем нам нужны случайные числа?
10.2. Генераторы случайных чисел
10.3. Случайные числа с неравномерным распределением
10.4. Генерирование случайных перестановок
10.5. Рандомизированные алгоритмы
10.6. Рандомизированная проверка на простоту числа
Итоги
Упражнения
Рекомендуемая литература
Часть III. Приложения
Глава 11. Развлечения и игры
11.1. Игры в поиск слов
11.1.1. Теория
11.1.2. Реализация на С++
11.2. Игра в крестики-нолики
11.2.1. Альфа-бета отсечение
11.2.2. Таблицы транспозиции
11.2.3. Компьютерные шахматы
Итоги
Упражнения
Рекомендуемая литература
Глава 12. Стеки и компиляторы
12.1. Программа проверки сбалансированности символов
12.1.1. Базовый алгоритм
12.1.2. Реализация
12.2. Простой калькулятор
12.2.1. Постфиксные автоматы
12.2.2. Преобразование инфиксной формы в постфиксную
12.2.3. Реализация
12.2.4. Деревья выражений
Итоги
Упражнения
Рекомендуемая литература
Глава 13. Утилиты
13.1. Сжатие файлов
13.1.1. Префиксные коды
13.1.2. Алгоритм Хаффмана
13.1.3. Реализация
13.2. Генератор перекрестных ссылок
13.2.1. Базовые идеи
13.2.2. Реализация на С++
Итоги
Упражнения
Рекомендуемая литература
Глава 14. Моделирование
14.1. Задача Иосифа
14.1.1. Простое решение
14.1.2. Более эффективный алгоритм
14.2. Моделирование, управляемое событиями
14.2.1. Базовые идеи
14.2.2. Пример: моделирование банка модемов
Итоги
Упражнения
Глава 15. Графы и маршруты
15.1. Определения
15.1.1. Представление
15.2. Задача поиска кратчайшего невзвешенного пути
15.2.1. Теория
15.2.2. С++-реализация
15.3. Задача поиска кратчайшего положительно взвешенного пути
15.3.1. Теория: алгоритм Дейкстры
15.3.2. С++-реализация
15.4. Задача поиска кратчайшего отрицательно взвешенного пути
15.4.1. Теория
15.4.2. С++-реализация
15.5. Задача поиска кратчайшего пути в ациклических графах
15.5.1. Топологическая сортировка
15.5.2. Теория алгоритма поиска кратчайшего пути в ациклическом графе
15.5.3. С++-реализация
15.5.4. Приложение: анализ критического пути
Итоги
Упражнения
Рекомендуемая литература
Часть IV. Реализации
Глава 16. Стеки и очереди
16.1. Реализации на базе динамических массивов
16.1.1. Стеки
16.1.2. Очереди
16.2. Реализации на базе связных списков
16.2.1. Стеки
16.2.2. Очереди
16.3. Сравнение обоих методов
16.4. Адаптеры библиотеки STL для стека и очереди
16.5. Очереди с двусторонним доступом
Итоги
Упражнения
Глава 17. Связные списки
17.1. Базовые идеи
17.1.2. Головные узлы
17.1.2. Классы итераторов
17.2. С++-реализация
17.3. Дважды связные списки и кольцевые связные списки
17.4. Упорядоченные связные списки
17.5. Реализация класса list библиотеки STL
Итоги
Упражнения
Глава 18. Деревья
18.1. Общие характеристики деревьев
18.1.1. Определения
18.1.2. Реализация
18.1.3. Приложение: файловые системы
18.2. Двоичные деревья
18.3. Рекурсия и деревья
18.4. Обход дерева: итераторные классы
18.4.1. Обратный обход
18.4.2. Симметричный обход
18.4.3. Прямой обход
18.4.4. Поуровневый обход
Итоги
Упражнения
Глава 19. Двоичные деревья поиска
19.1. Базовые идеи
19.1.1. Операции
19.1.2. С++-реализация
19.2. Порядковые операции
19.2.1. С++-реализация
19.3. Анализ операций над двоичным деревом поиска
19.4. AVL-деревья
19.4.1. Свойства
19.4.2. Одиночный поворот
19.4.3. Двойной поворот
19.4.4. Обзор AVL-включений
19.5. Красно-черные деревья
19.5.1. Восходящее включение
19.5.2. Нисходящие красно-черные деревья
19.5.3. С++-реализация
19.5.4. Нисходящее удаление
19.6. АА-деревья
19.6.1. Включение
19.6.2. Удаление
19.6.3. С++-реализация
19.7. Реализация классов set и тар библиотеки STL
19.8. В-деревья
Итоги
Упражнения
Рекомендуемая литература
Глава 20. Хеш-таблицы
20.1. Базовые идеи
20.2. Хеш-функция
20.3. Линейное зондирование
20.3.1. Примитивный анализ линейного зондирования
20.3.2. Что происходит в действительности: первичная кластеризация
20.3.3. Анализ операции поиска find
20.4. Квадратичное зондирование
20.4.1. С++-реализация
20.4.2. Анализ квадратичного зондирования
20.5. Хеширование с раздельными цепочками -таблиц и двоичных деревьев поиска.
20.6. Сравнение хеш-
20.7. Приложения операций хеширования
Итог
Упражнения
Рекомендуемая литература
Глава 21. Очередь с приоритетами: двоичная пирамида
21.1. Базовые идеи
21.1.1. Свойство структуры
21.1.2. Свойство порядка пирамиды
21.1.3. Допустимые операции
21.2. Реализация базовых операций
21.2.1. Операция insert
21.2.2. Операция deleteMin
21.3. Операция buildHeap: конструирование пирамиды за линейное время
21.4. Реализация класса priority_queue из библиотеки STL
21.5. Более сложные операции: decreaseKey и merge
21.6. Внутренняя сортировка: пирамидальная сортировка
21.7. Внешняя сортировка
21.7.1. Зачем нам нужны новые алгоритмы
21.7.2. Модель внешнего упорядочения
21.7.3. Простой алгоритм
21.7.4. Многоканальное слияние
21.7.5. Полифазное слияние
21.7.6. Выбор с замещением
Итоги
Упражнения
Рекомендуемая литература
Часть V. Более сложные структуры данных
Глава 22. Скошенные деревья
22.1. Саморегулирование и амортизационный анализ
22.1.1. Амортизированные временные границы
22.1.2. Простая стратегия саморегулирования (которая не работает)
22.2. Базовое восходящее скошенное дерево
22.3. Базовые операции над скошенным деревом
22.4. Анализ восходящего скашивания
22.4.1. Доказательство для границы скашивания
22.5. Нисходящие скошенные деревья
22.6. Реализация нисходящих скошенных деревьев
22.7. Сравнение скошенного дерева с другими деревьями поиска
Итоги
Упражнения
Рекомендуемая литература
Глава 23. Слияние очередей с приоритетами
23.1. Несимметричная пирамида
23.1.1. Слияние является фундаментальной операцией
23.1.2. Упрощенная процедура слияния для деревьев с порядком пирамиды.
23.1.3. Несимметричная пирамида: простая модификация
23.1.4. Анализ несимметричной пирамиды
23.2. Парная пирамида
23.2.1. Операции над парной пирамидой
23.2.2. Реализация парной пирамиды
23.2.3. Приложение: алгоритм Дейкстры поиска кратчайшего взвешенного пути
Итоги
Упражнения
Рекомендуемая литература
Глава 24. Класс непересекающихся множеств
24.1. Отношения эквивалентности
24.2. Динамическая эквивалентность и два приложения
24.2.1. Приложение: генерирование лабиринтов
24.2.2. Приложение: минимальные остовные деревья
24.2.3. Приложение: задача поиска ближайшего общего предка
24.3. Алгоритм быстрого поиска
24.4. Алгоритм быстрого объединения
24.4.1. Интеллектуальные алгоритмы объединения
24.4.2. Сокращение пути
24.5. С++-реализация
24.6. Худший случай для объединения по рангу с сокращением путей
24.6.1. Анализ алгоритма объединения/поиска
Итоги
Упражнения
Рекомендуемая литература
Приложения
Приложение А. Различные детали С++
АЛ. Ни один компилятор не реализует стандарт языка
А.2. Необычные операторы С+
А.2.1. Операторы автоинкремента и автодекремента
А.2.2. Преобразования типов
А.2.3. Операторы для работы с битами
А.2.4. Условный оператор
А.З. Аргументы командной строки
А.4. Ввод и вывод
А.4.1. Базовые потоковые операции
А.4.2. Последовательные файлы
А.4.3. Потоки строк
А. 5. Пространства имен
А.6. Новые средства С++
Приложение В. Операторы
Приложение С. Некоторые библиотечные процедуры
СЛ. Процедуры, объявленные в и
С.2. Константы, объявленные в и
С.З. Процедуры, объявленные в и
С.4. Процедуры, объявленные в и
Приложение D. Примитивные массивы в С++
D.1. Примитивные массивы
D.1.1. Реализация в С++: имя массива является указателем
D.1.2. Многомерные массивы
D.1.3. Тип char, указатели const и константные строки
D.2. Динамическое выделение памяти под массивы: new[ ] и delete[ ]
D.3. Арифметика указателей, перемещение указателей и примитивная итерация
D.3.1. Проблемы приоритетов операторов
D.3.2. Что означает арифметика указателей
D.3.3. Пример смещения указателей
D.3.4. Стоит ли использовать перемещение указателей?
Алфавитный указатель
