- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Многофазная сортировка.
В основе данной сортировки лежит отказ от жесткого понятия прохода и разделения файлов на две категории. Рассмотрим этот метод сортировки на примере:
Если
,
то
.
0,
1, 1, 2, 3, 5, 8, 13, 21, 34,…
f1
|
f2 |
f3 |
|
L |
|
|
|
13
|
8 |
0 |
L=6 |
0 |
1 |
0 |
1 |
5
|
0 |
8 |
L=5 |
1 |
1 |
1 |
2 |
0
|
5 |
3 |
L=4 |
2 |
2 |
1 |
3 |
3
|
2 |
0 |
L=3 |
3 |
3 |
2 |
5 |
1
|
0 |
2 |
L=2 |
4 |
5 |
3 |
8 |
0
|
1 |
1 |
L=1 |
5 |
8 |
5 |
13 |
1 |
0 |
0 |
L=0 |
6 |
13 |
8 |
21 |
Таким образом, необходимо, чтобы числа начальных серий в двух входных последовательностях были двумя соседними числами Фибоначчи.
f1
|
f2 |
f3 |
f4 |
f5 |
f6 |
|
L |
|
|
|
|
|
|
16
|
15 |
14 |
12 |
8 |
0 |
L=5 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
8
|
7 |
6 |
4 |
0 |
8 |
L=4 |
1 |
1 |
1 |
1 |
1 |
1 |
5 |
4
|
3 |
2 |
0 |
4 |
4 |
L=3 |
2 |
2 |
2 |
2 |
2 |
1 |
9 |
2
|
1 |
0 |
2 |
2 |
2 |
L=2 |
3 |
4 |
4 |
4 |
3 |
2 |
17 |
1
|
0 |
1 |
1 |
1 |
1 |
L=1 |
4 |
8 |
8 |
7 |
6 |
4 |
33 |
0 |
1 |
0 |
0 |
0 |
0 |
L=0 |
5 |
16 |
15 |
14 |
12 |
8 |
65 |
;
;
;
;
.
Подставляя вместо , получаем
(для i 4);
Такие числа называются числами Фибоначчи четвертого порядка. В общем случае числа Фибоначчи порядка р определяются следующим образом:
(для i > p); .
Заметим, что обычные числа Фибоначчи – числа первого порядка.
Теперь уже ясно, что исходные числа серий для идеальной многофазной сортировки с N последовательностями (файлами) представляют собой последовательность чисел Фибоначчи порядка N – 2. Отсюда следует, что метод применим для лишь входов, сумма серий на которых есть сумма N – 1 таких чисел Фибоначчи. В том случае, когда сумма серий отличается от идеальной суммы, то вводим фиктивную серию.