Разработка программных коллекций данных (200,00 руб.)

Стр.2

Стр.114

Стр.115

УДК 004.421(075.8) Р 691 Рецензенты: канд. техн. наук, доцент А.Б. Крохалева канд. техн. наук, доцент Е.Л. Романов для студентов III курса АВТФ, обучающихся по направлениям 09.03.01 – Информатика и вычислительная техника и 09.03.04 – Программная инженерия Работа подготовлена на кафедре вычислительной техники Р 691 Разработка программных коллекций данных: учебное пособие / Т.А. Романенко. – Новосибирск: Изд-во НГТУ, 2020. – 116 с. Романенко Т.А. ISBN 978-5-7782-4170-1 Настоящее пособие предназначено для изучения основных типов программных коллекций, хранящих множества данных, фундаментальных структур данных и алгоритмов управления ими. Также в пособии предлагается к применению технология проектирования и программирования коллекций, основывающаяся на объектно-ориентированном подходе в программировании. УДК 004.421(075.8) ISBN 978-5-7782-4170-1 2 © Романенко Т.А., 2020 © Новосибирский государственный технический университет, 2020

Стр.2

ОГЛАВЛЕНИЕ Предисловие ............................................................................................................. 3 1. Технология разработки коллекций данных ................................................. 5 1.1. Постановка задачи ......................................................................................... 5 1.2. Проектирование структуры класса для коллекции ................................... 16 1.3. Трудоёмкость операций коллекции............................................................ 17 1.4. Программирование коллекции ................................................................... 21 1.5. Отладка и тестирование .............................................................................. 27 1.6. Сопровождение ............................................................................................ 29 2. Практическая работа «Коллекция данных – список» .............................. 32 2.1. Структуры списков ...................................................................................... 32 2.2. Задание к практической работе .................................................................. 37 2.2.1. Варианты заданий .................................................................................. 39 2.2.2. Методические указания к выполнению задания ................................. 40 2.3. Контрольные вопросы и упражнения ........................................................ 40 3. Практическая работа «Коллекция данных – дерево поиска» ................. 42 3.1. Структуры BST-деревьев ............................................................................ 44 3.2. Задание к практической работе .................................................................. 46 3.2.1. Варианты заданий .................................................................................. 48 3.2.2. Методические указания к выполнению задания ................................. 49 3.3. Контрольные вопросы и упражнения ........................................................ 50 4. Практическая работа «Коллекция данных – сбалансированное дерево поиска» .................................................................................................. 52 4.1. Структуры сбалансированных деревьев .................................................... 52 114

Стр.114

4.2. Задание к практической работе .................................................................. 58 4.2.1. Варианты заданий .................................................................................. 60 4.2.2. Методические указания к выполнению задания ................................. 61 4.3. Контрольные вопросы и упражнения ........................................................ 62 5. Практическая работа «Коллекция данных – хеш-таблица» ................... 64 5.1. Методы хеширования ключей .................................................................... 65 5.1.1. Преобразование ключей перед хешированием ................................... 65 5.1.2. Хеш-функции ......................................................................................... 67 5.1.3. Качество хеширования .......................................................................... 69 5.2. Разрешение коллизий и структуры хеш-таблиц ........................................ 69 5.3. Трудоёмкость операций .............................................................................. 72 5.4. Задание к практической работе .................................................................. 73 5.4.1. Варианты заданий .................................................................................. 75 5.4.2. Методические указания к выполнению задания ................................. 77 5.5. Контрольные вопросы и упражнения ........................................................ 78 Библиографический список .................................................................................. 79 Приложения ............................................................................................................ 80 Приложение A. Основные правила и соглашения псевдокода .......................... 80 Приложение Б. Алгоритмы для BST-дерева ....................................................... 81 Приложение В. Тесты трудоёмкости операций BST-дерева .............................. 90 Приложение Г. Алгоритмы для сбалансированных деревьев ............................ 95 Приложение Д. Алгоритмы для хеш-таблицы с открытой адресацией .......... 112 115

Стр.115