Введение в информационные системы. Брюхомицкий Ю.А. - 83 стр.

UptoLike

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

Рубрика:

ся его место в структуре в соответствии с логическим порядком размещения

элементов. Путем соответствующей замены указателей ячейка с новой записью

включается в нужное место списка.

Особую осторожность необходимо проявлять при исключении элемен-

тов списковой структуры, так как на разрушаемый список могут быть ссылки из

других списков, что приведет к появлению «

висящих» указателей. Например, в

структуре, изображенной на рис. 5.38, по каким-либо причинам становится не-

нужным и удаляется подсписок 2, для чего указатель DPTR соответствующего

структурного слова устанавливается в ноль и доступ к удаляемому подсписку

обрывается. Блок ячеек подсписка 2 освобождается и может быть включен в

список свободной памяти для повторного использования. Однако в структурном

слове подсписка 1 останется «висящий» указатель на ячейку z. При следующем

возможном обращении к подсписку 2 произойдет обращение по «висящему»

указателю к блоку ячеек памяти бывшего подсписка 2 (теперь свободных или

занятых другими данными). Результаты будут непредвиденными.

Рис. 5.38. Граф списковой структуры

Рис. 5.39. Представление в памяти

списковой структуры, отображенной графом

на рис. 5.38

Во избежание таких ситуаций необходим какой-то механизм контроля

корректности использования свободной памяти. Один из таких механизмов за-

ключается в использовании счетчиков ссылок. При этом для каждого исполь-

a2 w

Подсписок 2

Подсписок 1

Вход в список

Основной список

2 a