Предисловие
А. С. Третьяков
АЛГОРИТМЫ
&
СТРУКТУРЫ ДАННЫХ
Оглавление
Предисловие........................................................................................................................ 4
I Структуры данных 5
Введение........................................................................................................... 6
1 Массивы........................................................................................................ 7
1.1 Введение.............................................................................................. 7
1.2 Хеш-функции...................................................................................... 8
1.2.1 Метод деления................................................................ 8
1.2.2 Метод умножения........................................................... 9
1.3 Хеш-таблица..................................................................................... 11
1.3.1 Открытое хеширование.............................................. 12
1.3.2 Закрытое хеширование............................................... 13
1.4 Ассоциативный массив.................................................................. 15
1.5 Динамический массив.................................................................... 18
2 Списки......................................................................................................... 20
2.1 Введение........................................................................................... 20
2.2 Связный список............................................................................... 24
2.3 Стек..................................................................................................... 31
2.4 Очередь............................................................................................ 36
2.4.1 Реализация очереди с помощью массива.............. 36
2.4.2 Реализация очереди с помощью указателей........ 42
2.5 Дек...................................................................................................... 45
3 Графы........................................................................................................... 51
3.1 Основные понятия и виды графов............................................ 51
3.2 Матрица смежности...................................................................... 55
3.3 Список смежности......................................................................... 57
3.4 Список ребер................................................................................. 62
3.5 Матрица инцидентности.............................................................. 67
4 Деревья...................................................................................................... 69
4.1 Введение.......................................................................................... 69
4.2 Двоичное дерево.......................................................................... 71
4.3 Двоичное дерево поиска............................................................ 74
4.4 Куча................................................................................................... 76
4.5 АВЛ-дерево..................................................................................... 78
4.5.1 Балансировка................................................................ 80
4.5.2 Добавление узлов....................................................... 83
4.5.3 Удаление узлов............................................................ 83
II Алгоритмы 85
Введение.................................................................................................................. 86
5 Анализ сложности алгоритмов........................................................ 87
5.1 Введение.......................................................................................... 87
5.2 Асимптотический анализ............................................................. 90
6 Сортировка............................................................................................... 92
6.1 Сортировка пузырьком................................................................ 92
6.2 Сортировка выбором................................................................... 96
6.3 Сортировка вставками.................................................................. 99
6.4 Сортировка Шелла...................................................................... 103
6.5 Быстрая сортировка.................................................................... 106
6.5.1 Разбиение массива................................................... 106
6.5.2 Рекурсивная сортировка частей массива............ 108
6.6 Сортировка слиянием................................................................ 111
6.7 Гномья сортировка...................................................................... 116
6.8 Шейкерная сортировка.............................................................. 120
7 Поиск......................................................................................................... 123
7.1 Линейный поиск........................................................................... 123
7.2 Двоичный поиск........................................................................... 126
7.3 Интерполяционный поиск........................................................ 130
8 Теория чисел......................................................................................... 133
8.1 Алгоритм Евклида........................................................................ 133
8.1.1 Метод вычитания...................................................... 133
8.1.2 Метод деления........................................................... 135
8.2 Бинарный алгоритм вычисления НОД................................... 139
8.3 Быстрое возведение в степень................................................ 142
8.4 Решето Эратосфена................................................................... 145
8.5 Решено Сундарама..................................................................... 148
9 Графы....................................................................................................... 150
9.1 Поиск в ширину........................................................................... 150
9.2 Поиск в глубину........................................................................... 155
9.3 Алгоритм Дейкстры..................................................................... 158
9.4 Алгоритм Флойда-Уоршелла................................................... 165
9.5 Алгоритм Беллмана-Форда...................................................... 170
Предисловие
Данная книга собрана по материалам сайта Kvodo.ru, которые были отредактированы и несколько обобщены. В ней кратко описаны алгоритмы и структуры данных, наиболее часто используемые в программировании, а также конкретные способы их реализации на двух популярных языках программирования: С++ и Pascal. Книга рассчитана на читателя с некоторым базовым набором знаний. Она не претендует называться учебником, и тем более заменить общепризнанный учебный материал.
Изучать главы книги необязательно по порядку. В этом плане она может служить справочником. Большинство тем содержат рисунки, схемы и таблицы, поясняющие работу алгоритмов и структур данных.
В отличие от первоначальной версии (материала сайта), в коде отсутствуют некоторые элементы, необходимые для реального функционирования программы. Сделано это с целью «оторвать» приведенный код от конкретной среды разработки. Читателю придется самому добавлять необходимые директивы и операторы.
В разделе «Алгоритмы» каждая тема подкреплена листингом, написанном как на C++, так и на Pascal. Но в разделе «Структуры данных», в подавляющем большинстве случаев, приведен код только для C++, т. к. некоторые темы требовали значительного обилия кода, что не позволило использовать сразу два языка. Поэтому предполагается, что читатель знаком с языком C++. Изучить его можно, воспользовавшись соответствующей книгой или сетевым ресурсом, например, тем же Kvodo.ru.
Книга, с большой вероятностью, содержит ошибки. Мы будем благодарны, если Вы укажите их, воспользовавшись электронной почтой: Kvodo.ru@inbox.ru
Выражаем благодарность всем тем читателям, что давали полезные советы и находили ошибки.