Учебное пособие. СПб.: ФТК СПБГПУ, 2009.- 200 с., ил. Учебное
пособие дополняет курс лекций, читаемых студентам
Санкт-Петербургского государственного политехнического
университета. Рассматриваются основные структуры данных, в том
числе связанные типы (списки, деревья, графы) и сложные
контейнерные типы (массивы, ассоциативные массивы, стеки и
очереди), а также особенности управления подобными типами в
компьютерной программе. Применительно к анализу фундаментальных
абстракций данных анализируются наиболее важные для проектной
практики алгоритмы сортировки, поиска, обработки древовидных
структур, алгоритмы лексического и синтаксического анализа и др.
Особое внимание уделяется построению алгоритмов, инвариантных к
типам обрабатываемых данных – обобщенных алгоритмов, – и методов
реализации таких алгоритмов средствами языка C++. Предполагается,
что студенты прослушали курс по программированию на языке C/C++ и
имеют основные представления о процедурной и
объектно-ориентированной парадигме программирования. Курс рассчитан
на 32 часа лекционных занятий (8 занятий по 4 часа) и
самостоятельный практикум (соответствует примерно двум практическим
занятиям по 4 часа). Учебное пособие может быть также полезно
студентам, изучающим курсы алгоритмизации, теории и технологии
программирования, программирования на языке высокого уровня.
Содержание
Алгоритмы и типы данных
Парадигмы программирования
Понятие об императивном программировании
Процедурная парадигма
Основные виды абстракций процедурного программирования
Иерархии процедур и функций
Модульность в процедурном программировании
Типы данных
Структуры и классы
Массивы
Множества
Алгоритмы и способы их записи
Текстуальная форма записи
Схема алгоритма
Псевдокод
Запись в форме программы на языке программирования
Запись алгоритмов функционирования реактивных систем
Построение программной модели конечного автомата
Оценка алгоритмов, рекурсия, сортировка
Постановка задачи внутренней сортировки и подходы к оценке эффективности
Сортировка простыми обменами
Реализация на примере сортировки массива целых чисел
Предварительная оценка эффективности
Улучшенная сортировка простыми обменами
Обобщение решения с использованием функций обратного вызова
Реализация в виде шаблонной функции
Рекурсивные алгоритмы
Задача поиска выхода из лабиринта
Быстрая сортировка Хоара (рекурсивный вариант)
Оценка эффективности быстрой сортировки
Реализация быстрой сортировки в итерационной форме
Другие классические алгоритмы внутренней сортировки и их анализ
Сортировка простыми вставками
Сортировка бинарными вставками
Сортировка Шелла
Сортировка простым выбором
Управление связанными структурами данных
Обработка линейного однонаправленного списка: основные операции
Постановка задачи
Реализация абстракции списка и базового комплекта операций
Определение других операций над списком.
Первоначальное представление об итераторах
Недостатки просмотра списка с использованием внутреннего итератора
Внешнее управление работой внутреннего итератора
Построение внешнего итератора списка
Другие виды списков
Древовидные структуры и их применение
Организация древовидных структур
Бинарные деревья и их применение
Бинарное дерево как вариант организации данных в одномерном массиве
Алгоритм поиска с использованием бинарного дерева
Реализация бинарного поиска для ключей-строк символов (пример)
Алгоритм сортировки с использованием бинарного дерева
Двоичные деревья общего вида: удаление и добавление узлов
Красно-черные деревья как инструмент восстановления
сбалансированности двоичных деревьев
Алгоритмы на графах
Некоторые напоминания из теории графов
Определение графа
Смежность и инцидентность
Подграф
Путь и расстояние
Связность
Древовидный граф
Способы задания
Поиск кратчайшего пути на графе
Структуры данных
Реализация алгоритма
Анализ работы алгоритма
Поиск минимального остовного дерева
Перемешанные таблицы и ассоциативные массивы
Алгоритм поиска по ключу с использованием hash-функций
Понятие hash-функции
Заполнение hash-таблицы
Поиск в подготовленной таблице
Удаление элементов из hash-таблицы
Распознавание служебных слов из фиксированного набора
Ассоциативные массивы
Элементы лексического и синтаксического анализа
Постановка задачи
Лексический анализ
Понятие синтерма: непересекающиеся и пересекающиеся синтермы
Формирование и распознавание синтерма
Использование визуального формализма на базе L-сети в методических целях преподавания
Среда последовательного управления
Среда разветвленного управления
Решение задачи синтаксического анализа логических выражений в форме L-сети
Лексический анализатор в форме L-сети
Синтаксический анализатор в форме L-сети
Элементы реализации на языке C++
Алгоритмы обработки контейнеров
Специализированные контейнеры
Итерируемые специализированные контейнеры
Разработка итерируемого специализированного контейнера
Стандартные контейнеры
Понятие об итерации стандартного контейнера
Разработка контейнеров и алгоритмов, совместимых с STL
Реализация альтернативных вариантов размещения элементов контейнера в памяти
Содержание
Алгоритмы и типы данных
Парадигмы программирования
Понятие об императивном программировании
Процедурная парадигма
Основные виды абстракций процедурного программирования
Иерархии процедур и функций
Модульность в процедурном программировании
Типы данных
Структуры и классы
Массивы
Множества
Алгоритмы и способы их записи
Текстуальная форма записи
Схема алгоритма
Псевдокод
Запись в форме программы на языке программирования
Запись алгоритмов функционирования реактивных систем
Построение программной модели конечного автомата
Оценка алгоритмов, рекурсия, сортировка
Постановка задачи внутренней сортировки и подходы к оценке эффективности
Сортировка простыми обменами
Реализация на примере сортировки массива целых чисел
Предварительная оценка эффективности
Улучшенная сортировка простыми обменами
Обобщение решения с использованием функций обратного вызова
Реализация в виде шаблонной функции
Рекурсивные алгоритмы
Задача поиска выхода из лабиринта
Быстрая сортировка Хоара (рекурсивный вариант)
Оценка эффективности быстрой сортировки
Реализация быстрой сортировки в итерационной форме
Другие классические алгоритмы внутренней сортировки и их анализ
Сортировка простыми вставками
Сортировка бинарными вставками
Сортировка Шелла
Сортировка простым выбором
Управление связанными структурами данных
Обработка линейного однонаправленного списка: основные операции
Постановка задачи
Реализация абстракции списка и базового комплекта операций
Определение других операций над списком.
Первоначальное представление об итераторах
Недостатки просмотра списка с использованием внутреннего итератора
Внешнее управление работой внутреннего итератора
Построение внешнего итератора списка
Другие виды списков
Древовидные структуры и их применение
Организация древовидных структур
Бинарные деревья и их применение
Бинарное дерево как вариант организации данных в одномерном массиве
Алгоритм поиска с использованием бинарного дерева
Реализация бинарного поиска для ключей-строк символов (пример)
Алгоритм сортировки с использованием бинарного дерева
Двоичные деревья общего вида: удаление и добавление узлов
Красно-черные деревья как инструмент восстановления
сбалансированности двоичных деревьев
Алгоритмы на графах
Некоторые напоминания из теории графов
Определение графа
Смежность и инцидентность
Подграф
Путь и расстояние
Связность
Древовидный граф
Способы задания
Поиск кратчайшего пути на графе
Структуры данных
Реализация алгоритма
Анализ работы алгоритма
Поиск минимального остовного дерева
Перемешанные таблицы и ассоциативные массивы
Алгоритм поиска по ключу с использованием hash-функций
Понятие hash-функции
Заполнение hash-таблицы
Поиск в подготовленной таблице
Удаление элементов из hash-таблицы
Распознавание служебных слов из фиксированного набора
Ассоциативные массивы
Элементы лексического и синтаксического анализа
Постановка задачи
Лексический анализ
Понятие синтерма: непересекающиеся и пересекающиеся синтермы
Формирование и распознавание синтерма
Использование визуального формализма на базе L-сети в методических целях преподавания
Среда последовательного управления
Среда разветвленного управления
Решение задачи синтаксического анализа логических выражений в форме L-сети
Лексический анализатор в форме L-сети
Синтаксический анализатор в форме L-сети
Элементы реализации на языке C++
Алгоритмы обработки контейнеров
Специализированные контейнеры
Итерируемые специализированные контейнеры
Разработка итерируемого специализированного контейнера
Стандартные контейнеры
Понятие об итерации стандартного контейнера
Разработка контейнеров и алгоритмов, совместимых с STL
Реализация альтернативных вариантов размещения элементов контейнера в памяти