Методы программирования. Громов Ю.Ю - 10 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

10
7. Рассмотрите задачу из упр. 2, заменив стек на дек. Найдите пере-
становки чисел 1, 2, 3 и 4, которые:
а) можно получить в случае дека с ограниченным входом, но нельзя
получить для дека с ограниченным выходом;
б) можно получить в случае дека с ограниченным выходом, но
нельзя получить для дека с ограниченным входом;
в) нельзя получить ни для дека с ограниченным входом, ни для дека
с ограниченным выходом.
8. Существуют ли какие-либо перестановки чисел 1, 2, …, n, кото-
рые нельзя получить с помощью дека, не имеющего ни ограниченного
входа, ни ограниченного выхода?
2. ПОСЛЕДОВАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ
ПРИ ХРАНЕНИИ ЛИНЕЙНЫХ СПИСКОВ
Простейший и наиболее естественный способ хранения линейного
списка в памяти машины сводится к размещению элементов списка в
последовательных ячейках памяти, один узел за другим. В этом случае
LOC (X [ j + 1]) = LOC (X [ j ]) + c,
где LOC (X [ j + 1]), LOC (X [ j ]) – адреса узлов X [ j + 1] и X [ j ] соответ-
ственно; c – количество слов в одном узле.
В общем случае адрес узла X [ j ] определяется выражением
LOC (X [ j ]) = L
0
+ c
j, (1)
где L
0
– константа, называемая базовым адресом и являющаяся адресом
гипотетического узла X [0].
X [0] X [1] X [2] X [3] … X [n]
L
0
L
0
+ c L
0
+ 2c
L
0
+ 3c
… L
0
+ nc
Последовательное распределение очень удобно при работе со сте-
ком. Для этого достаточно иметь указатель стека T. Когда стек пуст,
Т = 0. Для того чтобы поместить новый элемент в стек, необходимо
(в предположении, что c = 1):
T ← T + 1; X [T] ← Y. (2)

Страницы