Структуры данных в C#: линейные и нелинейные динамические структуры: учебное пособие для СПО

Предисловие............................................................................................. 3
Введение................................................................................................. 5
1. Идентификация объектов. Классы памяти ............................................ 7
1.1. Понятие типа данных ..................................................................... 7
1.2. Идентификация объектов ............................................................... 8
1.2.1. Именование ............................................................................... 8
1.2.2. Организация адресного пространства
оперативной памяти Windows................................................................ 9
1.2.3. Понятие ссылки......................................................................... 9
1.3. Классы памяти............................................................................... 10
1.3.1. Распределение адресного пространства
оперативной памяти............................................................................. 10
1.3.2. Стек ...........................................................................................11
1.3.3. Понятие фрейма активации метода.............................................. 12
1.3.4. Управляемая куча.................................................................... 15
1.3.5. Действия над ссылками............................................................. 18
1.3.6. Сборка мусора ......................................................................... 19
1.4. Контрольные вопросы к главе 1 .................................................. 21
1.5. Упражнения к главе 1................................................................ 22
2. Динамические структуры данных................................................. 23
2.1. Метод вычисляемого и хранимого адреса.
Последовательная и связанная организация данных........................ 23
2.2. Понятие динамической структуры данных ................................ 27
2.3. Линейные динамические структуры данных
(связанные списки) ....................................................................... 27
2.3.1. Основные виды списков в соответствии
с возможностями доступа к элементам.............................................. 28
2.4. Односвязные (однонаправленные) списки ................................. 28
2.4.1. Включение узла в начало односвязного списка ........................ 30
2.4.2. Создание односвязного списка из n узлов:
добавление узлов в начало списка................................................... 31
2.4.3. Создание односвязного списка из n узлов:
добавление узлов в конец списка .................................................... 32
2.4.4. Исключение узла из начала односвязного списка...................... 34
2.4.5. Переустановка ссылки............................................................ 35
2.4.6. Поиск узла в односвязном списке
по заданному условию...................................................................... 35
2.4.7. Включение в односвязный список нового узла справа
от узла, на который предварительно установлена ссылка ................ 36
2.4.8. Исключение из односвязного списка узла справа от узла,
на который предварительно установлена ссылка ........................... 37
2.4.9. Исключение из односвязного списка узла,
на который предварительно установлена ссылка .......................... 38
2.4.10. Разрушение односвязного списка........................................ 39
2.4.11. Демонстрационная программа, реализующая
операции создания, обработки, просмотра содержимого
односвязного списка произвольного вида ...................................... 40
2.4.12. Демонстрационная программа, реализующая
пример использования стека............................................................ 42
2.4.13. Демонстрационная программа, реализующая
пример использования очереди ....................................................... 46
2.5. Односвязные циклические списки .............................................. 51
2.6. Двусвязные (двунаправленные) списки ...................................... 55
2.6.1. Двусвязные нециклические списки............................................ 55
2.6.2. Демонстрационная программа, реализующая
операции создания, обработки, просмотра содержимого
двусвязного нециклического списка ............................................... 58
2.6.3. Двусвязные циклические списки........................................... 60
2.6.4. Демонстрационная программа, реализующая
операции создания, обработки, просмотра содержимого
двусвязного циклического списка ................................................... 66
2.6.5. Создание упорядоченного двусвязного
циклического списка......................................................................... 69
2.7. Ортогональные списки (мультисписки)...................................... 71
2.8. Контрольные вопросы к главе 2 .............................................. 77
2.9. Упражнения к главе 2 (структура списка по выбору)................ 77
3. Рекурсивные алгоритмы обработки структур данных .................... 80
3.1. Итерация и рекурсия в программировании ................................ 80
3.1.1. Понятие рекурсии ................................................................... 80
3.1.2. Итеративная и рекурсивная схема организации
вычислительного процесса .............................................................. 81
3.2. Виды рекурсивных алгоритмов ................................................... 89
3.2.1. Вычислительные алгоритмы.................................................. 89
Powered by TCPDF (www.tcpdf.org)
3.2.2. Перебор с возвратами ............................................................. 91
3.2.3. Комбинаторика ........................................................................ 93
3.2.4. Игры и головоломки: задача о «ханойских башнях».................. 96
3.2.5. Арифметические выражения — пример
рекурсивной структуры данных .................................................... 100
3.3. Рекурсивные алгоритмы обработки динамических
линейных структур данных на примере списков............................ 101
3.4. Эффективность рекурсивных вычислений............................... 105
3.5. Контрольные вопросы к главе 3 ................................................ 105
3.6. Упражнения к главе 3.................................................................. 106
4. Иерархические нелинейные структуры данных. Деревья ................ 108
4.1. Деревья общего вида (произвольной степени) ........................... 108
4.2. Бинарные деревья .................................................................... 109
4.3. Представление бинарных деревьев ............................................111
4.3.1. Представление бинарных деревьев в памяти
с последовательной организацией..................................................111
4.3.2. Связанное представление бинарных деревьев ....................112
4.4. Алгоритмы обхода бинарных деревьев......................................113
4.4.1. Алгоритмы обхода в глубину ................................................114
4.4.2. Алгоритм обхода в ширину...................................................118
4.5. Виды бинарных деревьев ........................................................119
4.5.1. Бинарные деревья произвольного вида ...............................119
4.5.2. Сбалансированные деревья.................................................. 120
4.5.3. Дихотомические деревья (деревья поиска) ........................ 123
4.5.4. Деревья выражений .............................................................. 130
4.6. Демонстрационная программа, реализующая операции
создания, обработки, просмотра содержимого бинарного дерева
(на примере сбалансированного дерева) ......................................... 133
4.7. Контрольные вопросы к главе 4 ................................................ 135
4.8. Упражнения к главе 4.................................................................. 136
5. Иерархические нелинейные структуры данных. Графы.................... 137
5.1. Основные понятия и определения............................................. 137
5.2. Представление графов................................................................ 139
5.2.1. Матричное представление графов....................................... 139
5.2.2. Представление графа в виде списка смежности .................... 141
5.3. Алгоритмы обхода графов.......................................................... 143
5.3.1. Алгоритм обхода в глубину.................................................. 143
5.3.2. Алгоритм обхода в ширину.................................................. 145
5.4. Остовные деревья ................................................................. 146
5.4.1. Остовные деревья минимального веса ............................... 147
5.5. Алгоритмы нахождения кратчайших путей в графе................ 149
5.5.1. Алгоритм Флойда.................................................................. 149
5.5.2. Алгоритм Дейкстры.............................................................. 150
5.6. Демонстрационная программа, реализующая операции
создания графа, обхода в глубину, построения матрицы
достижимости на основе матрицы смежности ............................... 151
5.7. Контрольные вопросы к главе 5 ................................................ 154
5.8. Упражнения к главе 5.................................................................. 155
Заключение ..................................................................................... 157
Библиографический список.............................................................. 158

 Учебное пособие включает разделы, которые подробно описывают абстрагирование типов, идентификацию объектов, классы оперативной памяти, линейные динамические структуры данных (односвязные, двусвязные списки, мультисписки), рекурсивные алгоритмы обработки структур данных, иерархические структуры данных (деревья и графы). Теоретический материал иллюстрируется большим количеством программных фрагментов, реализующих алгоритмы обработки различных структур данных. Учебное пособие содержит контрольные вопросы и упражнения по всем разделам.
 Предназначено для студентов среднего профессионального образования, обучающихся по специальностям, входящим в укрупненную группу специальностей «Информатика и вычислительная техника».