Книга посвящена алгоритмам обработки различных внутренних
структур данных — массивов, множеств, деревьев и графов. Кроме того, в
отдельной главе дано описание имеющихся в языке C# средств работы с
внешними структурами данных — файлами. Описаны основные классы,
реализующие методы обработки текстовых и бинарных файлов, организация
записи и чтения файлов в режимах последовательного и прямого доступа.
На примере алгоритмов сортировки массивов обсуждаются способы оценки
эффективности алгоритмов, используемые для их сравнения.
Текст содержит большое количество примеров программного кода,
способствующих усвоению материала. Книга рассчитана на бакалавров,
обучающихся по направлениям подготовки «Прикладная математика и
информатика», «Математика и компьютерные науки», «Фундаментальная
информатика и информационные технологии», «Математическое обеспе»
чение и администрирование информационных систем», «Информатика и
вычислительная техника», «Информационные системы и технологии»,
«Прикладная информатика», «Программная инженерия», «Информацион»
ная безопасность», специальностям «Компьютерная безопасность», «Инфор»
мационная безопасность телекоммуникационных систем», «Информацион»
ная безопасность автоматизированных систем», «Информационно»
аналитические системы безопасности», «Безопасность информационных
технологий в правоохранительной сфере», а также учащихся старших
классов и лиц, самостоятельно изучающих языки программирования.
Author(s): Н. А. ТЮКАЧЕВ, В. Г. ХЛЕБОСТРОЕВ
Edition: 3
Publisher: Издательство «Лань»
Year: 2018
Language: Russian
Commentary: Has a nasty watermark on every single fricking page.
City: САНКТ ПЕТЕРБУРГ
Tags: C#; C# Programming Language; Algorithms; Data Structures
ОГЛАВЛЕНИЕ
Введение ....................................................................................................... 3
Глава 1. Базовые понятия ............................................................................ 4
1.1. Данные, типы данных и структуры данных................................... 4
1.2. Алгоритмы, анализ алгоритмов ...................................................... 5
1.3. Измерение времени выполнения программного кода................... 8
1.3.1. Измерение с помощью объекта класса Stopwatch.................. 9
1.3.2. Измерение на уровне потока выполнения. Класс Timing ... 10
Выводы................................................................................................... 14
Упражнения ........................................................................................... 14
Глава 2. Алгоритмы поиска и сортировки ............................................... 15
2.1. Алгоритмы поиска.......................................................................... 15
2.1.1. Поиск в неупорядоченном массиве....................................... 15
2.1.2. Поиск в упорядоченном массиве........................................... 17
2.2. Алгоритмы сортировки.................................................................. 18
2.2.1. Сортировка простым выбором .............................................. 19
2.2.2. Сортировка включениями...................................................... 22
2.2.3. Сортировка обменом .............................................................. 24
2.2.4. Сортировка Шелла.................................................................. 27
2.2.5. Сортировка подсчетом ........................................................... 29
2.3. Хеширование .................................................................................. 30
2.3.1. Метод цепочек.......... .............................................................. 32
2.3.2. Открытая адресация.. ............................................................. 32
2.3.3. Двойное хеширование ............................................................ 33
2.3.4. Проект «Телефонный справочник»....................................... 33
2.3.5. Класс Hashtable......... .............................................................. 42
Выводы................................................................................................... 44
Упражнения ........................................................................................... 45
Глава 3. Рекурсия ....................................................................................... 46
3.1. Рекурсивные определения и рекурсивные алгоритмы................ 46
3.2. Когда рекурсия необходима .......................................................... 50
3.3. Примеры рекурсивных программ ................................................. 51
3.3.1. Задача о Ханойских башнях .................................................. 51
3.3.2. Быстрая сортировка... ............................................................. 57
3.4. Алгоритмы с возвратом ................................................................. 61
3.4.1. Расстановка ферзей................................................................. 62
3.4.2. Задача оптимального выбора................................................. 68
Выводы................................................................................................... 72
Упражнения ........................................................................................... 73
Глава 4. Деревья ......................................................................................... 74
4.1. Понятия и определения.................................................................. 74
4.2. Основные операции с бинарными деревьями.............................. 76
4.2.1. Упорядоченные деревья......................................................... 80
4.2.2. Поиск по дереву с включением ............................................. 86
4.2.3. Удаление из упорядоченного дерева .................................... 88
4.3. Турнирная сортировка ................................................................... 91
4.4. Основы работы интерпретатора.................................................. 100
4.5. Пример интерпретатора ............................................................... 113
Выводы................................................................................................. 131
Упражнения ......................................................................................... 131
Глава 5. Графы.......................................................................................... 133
5.1. Основные определения теории графов....................................... 134
5.2. Проект для алгоритмов на графах............................................... 136
5.2.1. Сруктура стек для обработки графов.................................. 138
5.2.2. Структура данных для представления графов ................... 141
5.2.3. Изображение графов............................................................. 144
5.2.4. Запись и чтение графов ........................................................ 148
5.3. Поиск в графах.............................................................................. 153
229
5.3.1. Поиск в глубину.................................................................... 154
5.3.2. Поиск в ширину......... ........................................................... 162
5.3.3. Остов графа................. .......................................................... 165
5.4. Кратчайшие пути.......................................................................... 167
5.4.1. Волновой алгоритм............................................................... 167
5.4.2. Алгоритм Дейкстры.............................................................. 169
5.4.3. Алгоритм Форда-Мура-Беллмана ....................................... 174
5.5. Циклы на графах........................................................................... 177
5.5.1. Эйлеровы циклы.................................................................... 177
5.5.2. Гамильтонов цикл. Алгоритмы с возвратом ...................... 179
5.6. Гамильтоновы циклы и задача коммивояжера .......................... 182
5.7. Комбинаторные задачи на графах............................................... 183
5.7.1. Минимальная раскраска графа ............................................ 183
5.7.2. Приближенные алгоритмы раскраски графа...................... 185
5.8. Алгоритмы о связности графа..................................................... 191
5.8.1. Топологическая сортировка................................................. 192
5.8.2. Минимальное остовное дерево............................................ 194
5.8.3. Построение минимального остовного дерева .................... 197
5.8.4. Выделение компонент связности ........................................ 202
Выводы................................................................................................. 203
Упражнения ......................................................................................... 204
Глава 6. Некоторые численные методы ................................................. 205
6.1. Решение системы линейных уравнений методом Гаусса ......... 205
6.2. Приближенное вычисление производных.................................. 210
6.3. Приближенное вычисление интегралов ..................................... 212
6.3.1. Формула прямоугольников.................................................. 213
6.3.2. Формула трапеций..................... ........................................... 214
6.3.3. Формула Симпсона............................................................... 215
6.4. Линейные дифференциальные уравнения.................................. 219
Литература ................................................................................................ 224
