Теория экономических информационных систем


Теория экономических информационных систем - стр. 65


/p>

                                      б)                     Записи

Рис. 15. Варианты списковой организации данных:

а) - совместное хранение записей и адресов связи;

б) - раздельное хранение записей и адресов связи

(Ø – конец списка)

 

Кроме того, адрес связи последней записи списка должен содержать специальное значение, называемое концом списка и отмечающее, что последующих записей у данной записи нет. Обычно конец списка отмечается нулем.

На рисунках адрес связи изображается прямоугольником со стрелкой, стрелка указывает на запись, адрес хранения которой содержится в адресе связи.

При формировании упорядоченного списка записей возможны два варианта:

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

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

Учитывая, что для сортировки можно использовать метод слияния, второй вариант следует признать более целесообразным.

В итоге время формирования упорядоченного списка пропорционально Т~М*1оgМ.

Поиск в упорядоченном списке основан на использовании тех же методов, что и в последовательном массиве, но так как адреса связи создают возможность быстрого доступа только к следующей записи, эффективность этих методов иная.

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

Бинарный поиск для списковой организации является неэффективным, так как число переходов от записи к записи при доступе к середине интервала представляется величиной практически равной количеству записей.

При применении двунаправленных и кольцевых списков время доступа к записям уменьшается. На рис. 16 приведены примеры этих списков.

                                                      Адреса связи                        Указатель

                                                                                                    обратного




Начало  Назад  Вперед



Книжный магазин