ВУЗ:
Составители:
86
Таблица 2
503
87 512
61 908
170
897
275
653
426
154
509
612
677
765
703
503
703
512
677
509
908
426
897
653
275
170
154
612
61 765
87
87 503
703
765
154
170
509
908
897
653
426
275
677
612
512
61
61 87 503
512
612
677
703
765
908
897
653
509
426
275
170
154
61 87 154
170
275
426
503
509
512
612
653
677
703
765
897
908
Рассмотрим теперь алгоритмы N и S с точки зрения структур дан-
ных. Для работы этих алгоритмов необходима память под 2N записей,
поскольку в каждом просмотре работа ведётся с четырьмя списками пе-
ременного размера: двумя «входными списками» и двумя «выходными
списками». С целью экономии памяти можно воспользоваться её связан-
ным распределением. При этом к каждой из N записей добавить по одно-
му полю связи, и все необходимые слияния проделать, манипулируя со
связями и не перемещая сами записи. Заметим, что добавление N полей
связи, как правило, выгоднее, чем добавление пространства памяти ещё
под N записей, и, кроме того, за счёт отказа от перемещения записей мо-
жет быть также сэкономлено и время.
Алгоритм L. (Сортировка посредством слияния списков.) Предпо-
лагается, что записи R
1
, …, R
N
содержат ключи K
1
, …, K
N
и «поля связи»
L
1
, …, L
N
, в которых могут храниться числа от минус (N + 1) до (N + 1).
В начале и конце файла имеются искусственные записи R
0
и R
N+1
с поля-
ми связи L
0
и L
N+1
. Этот алгоритм сортировки списков устанавливает по-
ля связи таким образом, что записи оказываются связанными в возрас-
тающем порядке. После завершения сортировки L
0
указывает на запись с
наименьшим ключом; при 1 ≤ k ≤ N связь L
k
указывает на запись, сле-
дующую за R
k
, а если R
k
является записью с наибольшим ключом, то
связь L
k
= 0.
В процессе выполнения этого алгоритма записи R
0
и R
N+1
служат
«головами» двух линейных списков, подсписки которых в данный мо-
мент сливаются. Отрицательная связь означает конец подсписка, о кото-
ром известно, что он упорядочен. Нулевая связь означает конец всего
списка. Предполагается, что число записей N ≥ 2.
Через оператор вида |L
s
| ← p обозначено присваивание переменной L
s
значения p или – р с сохранением прежнего знака значения указателя L
s
.
L1. [Подготовка двух списков.] Присвоить L
0
← 1, L
N+1
← 2,
L
i
← – (i + 2) при 1 ≤ i ≤ N – 2 и L
N–1
← L
N
← 0. (Созданы два списка, со-
держащие соответственно записи R
1
, R
3
, R
5
, … и R
2
, R
4
, R
6
, … . Отрица-
тельные связи говорят о том, что каждый упорядоченный «подсписок»
состоит всего лишь из одного элемента.)
L2. [Начало нового просмотра.] Присвоить s ← 0, t ← N + 1, р ← L
s
,
q ← L
t
. Если q = 0, то работа алгоритма завершена. (При каждом про-
Страницы
- « первая
- ‹ предыдущая
- …
- 84
- 85
- 86
- 87
- 88
- …
- следующая ›
- последняя »
