Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.3.13).

LST1 - указатель на начало первого списка (ориентированного указателями PTR1). Он линейный и состоит из 5-и элементов.

2-ой список образован из этих же самых элементов, но в произвольной последовательности. Началом 2-ого списка является 3-ий элемент, а концом 2-ой элемент.

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

Можно выделить 3 признака отличия нелинейной структуры:

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

2) На данный элемент структуры может ссылаться любое число других элементов этой структуры.

3) Ссылки могут иметь вес, то есть подразумевается иерархия ссылок.

Представим, что имеется дискретная система, в графе состояния которой узлы - это состояния, а ребра - переходы из состояния в состояние (рис. 3.14).

Входной сигнал в систему это X. Реакцией на входной сигнал является выработка выходного сигнала Y и переход в соответствующее состояние.

Граф состояния дискретной системы можно представить в виде комбинации одного двусвязного и трех односвязных списков, которые вместе составляют  нелинейный двусвязный список. При этом в информационных полях должна записываться информация о состояниях системы и ребрах. Указатели элементов должны формировать логические ребра системы (рис. 3.15).

Для реализации вышесказанного:

1) должен быть создан список, отображающий состояния системы  (1, 2, 3);

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

В общем случае при реализации многосвязной структуры получается сеть.

Контрольные вопросы

1. Какие динамические структуры Вам известны?

2. В чем отличительная особенность динамических объектов?

3. Какой тип представлен для работы с динамическими объектами?

4. Как связаны элементы в динамической структуре?

5. Назовите основные особенности односвязного списка?

6. В чем отличие линейных списков от кольцевых?

7. Зачем были введены двусвязные списки?

8. В чем разница в операциях, производимых над односвязными и двусвязными списками?

9. Какой список является более удобным в обращении, односвязный или двусвязный?

10. Что такое указатель?

11. Какие стековые операции можно производить над списками?

12. Какие операции, производимые над очередью, можно производить над списками?

13. Почему можно производить все эти операции над списками?

14. Для чего предназначены операции Getnode и Freenode?

15. Какие методы утилизации вы знаете?

16. Перечислите элементы заголовков в списках.

17. Зависит ли время, затраченное на вставку элемента в односвязный список, от количества элементов в списке?

18. Где процесс вставки и удаления эффективнее, в списке или в массиве?

19. Как можно производить просмотр односвязного списка?

20. Что означает AVAIL?

21. Какой недостаток односвязных списков по сравнению с

22. массивом?

23. Какие структуры являются нелинейными?

24. Каковы признаки отличия нелинейных структур?

25. Как можно создать нелинейную связную структуру?

26. Что такое граф состояния?