Главная » 2012 » Март » 6 » Абстракция данных и решение задач на C++. Стены и зеркала
20:27
Абстракция данных и решение задач на C++. Стены и зеркала
Книга представляет собой классический учебник для высшей школы, содержащий глубокое изложение вопросов, связанных с абстракцией и структурами данных, а также их реализацией на языке C++ . Помимо предоставления прочных основ методов абстракции данных, в ней особо подчеркивается различие между спецификацией и реализацией, что является принципиально важным в объектно-ориентированном подходе. В книге подробно обсуждаются ключевые понятия объектно-ориентированного программирования, включая инкапсуляцию, наследование и полиморфизм, однако в центре внимания всегда находится именно абстракция данных, а не синтаксические конструкции языка C++. Книга будет полезна всем, кто заинтересован в глубоком изучении важнейших аспектов ООП и полном освоении соответствующих возможностей языка C++.
Название: Абстракция данных и решение задач на C++. Стены и зеркала Автор: Каррано Ф. М., Причард Дж.Дж. Издательство: Издательский дом "Вильямс" Год: 2003 Страниц: 848 Формат: PDF Размер: 22,1 МБ ISBN: 5-8459-0389-0 Качество: Отличное
Содержание:
Предисловие Обращение к студентам Метод изложения Необходимые условия Гибкость Абстракция данных Решение задач Приложения Новый и переработанный материал Обзор Методические особенности Организация Вспомогательные материалы Пишите нам Благодарности ЧАСТЬ I. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ Глава 1. Принципы программирования и разработки программного обеспечения Решение задач и разработка программного обеспечения Решение задачи Жизненный цикл программного обеспечения Хорошее решение задачи Модульный подход Абстракция и сокрытие информации Объектно-ориентированное проектирование Проектирование "сверху вниз" Общие принципы проектирования Моделирование объектно-ориентированных проектов с помощью языка UML Преимущества объектно-ориентированного подхода Краткий обзор основных понятий программирования Модульность Модифицируемость Легкость использования Надежное программирование Стиль Отладка Резюме Предупреждения Вопросы для самопроверки Упражнения Задачи по программированию Глава 2. Рекурсия: зеркала Рекурсивные решения Рекурсивная функция, возвращающая значение: факториал числа n Рекурсивные функции, не возвращающие никаких значений: обратная запись строки Перечислимые предметы Размножающиеся кролики (последовательность Фибоначчи) Организация парада Дилемма мистера Спока (выбор k из n предметов) Поиск элемента в массиве Поиск наибольшего элемента в массиве Бинарный поиск Поиск k-го наименьшего элемента массива Организация данных Ханойские башни Рекурсия и эффективность Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 3. Абстракция данных: стены Абстрактные типы данных Спецификации абстрактных типов данных Абстрактный список Абстрактный упорядоченный список Разработка абстрактных типов данных Аксиомы Реализация абстрактных типов данных Классы языка C++ Пространства имен Реализация абстрактного списка в виде массива Исключительные ситуации в языке C++ Реализация абстрактного списка с учетом исключительных ситуаций Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 4. Связанные списки Предварительные замечания Указатели Динамические массивы Связанные списки, основанные на указателях Работа со связанными списками Вывод на экран содержания связанного списка Удаление указанного узла из связанного списка Вставка узла в указанную позицию связанного списка Реализация абстрактного списка, основанная на указателях Реализации списка в виде массива и на основе указателей Запись связанных списков в файл и считывание их из файла Передача связанного списка в качестве аргумента функции Рекурсивная обработка связанных списков Объекты, хранящиеся в узлах списка Разновидности связанных списков Кольцевые связанные списки Фиктивные головные узлы Дважды связанные списки Приложение: инвентарная ведомость Стандартная библиотека шаблонов языка C++ Контейнеры Итераторы Шаблонный класс list из библиотеки STL Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 5. Рекурсивный метод решения задач Поиск с возвратом Задача о восьми ферзях Определение языков Основы грамматики Два простых языка Алгебраические выражения Связь между рекурсией и математической индукцией Правильность рекурсивной функции для вычисления факториала Количество ходов при решении задачи о ханойских башнях Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию ЧАСТЬ II. РЕШЕНИЕ ЗАДАЧС ПОМОЩЬЮ АБСТРАКТНЫХ ТИПОВ ДАННЫХ Глава 6. Стеки Абстрактный стек Разработка абстрактных типов данных в процессе решения задачи Простые примеры использования абстрактного стека Проверка баланса фигурных скобок Распознавание строк языка Реализации абстрактного стека Реализация абстрактного стека в виде массива Реализация абстрактного стека в виде связанного списка Реализация стека в виде абстрактного списка Сравнение реализаций Класс stack из стандартной библиотеки шаблонов Приложение: алгебраические выражения Вычисление постфиксных выражений Преобразование инфиксного выражения в постфиксное Приложение: поиск Итеративное решение с помощью стеков Рекурсивное решение Взаимосвязь между стеками и рекурсией Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 7. Очереди Абстрактная очередь Некоторые применения абстрактной очереди Считывание строки символов Распознавание палиндромов Реализация абстрактной очереди Реализация очереди в виде связанного списка Реализация очереди в виде массива Реализация очереди с помощью абстрактного списка Шаблонный класс queue из библиотеки STL Сравнение реализаций Абстрактные типы данных, основанные на позиционном принципе Приложение: моделирование Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 8. Особенности языка C++ Еще раз о наследовании Открытое, закрытое и защищенное наследование Отношения "является", "содержит" и "подобен" Виртуальные функции и позднее связывание Абстрактные базовые классы Дружественные функции и классы Новая реализация абстрактного и упорядоченного списка Реализации абстрактного упорядоченного списка на основе абстрактного списка Шаблонные классы Перегруженные операторы Итераторы Реализация абстрактного списка с помощью итераторов Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 9. Эффективность алгоритмов и сортировка Измерение эффективности алгоритмов Быстродействие алгоритмов Степень роста временных затрат Оценка порядка величины и обозначение 0-большое Перспективы Эффективность алгоритмов поиска Алгоритмы сортировки и их эффективность Сортировка методом пузырька Сортировка методом вставок Сортировка слиянием Быстрая сортировка Поразрядная сортировка Сравнение алгоритмов сортировки Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 10. Деревья Терминология Абстрактное бинарное дерево Обход бинарного дерева Способы представления бинарного дерева Реализация абстрактного бинарного дерева в виде связанного списка Абстрактное бинарное дерево поиска Алгоритмы, реализующие операции над абстрактным бинарным деревом поиска Реализация абстрактного бинарного дерева поиска с помощью указателей Эффективность операций над бинарными деревьями поиска Древовидная сортировка Запись бинарного дерева поиска в файл Деревья общего вида Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 11. Таблицы и очереди с приоритетами Абстрактная таблица Выбор способа реализации Реализация абстрактной таблицы в виде упорядоченного массива Реализация абстрактной таблицы в виде бинарного дерева поиска Абстрактная очередь с приоритетами: вариант абстрактной таблицы Кучи Реализация абстрактной очереди с приоритетами в виде кучи Пирамидальная сортировка Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 12. Эффективные реализации таблиц Сбалансированные деревья поиска 2-3 деревья 2-3-4 деревья Красно-черные деревья AVL-деревья Хэширование Функции хэширования Разрешение конфликтов Эффективность хэширования Чем отличается хорошая функция хэширования Обход таблицы: неэффективная операция при хэшировании Одновременное применение нескольких структур данных Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 13. Графы Терминология Графы как абстрактные типы данных Реализация графов Алгоритмы обхода графа Поиск в глубину Поиск в ширину Применения графов Топологическая сортировка Остовные деревья Минимальные остовные деревья Кратчайшие пути Простые цепи Некоторые трудные задачи Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Глава 14. Методы работы с внешними запоминающими устройствами Внешние запоминающие устройства Сортировка данных во внешнем файле Внешние таблицы Индексирование внешнего файла Внешнее хэширование B-деревья Алгоритмы обхода Множественная индексация Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Приложение А. Основы языка C++ Основные конструкции языка Комментарии Идентификаторы и ключевые слова Основные типы данных Переменные Литеральные константы Именованные константы Перечисления Оператор typedef Присваивания и выражения Входной и выходной потоки Ввод Вывод Флаги формата и манипуляторы Функции Стандартные функции Условные операторы Оператор if Оператор switch Операторы цикла Оператор while Оператор for Оператор do Массивы Одномерные массивы Многомерные массивы Массивы массивов Строки Строки языка C++ Строки языка C Структуры Структуры внутри других структур Массивы структур Исключительные ситуации Перехват исключительных ситуаций Генерирование исключительных ситуаций Работа с файлами Текстовые файлы Бинарные файлы Библиотеки Предотвращение дублирования заголовочных файлов Сравнение с языком Java Резюме Предупреждения Вопросы для самопроверки Упражнения Задания по программированию Приложение Б. ASCII-коды символов и ключевые слова языка Приложение В. Заголовочные файлы и стандартные функции в языке C++ Приложение Г. Метод математической индукции Вопросы для самопроверки Упражнения Приложение Д. Стандартные шаблонные классы Приложение Е. Операторы языка C++ Словарь терминов Ответы на вопросы для самопроверки Предметный указатель
