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



страница1/12
Дата07.12.2016
Размер0.58 Mb.
Просмотров841
Скачиваний0
ТипУчебное пособие
  1   2   3   4   5   6   7   8   9   ...   12


Мautoshape 70autoshape 91инистерство образования республики Беларусь

Белорусский национальный технический университет

А. В. Романов

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

Учебное пособие по дисциплине


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

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


введение


    1. Данные

Данные – непременный атрибут любой программы. Когда употребляют термин «программа», подразумевают не только последовательность операторов некоторого языка программирования, но и набор различных информационных объектов (константы, переменные, массивы и т. д.), над которыми выполняются действия, описанные операторами программы. Такие объекты называют данными. В операторе

If a > b[i] Then a := 0;

описаны действия, в которых «участвуют» переменные a, i, элемент массива b[i] и константа 0. Эти информационные объекты и являются данными.

Данные и команды хранятся в памяти компьютера в двоичном коде. Этот код занимает часть памяти, называемую ячейкой или слотом памяти. Местоположение каждой ячейки определяется ее адресом. В оперативной памяти минимальная двоичная ячейка, имеющая собственный уникальный адрес, – это последовательность восьми битов, т. е. байт. Обычно ячейка, предназначенная для хранения индивидуального данного, состоит из нескольких последовательных байтов, т. е. из нескольких адресуемых ячеек.

При компиляции программы программа-компилятор выполняет, в частности, следующие действия:


  1. каждому данному выделяется своя ячейка памяти,

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

Каждое данное относится к одному из конечного множества типов, допустимых для конкретной версии языка программирования. Программистам хорошо известны данные таких типов как 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 – Пример представления двойного слова




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

Структурой данных (data structure) называют совокупность (множество) данных и отношений между ними. Один и тот же набор данных можно представить по-разному. Пусть имеется пять данных типа Char: А, B, С , D и Е. Из этой совокупности значений можно сформировать как линейную последовательность элементов, так и дерево или сеть, как показано на рисунке 1.3.

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

А

B

C



D

E

а



б

А

B



C

D

E



А

B

D



C

E

в


Рисунок 1.3 – Представление множества из пяти элементов разными структурами:

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

Используя термин «структура данных», следует различать понятия логической и физической структур. Логическая структура  это абстрактная схема расположения данных, которую представляет себе пользователь или программист. Физическая структура – это способ (или схема) конкретного размещения данных в памяти вычислительной машины. Физическую структуру иногда называют структурой хранения. В общем случае логическая и физическая структуры одних и тех же данных не совпадают. Например, последовательность записей, имеющая логическую структуру, изображенную на рисунке 1.4, представляется программисту как непрерывная последовательность строк одинакового размера.

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


Запись 1

Запись 2

...

Запись N

Рисунок 1.4 – Логическая структура таблицы

Или другой пример. Логическая структура двумерного массива чисел  это прямоугольная двумерная фигура элементов или матрица, в которой каждый элемент однозначно идентифицируется парой индексов строки и столбца, на пересечении которых он находится. Физической же структурой двумерного массива является линейная последовательность ячеек оперативной памяти компьютера, каждая из которых однозначно определяется своим единственным адресом. На рисунке 1.5 показаны логическая и физическая структуры двумерного массива типа Word, состоящего их трех строк и двух столбцов.

Одна и та же логическая структура может по-разному храниться в памяти разных ЭВМ (различная конфигурация памяти) или для разных компиляторов.




















Ячейка ОЗУ

Адрес
(смещение)




a

x [0, 0]

x [0, 1]




б

x [0, 0]

$0A56







x [1, 0]

x [1, 1]







x [0, 1]

$0A58







x [2, 0]

x [2, 1]







x [1, 0]

$0A5А



















x [1, 1]

$0A5С



















x [2, 0]

$0A5Е



















x [2, 1]

$0A60

Рисунок 1.5 – Логическая (а) и физическая (б) структуры матрицы типа Word




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

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

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

Структуры данных, которые физически создаются, хранятся и обрабатываются в основной (оперативной) памяти ЭВМ, называются оперативными структурами. Представление структуры хранения во внешней памяти называют файловой структурой. Файл – это поименованная совокупность данных, расположенных на внешнем носителе, например, на диске. Элементами файловой структуры служат, в общем случае, записи. В процессе «зарождения» запись проходит фазу существования в оперативной памяти.

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

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

По характеру упорядоченности элементов структуры различают линейно-упорядоченные (или линейные) и нелинейные структуры данных. К линейным структурам, в частности, относятся такие структуры как векторы, линейные списки. Примеры нелинейных структур дают многосвязные списки (плексы), древовидные и сетевые структуры.

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


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

К основным операциям над структурами данных отно­сятся следующие операции:

  • формирование;

  • просмотр;

  • вставка (включение);

  • добавление (дополнение);

  • извлечение;

  • удаление (исключение);

  • сдвиг;

  • изменение содержимого элемента;

  • сортировка.

Большинство из перечисленных операций связано с корректи­ровкой (updating) структуры данных. Под корректировкой структуры данных понимают алгоритм, применение кото­рого позволяет изменить содержимое отдельных элементов структуры, либо сами структуры (количество элементов, характер отношений между элементами). Рассмотрим эти операции.

Формирование  это создание в памяти компьютера структуры данных, соответствующей ее логическому пред­ставлению. При этом различают фазы:

  1. первоначальное формирование (generation), когда создаются ячейки памяти для элементов структуры и отношений, и значения данных размещаются в порядке их поступления извне в этих ячейках, и

  2. перегруппирования (regrouping), например, созда­ния древовидной структуры из записей, хранящихся в неко­торой таблице; на этапе перегруппирования может быть применена сортировка.

Просмотр (scan, pass)  последовательное выполне­ние над элементами структуры одной и той же операции, например, сравнение их содержимого с некоторым задан­ным значением. Просмотр может выполняться с целью контроля содержимого элементов или для подсчета их числа.

Вставка (insertion)  это ввод нового данного в струк­туру данных. При вставке указываются элементы, между которыми в логической структуре расположится новый элемент; эти элементы определяют точку вставки. Хотя на расположение точки вставки мо­гут быть наложены ограничения (например, включение в очередь возможно только со стороны «хвоста»), обыч­но, употребляя термин «вставка», подразумевают возмож­ность включения нового элемента в любое место исходной структуры. При вставке в массивах выполняется сдвиг некоторого количества элементов, чтобы ос­вободить место для вставляемого элемента. Вставка в ди­намические структуры такого сдвига не требует: просто изменяются адреса связей без физического перемещения данных в памяти.

Под добавлением (store) понимают вставку нового элемента в логический конец корректируемой структуры. В сущности, формирование структуры  это последова­тельность добавлений элементов данных.



Извлечение (extraction) выполняется с целью передачи содержимого элемента структуры для дальнейшего ис­пользования, например, для печати этого содержимого.

Удаление (deletion)  это исключение некоторого элемен­та из структуры данных. При удалении в массивах удаляе­мый элемент либо помечают как удаленный (такое удале­ние без физического уничтожения называется логическим удалением logical deletion), либо осуществляют сдвиг некоторого количества элементов, при котором в ячейку с адресом удаляемого элемента заносится значение соседне­го сдвигаемого элемента. В динамических структурах про­сто изменяются адреса связей без физического перемеще­ния данных, а ячейка, в которой размещался удаляемый элемент, включается в список свободных ячеек, доступных для вставки.

Сдвиг (shift)  это перемещение некоторых элементов данных в одном из направлений: либо от логического нача­ла структуры к ее логическому концу, либо наоборот. При сдвиге сохраняется порядок следования сдвигаемых эле­ментов.

Под изменением содержимого (data modification) элемента данных обычно понимают присваивание этому элементу нового значения.



Сортировка (sorting)  это распределение элементов некоторого множества с целью их расположения в соответ­ствии с некоторыми правилами. Разновидностью сортиров­ки является упорядочение данных по возрастанию или убыванию значений некоторого признака или ключа сортировки. Часто сортировка выполняется как переупорядочение (reordering) ранее упорядоченной последовательности по другому признаку (полю). Сортировка массивов предпола­гает, что перестановки, приводящие элементы в порядок, должны выполняться «на том же месте». Сортировка ди­намической структуры предполагает изменение адресов связей.

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





    1. Поделитесь с Вашими друзьями:
  1   2   3   4   5   6   7   8   9   ...   12


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал