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

 
 

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


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.