Информационное обеспечение систем управления

       

В голове списка можно хранить


В голове списка можно хранить различную слу-ясебную информацию, необходимую при обработке списка (идентификатор списка, количество узлов в списке и т. п.).

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



Рис. 3.6. Пример однонаправленного циклического списка

Наряду с однонаправленными используются двунаправленные циклические списки. В ряде случаев удобно использовать циклический список с указателями на голову списка из каждого узла, за исключением последнего узла, поскольку используется прямой указатель на голову списка [17].

Базируясь на использовании способов представления связанных линейных списков, можно реализовать в памяти ЭВМ сложные нелинейные структуры, например древовидные или сетевые. Такие представления структур называются многосвязанными списками. Для построения многосвязанного списка требуется иметь в узлах достаточное количество указателей. Наличие большого числа указателей в многосвязанной структуре в ряде случаев повышает эффективность обработки.

Таким образом, основой построения связанных списковых структур являются указатели.

При практической реализации на ЭВМ можно использовать три типа указателей (адресов записей):

–       машинный (действительный);

–       относительный;

–       символический (идентификатор).

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

Содержание  Назад  Вперед