Списки общего вида

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

Рис 16. Узел списка общего вида.

Такое определение рекурсивно, и список может содержать в качестве элемента самого себя. Рассмотрим списочную структуру:

L=(a:N,b,c:(d:N),e:L)

N=(f, g:(h:L, j:N))

Запись вида x:Y означает, что узел x содержит подсписок Y. Узлы списка перечисляются через запятую. Графически списочная структура изображена на рис 17.

Рис. 17. Представление списка общего вида

Такое представление несёт с собой одну проблему. На рис. 17 видно, что на узел f имеется три ссылки. В действительности, это ссылки на список N, в котором узел f является начальным. Если потребуется удалить узел f из списка N, то придется регулярным образом обходить всю списочную структуру с целью обнаружения всех ссылок на узел f, что, конечно, неприемлемо.

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

Рис 18. Список общего вида с головами списков.

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

Дата добавления: 2014-12-08