Структуры данных и алгоритмы: реализация на C/C++

Купить бумажную книгу и читать

Автор: Пышкин Е.В.

Название: Структуры данных и алгоритмы: реализация на C/C++

Издательство: СПб.: ФТК СПБГПУ

Год: 2009

Количество страниц: 200

Формат: pdf

Размер: 17 Mb

Для сайта:

Учебное пособие дополняет курс лекций, читаемых студентам Санкт-Петербургского государственного политехнического университета. Рассматриваются основные структуры данных, в том числе связанные типы (списки, деревья, графы) и сложные контейнерные типы (массивы, ассоциативные массивы, стеки и очереди), а также особенности управления подобными типами в компьютерной программе. Применительно к анализу фундаментальных абстракций данных анализируются наиболее важные для проектной практики алгоритмы сортировки, поиска, обработки древовидных структур, алгоритмы лексического и синтаксического анализа и др. Особое внимание уделяется построению алгоритмов, инвариантных к типам обрабатываемых данных – обобщенных алгоритмов, – и методов реализации таких алгоритмов средствами языка C++. Предполагается, что студенты прослушали курс по программированию на языке C/C++ и имеют основные представления о процедурной и объектно-ориентированной парадигме программирования.

Содержание

Алгоритмы и типы данных

Парадигмы программирования

Понятие об императивном программировании

Процедурная парадигма

Основные виды абстракций процедурного программирования

Иерархии процедур и функций

Модульность в процедурном программировании

Типы данных

Структуры и классы

Массивы

Множества

Алгоритмы и способы их записи

Текстуальная форма записи

Схема алгоритма

Псевдокод

Запись в форме программы на языке программирования

Запись алгоритмов функционирования реактивных систем

Построение программной модели конечного автомата

Оценка алгоритмов, рекурсия, сортировка

Постановка задачи внутренней сортировки и подходы к оценке эффективности

Сортировка простыми обменами

Реализация на примере сортировки массива целых чисел

Предварительная оценка эффективности

Улучшенная сортировка простыми обменами

Обобщение решения с использованием функций обратного вызова

Реализация в виде шаблонной функции

Рекурсивные алгоритмы

Задача поиска выхода из лабиринта

Быстрая сортировка Хоара (рекурсивный вариант)

Оценка эффективности быстрой сортировки

Реализация быстрой сортировки в итерационной форме

Другие классические алгоритмы внутренней сортировки и их анализ

Сортировка простыми вставками

Сортировка бинарными вставками

Сортировка Шелла

Сортировка простым выбором

Управление связанными структурами данных

Обработка линейного однонаправленного списка: основные операции

Постановка задачи

Реализация абстракции списка и базового комплекта операций

Определение других операций над списком.

Первоначальное представление об итераторах

Недостатки просмотра списка с использованием внутреннего итератора

Внешнее управление работой внутреннего итератора

Построение внешнего итератора списка

Другие виды списков

Древовидные структуры и их применение

Организация древовидных структур

Бинарные деревья и их применение

Бинарное дерево как вариант организации данных в одномерном массиве

Алгоритм поиска с использованием бинарного дерева

Реализация бинарного поиска для ключей-строк символов (пример)

Алгоритм сортировки с использованием бинарного дерева

Двоичные деревья общего вида: удаление и добавление узлов

Красно-черные деревья как инструмент восстановления

сбалансированности двоичных деревьев

Алгоритмы на графах

Некоторые напоминания из теории графов

Определение графа

Смежность и инцидентность

Подграф

Путь и расстояние

Связность

Древовидный граф

Способы задания

Поиск кратчайшего пути на графе

Структуры данных

Реализация алгоритма

Анализ работы алгоритма

Поиск минимального остовного дерева

Перемешанные таблицы и ассоциативные массивы

Алгоритм поиска по ключу с использованием hash-функций

Понятие hash-функции

Заполнение hash-таблицы

Поиск в подготовленной таблице

Удаление элементов из hash-таблицы

Распознавание служебных слов из фиксированного набора

Ассоциативные массивы

Элементы лексического и синтаксического анализа

Постановка задачи

Лексический анализ

Понятие синтерма: непересекающиеся и пересекающиеся синтермы

Формирование и распознавание синтерма

Использование визуального формализма на базе L-сети в методических целях преподавания

Среда последовательного управления

Среда разветвленного управления

Решение задачи синтаксического анализа логических выражений в форме L-сети

Лексический анализатор в форме L-сети

Синтаксический анализатор в форме L-сети

Элементы реализации на языке C++

Алгоритмы обработки контейнеров

Специализированные контейнеры

Итерируемые специализированные контейнеры

Разработка итерируемого специализированного контейнера

Стандартные контейнеры

Понятие об итерации стандартного контейнера

Разработка контейнеров и алгоритмов, совместимых с STL

Реализация альтернативных вариантов размещения элементов контейнера в памяти