Проектирование, Анализ и программная Реализация структур данных и алгоритмов

1 2 3 4 5 6 7

Институт менеджмента и информационных технологий

Министерство образования Российской Федерации

Санкт-Петербургский государственный политехнический университет

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

Череповец

УДК 004.2

Царев В.А., Дробанов А.Ф.

Проектирование, анализ и программная реализация структур данных и алгоритмов – Череповец, 2007. – 169 с.

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

Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Высокоуровневые методы информатики и программирования» студентами различных форм обучения, проходящих подготовку по специальностям 080801 и 230105.

Рецензенты:

Утверждено:

Содержание

1 Алгоритмы... 6

1.1 Основные определения: алгоритм, вход, результат; понятие правильного и неправильного алгоритма; псевдокод 6

1.2 Скорость роста функций.. 7

1.3 Анализ алгоритмов; время работы в лучшем, худшем случаях и в среднем.. 9

1.4 Типы данных, структуры данных и абстрактные типы данных. 14

1.5 Динамические множества. 21

2 Алгоритмы сортировок.. 22

2.1 Понятие внутренней и внешней сортировки.. 22

2.2 Сортировка вставками.. 23

2.3 Сортировка слиянием.. 24

2.3.1 Описание алгоритма. 24

2.3.2 Анализ времени работы алгоритмов «разделяй и властвуй». 26

2.3.2 Анализ времени работы сортировки слиянием через рекуррентное соотношение. 27

2.3.3 Анализ времени работы сортировки слиянием через геометрическую интерпретацию.. 27

2.4 Пирамидальная сортировка. 28

2.4.1 Введение в алгоритм.. 28

2.4.2 Сохранение основного свойства кучи. 30

2.4.3 Построение кучи. 31

2.5 Быстрая сортировка. 32

2.5.1 Введение в алгоритм.. 32

2.5.2 Описание. 33

2.5.3 Разбиение массива. 33

2.5.4 Особенности работы быстрой сортировки. 36

2.6 Особенности реализации алгоритмов сортировки; сортировка за линейное время. 38

2.6.1 Введение. 38

2.6.2 Разрешающее дерево сортировки сравнениями. 38

2.7 Цифровая сортировка. 39

2.8 Сортировка вычерпыванием.. 41

2.8.1 Описание алгоритма. 41

2.8.2 Вероятностный анализ времени работы сортировки вычерпыванием.. 42

2.8.3 Анализ времени работы сортировки вычерпыванием через геометрическую интерпретацию.. 43

2.9 Сортировка подсчетом.. 44

2.9.1 Описание алгоритма. 44

2.9.2 Анализ времени работы.. 46

3 Элементарные и нелинейные структуры данных.. 46

3.1 Элементарные структуры: список, стек, очередь, дек.. 46

3.1.1 Список. 47

3.1.2 Стек. 62

3.1.3 Очередь. 65

3.1.3 Дек. 68

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

3.2.1 Представление корневых деревьев в ЭВМ... 70

3.2.2 Двоичные деревья. 73

3.2.3 Двоичные деревья поиска. 77

4 Хеширование.. 87

4.2 Прямая адресация; таблицы с прямой адресацией.. 89

4.3 Хеш – таблицы; возникновение коллизий и их разрешение. 91

4.4 Способы построения хеш – функций.. 96

4.5 Открытая адресация; способы вычисления последовательности испробованных мест: линейная последовательность проб, квадратичная последовательность проб, двойное хеширование. 101

5 Основные принципы разработки алгоритмов.. 109

5.1 Введение в теорию графов. 109

5.1.1 Графы.. 109

5.1.2 Представление графов. 113

5.2 Алгоритмы на графах: поиск в ширину, поиск в глубину. 116

5.2.1 Поиск в ширину (волновой алгоритм) 116

5.2.2 Анализ поиска в ширину. 119

5.2.3 Деревья поиска в ширину. 119

5.2.4 Поиск в глубину. 120

5.2.5 Анализ поиска в глубину. 124

5.2.6 Свойства поиска в глубину. 124

5.2.7 Классификация рёбер. 126