Списки общего вида
 |
Списки общего вида отличаются от обычных линейных списков только одной деталью – элементом списка общего вида может быть список. Список общего вида является простым обобщением линейного списка. В случае односвязного списка в узел добавляется указатель на подсписок, как на рис 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-02; просмотров: 1156;