Симонова Е.В. Структуры данных в C#. Часть 2. Нелинейные динамические структуры

Учеб. пособие. — Самар. нац. исслед. ун-т им. С. П. Королева (Самар. ун-т), 2018. — 82 с.Учебное пособие включает разделы, которые подробно описывают рекурсивные алгоритмы обработки структур данных, иерархические структуры данных (деревья и графы), принципы организации множества объектов с заданным отношением порядка на основе хеширования.
Теоретический материал иллюстрируется большим количеством программных фрагментов, реализующих алгоритмы обработки различных структур данных. Содержит контрольные вопросы и упражнения по всем разделам.
Предназначено для студентов направления подготовки 09.03.01 Информатика и вычислительная техника.
Подготовлено на кафедре информационных систем и технологий.Предисловие.
Введение.
Рекурсивные алгоритмы обработки структур данных.
Итерация и рекурсия в программировании.
Понятие рекурсии.
Итеративная и рекурсивная схема организации вычислительного процесса.
Виды рекурсивных алгоритмов.
Вычислительные алгоритмы.
Перебор с возвратами.
Комбинаторика.
Игры и головоломки: задача о “ханойских башнях”.
Арифметические выражения – пример рекурсивной структуры данных.
Рекурсивные алгоритмы обработки динамических линейных структур данных на примере списков.
Эффективность рекурсивных вычислений.
Контрольные вопросы к главе.
Упражнения к главе.
Иерархические нелинейные структуры данных. Деревья.
Деревья общего вида (произвольной степени).
Бинарные деревья.
Представление бинарных деревьев.
Представление бинарных деревьев в памяти с последовательной организацией.
Связанное представление бинарных деревьев.
Алгоритмы обхода бинарных деревьев.
Алгоритмы обхода в глубину.
Алгоритм обхода в ширину.
Виды бинарных деревьев.
Деревья произвольного вида.
Сбалансированные деревья.
Дихотомические деревья (деревья поиска).
Деревья выражений.
Демонстрационная программа, реализующая операции создания, обработки, просмотра содержимого бинарного дерева (на примере сбалансированного дерева).
Контрольные вопросы к главе.
Упражнения к главе.
Иерархические нелинейные структуры данных. Графы.
Основные понятия и определения.
Представление графов.
Матричное представление графов.
Представление графа в виде списка смежности.
Алгоритмы обхода графов.
алгоритм обхода в глубину.
алгоритм обхода в ширину.
Остовные деревья.
Остовные деревья минимального веса.
Алгоритмы нахождения кратчайших путей в графе.
Алгоритм флойда.
Алгоритм дейкстра.
Контрольные вопросы к главе.
Упражнения к главе.
Организация множества объектов с заданным отношением порядка. Хеширование.
Основные понятия и определения.
Выбор функции преобразования.
Разрешение коллизий.
Метод открытой адресации.
Реализация хеш-таблицы (класс Hashtable).
Метод цепочек.
Реализация словаря (класс Dictionary).
Контрольные вопросы к главе.
Библиографический список.