- •Оглавление
- •Список рисунков
- •ВвЕдение
- •Необходимые понятия и определения
- •Основные структуры данных
- •Задача сортировки массивов
- •Трудоемкость методов сортировки массивов
- •Задача сортировки последовательностей
- •Теорема о сложности сортировки
- •Задача поиска элементов с заданным ключом
- •Методы сортировки с квадратичной трудоемкостью
- •Метод прямого выбора
- •Алгоритм на псевдокоде
- •Пузырьковая сортировка
- •Алгоритм на псевдокоде
- •Шейкерная сортировка
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Метод Шелла
- •Метод прямого включения
- •Алгоритм на псевдокоде
- •Метод Шелла
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Быстрые методы сортировки массивов
- •Пирамидальная сортировка
- •Свойства пирамиды
- •Алгоритм на псевдокоде
- •Построение (1, 8)-пирамиды
- •Сортировка
- •Алгоритм на псевдокоде
- •Метод Хоара
- •Алгоритм на псевдокоде
- •Проблема глубины рекурсии.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Работа с линейными списками
- •Указатели. Основные операции с указателями
- •Основные операции с линейными списками
- •Методы сортировки последовательностей
- •Метод прямого слияния
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Цифровая сортировка
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Двоичный поиск в упорядоченном массиве
- •Алгоритм двоичного поиска
- •Алгоритм на псевдокоде
- •Обозначим
- •Найден – логическая переменная, в которой будем отмечать факт успешного завершения поиска.
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сортировка данных с произвольной структурой
- •Сравнение данных произвольной структуры
- •Сортировка по множеству ключей. Индексация
- •Алгоритм на псевдокоде (на примере пузырьковой сортировки)
- •Индексация через массив указателей
- •Варианты заданий
- •Двоичные деревья
- •Основные определения и понятия
- •Различные обходы двоичных деревьев
- •Варианты заданий
- •Деревья поиска
- •Поиск в дереве
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Идеально сбалансированное дерево поиска
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Случайное дерево поиска
- •Определение случайного дерева поиска
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Сбалансированные по высоте деревья (авл-деревья)
- •Определение и свойства авл-дерева
- •Повороты при балансировке
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Удаление вершины из дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Определение б-дерева порядка m
- •Поиск в б-дереве
- •Алгоритм на псевдокоде
- •Построение б-дерева
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Определение двоичного б-дерева
- •Добавление вершины в дерево
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Деревья оптимального поиска (доп)
- •Определение дерева оптимального поиска
- •Точный алгоритм построения доп
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Хэширование и поиск
- •Понятие хэш-функции
- •Алгоритм на псевдокоде
- •Метод прямого связывания
- •Метод открытой адресации
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Элементы теории кодирования информации
- •Необходимые понятия
- •Кодирование целых чисел
- •Алфавитное кодирование
- •Оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Почти оптимальное алфавитное кодирование
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •Варианты заданий
- •Рекомендуемая литература
- •Псевдокод для записи алгоритмов
- •Структуры и алгоритмы обработки данных
- •630102, Г. Новосибирск, ул. Кирова, 86.
Министерство информационных технологий и связи
Российской Федерации
Сибирский государственный университет
телекоммуникаций и информатики
Е. В. Курапова
Е. П. Мачикина
СТРУКТУРЫ И АЛГОРИТМЫ
ОБРАБОТКИ ДАННЫХ
Методическое пособие
Новосибирск 2006
УДК 681.3.06
ктн Е. В. Курапова, кф-мн Е. П. Мачикина
Структуры и алгоритмы обработки данных: Методическое пособие. / Сиб. гос. ун-т телекоммуникаций и информатики. – Новосибирск, 2006. – 105 с.
Методическое пособие предназначено для студентов технических специальностей, обучающихся по направлению “550400 Телекоммуникации” и изучающих дисциплину «Структуры и алгоритмы обработки данных». Пособие содержит необходимый теоретический минимум по данному предмету и варианты заданий для самостоятельного выполнения.
Рисунков 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 Шейкерная сортировка 16
2.4 Варианты заданий 18
3. Метод Шелла 19
3.1 Метод прямого включения 19
3.2 Метод Шелла 20
3.3 Варианты заданий 22
4. Быстрые методы сортировки массивов 23
4.1 Пирамидальная сортировка 23
4.2 Метод Хоара 26
4.3 Проблема глубины рекурсии. 28
4.4 Варианты заданий 29
5. Работа с линейными списками 30
5.1 Указатели. Основные операции с указателями 30
5.2 Основные операции с линейными списками 31
6. Методы сортировки последовательностей 34
6.1 Метод прямого слияния 34
6.2 Цифровая сортировка 37
6.3 Варианты заданий 39
7. Двоичный поиск в упорядоченном массиве 39
7.1 Алгоритм двоичного поиска 39
7.2 Варианты заданий 41
8. Сортировка данных с произвольной структурой 41
8.1 Сравнение данных произвольной структуры 41
8.2 Сортировка по множеству ключей. Индексация 42
8.3 Индексация через массив указателей 43
8.4 Варианты заданий 43
9. Двоичные деревья 44
9.1 Основные определения и понятия 44
9.2 Различные обходы двоичных деревьев 44
9.3 Вычисление основных характеристик дерева 45
9.4 Варианты заданий 46
10. Деревья поиска 47
10.1 Поиск в дереве 47
10.2 Идеально сбалансированное дерево поиска 48
10.3 Варианты заданий 49
11. Случайное дерево поиска 50
11.1 Определение случайного дерева поиска 50
11.2 Добавление вершины в дерево 51
11.3 Удаление вершины из дерева 52
11.4 Варианты заданий 54
12. сбалансированные по высоте деревья (АВЛ-ДЕРЕВЬЯ) 54
12.1 Определение и свойства АВЛ-дерева 54
12.2 Повороты при балансировке 56
12.3 Добавление вершины в дерево 59
12.4 Удаление вершины из дерева 60
12.5 Варианты заданий 65
13. Б-ДЕРЕВЬЯ 65
13.1 Определение Б-дерева порядка m 65
13.2 Поиск в Б-дереве 67
13.3 Построение Б-дерева 68
13.4 Определение двоичного Б-дерева 70
13.5 Добавление вершины в дерево 71
13.6 Варианты заданий 75
14. Деревья оптимального поиска (ДОП) 75
14.1 Определение дерева оптимального поиска 75
14.2 Точный алгоритм построения ДОП 77
14.3 Приближенные алгоритмы построения ДОП 80
14.4 Варианты заданий 83
15. Хэширование и поиск 84
15.1 Понятие хэш-функции 84
15.2 Метод прямого связывания 86
15.3 Метод открытой адресации 87
15.4 Варианты заданий 90
16. Элементы теории кодирования информации 90
16.1 Необходимые понятия 90
16.2 Кодирование целых чисел 92
16.3 Алфавитное кодирование 95
16.4 Оптимальное алфавитное кодирование 98
16.5 Почти оптимальное алфавитное кодирование 102
16.6 Варианты заданий 105
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА 107
Приложение А 108