Нелинейные связанные структуры
Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.3.13).
LST1 - указатель на начало 1 - ого списка (ориентированного указателем P1). Он линейный и состоит из 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. Что такое граф состояния ?
