Романенко Т.А. Разработка программных коллекций данных

Учебное пособие. — Новосибирск: Новосибирский государственный технический университет, 2020. —116 с. — ISBN 978-5-7782-4170-1.Предназначено для изучения основных типов программных коллекций, хранящих множества данных, фундаментальных структур данных и алгоритмов управления ими. Также в пособии предлагается к применению технология проектирования и программирования коллекций, основывающаяся на объектно-ориентированном подходе в программировании.Предисловие.
Технология разработки коллекции данных.
Постановка задачи.
Проектирование структуры класса для коллекции.
Трудоемкость операций коллекции.
Программирование коллекции.
Отладка и тестирование.
Сопровождение.
Практическая работа «Коллекция данных — список».
Структуры списков.
Задания к практической работе.
Варианты заданий.
Методические указания к выполнению задания.
Практическая работа «Коллекция данных — дерево поиска».
Структуры BST-деревьев.
Задания к практической работе.
Варианты заданий.
Методические указания к выполнению задания.
Практическая работа «Коллекция данных — сбалансированное дерево поиска».
Структуры сбалансированных деревьев.
Задания к практической работе.
Варианты заданий.
Методические указания к выполнению задания.
Практическая работа «Коллекция данных — хеш-таблица».
Методы хеширования ключей.
Преобразование ключей перед хешированием.
Хеш-функции.
Качество хеширования.
Разрешение коллизий и структуры хеш-таблиц.
Трудоемкость операций.
Задания к практической работе.
Варианты заданий.
Методические указания к выполнению задания.
Контрольные вопросы и упражнения..
Библиографический список.
Приложения.
Основные правила и соглашения псевдокода.
Алгоритмы для BST-дерева.
Тесты трудоемкости операций BST-дерева.
Алгоритмы для сбалансированных деревьев.
Алгоритмы для хеш-таблицы с открытой адресацией.