СПИСКОМ называется множество записей, занимающих произвольные участки памяти, последовательность обработки которых задается с помощью адресов связи. АДРЕСОМ СВЯЗИ некоторой записи называется атрибут, в котором хранится начальный адрес или номер записи, обрабатываемой после этой записи. Обычная последовательность обработки записей в списке определяется возрастанием значений ключа в записях.
В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е. все адреса связи.
Возможны два способа организации списка - совместное размещение собственной и ассоциативной информации, когда запись и ее адрес связи образуют одно целое (рис. 3.3,а), и раздельное, когда имеется списковая организация адресов связи и последовательное хранение собственной информации (рис. 3.3,6).
Рис. 3.3. Варианты списковой организации данных: а - совместное хранение записей и адресов связи; б - раздельное хранение записей и адресов связи (0 – конец списка)
При формировании упорядоченного списка записей возможны два варианта:
• вновь поступающие записи вставлять так, чтобы не нарушать упорядоченность по ключу;
• создать сначала неупорядоченный список, а затем отсортировать его.
итоге время формирования упорядоченного списка пропорционально T~M-logM.
Для ПОИСКА ДАННЫХ В ОДНОНАПРАВЛЕННОМ СПИСКЕ используется единственный метод – ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК. Ключевой атрибут первой
записи (ее адрес извлекается из указателя списка) сравнивается с искомым значением q, затем такое же сравнение выполняется для ключа второй записи, которая извлекается по адресу связи первой записи, и т. д. Время поиска, естественно, пропорционально Т~М.
Для ускорения доступа к списку могут быть рекомендованы такие варианты использования адресов связи, как двунаправленный и кольцевой список (рис. 3.4):
• двунаправленный список образован двумя цепочками адресов связи - от первой записи к последней и от последней записи к первой;
• в кольцевом списке последний адрес связи указывает на первую запись.
ЦЕПНОЙ КАТАЛОГ
ЦЕПНЫМ КАТАЛОГОМ называется сплошной участок памяти (или несколько таких участков), в котором одновременно размещаются список обрабатываемых записей и список свободных позиций памяти. Адрес связи, отмечающий первую обрабатываемую
запись, называется УКАЗАТЕЛЕМ СПИСКА. Адрес связи, отмечающий первую свободную позицию памяти, называется УКАЗАТЕЛЕМ СВОБОДНОЙ ПАМЯТИ. Адрес связи последней записи (или последней позиции свободной памяти) в списке называется
КОНЦОМ СПИСКА, и здесь отмечается нулевым значением. Включение и исключение записей в цепном каталоге предполагает поиск местоположения включаемой исключаемой) записи и замену значений адресов связи для установления новой последовательности записей основного списка и списка свободной памяти.