ВУЗ:
Составители:
90
Распределение памяти 1 2 4 7 8 10
11
14
15
16
Вспом.
область
170
061
512
612
503
653
703
154
275
765
426
087
897
677
908
509
Счётчики для средних цифр 4 2 1 0 0 2 2 3 1 1
Распределение памяти 4 6 7 7 7 9 11
14
15
16
Область
ввода
503
703
908
509
512
612
426
653
154
061
765
170
275
677
087
897
Счётчики для старших цифр 2 2 1 0 1 3 3 2 1 1
Распределение памяти 2 4 5 5 6 9 12
14
15
16
Вспом.
область
061
087
154
170
275
426
503
509
512
612
653
677
703
765
897
908
Заметим, что идея счётчиков для распределения памяти привязана к
«старомодным» понятиям о последовательном представлении данных, а
для работы с множеством таблиц переменной длины специально приду-
мано связанное распределение. Поэтому для поразрядной сортировки
естественно будет воспользоваться связанными структурами данных. Так
как каждая стопка просматривается последовательно, при каждом эле-
менте достаточно иметь ссылку на следующий элемент. Кроме того, при
связанном распределении, как известно, нет необходимости перемещать
записи, а достаточно лишь должным образом скорректировать связи в
списках. При таком подходе необходима память в объёме (1 + ε)N + 2εМ
записей, где ε – пространство, занимаемое одним полем связи.
Рассмотрим алгоритм, который является ярким примером типичных
манипуляций со структурами данных, соединяющих в себе последова-
тельное и связанное распределение памяти.
Алгоритм R. (Поразрядная сортировка списка.)
Предполагается, что каждая из записей R
1
, …, R
N
содержит поле свя-
зи LINK, а ключи представляют собой последовательность из p элементов:
(a
p
, …, a
2
, a
1
), 0 ≤ a
i
< M.
Отношение порядка – лексикографическое, т.е.
(a
p
,
…, a
2
, a
1
) < (b
p
, …, b
2
, b
1
)
тогда и только тогда, когда существует такой индекс j, 1 ≤ j ≤ p, что
a
i
= b
i
при i > j, но a
j
< b
j
.
Ключи могут быть представлены, в частности, как числа в системе
счисления с основанием М:
a
p
М
p–1
+ … + a
2
М + a
1
,
Страницы
- « первая
- ‹ предыдущая
- …
- 88
- 89
- 90
- 91
- 92
- …
- следующая ›
- последняя »
