Цепная организация данных. Цепной каталог.
Цепной каталог – сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются список обрабатываемых записей и список свободных позиций памяти. Адрес связи, отмечающий первую обрабатываемую запись, называется указателем списка. Адрес связи, отмечающий первую свободную позицию памяти, называется указателем свободной памяти. Адрес связи последней записи (или последней позиции свободной памяти) в списке называется концом списка, и здесь отмечается нулевым значением.
Включение и исключение записи в цепном каталоге предполагает поиск местоположения включаемой (исключаемой) записи и замену значений адресов связи для установления новой последовательности записей основного списка и списка свободной памяти.
Алгоритм вставки записей с ключом F в цепной каталог.
1.Найти в каталоге запись с ключом непосредственно меньше, чем F (предшествующая запись).
2.Поместить запись с ключом F в 1-ю позицию свободной памяти.
3.Заменить указатель свободной памяти (УСП) на адрес связи новой записи, этот адрес – на адрес связи предшествующей записи, а последний – на первоначальное значение УСП.