Оглавление
| Введение | |
| Раздел 1. Основные структуры данных | |
| 1. Введение в структуры данных. Динамическое распределение памяти | |
| 1.1. Классификация структур данных | |
| 1.2. Переменные-указатели и динамическое распределение памяти | |
| 1.3. Дополнительные вопросы использования переменных-указателей | |
| 1.4. Контрольные вопросы по теме | |
| 2. Структуры данных “стек” и “очередь” | |
| 2.1. Что такое стек и очередь? | |
| 2.2. Статическая реализация стека | |
| 2.3. Динамическая реализация стека | |
| 2.4. Статическая реализация очереди | |
| 2.5. Динамическая реализация очереди | |
| 2.6. Практические задания | |
| 2.7. Контрольные вопросы по теме | |
| 3. Основы реализации списковых структур | |
| 3.1. Структуры данных типа “линейный список” | |
| 3.2. Первый способ статической реализации списка | |
| 3.3. Второй способ статической реализации списка | |
| 3.4. Управление памятью при статической реализации списка | |
| 3.5. Динамическая реализация линейных списков | |
| 3.6. Практические задания | |
| 3.7. Контрольные вопросы | |
| 4. Усложненные списковые структуры | |
| 4.1. Двунаправленные линейны списки | |
| 4.2. Комбинированные структуры данных: массивы и списки указателей | |
| 4.3. Комбинированные структуры данных: массивы и списки списков | |
| 4.4. Практические задания | |
| 4.5. Контрольные вопросы | |
| 5. Основные понятия о древовидных структурах | |
| 5.1. Основные определения | |
| 5.2. Двоичные деревья | |
| 5.3. Идеально сбалансированные деревья | |
| 5.4. Практические задания | |
| 5.5. Контрольные вопросы | |
| 6. Реализация поисковых деревьев | |
| 6.1. Двоичные деревья поиска | |
| 6.2. Добавление вершины в дерево поиска | |
| 6.3. Удаление вершины из дерева поиска | |
| 6.4. Практические задания | |
| 6.5. Контрольные вопросы | |
| 7. Дополнительные вопросы обработки деревьев. Графы. | |
| 7.1. Проблемы использования деревьев поиска | |
| 7.2. Двоичные деревья с дополнительными указателями | |
| 7.3. Деревья общего вида (не двоичные) | |
| 7.4. Представление графов | |
| 7.5. Практические задания | |
| 7.6. Контрольные вопросы | |
| Раздел 2. Алгоритмы сортировки и поиска | |
| 1. Классификация методов. Простейшие методы сортировки | |
| 1.1. Задача оценки и выбора алгоритмов | |
| 1.2. Классификация задач сортировки и поиска | |
| 1.3. Простейшие методы сортировки: метод обмена | |
| 1.4. Простейшие методы сортировки: метод вставок | |
| 1.5. Простейшие методы сортировки: метод выбора | |
| 1.6. Практическое задание | |
| 1.7. Контрольные вопросы | |
| 2. Улучшенные методы сортировки массивов | |
| 2.1. Метод Шелла | |
| 2.2. Метод быстрой сортировки | |
| 2.3. Пирамидальная сортировка | |
| 2.4. Практическое задание | |
| 2.5. Контрольные вопросы | |
| 3. Специальные методы сортировки | |
| 3.1. Простейшая карманная сортировка | |
| 3.2. Карманная сортировка для случая повторяющихся ключей | |
| 3.3. Поразрядная сортировка | |
| 3.4. Практическое задание | |
| 3.5. Контрольные вопросы | |
| 4. Поиск с использованием хеш-функций | |
| 4.1. Основные понятия | |
| 4.2. Разрешение конфликтов: открытое хеширование | |
| 4.3. Разрешение конфликтов: внутреннее хеширование | |
| 4.4. Практические задания | |
| 4.5. Контрольные вопросы | |
| 5. Внешний поиск и внешняя сортировка | |
| 5.1. Особенности обработки больших наборов данных | |
| 5.2. Организация внешнего поиска с помощью Б-деревьев | |
| 5.3. Б-дерево как структура данных | |
| 5.4. Поиск элемента в Б-дереве | |
| 5.5. Добавление вершины в Б-дерево | |
| 5.6. Удаление вершины из Б-дерева | |
| 5.7. Внешняя сортировка | |
| 5.8. Практические задания | |
| 5.9. Контрольные вопросы | |
| Основные термины и понятия | |
| Литература |
Введение
В учебном пособии рассматриваются вопросы программной реализации основных важнейших структур данных, таких как стеки, очереди, списки, деревья и их различных комбинаций. Для большинства структур приводятся различные способы реализации – статические и динамические, даются рекомендации по их практическому применению. Во второй части приводятся алгоритмы сортировки данных, причем основное внимание уделяется методам сортировки массивов, включая все основные простейшие и улучшенные методы и несколько наиболее известных специальных.
Пособие содержит большое число примеров фрагментов программ, а также задания для самостоятельного практического решения. Выполнение практических заданий является абсолютно необходимым, поскольку именно оно развивает навыки самостоятельного написания, выполнения и отладки программ. Наиболее сложные задания имеют рекомендации по программной реализации, облегчающие их выполнение.
Материал учебного пособия соответствует содержанию Государственного образовательного стандарта по одноименному учебному курсу для студентов специальности «Программное обеспечение вычислительной техники и автоматизированных систем» и предполагает знание студентами основ классического структурного программирования. Отдельные темы пособия могут быть полезны и для студентов других специальностей, связанных с информационными и компьютерными технологиями.
Раздел 1. Основные структуры данных
Тема 1. Введение в структуры данных. Динамическое распределение памяти