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

4.1  Деревья     66
4.1.1 Представление  деревьев    68
4.2   Бинарные деревья    68
4.2.1  Сведение m-арного дерева к бинарному    70
4.2.2 Основные операции с деревьями    72
4.2.3 Алгоритм создания дерева бинарного поиска    73
4.2.4 Прохождение бинарных деревьев    75
5. Поиск    78
5.1 Последовательный поиск    79
5.2.Индексно-последовательный поиск    81
5.3. Эффективность последовательного поиска    83
5.4. Эффективность индексно-последовательного поиска     84
5.5 Методы оптимизации поиска    84
5.5.1 Переупорядочивание таблицы поиска путем перестановки найденного элемента в начало списка     85
5.5.2. Метод  транспозиции     87
5.5.3. Дерево оптимального поиска     88
5.6  Бинарный поиск (метод деления пополам)    90
5.7. Поиск по бинарному дереву    92
5.8  Поиск со вставкой (с включением)    94
5.9  Поиск с удалением    95
6.  Сортировка    100
6.1. Сортировка методом прямого включения     101
6.2  Сортировка методом прямого выбора    104
6.3. Сортировка с помощью прямого обмена (пузырьковая сортировка)    105
6.4. Улучшенные методы сортировки    107
6.4.1.  Быстрая сортировка (Quick Sort)    108
6.4.2  Сортировка Шелла (сортировка с уменьшающимся шагом)    109
7. ПРЕОБРАЗОВАНИЕ КЛЮЧЕЙ (РАССТАНОВКА)    113
7.1. Выбор функции преобразования    113
7.2. Алгоритм    115
часть 2.
практикум по сруктурам и алгоритмам обработки данных в эвм    119
методическое руководство к лабораторным работам    120
Организационно-методические указания    120
Лабораторная работа № 1. «ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ»    122
Краткая теория    122
Алгоритм    124
Задания    126
Лабораторная работа № 2. «СПИСКОВЫЕ СТРУКТУРЫ ДАННЫХ»    127
Краткая теория    127
Линейные однонаправленные списки    129
Алгоритм    130
Удаление элемента из начала односвязного списка    131
Вставка элемента в список    132
Удаление элемента из односвязного списка    133
Задания    134
Лабораторная работа № 3. «КОЛЬЦЕВЫЕ СПИСКИ»    135
Краткая теория    135
Алгоритм    136
Вставка элемента в кольцевой список    136
Удаление элемента из кольцевого списка    137
Задания    138
Лабораторная работа № 4. «МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ»    140
Краткая теория    140
Алгоритм    142
Процедура прибавления элемента в начало списка.    142
Процедура удаления из начала списка.    142
Процедура прибавления элемента в список.    143
Процедура удаления из списка    143
Задания    143
Лабораторная работа № 5. «БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)»    145
Краткая теория    145
Алгоритм    148
Процедура создания бинарного дерева    148
Процедуры «обхода» дерева    150
Процедура поиска по бинарному дереву    151
Процедура включения элемента в дерево    152
Процедура удаления элемента из бинарного дерева    154
Задания    156
Лабораторная работа № 6 . «СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВКЛЮЧЕНИЯ»    159
Краткая теория    159
Алгоритм    161
Задания    162
Лабораторная работа № 7. «СОРТИРОВКА МЕТОДОМ ПРЯМОГО ВЫБОРА»    164