Структуры и алгоритмы обработки данных : учебно-метод. пособие

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

Структуры и алгоритмы обработки данных : учебно-метод. пособие

Министерствоинформационных технологий и связи

Российской Федерации

Сибирскийгосударственный университет

телекоммуникацийи информатики

Е. В. Курапова

Е. П. Мачикина

Новосибирск2006

УДК 681.3.06

Ктн е. В. Курапова, кф-мн е. П. Мачикина

Структурыи алгоритмы обработки данных: Учебноепособие. / Сиб. гос. ун-т телекоммуникацийи информатики. – Новосибирск, 2006. – 105с.

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

Рисунков69, таблиц 13. Список лит. –5 назв.

Кафедра прикладнойматематики и кибернетики.

Рецензент: ЗайцевМ.Г., Венедиктов М.Д.

Утвержденоредакционно-издательским советомСибГУТИ в качестве учебного пособия.

 Сибирскийгосударственный университет

телекоммуникацийи информатики, 2006 г.

Оглавление

ВВЕдение 7

1.Необходимые понятия и определения 7

1.1Основные структуры данных 7

1.2 Задача сортировки массивов 8

1.3 Трудоемкость методов сортировки массивов 9

1.4 Задача сортировки последовательностей 10

1.5Теорема о сложности сортировки 10

1.6 Задача поиска элементов с заданным ключом 11

2.Методы сортировки с квадратичной трудоемкостью 12

2.1Метод прямого выбора 12

2.2 Пузырьковая сортировка 13

2.3 Шейкерная сортировка 15

2.4 Варианты заданий 17

3. Метод Шелла 18

3.1 Метод прямого включения 18

3.2Метод Шелла 19

3.3Варианты заданий 21

4.Быстрые методы сортировки массивов 22

4.1Пирамидальная сортировка 22

4.2Метод Хоара 25

4.3Проблема глубины рекурсии. 27

4.4Варианты заданий 28

5.Работа с линейными списками 29

5.1Указатели. Основные операции с указателями 29

5.2Основные операции с линейными списками 30

6.Методы сортировки последовательностей 32

6.1Метод прямого слияния 32

6.2Цифровая сортировка 36

6.3Варианты заданий 37

7.Двоичный поиск в упорядоченном массиве 38

7.1Алгоритм двоичного поиска 38

7.2Варианты заданий 40

8.Сортировка данных с произвольной структурой 40

8.1Сравнение данных произвольной структуры 40

8.2Сортировка по множеству ключей. Индексация 41

8.3Индексация через массив указателей 42

8.4Варианты заданий 42

9.Двоичные деревья 42

9.1Основные определения и понятия 42

9.2Различные обходы двоичных деревьев 43

9.3Вычисление основных характеристик дерева 44

9.4Варианты заданий 45

10.Деревья поиска 45

10.1Поиск в дереве 45

10.2Идеально сбалансированное дерево поиска 46

10.3Варианты заданий 48

11.Случайное дерево поиска 48

11.1Определение случайного дерева поиска 48

11.2Добавление вершины в дерево 49

11.3Удаление вершины из дерева 50

11.4Варианты заданий 52

12.сбалансированные по высоте деревья (АВЛ-ДЕРЕВЬЯ) 52

12.1Определение и свойства АВЛ-дерева 52

12.2Повороты при балансировке 54

12.3Добавление вершины в дерево 56

12.4Удаление вершины из дерева 58

12.5Варианты заданий 62

13.Б-ДЕРЕВЬЯ 63

13.1Определение Б-дерева порядка m 63

13.2Поиск в Б-дереве 64

13.3Построение Б-дерева 65

13.4Определение двоичного Б-дерева 68

13.5Добавление вершины в дерево 69

13.6Варианты заданий 72

14.Деревья оптимального поиска (ДОП) 73

14.1Определение дерева оптимального поиска 73

14.2Точный алгоритм построения ДОП 74

14.3Приближенные алгоритмы построения ДОП 77

14.4Варианты заданий 80

15.Хэширование и поиск 81

15.1Понятие хэш-функции 81

15.2Метод прямого связывания 83

15.3Метод открытой адресации 84

15.4Варианты заданий 86

16.Элементы теории кодирования информации 87

16.1Необходимые понятия 87

16.2Кодирование целых чисел 89

16.3Алфавитное кодирование 92

16.4Оптимальное алфавитное кодирование 95

16.5Почти оптимальное алфавитное кодирование 98

16.6Варианты заданий 102

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА 103

Приложение А 104

Список рисунков

Рисунок 1 Дерево решений для 6 элементов 10

Рисунок 2 Метод прямого выбора 12

Рисунок 3 Пузырьковая сортировка 15

Рисунок 4 Шейкерная сортировка 16

Рисунок 5 Метод прямого включения 18

Рисунок 6 Метод Шелла 21

Рисунок 7 Добавление в пирамиду нового элемента 22

Рисунок 8 Пирамидальная сортировка 24

Рисунок 9 Метод Хоара 26

Рисунок 10 Схема вызовов при вычислении 4! 27

Рисунок 11 Структура фрейма 28

Рисунок 12 Равенство указателей 29

Рисунок 13 Указатель на элемент списка 30

Рисунок 14 Добавление в стек 31

Рисунок 15 Удаление из стека 31

Рисунок 16 Добавление в очередь 31

Рисунок 17 Структура очереди 32

Рисунок 18 Добавление в очередь 32

Рисунок 19 Перемещение элемента 32

Рисунок 20 Слияние серий 33

Рисунок 21 Метод прямого слияния 34

Рисунок 22 Начальное расщепление 34

Рисунок 23 Цифровая сортировка 36

Рисунок 24 Первая версия поиска 38

Рисунок 25 Вторая версия поиска 39

Рисунок 26 Список абонентов 40

Рисунок 27 Пример двоичного дерева 43

Рисунок 28 43

Рисунок 29 Дерево поиска 45

Рисунок 30 Примеры ИСД и неИСД 46

Рисунок 31 Построение ИСДП 47

Рисунок 32 Случайное дерево поиска 49

Рисунок 33 Плохие СДП 49

Рисунок 34 Добавление вершины В 50

Рисунок 35 Добавление вершины 9 50

Рисунок 36 Варианты удаления вершин 51

Рисунок 37 Удаляемая вершина с двумя поддеревьями 51

Рисунок 38 Порядок изменения указателей при удалении вершины 51

Рисунок 39 Пример АВЛ-дерева и не АВЛ-дерева 53

Рисунок 40 Деревья Фибоначчи 53

Рисунок 41 LL — поворот 54

Рисунок 42 LR – поворот 55

Рисунок 43 RR – поворот 56

Рисунок 44 RL – поворот 56

Рисунок 45 Построение АВЛ-дерева 58

Рисунок 46 Три случая при удалении вершины из левого (для BL) поддерева 59

Рисунок 47 Три случая при удалении вершины правого (для BR) поддерева 60

Рисунок 48 Удаление из АВЛ-дерева 62

Рисунок 49 Страница Б-дерева 64

Рисунок 50 Пример Б-дерева 64

Рисунок 51 Структура страницы Б-дерева 65

Рисунок 52 Построение Б-дерева 66

Рисунок 53 Виды вершин ДБД 68

Рисунок 54 Вершины двоичного Б-дерева 68

Рисунок 55 Четыре ситуации, возникающих при росте левых или правых поддеревьев 70

Рисунок 56 Построение двоичного Б-дерева 72

Рисунок 57 Различные деревья поиска с вершинами V1=1, V2=2, V3=3 74

Рисунок 58 ДОП для w1=60, w2=30, w3=10 76

Рисунок 59 Дерево, построенное приближенным алгоритмом А1 79

Рисунок 60 Дерево, построенное приближенным алгоритмом А2 80

Рисунок 61. Отображение H: K→A 81

Рисунок 62. Хэш-таблица, построенная методом прямого связывания 84

Рисунок 63. Использование квадратичных проб 86

Рисунок 64 Полное двоичное дерево с помеченными вершинами 93

Рисунок 65 Построение префиксного кода с заданными длинами 94

Рисунок 66 Процесс построения кода Хаффмена 97

Рисунок 67 Кодовое дерево для кода Хаффмена 97

Рисунок 68 Кодовое дерево для кода Фано 100

СПИСОК ТАБЛИЦ

Таблица 1 Различные типы данных 7

Таблица 2 Основные операции с указателями 29

Таблица 3 Частоты вхождения символов в строку 78

Таблица 4 Упорядоченный набор вершин 79

Таблица 5. Номера символов строки 86

Таблица 6 Код класса Fixed + Variable 89

Таблица 7 Код класса Variable + Variable 90

Таблица 8 γ-код Элиаса 90

Таблица 9 ω-код Элиаса 91

Таблица 10 Код Хаффмена 97

Таблица 11 Код Шеннона 99

Таблица 12 Код Фано 100

Таблица 13 Код Гилберта-Мура 101

Источник: https://studfile.net/preview/2919114/

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

Структуры и алгоритмы обработки данных : учебно-метод. пособие

ЮраговЕвгений Алексеевич 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-компиляторы в таких случаях лишь выдадут предупреждения. Отсутствие жесткой защиты типов дает дополнительные возможности, но за правильностью действий приходится следить самостоятельно.

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

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

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

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

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

Источник: https://studfile.net/preview/2262019/

Biz-books
Добавить комментарий