Структуры данных и алгоритмы их обработки (Учебное пособие)

Юрагов Евгений Алексеевич evg_uragov@mtu-net.ru

Москва 2007

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

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

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

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

Содержание

1. Структуры данных и алгоритмы 6

1.1. Понятие структур данных и алгоритмов 6

1.2. Информация и ее представление 7

1.2.1. Природа информации 7

1.2.2. Хранение информации 7

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

1.3. Операции над структурами данных 9

1.4. Порядок алгоритма 10

1.5. Структурность данных и технологии программирования 11

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

2. Простые структуры данных 12

2.1. Порядковые типы 13

2.2. Целочисленный тип 13

2.3. Символьный тип 14

2.4. Перечисляемый тип 15

2.5. Интервальный тип 16

2.6. Логический тип 16

2.7. Битовый тип 17

2.8. Вещественный тип 17

2.9. Указательный тип 19

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

3. Объектные типы данных 24

3.1. Объявление и реализация классов 24

3.2. Директивы видимости 26

3.3. Свойства классов 27

3.4. Структурированная обработка ошибок 27

3.5. Применение объектов 29

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

4. Статические структуры данных 32

4.1. Векторы 32

4.2. Массивы 34

4.3. Множества 37

4.4. Записи 39

4.5. Таблицы 43

4.6. Операции над статическими структурами 43

4.6.1. Алгоритмы поиска 43

4.6.2. Алгоритмы сортировки 46

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

5. Полустатические структуры данных 65

5.1. Стеки 65

5.1.1. Стеки в вычислительных системах 66

5.2. Очереди FIFO 66

5.2.1. Очереди с приоритетами 67

5.2.2. Очереди в вычислительных системах 67

5.3. Деки 68

5.3.1. Деки в вычислительных системах 68

5.4. Строки 69

5.4.1. Операции над строками 69

5.4.2. Представление строк в памяти 70

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

6. Динамические структуры данных 74

6.1. Связное представление данных в памяти 74

6.2. Связные линейные списки 75

6.2.1. Машинное представление связных линейных списков 75

6.2.2. Реализация операций над связными линейными списками 76

6.2.3. Применение линейных списков 83

6.3. Нелинейные разветвленные списки 85

6.3.1. Основные понятия 85

6.3.2. Представление списковых структур в памяти 87

6.3.3. Операции обработки списков 87

6.4. Язык программирования LISP 88

6.5. Управление динамически выделяемой памятью 88

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

7. Нелинейные структуры данных 90

7.1. Графы и деревья 90

7.2. Машинное представление графов 92

7.3. Бинарные деревья 96

7.3.1. Представление бинарных деревьев 97

7.3.2. Прохождение бинарных деревьев 99

7.4. Алгоритмы на деревьях 100

7.4.1. Сортировка с прохождением бинарного дерева 101

7.4.2. Сортировка методом турнира с выбыванием 101

7.4.3. Применение бинарных деревьев для сжатия информации 103

7.4.4. Представление выражений с помощью деревьев 105

7.5. Представление сильноветвящихся деревьев 106

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

8. Методы ускорения доступа к данным 108

8.1. Хеширование данных 108

8.1.1. Функции хеширования 109

8.1.2. Оценка качества хеш-функции 110

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

8.1.4. Переполнение таблицы и рехеширование 116

8.2. Организация данных для поиска по вторичным ключам 117

8.2.1. Инвертированные индексы 117

8.2.2. Битовые карты 118

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

Листинги рабочих примеров 119

1. Создание и управление списковыми объектами 119

2. Алгоритмы поиска и сортировки 121

3. Моделирование работы стека 134

4. Создание и редактирование бинарных деревьев 137

5. Создание и редактирование сильноветвящихся деревьев 139

Задания для самостоятельной работы 142

Литература 144

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

1. 1.1. Понятие структур данных и алгоритмов

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

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

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

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

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

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

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

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

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

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

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