Москва 2007

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

(Учебное пособие)

Юрагов Евгений Алексеевич [email protected]

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

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

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

Пособие предназначено для студентов специальностей 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. Множества.................................................................................................................................................................................. 38

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............................................................................................................................................................................ 67

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

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

5.3. Деки.............................................................................................................................................................................................. 68

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

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. Нелинейные структуры данных.......................................................................... 91

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

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

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

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

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

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

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

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

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

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

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

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

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. Структуры данных и алгоритмы

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