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

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

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

Минск 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