Структуры и алгоритмы обработки данных

Таганрог

Издательство Южного федерального университета

2016

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное 

учреждение высшего образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Инженерно-технологическая академия

С.Н. Дроздов

Структуры и алгоритмы обработки данных

Учебное пособие

УДК 004.021(075.8)
ББК 32.973я73

Д754

Печатается по решению редакционно-издательского совета

Южного федерального университета

Рецензенты:

профессор кафедры систем автоматизации проектирования Института 

компьютерных технологий и информационной безопасности ЮФУ 

Е.В. Нужнов;

директор направления ООО AT Consulting, кандидат технических наук 

Д.П. Калачев.

Дроздов, С.Н.

Д754
Структуры и алгоритмы обработки данных : учебное пособие / 

С.Н. Дроздов;
Южный
федеральный
университет.
–

Таганрог : Издательство Южного федерального университета, 2016. 
– 228 с. 

ISBN 978-5-9275-2242-2

В учебном пособии рассматриваются базовые структуры данных и 

важнейшие алгоритмы, используемые при разработке системного и 
прикладного программного обеспечения. Излагаются наиболее эффективные 
алгоритмы сортировки и поиска данных, рассматриваются комбинаторные 
задачи и методы их решения (метод ветвей и границ, динамическое 
программирование, эвристические алгоритмы). Подчеркивается важность 
оценки эффективности алгоритмов при проектировании программ. Дается 
представление о теории вычислительной сложности и о проблемах, 
связанных с понятием NP-полноты задач.

Предназначено 
для 
студентов, 
обучающихся 
по 
направлениям 

подготовки 
бакалавров 
02.03.03 
«Математическое 
обеспечение 
и 

администрирование информационных систем» и 09.03.04 «Программная 
инженерия».

ISBN 978-5-9275-2242-2
УДК 004.021(075.8)

ББК 32.973я73

 Южный федеральный университет, 2016
 Дроздов С.Н., 2016

СОДЕРЖАНИЕ

1. ВВЕДЕНИЕ..................................................................................................7

1.1. Предмет и задачи курса .......................................................................7
1.2. Рекомендации по литературе ..............................................................7
1.3. Понятие типа данных...........................................................................8
Контрольные вопросы...............................................................................10

2. ПРОСТЫЕ ТИПЫ ДАННЫХ ..................................................................10

2.1. Числовые типы данных......................................................................10
2.2. Логический тип данных.....................................................................13
2.3. Другие простые типы.........................................................................16

2.3.1. Символьный тип ..................................................................................16
2.3.2. Перечисляемые типы данных.............................................................17
2.3.3. Ограниченные типы данных...............................................................18

Контрольные вопросы...............................................................................18

3. СТРУКТУРНЫЕ ТИПЫ ДАННЫХ........................................................19

3.1. Способы представления структурных данных ...............................19
3.2. Записи ..................................................................................................21
3.3. Массивы...............................................................................................23
3.4. Строки..................................................................................................24
3.5. Множества...........................................................................................26
3.6. Стеки....................................................................................................28
3.7. Очереди................................................................................................34
3.8. Приоритетные очереди ......................................................................40
3.9. Линейные списки................................................................................44
3.10. Деревья ..............................................................................................48

3.10.1. Основные определения .....................................................................48
3.10.2. Бинарные деревья и их представление............................................49
3.10.3. Операции с деревьями.......................................................................50
3.10.4. Устранение рекурсии при операциях с деревьями ........................56

3.11. Последовательные контейнеры ......................................................60

3.11.1. Контейнеры в библиотеке STL.........................................................60
3.11.2. Массивы..............................................................................................61
3.11.3. Списки.................................................................................................62
3.11.4. Дек.......................................................................................................63
3.11.5. Стек и очередь....................................................................................65
3.11.6. Приоритетная очередь.......................................................................65

Контрольные вопросы...............................................................................66

4. СОРТИРОВКА И ПОИСК .......................................................................67

4.1. Задачи поиска в информатике...........................................................67
4.2. Задача поиска в таблице ....................................................................68
4.3. Понятие об оценке эффективности алгоритмов и программ ........70
4.4. Линейный поиск .................................................................................74
4.5. Бинарный поиск..................................................................................77
4.6. Задачи сортировки таблиц и массивов.............................................79
4.7. Простые алгоритмы сортировки.......................................................81

4.7.1. Алгоритм пузырька (BubbleSort) .......................................................81
4.7.2. Алгоритм выбора (SelectionSort)........................................................82
4.7.3. Алгоритм вставок (InsertionSort)........................................................82
4.7.4. Общая характеристика простых алгоритмов....................................83

4.8. Алгоритм Шелла (ShellSort)..............................................................84
4.9. Алгоритм быстрой сортировки (QuickSort).....................................85
4.10. Алгоритм пирамидальной сортировки (HeapSort)........................89
4.11. Алгоритмы сортировки слиянием (MergeSort) .............................94
4.12. Задача внешней сортировки............................................................96
4.13. Сравнение алгоритмов сортировки ................................................99
Контрольные вопросы.............................................................................100

5. ПОИСК СО ВСТАВКОЙ .......................................................................102

5.1. Постановка задачи............................................................................102
5.2. Бинарные деревья поиска................................................................104
5.3. АВЛ-деревья .....................................................................................109
5.4. Страничные деревья поиска............................................................113
5.5. B-деревья...........................................................................................117
5.6. Использование B-деревьев в базах данных...................................122
5.7. Ассоциативные контейнеры на базе деревьев поиска..................123

5.7.1. Структуры данных.............................................................................123
5.7.2. Множества..........................................................................................124
5.7.3. Отображения ......................................................................................125

Контрольные вопросы.............................................................................125

6. СПЕЦИАЛЬНЫЕ МЕТОДЫ СОРТИРОВКИ И ПОИСКА................126

6.1. Поразрядная сортировка..................................................................127
6.2. Поиск в словаре и боры ...................................................................132
6.3. Определение порядковых статистик..............................................134

Контрольные вопросы.............................................................................136

7. ХЕШИРОВАНИЕ....................................................................................137

7.1. Основные понятия хеширования....................................................137
7.2. Способы построения хеш-функций................................................140

7.2.1. Общие требования к хеш-функциям ...............................................140
7.2.2. Алгоритм деления..............................................................................141
7.2.3. Алгоритм середины квадрата...........................................................142
7.2.4. Алгоритм умножения........................................................................144
7.2.5. Хеширование строковых ключей.....................................................145

7.3. Методы разрешения коллизий........................................................147

7.3.1. Алгоритм линейных проб.................................................................148
7.3.2. Алгоритм квадратичных проб..........................................................148
7.3.3. Алгоритм двойного хеширования....................................................149
7.3.4. Алгоритм списков в динамической памяти....................................149
7.3.5. Алгоритм Уильямса...........................................................................150

7.4. Условия эффективности хеширования ..........................................150
7.5. Другие применения хеширования ..................................................152

7.5.1. Проверка принадлежности к множеству.........................................152
7.5.2. Проверка целостности сообщений и текстовых файлов ...............153
7.5.3. Криптографическое хеширование ...................................................154

7.6. Ассоциативные контейнеры на базе хеширования.......................155
Контрольные вопросы.............................................................................156

8. МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ ........................157

8.1. Понятие комбинаторной задачи .....................................................157
8.2. Примеры комбинаторных задач......................................................158
8.3. Организация исчерпывающего перебора с возвратами ...............162
8.4. Сокращение перебора ......................................................................166
8.5. Полный перебор с перечислением планов ....................................168
8.6. Метод ветвей и границ.....................................................................170

8.6.1. Общее понятие о методе ветвей и границ.......................................170
8.6.2. Метод ветвей и границ для задачи о коммивояжере .....................173

8.7. Метод --отсечений для позиционных игр с полной 

информацией .......................................................................................180

8.8. Метод динамического программирования ....................................184

8.8.1. Задача о двух армиях и рекуррентные вычисления.......................184
8.8.2. Общее понятие о методе динамического программирования ......187

8.8.3. Метод динамического программирования для задачи о 

рюкзаке ...............................................................................................190

8.8.4. Метод динамического программирования для задачи  о 

наибольшей общей подпоследовательности ..................................194

8.9. Приближенные и эвристические методы решения задач 

комбинаторной оптимизации ............................................................196
8.9.1. Точные,  приближенные и эвристические алгоритмы...................196
8.9.2. «Жадные» алгоритмы........................................................................198
8.9.3. Генетические алгоритмы ..................................................................200
8.9.4. О доказательствах и контрпримерах ...............................................201

Контрольные вопросы.............................................................................202

9. ЭЛЕМЕНТЫ ТЕОРИИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ ...................203

9.1. Основные понятия и проблемы теории сложности 

вычислений..........................................................................................203

9.2. Полиномиальная сводимость задач................................................207
9.3. Недетерминированные машины Тьюринга и NP-задачи.............207
9.4. NP-полные и NP-трудные задачи....................................................211
9.5. Теорема Кука ....................................................................................212

9.5.1. Постановка задачи.............................................................................212
9.5.2. Формулировка теоремы ....................................................................213
9.5.3. Доказательство теоремы ...................................................................213

9.6. Примеры NP-полных задач .............................................................216

9.6.1. Задача «3-Выполнимость» (задача «3-ВЫП»)................................216
9.6.2. Задача о вершинном покрытии графа (задача ВП) ........................218
9.6.3. Другие NP-полные задачи ................................................................220

9.7. Псевдополиномиальные задачи......................................................221
9.8. Практическое значение результатов теории сложности 

вычислений..........................................................................................223

Контрольные вопросы.............................................................................225

ЗАКЛЮЧЕНИЕ ...........................................................................................226
БИБЛИОГРАФИЧЕСКИЙ СПИСОК .......................................................227

1. ВВЕДЕНИЕ

1.1. Предмет и задачи курса
Предметом изучения в данном
курсе
являются базовые 

структуры данных и алгоритмы обработки данных, составляющие 
«золотой фонд» современного программирования и являющиеся 
обязательной компонентой знаний каждого квалифицированного 
программиста.

В качестве основных задач изучения курса можно выделить 

следующие:

- знание основных, наиболее важных структур данных и 

алгоритмов, умение применять их в практике программирования;

- знание принципов и критериев оценки эффективности 

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

Практическим 
итогом 
изучения 
курса 
должно 
стать 

обогащение арсенала программиста рядом высокоэффективных 
средств, 
позволяющих 
значительно 
повысить 
качество 

разрабатываемых программ.

1.2. Рекомендации по литературе
Классическим 
источником 
по 
базовым 
алгоритмам 
и 

структурам данных является книга Н. Вирта [1]. Впоследствии 
автор несколько раз переписывал эту книгу, делая существенные 
дополнения и переводя примеры программ на очередной 
изобретенный им язык программирования. В частности, книга [2] 
содержит важный новый материал.

Очень хороша по подбору материала и по качеству изложения 

книга [3].

Книга [4] представляет собой огромную по объему, но вполне 

доступную по изложению монографию, часть материалов которой 
трудно найти в других источниках.

Классическая
серия
книг
Д. Кнута 
«Искусство 

программирования» 
содержит 
описания 
очень 
большого 

количества алгоритмов и связанных с ними структур данных, при 
этом значительное
внимание
уделено оценке эффективности 

алгоритмов. Для освоения данного курса наибольшее значение 
имеет том 3 «Сортировка и поиск» [5].

В книге [6] хорошо изложены основы теории вычислительной 

сложности и приведен огромный список известных на момент 
публикации NP-полных задач.

Много информации по алгоритмам и структурам данных 

можно найти в Интернете. Определения и краткие описания 
многих терминов можно найти в Википедии [7], хотя этот 
полезный ресурс нельзя считать исчерпывающим или полностью 
достоверным. Среди других русскоязычных ресурсов можно 
назвать [8], а также значительно более продвинутый по 
содержанию 
и 
сложности 
сайт 
[9].
Весьма 
полезно 
для 

начинающего 
программиста 
регулярное 
посещение 
сайта 

Хабрахабр [10], который содержит постоянно пополняемую 
пользователями коллекцию интересных материалов, относящихся 
как к теме данного пособия, так и к другим разделам информатики 
и программирования.

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

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

Согласно современному подходу к проектированию программ, 

тип данных определяется двумя множествами:

- множеством значений, которые могут принимать величины 

данного типа;

- множеством операций, которые можно выполнять над этими 

величинами.

В качестве примера того, почему множество операций 

является обязательной частью определения типа, рассмотрим два 
типа данных, которые условно назовем «Время дня» и «Интервал 
времени». Можно договориться, что значениями каждого из типов 
могут быть пары целых чисел «часы : минуты». Тем не менее, 
интуитивно ясно, что эти типы представляют разные по смыслу 
вещи, и это сказывается на наборе допустимых операций. 
Например, можно сложить два интервала времени, но совершенно 
бессмысленно складывать два времени дня: сумма «10:20 + 8:30»

не имеет смысла. Зато вполне осмысленна разность двух времен 
дня, но при этом разность будет уже относиться к типу «Интервал 
времени».

Выбор используемых типов данных является важнейшим 

элементом грамотного проектирования программы, а в некоторых 
случаях 
фактически 
предопределяет 
выбор 
используемых 

алгоритмов.

Различают простые и структурные типы
данных. Тип 

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

Примерами структурных данных могут служить любые массивы, 
состоящие из отдельных элементов, или записи, состоящие из 
полей.

При 
выборе 
типа 
данных 
следует 
исходить 
не 
из 

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

Современные языки программирования предоставляют для этого 
достаточные возможности.

Для того чтобы тип данных можно было использовать в 

программах, его определение должно включать две составляющие 
части: интерфейс и реализацию (представление).

Интерфейс типа данных содержит, как было указано выше, 

описание множества возможных значений и множества операций
над ними, с указанием сигнатуры, т.е. количества и типа 
операндов и результата операции. Знание интерфейса позволяет 
использовать тип данных при разработке программ.

Реализация типа данных включает в себя описание структур,

используемых для представления данных, и программные модули, 
выполняющие все операции, перечисленные в интерфейсе.

Нередко возникает ситуация, когда одному и тому же 

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

структур данных и алгоритмов выполнения операций для 
конкретной рассматриваемой задачи.

Получившая широкое распространение технология объектно
ориентированного программирования (ООП) включает в качестве
одного из основных своих компонентов механизм инкапсуляции, 
т.е. описания типа данных
(класса)
вместе с функциями

(методами), применимыми к данным этого класса.

Некоторым неудобством понятия класса является то, что 

определение класса должно включать определение полей данных 
объектов этого
класса. Это ограничивает гибкость выбора 

реализации методов класса для конкретных задач. В таких языках 
программирования, как Java, C# и ряд других, наряду с понятием 
класса, успешно используется понятие интерфейса (interface) как 
описания набора функций для типа данных. Интерфейс включает 
только имена функций, типы их аргументов и значений, но не 
содержит 
ни 
описания 
конкретных 
структур 
данных, 
ни 

реализации функций. То и другое должно выбираться при 
разработке 
конкретного 
класса, 
реализующего 
указанный 

интерфейс.

Контрольные вопросы
1. Могут ли два разных типа данных иметь одинаковое 

множество значений?

2. Могут ли два разных типа данных иметь одинаковое 

множество операций?

3. Какие типы данных относятся к простым?
4. Что такое интерфейс и реализация типа данных?
5. Что такое сигнатура операции?
6. Что такое инкапсуляция данных?
7. Что такое интерфейс в языках Java, C#?
8. Чем понятие интерфейса отличается от понятия класса?

2. ПРОСТЫЕ ТИПЫ ДАННЫХ

2.1. Числовые типы данных
На вопрос: «Какие существуют числовые типы данных?» часто 

следует немедленный ответ: «Целый и вещественный». Такая точка 
зрения 
основана 
на 
знакомстве 
с 
популярными 
языками 

программирования (C, Pascal и др.), которые содержат именно эти