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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

17
BASE [3] = 5, BASE [4] = 9 и адреса верхних элементов стеков − значения:
TOP [1] = 1, TOP [2] = 2, TOP [3] = 8, TOP [4] =11.
Предположим, что требуется включить новый элемент во второй
стек, затем новый элемент в третий стек и ещё раз включить новый эле-
мент в третий стек (обозначим эту последовательность в виде I2, I3, I3).
Тогда первые две из этих трёх операций пройдут успешно, а последняя −
нет, поскольку возникнет ситуация ПЕРЕПОЛНЕНИЯ третьего стека:
1 1 2 3 3 3 3 4 4
0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
18
19
при значениях базовых адресов стеков: BASE [1] = –1, BASE [2] = 2,
BASE [3] = 5, BASE [4] = 9 и адресов верхних элементов: TOP [1] = 1,
TOP [2] = 3, TOP [3] = 10, TOP [4] =11.
Для исключения этой критической ситуации начинает свою работу
алгоритм переупаковки памяти G.
Требуется определить состояние памяти и значения указателей
BASE [ j ] и TOP [ j ] для j = 1, 2, 3 и 4 по окончании переупаковки.
3. СВЯЗАННОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ
ПРИ ХРАНЕНИИ ЛИНЕЙНЫХ СПИСКОВ
Вместо хранения списка в последовательных ячейках памяти, можно
использовать более гибкую схему, в которой каждый узел содержит связь
со следующим узлом списка. Ниже представлены схемы последователь-
ного и связанного распределения памяти при хранении линейного списка,
состоящего из пяти элементов.
Последовательное распределение Связанное распределение
Адрес Содержимое Адрес Содержимое
L
0
+ c:
Элемент 1 A: Элемент 1 B
L
0
+ 2c:
Элемент 2 B: Элемент 2 C
L
0
+ 3c:
Элемент 3 C: Элемент 3 D
L
0
+ 4c:
Элемент 4 D: Элемент 4 E
L
0
+ 5c:
Элемент 5 E: Элемент 5 Λ
Здесь A, B, C, D и E – адреса произвольных ячеек в памяти, Λ – пус-
тая связь.
В случае связанного распределения памяти в программе имеется пе-
ременная связи или константа, имеющая значение A. Отправляясь от узла
по адресу A, можно найти все другие элементы списка.

Страницы