Министерство образования республики Беларусь
Белорусский национальный технический университет
А. В. Романов
Структуры и алгоритмы обработки данных
Учебное пособие по дисциплине «Структуры и алгоритмы обработки данных» для специальностей «Программное обеспечение информационных технологий» и «Информационные системы и технологии»
Минск 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
введение
Данные
Данные – непременный атрибут любой программы. Когда употребляют термин «программа», подразумевают не только последовательность операторов некоторого языка программирования, но и набор различных информационных объектов (константы, переменные, массивы и т. д.), над которыми выполняются действия, описанные операторами программы. Такие объекты называют данными. В операторе
If a > b[i] Then a := 0;
описаны действия, в которых «участвуют» переменные a, i, элемент массива b[i] и константа 0. Эти информационные объекты и являются данными.
Данные и команды хранятся в памяти компьютера в двоичном коде. Этот код занимает часть памяти, называемую ячейкой или слотом памяти. Местоположение каждой ячейки определяется ее адресом. В оперативной памяти минимальная двоичная ячейка, имеющая собственный уникальный адрес, – это последовательность восьми битов, т. е. байт. Обычно ячейка, предназначенная для хранения индивидуального данного, состоит из нескольких последовательных байтов, т. е. из нескольких адресуемых ячеек.
При компиляции программы программа-компилятор выполняет, в частности, следующие действия:
каждому данному выделяется своя ячейка памяти,
каждый оператор, записанный на языке высокого уровня, представляется последовательностью машинных команд (или одной командой), которые содержат адреса тех данных, с которыми эти команды оперируют (именно поэтому данные часто называют операндами).
Каждое данное относится к одному из конечного множества типов, допустимых для конкретной версии языка программирования. Программистам хорошо известны данные таких типов как Byte (байтовый), Integer (целый), Rеаl(вещественный), Boolean (логический), Char (символьный). Значение любого данного этих типов логически неразделимо, поэтому такие данные называются неструктурированными или примитивными данными. Неструктурированные данные служат для построения структур данных: записей, массивов, деревьев, файлов и т. д.
Биты в байте нумеруются от 0 до 7, при этом бит с номером 0 является самым младшим битом. При схематическом изображении ячейки, состоящей из одного или нескольких байтов, самый младший бит принято располагать на правом конце ячейки, и старшинство битов увеличивается при приближении к левому концу. На рисунке 1.1 показано схематичное изображение байта, содержащего значение 5 в прямом двоичном коде.
Рисунок 1.1 – Нумерация битов в байте
Два байта со смежными адресами образуют слово (word) разрядностью 16 бит, два смежных слова образуют двойное слово (double word). Учетверенное слово (quad word), образуемое последовательностью из восьми байт, имеет разрядность 64 бита. Биты ячеек, состоящих более чем из одного байта, нумеруются от 0, до общего количества битов минус 1, например, самый старший бит учетверенного слова имеет номер 63
Если ячейка состоит более чем из двух байтов, то адресом всей ячейки является адрес ее младшего байта. При графическом изображении ячейки, состоящей из нескольких байтов, старшинство байтов (и соответственно значения их адресов) увеличиваются в направлении справа налево, т. е. самый правый байт, является самым младшим байтом ячейки, как это показано на рисунке 1.2 на примере двойного слова
Рисунок 1.2 – Пример представления двойного слова