Связанное представление. Кольцевые списки

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

1. Однонаправленные линейные списки

Головной указатель

……

У линейных списков отсутствуют циклы и петли. Для получения доступа к какому-либо элементу списка необходимо начинать продвижение по списку начиная от головного указателя. Если требуется частое применение операции добавления элемента в конец списка или удаление последнего элемента, то в реализацию списка включают хвостовой указатель.

Головной указатель Хвостовой указатель

2. Двунаправленные линейные списки

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

Головной указатель Хвостовой указатель

Списки такого типа более зффективны по сравнению с предыдущими, если часто выполняются операции включения или исключения элементов из середины списка.

3. Кольцевые списки

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

Головной указатель

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

Головной указатель

Модификация для двунаправленных и кольцевых списков выполняется аналогичным образом.

Стеки и очереди

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

Рассмотрим реализацию очереди на основе применения кольцевого списка. Элементы данных отделены от связующих элементов. Используемые типы данных:

typedef struct CHAIN_EL {

struct CHAIN_EL * succ; // ссылка вперед

struct CHAIN_EL * pred; // ссылка назад

MY_BOOKS * elptr; } T_CHAIN;

typedef struct { unsigned cursize; // текущая длина очереди

T_CHAIN * head; // головной указатель

} T_QUEUE;

Выполните реализацию конструктора и функции выбора элемента из очереди в качестве упражнения!

Функция записи элемента в очередь возвращает NULL, если добавить элемент в очередь не удается, в противном случае – возвращает ссылку на элемент-очередь (типа T_QUEUE).

MY_BOOKS * addTo (T_QUEUE *queue, MY_BOOKS * elptrp)

{

T_CHAIN * cptr, * last;

if ((cptr = (T_CHAIN *)malloc(sizeof (T_CHAIN))) == NULL)

return NULL;

cptr -> elptr = elptrp;

if ( queue -> head == NULL) // очередь пуста?

{

queue -> head = cptr; // да, включить первым

cptr -> pred = cptr;

cptr -> succ = cptr;

}

else

{

last = queue -> head -> pred;

if (last == last -> pred) //единственный элемент?

{

last -> pred = cptr; // да, включаем первым

last -> succ = cptr;

cptr -> pred = last;

cptr -> succ = last;

}

else

{

cptr -> pred = last;

cptr -> succ =queue -> head;

last -> succ = cptr;

queue -> head -> pred = cptr;

}

}

return queue;

}

При работе со списками необходим тщательный анализ всех возможных состояний списка.