Романов Александр Васильевич

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

Учебное пособие по дисциплине
«Структуры и алгоритмы обработки данных»
для специальностей
«Программное обеспечение информационных технологий» и
«Информационные системы и технологии»

Минск 2010

ББК 32.973.2

УДК 681.3.06(075)

Структуры и алгоритмы обработки данных: Учеб. пособие. – Мн: БНТУ, 2010. – 151 с.: ил.

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

Содержание

1 Введение.............................................................................................................. 6

1.1 Данные................................................................................................................... 6

1.2 Логическая и физическая структуры данных.................................................... 7

1.3 Классификация структур данных....................................................................... 9

1.4 Основные операции над структурами данных.................................................. 10

1.5 Алгоритм и примеры задач, решаемых с помощью алгоритмов..................... 12

2 Адресация и распределение памяти................................................ 14

2.1 Адресные пространства и модели оперативной памяти.................................. 14

2.2 Формирование физического адреса в реальном режиме................................. 15

2.3 Особенности адресации в защищенном режиме............................................... 16

2.4 Кэширование......................................................................................................... 17

3 Анализ алгоритмов...................................................................................... 19

3.1 Быстродействие – основной показатель эффективности алгоритма.............. 19

3.2 Подсчет числа простейших операций................................................................ 21

3.3 О-нотация.............................................................................................................. 22

3.4 Лучший, средний и худший случаи.................................................................... 23

3.5 Алгоритмы и платформы..................................................................................... 24

3.5.1 Виртуализация памяти...................................................................................... 24

3.5.2 Использование кэша.......................................................................................... 25

3.5.3 Выравнивание данных...................................................................................... 26

3.6 Рандомизированные алгоритмы......................................................................... 26

4 Записи................................................................................................................... 27

4.1 Общая характеристика записей и способы описания в Delphi........................ 27

4.2 Многоуровневые записи...................................................................................... 29

4.3 Выравнивание и упакованные записи............................................................... 29

4.4 Записи с вариантной частью............................................................................... 30

5 Массивы.............................................................................................................. 33

5.1 Общая характеристика массивов........................................................................ 33

5.2 Статические (стандартные) массивы.................................................................. 34

5.2.1 Вектор................................................................................................................. 34

5.2.2 Многомерные статические массивы................................................................ 35

5.2.3 Свойства статических массивов...................................................................... 37

5.3 Открытые массивы............................................................................................... 37

5.4 Динамические массивы........................................................................................ 38

5.4.1 Динамические векторы..................................................................................... 38

5.4.2 Многомерные динамические массивы............................................................ 40

5.5 Массивы типа Variant........................................................................................... 42

5.6 Вставка и удаление в массиве............................................................................. 43

6 Связные списки и алгоритмы их обработки................................ 46

6.1 Списки и их разновидности................................................................................ 46

6.2 Односвязный список............................................................................................ 47

6.2.1 Общая характеристика односвязного списка................................................. 47

6.2.2 Структура элемента односвязного списка...................................................... 49

6.2.3 Формирование односвязного списка............................................................... 49

6.2.4 Просмотр односвязного списка........................................................................ 50

6.2.5 Вставка элемента в односвязный список........................................................ 51

6.2.6 Удаление элемента из односвязного списка................................................... 53

6.3 Линейный двухсвязный список.......................................................................... 54

6.3.1 Структура элемента двухсвязного списка...................................................... 55

6.3.2 Реализация операций в линейном двухсвязном списке................................ 55

6.4 Плексы................................................................................................................... 58

6.4.1 Нелинейный двухсвязный список................................................................... 58

6.4.2 Нелинейный трехсвязный список................................................................... 59

6.4.3 Определение плекса и его общие признаки................................................... 60

6.5 Иерархическая списковая структура. Сетевая структура................................. 60

6.6 Достоинства и недостатки связных списков..................................................... 63

6.7 Функциональные и свободные списки.............................................................. 63

6.7.1 Общая характеристика функционального и свободного списка.................. 63

6.7.2 Методы формирования свободного списка.................................................... 65

7 Стеки, очереди, деки и операции в них........................................... 66

7.1 Общая характеристика......................................................................................... 66

7.2 Стек........................................................................................................................ 66

7.3 Очередь.................................................................................................................. 68

7.4 Дек.......................................................................................................................... 70

8 Динамические множества и словари.............................................. 72

8.1 Общая характеристика......................................................................................... 72

8.2 Таблица – логическое представление словаря................................................... 73

8.3 Операции в динамических множествах............................................................. 74

9 Деревья.................................................................................................................. 76

9.1 Общая характеристика и некоторые определения............................................ 76

9.2 Представление дерева в памяти.......................................................................... 78

9.2.1 Естественное представление дерева................................................................ 78

9.2.2 Представление дерева с помощью вектора..................................................... 80

9.2.3 Представление дерева с использованием списков сыновей......................... 82

9.3 Методы обхода деревьев...................................................................................... 82

9.4 Бинарное дерево.................................................................................................... 84

9.4.1 Структура бинарного дерева............................................................................ 84

9.4.2 Формирование бинарного дерева.................................................................... 85

9.4.3 Обход бинарного дерева................................................................................... 86

9.4.4 Преобразование любого дерева к бинарному дереву.................................... 88

9.5 Включение и исключение в дереве.................................................................... 89

9.5.1 Включение в дереве........................................................................................... 90

9.5.2 Исключение в дереве......................................................................................... 90

10 Поиск................................................................................................................... 91

10.1 Поиск: определение и общая терминология.................................................... 91

10.2 Линейный (последовательный) поиск............................................................. 93

10.3 Последовательный поиск в упорядоченной таблице..................................... 94

10.4 Последовательный поиск при накоплении запросов..................................... 95

10.5 Индексно-последовательный поиск................................................................. 96

10.6 Бинарный поиск.................................................................................................. 98

10.7 Поиск, использующий бинарное дерево.......................................................... 100

11 Сортировка....................................................................................................... 102

11.1 Общие сведения и некоторые определения..................................................... 102

11.2 Внутренняя сортировка...................................................................................... 103

11.2.1 Сортировка прямыми включениями............................................................. 104

11.2.2 Сортировка бинарными включениями......................................................... 106

11.2.3 Сортировка прямым выбором........................................................................ 106

11.2.4 Сортировка прямым обменом........................................................................ 108

11.2.5 Сортировка методом Шелла........................................................................... 111

11.2.6 Сортировка с помощью бинарного дерева................................................... 113

11.2.7 Пирамидальная сортировка............................................................................ 115

11.2.8 Быстрая сортировка разделением................................................................... 119

11.3 Внешняя сортировка........................................................................................... 121

11.3.1 Сортировка прямым слиянием....................................................................... 122

11.3.2 Сортировка естественным слиянием............................................................. 125

11.3.3 Сортировка многопутевым слиянием........................................................... 126

11.3.4 Многофазная сортировка................................................................................ 127

12 Хеширование и хеш-таблицы.............................................................. 129

12.1 Общие сведения и определения........................................................................ 129

12.2 Коллизии при хешировании.............................................................................. 132

12.3 Разрешение коллизий при хешировании......................................................... 132

12.3.1 Разрешение коллизий методом открытой адресации.................................. 132

12.3.2 Разрешение коллизий методом цепочек........................................................ 137

12.4 Функции хеширования...................................................................................... 139

12.4.1 Хеш-функции для целочисленных ключей.................................................. 139

12.4.2 Хеш-функции для строковых ключей........................................................... 141

13 Поисковые деревья..................................................................................... 143

13.1 Бинарное дерево поиска..................................................................................... 143

13.1.1 Структура бинарного дерева поиска и алгоритм поиска............................ 143

13.1.2 Вставка элемента в бинарное дерево поиска................................................ 144

13.1.3 Удаление из бинарного дерева поиска.......................................................... 146

13.2 Красно-черные деревья...................................................................................... 147

13.2.1 Определение красно-черного дерева, структура его элементов................. 147

13.2.2 Повороты.......................................................................................................... 149

ЛИТЕРАТУРА.............................................................................................................. 151

Дата добавления: 2014-01-07