Предисловие

А. С. Третьяков

АЛГОРИТМЫ

&

СТРУКТУРЫ ДАННЫХ

Оглавление

Предисловие........................................................................................................................ 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

Выражаем благодарность всем тем читателям, что давали полезные советы и находили ошибки.