40. Цепная организация данных.

Решение целого ряда задач обработки данных требует применения таких методов организации данных, которые позволили бы связать физически разнесенные в памяти данные в логическую последовательность, определяющую порядок их обработки. Простейшим методом, применяемым для этих целей, является списковая (цепная) организация данных. Списком называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. Адресом связи некоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрастанием значений ключа в записях. В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е. все адреса связи. Возможны два способа организации списка - совместное размещение собственной и ассоциативной информации, когда запись и ее адрес связи образуют одно целое, и раздельное, когда имеется списковая организация адресов связи и последовательное хранение собственной информации. При списковой организации данных необходим специальный атрибут, называемый указателем списка, который содержит начальный адрес или номер первой в порядке обработки записи списка. Кроме того, адрес связи последней записи списка должен содержать специальное значение, называемое концом списка и отмечающее, что последующих записей у данной записи нет. Обычно конец списка отмечается нулем. При формировании упорядоченного списка записей возможны

два варианта:

• вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу;

• создать сначала неупорядоченный список, а затем отсортировать его.

Учитывая, что для сортировки можно использовать метод слияния, второй вариант следует признать более целесообразным. В итоге время формирования упорядоченного списка пропорционально T~M-logM.

41. Цепной каталог.

Цепным каталогом называется сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются список обрабатываемых записей и список свободных позиций памяти. Адрес связи, отмечающий первую обрабатываемую запись, называется указателем списка. Адрес связи, отмечающий первую свободную позицию памяти, называется указателем свободной памяти. Адрес связи последней записи (или последней позиции свободной памяти) в списке называется концом списка, и здесь отмечается нулевым значением. Включение и исключение записей в цепном каталоге предполагает поиск местоположения включаемой (исключаемой) записи и замену значений адресов связи для установления новой последовательности записей основного списка и списка свободной памяти.

42. Корректировка в цепном каталоге.

Алгоритм вставки записи с ключом F в цепной каталог.

1. Найти в каталоге запись с ключом непосредственно меньше, чем F (предшествующая запись).

2. Поместить запись с ключом F в первую позицию свободной памяти.

3. Заменить указатель свободной памяти (УСП) на адрес связи новой записи, этот адрес - на адрес связи предшествующей записи, а последний - на первоначальное значение УСП.

Алгоритм удаления записи с ключом W из каталога.

1. Найти в каталоге запись с ключом непосредственно меньше, чем W (предшествующая запись).

2. Заменить УСП на адрес связи предшествующей записи, этот адрес - на адрес связи исключаемой записи, а последний- на первоначальное значение УСП.

Оценка времени корректировки складывается из времени реализации поиска и времени на замену значений адресов связи. В последнем случае число пересылок адресов связи всегда

одинаково и не зависит от числа записей в цепном каталоге, поэтому затраты времени на поиск при корректировке являются доминирующими и время корректировки пропорционально Т~М.