double arrow

Кольцевой однонаправленный список


Этот способ организации таблиц сходен с предшествующим вариан-

том. Отличие заключается лишь в том, что последний элемент списка замы-

кается на первый, что позволяет обращаться через один вход к предшест-

вующему и последующему элементам. Алгоритмы работы, достоинства и

недостатки метода те же, что и для простого однонаправленного списка.

struct node { // структура, определяющая элемент списка

// и указатель на следующий элемент

Struct element val; // значение элемента списка

struct node *next; // указатель на следующий элемент

};

struct node *last = NULL; // указатель на последний

// элемент списка

// (обнулен, если список пуст)

Однонаправленный список одномерных массивов

Для достижения компромисса между эффективностью и экономично-

стью динамического распределения памяти и затратами аппаратных и вре-

менных ресурсов на его организацию применяется выделение памяти сразу

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

1.6). Этот вариант организации таблицы сходен со структурой организации

хранения к лючей в виде списка массивов. Выделение памяти осуществляет-

ся одновременно для группы элементов. Возможны разнообразные подхо-




ды к упорядочиванию и поиску информации. Например, сортировка данных

и двоичный их поиск могут осуществляться только в пределах одномерных

массивов. Переход же по списку от одного одномерного массива к другому

организуется последовательно.


Начало

Конец


ptr

next

ptr

next

. . .

ptr

*


Элемент 1

Элемент 1

Элемент 1


. . .

. . .

. . .

. . .


Элемент N

Элемент N

Элемент N


Рис. 1.6. Организация однононаправленного списка одномерных массивов


Однонаправленный кольцевой список массивов



Этот вариант сходен с предыдущим по способу организации таблицы,

характеристикам, алгоритмам работы, достоинствам и недостаткам.







Сейчас читают про: