Абстрактные типы данных, 4-е издание
Год издания: 2024
Автор: Окулов С. М.
Издательство: Лаборатория знаний
ISBN: 978-5-93208-673-5
Серия: Развитие интеллекта школьников
Язык: Русский
Формат: PDF
Качество: Издательский макет или текст (eBook)
Количество страниц: 253
Описание: Абстракция, абстрагирование—одна из составляющих мыслительного процесса творческой личности. Для развития этого компонента мышления в процессе обучения информатике есть дополнительные возможности, так как знание абстрактных типов данных, умение оперировать ими—необходимый элемент профессиональной культуры специалиста, связанного с разработкой программных комплексов.
Для школьников, преподавателей информатики и студентов младших курсов университетов. Книга может быть использована при проведении факультативных занятий и при углубленном изучении информатики.
Примеры страниц (скриншоты)
Оглавление
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Глава 1. Матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2. Операции над матрицами . . . . . . . . . . . . . . . . . . . . .18
1.3. Элементарные преобразования матриц . . . . . . . . . . .27
Глава 2. Списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.1. Основные понятия о ссылочном типе данных
(указателях) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2. Линейный список . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3. Реализация линейного списка с использованием
массивов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .47
2.4. Двусвязные списки . . . . . . . . . . . . . . . . . . . . . . . . .51
Глава 3. Стек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2. Реализация стека через линейный список. . . . . . . . .59
3.3. Реализация стека с использованием массива . . . . . .60
3.4. Постфиксная, префиксная и инфиксная формы
записи выражений. . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
3.5. Стек и рекурсивные процедуры . . . . . . . . . . . . . . . 73
Глава 4. Очередь. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84
4.1. Определение и реализация очереди
с использованием списков . . . . . . . . . . . . . . . . . . . . . . 84
4.2. Реализация очереди с помощью массива . . . . . . . . .86
Глава 5. Деревья. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .94
5.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . .94
5.2. Двоичные деревья поиска . . . . . . . . . . . . . . . . . . . 96
5.3. Способы описания деревьев . . . . . . . . . . . . . . . . . 105
5.4. Оптимальные двоичные деревья поиска . . . . . . . . .115
Глава 6. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2. Стандартные способы реализации множества . . . . 127
6.3. Объединение непересекающихся множеств . . . . . .129
6.4. Использование древовидных структур данных
в задаче объединения непересекающихся
множеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.5. Словари и хеширование . . . . . . . . . . . . . . . . . . . . 141
Глава 7. Очереди с приоритетами. . . . . . . . . . . . . . . . 150
7.1. Двоичная куча и пирамидальная сортировка . . . . .150
7.2. Очередь с приоритетом на базе двоичной кучи . . . 161
7.3. Биномиальная куча . . . . . . . . . . . . . . . . . . . . . . . 165
Глава 8. Сбалансированные деревья. . . . . . . . . . . . . . .178
8.1. АВЛ-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.2.«2–3»-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.3. Б-деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
8.4. Красно-черные деревья . . . . . . . . . . . . . . . . . . . . 225
