Структуры данных и стандартная библиотека шаблонов, Коллинз У.Дж., 2004

Структуры данных и стандартная библиотека шаблонов, Коллинз У.Дж., 2004.
 
   В книге рассматриваются основы организации структур данных и их реализации с использованием C++ в качестве языка инструкций. Большинство рассматриваемых структур данных, таких как массивы, векторы, очереди, списки и стеки, имеются в составе стандартной библиотеки шаблонов (STL). Достаточно подробно исследуется каноническая реализация этих структур данных, которая является как эффективной, так и краткой. Большое внимание уделяется также алгоритмам для работы со структурами данных.
Книга следует принципу изучения на практических примерах. Программные проекты в конце каждой главы позволяют читателю разрабатывать и реализовывать свои собственные структуры данных, либо расширять или применять структуры данных, рассматриваемые в главе. При выполнении лабораторных работ, предусмотренных в каждой главе, читатель сможет получить практические навыки применения полученных знаний при реальном программировании.
Книга может быть использована в качестве учебного пособия при изучении компьютерных технологий в программах высших учебных заведений.




Наследование.
Следует стремиться писать программные компоненты, которые могут быть использованы многократно. Например, вместо того, чтобы определять функцию, которая вычисляет среднее 10 значений, лучше определить функцию, которая вычисляет среднее значение любого количества чисел. Создавая код, допускающий многократное использование, мы не только экономим время, но и сводим на нет риск некорректной модификации существующего кода.

Одним из способов сделать классы многократно используемыми является применение механизма наследования. Наследование — это возможность определять новый класс, который включает в себя все поля и некоторые или все методы существующего класса. Ранее существующий класс называется суперклассом, базовым классом или классом-предком. Новый класс, который может объявлять новые поля и методы, называется подклассом, производным классом или классом-потомком. Подкласс может также замещать (подменять) существующие методы, предоставляя для них определения методов, отличные от тех, которые содержатся в суперклассе.

ОГЛАВЛЕНИЕ.
Предисловие.
Глава 1. Классы в C++.
1.1. Классы.
1.1.1. Интерфейсы методов.
1.1.2. Объекты.
1.1.3. Абстракция данных.
1.1.4. Конструкторы.
1.1.5. Класс Employee.
1.1.6. Определение класса Employee.
1.1.7. Наследование.
1.1.8. Защищенный доступ.
1.1.9. Класс HourlyEmployee.
1.1.10. Перегрузка операторов.
1.1.11. Дружественные классы и методы.
1.1.12. Сокрытие информации.
Резюме.
Упражнения.
Программный проект 1.1. Класс Sequence.
Глава 2. Структуры хранения данных для классов-контейнеров.
2.1. Указатели.
2.1.1. Динамически распределяемая область памяти и стек.
2.1.2. Параметры-ссылки.
2.1.3. Поля-указатели.
2.1.4. Массивы и указатели.
2.1.5. Освобождение динамических переменных.
2.2. Массивы.
2.3. Классы-контейнеры.
2.3.1. Структуры хранения данных для классов-контейнеров.
2.3.2. Связанные структуры.
2.3.3. Итераторы.
2.3.4. Структура и реализация класса Iterator.
2.3.5. Метод pop_front.
2.3.6. Деструкторы.
2.3.7. Обобщенные алгоритмы.
2.3.8. Структуры данных и стандартная библиотека шаблонов.
Резюме.
Упражнения.
Программный проект 2.1. Расширение класса Linked.
Глава 3. Введение в программную инженерию.
3.1. Цикл разработки программного обеспечения.
3.2. Анализ задачи.
3.2.1. Системные тесты.
3.3. Разработка плана программы.
3.3.1. Интерфейсы методов и поля.
3.3.2. Диаграммы зависимостей.
3.4. Реализация программы.
3.4.1. Проверка корректности метода.
3.4.2. Достижима ли полная корректность?.
3.4.2. Оценка эффективности методов.
3.4.4. Нотация «большого О».
3.4.5. Быстрая оценка с помощью «большого О».
3.4.6. Выбор разумного компромисса.
3.4.7. Анализ в процессе выполнения.
3.4.8. Случайная выборка.
3.4.9. Преобразование типов.
3.5. Сопровождение программы.
Резюме.
Упражнения.
Программный проект 3.1. Дальнейшее расширение класса Linked.
Глава 4. Рекурсия.
4.1. Введение.
4.2. Факториалы.
4.2.1. Фреймы выполнения.
4.3. Десятично-двоичное преобразование.
4.4. Ханойские башни.
4.4.1. Рекуррентное соотношение.
4.5. Поиск с возвратом.
4.5.1. Поиск пути в лабиринте.
4.6. Двоичный поиск.
4.7. Получение всех возможных перестановок.
4.7.1. Оценка времени выполнения и потребности в памяти.
4.8. Косвенная рекурсия.
4.9. Цена рекурсии.
Резюме.
Упражнения.
Программный проект 4.1. Итеративная версия задачи о Ханойских башнях.
Программный проект 4.2. Задача о восьми ферзях.
Программный проект 4.3. Маршрут коня.
Глава 5. Векторы и очереди с двусторонним доступом.
5.1. Стандартная библиотека шаблонов.
5.2. Векторы.
5.2.1. Интерфейсы методов класса vector.
5.2.2. Итераторы класса vector.
5.2.3. Сравнение векторов с другими видами контейнеров.
5.2.4. Поля класса vector, допустимые к использованию.
5.2.5. Реализация класса vector.
5.3. Применение векторов: арифметические действия с высокой точностью.
5.3.1. Структура класса very_long_int.
5.3.2. Реализация класса very_long_int.
5.4. Очереди с двусторонним доступом.
5.4.1 Поля и реализация класса deque.
5.5. Применение очереди с двусторонним доступом: сверхбольшие целые числа.
Резюме.
Упражнения.
Программный проект 5.1. Расширение класса very_long_int.
Программный проект 5.2. Альтернативная реализация класса deque.
Глава 6. Списки.
6.1. Списки.
6.1.1. Интерфейсы методов класса list.
6.1.2. Интерфейсы итератора.
6.1.3. Различия между методами списков и методами векторов или двусторонних очередей.
6.1.4. Поля и реализации класса list.
6.1.5. Хранение информации в узлах списка.
6.1.6. Альтернативные реализации класса list.
6.2. Применение списков: простой строчный редактор.
6.2.1. Структура класса Editor.
6.2.2. Реализация класса Editor.
Резюме.
Упражнения.
Программный проект 6.1. Расширение класса Editor.
Программный проект 6.2. Альтернативная реализация класса list.
Глава 7. Очереди и стеки.
7.1. Очереди.
7.1.1. Интерфейсы методов класса queue.
7.1.2. Использование класса queue.
7.1.3. Адаптеры контейнеров.
7.1.4. Базовый класс на основе массива.
7.2. Компьютерное моделирование.
7.3. Применение очереди: модель мойки автомобилей.
7.3.1. Структура программы.
7.3.2. Реализация класса CarWash.
7.3.3. Анализ методов класса CarWash.
7.3.4. Как сделать время прибытия случайным.
7.4. Стеки.
7.4.1. Интерфейсы методов класса stack.
7.4.2. Использование класса stack.
7.4.3. Класс stack как адаптер контейнера.
7.5. Применение стека (1): как реализуется рекурсия.
7.6. Применение стека (2): преобразование инфиксной нотации в постфиксную.
7.6.1. Постфиксная нотация.
7.6.2. Матрица перевода.
7.6.3. Лексемы.
7.6.4. Префиксная нотация.
Резюме.
Упражнения.
Программный проект 7.1. Расширение модели мойки автомобилей.
Программный проект 7.2. Оценка условия.
Программный проект 7.3. Итеративная версия решения задачи прохождения лабиринта.
Программный проект 7.4. Альтернативный дизайн класса queue.
Глава 8. Двоичные деревья и двоичные деревья поиска.
8.1 Определение и свойства.
8.1.1. Теорема о двоичном дереве.
8.1.2. Длина внешнего пути.
8.1.3. Способы обхода двоичного дерева.
8.2. Двоичные деревья поиска.
8.2.1. Класс BinSearchTree.
8.2.2. Класс Iterator для класса BinSearchTree.
8.2.3. Поля и реализация класса BinSearchTree.
8.2.4. Рекурсивные методы?.
8.2.5. Итераторы класса BinSearchTree.
Резюме.
Упражнения.
Программный проект 8.1. Альтернативная реализация класса BinSearchTree.
Глава 9. AVL-деревья.
9.1. Сбалансированные двоичные деревья поиска.
9.2. Повороты.
9.3. AVL-деревья.
9.3.1. Высота AVL-дерева.
9.3.2. Объекты-функции.
9.3.3. Класс AVLTree.
9.3.4. Метод fixAfterInsertion.
9.3.5. Корректность метода insert.
9.4. Применение AVL-дерева: простая программа проверки орфографии.
Резюме.
Упражнения.
Программный проект 9.1. Метод erase класса AVLTree.
Программный проект 9.2. Усовершенствование программы проверки орфографии.
Глава 10. Красно-черные деревья.
10.1. Красно-черные деревья.
10.1.1. Высота красно-черного дерева.
10.1.2. Класс rb_tree Hewlett-Packard.
10.1.3. Метод insert класса rb_tree.
10.1.4. Метод erase.
10.2. Ассоциативные контейнеры в составе стандартной библиотеки шаблонов.
10.2.1. Класс set.
10.3. Модифицированная программа проверки орфографии.
10.3.1. Класс multiset.
10.3.2. Класс шар.
10.3.3. Класс multimap.
Резюме.
Упражнения.
Программный проект 10.1. Простой словарь синонимов (тезаурус).
Программный проект 10.2. Построение алфавитного указателя слов (конкорданса).
Глава 11. Очереди с приоритетом и кучи.
11.1 Введение.
11.1.1. Класс priority_queue.
11.1.2. Поля и реализация класса priority_queue.
11.1.3. Кучи.
11.1.4. Альтернативные конструкции и реализации класса priority_queue.
11.2. Применение очередей с приоритетом: коды Хаффмана.
11.2.1. Структура класса huff man.
11.2.2. Реализация класса huffman.
Резюме.
Упражнения.
Программный проект 11.1. Декодирование сообщения.
Глава 12. Сортировка.
12.1. Введение.
12.1.1. Сортировка методом вставки.
12.2. Насколько быстрой может быть сортировка?.
12.3. Быстрые методы сортировки.
12.3.1. Древовидная сортировка.
12.3.2. Пирамидальная сортировка.
12.3.3. Сортировка слиянием.
12.3.4. Быстрая сортировка.
12.3.5. Алгоритмы с разбиением.
Резюме.
Упражнения.
Программный проект 12.1. Сортировка файла.
Глава 13. Поиск и хэш-классы.
13.1. База для анализа алгоритмов поиска.
13.2. Обзор методов поиска.
13.2.1. Последовательный поиск.
13.2.2. Двоичный поиск.
13.2.3. Красно-черные деревья.
13.3. Класс hash_map.
13.3.1. Поля в составе класса hash_map.
13.3.2. Хэширование.
13.3.3. Сцепление.
13.3.4. Поля и реализация класса iterator.
13.3.5. Реализация класса hash_map.
13.3.6. Анализ сцепленного хэширования.
13.3.7. Класс value_type.
13.3.8. Применения.
13.4. Класс hash_set.
13.5. Хэширование с открытым адресом.
13.5.1. Метод erase.
13.5.2. Первичная кластеризация.
13.5.3. Двойное хэширование.
13.5.4. Анализ хэширования с открытым адресатом.
Резюме.
Упражнения.
Программный проект 13.1. Сравнение сцепленного и двойного хэширования по фактическому времени выполнения при построении таблицы символов.
Глава 14. Графы, деревья и сети.
14.1. Ненаправленные графы.
14.2. Направленные графы.
14.3. Деревья.
14.4. Сети.
14.5. Алгоритмы для работы с графами.
14.5.1. Итераторы.
14.5.2. Связность.
14.5.3. Генерирование минимального покрывающего дерева.
14.5.4. Нахождение кратчайшего пути в сети.
14.6. Разработка класса для работы с сетями.
14.7. Класс network.
14.7.1. Поля в составе класса network.
14.7.2. Реализация класса network.
14.7.3. Реализация методов для работы с ребрами.
14.7.4. Реализация глобальных методов.
14.7.5. Метод get_minimum_spanning_tree.
14.7.6. Метод get_shortest_path.
14.7.7. Оценки времени выполнения методов.
14.7.8. Альтернативная конструкция и реализация метода network.
14.8. Поиск с возвратом применительно к сети.
Резюме.
Упражнения.
Программный проект 14.1. Завершение реализации на основе матриц смежности.
Программный проект 14.2. Поиск с возвратом для сети.
Приложение 1. Некоторые сведения из математики.
А1.1 Введение.
А1.2 Функции и последовательности.
А1.3 Суммы и произведения.
А1.4 Логарифмы.
А1.5 Математическая индукция.
А1.6 Индукция и рекурсия.
Упражнения.
Приложение 2. Класс string.
А2.1 Введение.
А2.2 Объявление класса string.
А2.2.1 Конструкторы.
А2.2.2 Операторы.
А2.2.3 Функции, не являющиеся членами.
А2.2.4 Методы, не являющиеся конструкторами и операторами.
А2.2.5 Программа для обработки строк.
А2.3 Поля и реализация класса string.
Приложение 3. Полиморфизм.
А3.1 Введение.
А3.2 Значение полиморфизма.
А3.3 Динамическое связывание.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Структуры данных и стандартная библиотека шаблонов, Коллинз У.Дж., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Хештеги: #учебник по программированию :: #программирование :: #Коллинз