Теория экономических информационных систем. Малова Е.А. - 29 стр.

    • время корректировки данных. Из всех возможных вариантов корректи-
ровки учитывается включение и исключение одной записи;
    • объем дополнительной памяти, расходуемой под служебную информа-
цию (например, адреса связи).
    При анализе алгоритмов необходим еще ряд допущений, обеспечивающих
использование равномерного распределения вероятностей для всех случайных
величин, описывающих работу алгоритма, в том числе:
    • распределение значений ключевых атрибутов в массиве из М записей –
равномерное,
    • значение q при поиске по совпадению выбрано случайно: это означает, что
поиск с одинаковой вероятностью 1/М может закончиться на любой записи массива,
    • положение включаемой (выключаемой) записи при корректировке оп-
ределяется теми же вероятностями, что и при поиске.

                   Цепная (списковая) организация данных

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

                                     29